# Rapport de Projet de PIM

## Résumé

Ce projet a été réalisé dans le cadre du cours de Programmation Impérative de 1ère année par Loïc BLANC, Valentine BREGEOT, et Nikola DABIC.
L'objectif de ce projet est d'implémenter un routeur en langage Ada, et d'étudier les différentes manières de gérer et stocker les données. Après avoir détaillé le raffinage de ce routeur, nous avons dans un premier temps implémenté une version simplifiée du routeur, sans cache. Une fois cette base établie, nous avons codé le cache selon sa politique de gestion et sa représentation.
Pour cela, nous avons utilisé le travail fourni pour le mini-projet 2, à savoir le module LCA, qui permet de stocker les données de façon efficace.
Ce rapport contient notre travail de reflexion, permettant ainsi de détailler et justifier nos choix, décrire le code obtenu, et faire un bilan sur ce projet.

## Introduction

Un routeur est un outil du réseau utilisé pour diriger les données reçues vers l'interface de sortie correspondante d'après le contenu de la table de routage.
Dans le but d'optimiser le traitement des données par le routeur, nous utilisons un cache. Il mémorise les données passées en se basant sur le principe que si une information a déjà été utilisée, il est très probable qu'elle soit utilisée de nouveau.
Dans le cadre de ce projet, plusieurs gestions de cache etaient proposées, supprimant des éléments au fur et à mesure d'après différents critères:

- FIFO *First In First Out*, qui supprime le premier élément rentré,
- LRU *Last Recently Used*, qui supprime l'élément le plus ancien utilisé,
- LFU *Last Frequently Used*, qui supprime l'élément le moins fréquemment utilisé.

De même, 2 représentations du cache étaient recommandées:

- Le routeur *LL*, composé d'une table de routage en liste chaînée et d'un cache en liste chaînée,
- Le routeur *LA*, composé d'une table de routage en liste chaînée et d'un cache en arbre binaire préfixe.

Ce rapport est composé de plusieurs parties permettant de saisir le raisonnement et le code généré dans leur globalité.
Dans une première partie, nous vous présenterons l’architecture en modules que nous avons utilisée.
Comme nous l'évoquions dans le résumé du projet, nous avons été amenés choisir une façon de faire parmi plusieurs options, nous vous les détaillerons et justifierons dans une deuxième partie.
Ainsi, après avoir réfléchi sur notre façon de procéder, nous avons mis nos idées sous la forme d'algorithmes et de types de données, nous vous présenterons
les principaux dans une troisème partie.
Une fois le code, obtenu, nous nous sommes assurés que le résultat était correct à l'aide de tests dont nous expliquerons la démarche.
Au cours de ce projet, nous avons été confrontés à plusieurs difficultés auquelles nous avons fait face en essayant de trouver la solution la plus adaptée à chaque cas. Nous justifierons ainsi les solutions adoptées, notamment lorsque nous avions plusieurs idées pour y remédier.
Finalement, nous détaillerons l'organisation de l'équipe pendant ces 2 mois de travail, et nous dresserons 2 bilans: un technique portant en particulier sur les perspectives d'amélioration, et un plus personnel pour analyser notre investissement et les apprentissages acquis pendant ce projet.

## Architecture de l'application en modules

Le développement du routeur a nécessité la création et/ou l'utilisation d'un certain nombre de modules. Nous allons ici présenter briévement chaque module utilisé et expliciter leurs interactions.

Il y a deux programmes principaux : routeur LL et routeur LA. Ils ont chacun leur architectures mais avec des modules en commun.

Nous avons tout d'abord eu besoin de créer le module *adresse_ip*. Ce module défini le type *T_adresse_ip* et regroupe tous les sous-programmes que nous avons implémenté pour manipuler des adresses ip.
Puisque la table de routage (et parfois même le cache) est représentée par une liste chaînée, nous avons décider de reprendre le module *lca* (et son module *sda_exceptions*) du mini projet 2 qui définit le type *T_LCA* et regroupe les opérations élémentaires sur une liste chaînée (e.g ajouter un élément).

Le module ligne_de_commande permet la gestion des paramètres des lignes de commandes et les statistiques.

Le module gestion_regle_routage_LCA regroupe les sous-programmes qui gère les règles de routage (table de routage et cache) défini avec le type LCA.

Le routeur LA a un module en plus *arbre_binaire* qui contient les règles de gestion de l'arbre binaire. Il permet ainsi de réaliser des fonctions de base comme ajouter, supprimer et rechercher dans un arbre binaire mais aussi certaines plus spécifiques au sujet comme *modifierélémentcache*.

Pour finir, les fichiers routeur.adb et routeur_arbre.adb contiennent les deux programmes principaux du routeur LL respectivement LA. Ils font le lien entre les autres modules.

Vous trouverez ci-dessous un schéma récapitulant d'une part l'architecture de l'application, et précisant d'autre part les différentes intéractions entre ces modules.
## Schéma ici Loïc :)

## Présentation des principaux algorithmes et types de données

Dans cette partie, nous allons vous présenter les algorithmes essentiels au bon fonctionnement du routeur, ainsi que les types de données choisis pour modéliser les informations.

### définition des types de données choisis
Nous avions défini le type *T_LCA* dans le mini-projet 2 de Programmation Impérative.
Le type *T_LCA* est un type pointeur (*Type T_LCA is access T_Cellule*) vers une cellule, qui modélise une liste chaînée. Le type T_Cellule est un type enregistrement composé d'une clé ( type *T_Cle*), d'une donnée (type *T_Donnee*), et d'un pointeur de type *T_LCA* vers la cellule suivante.
lorsqu'ils sont définis dans la spécification du module *LCA*, les types *T_Cle* et *T_Donnee* sont génériques. Ici, *T_Cle* est un type *T_adresse_ip*, et *T_Donnee* est *T_regle*.
Le type *T_adresse_ip* a été défini dans le package *adresse_ip*:

type T_Adresse_IP is mod 2 ** 32;

En effet, dans ce cadre, les adresses IP sont codées par 4 octets en base 10 séparés par des points. Ce sont donc des entiers naturels que l'on convertira en langage binaire.

La création du type *T_adresse_ip* a entrainé l'écriture de plusieurs sous-programmes, permettant de convertir une adresse IP en chaine de caractère (ou inversement), ou d'indiquer si une ligne sélectionnée est une adresse IP ou non par exemple.

Cela donne lieu à la création de la fonction *is_adresse_ip* qui prend en paramètre une chaîne de caractères et retourne un booléen.
Cette fonction est robuste car elle couvre tous les cas possibles.
L'adresse IP est forcément composée de 7 caractères au moins, et 15 au plus, dont 3 points. De même, les caractères compris entre 2 points sont obligatoirement entre 1 et 3, et doivent être des entiers. Si ce n'est pas le cas, l'exception __Constraint_Error__ est levée et la fonction retourne que ce n'est pas une adresse IP.

Le type *T_regle* est défini dans le package *gestion_regle_routage_lca* comme un enregistrement, qui correspond à une ligne de la table de routage ou du cache. L'enregistrement comprend un masque (type *T_adresse_IP*), une interface(type *Unbounded_String*), et un compteur qui servira à la gestion du cache, de type *Integer*.

### Principaux algorithmes
#### Procédures *Parcourir*
Nous allons commencer par traiter 2 procédures essentielles, au fonctionnement similaire: *Parcourir_Table_Routage* et *Parcourir_Cache* .

procedure Parcourir_table_routage( table_routage : in out T_LCA; regle_choisie : in out T_LCA ; destination : T_adresse_ip; masque_plus_grand : in out T_Adresse_IP) is 

	        masque_memoire : T_adresse_IP;
        	interf_memoire : Unbounded_String;
	        table_routage_parcours : T_LCA;
        	application_masque_destination : T_adresse_IP;
	        application_masque_table : T_adresse_IP;
        begin 
	        Creer(masque_memoire,0,0,0,0);
        	Initialiser(table_routage_parcours);
	        Recopier(table_routage_parcours,table_routage);
        	While  not(Est_vide(table_routage_parcours)) loop 
		
	        	application_masque_destination :=appliquer_masque(destination,La_donnee (table_routage_parcours,La_Cle(table_routage_parcours)).masque);
		        application_masque_table :=appliquer_masque(La_Cle(table_routage_parcours),La_donnee (table_routage_parcours,La_Cle(table_routage_parcours)).masque);
        		if Est_Egal(application_masque_destination,application_masque_table)then 			
	        		if Est_Superieur(La_donnee (table_routage_parcours,La_Cle(table_routage_parcours)).masque ,masque_memoire) then
		        			
			        	vider(regle_choisie);
				        Enregistrer (regle_choisie,destination,(La_donnee(table_routage_parcours,La_Cle(table_routage_parcours)).masque,La_donnee (table_routage_parcours,La_Cle(table_routage_parcours)).interf,0));
				        masque_memoire :=La_donnee (table_routage_parcours,La_Cle(table_routage_parcours)).masque;
        			end if;
	        	end if;
		        if La_donnee (table_routage_parcours,La_Cle(table_routage_parcours)).masque > masque_plus_grand then 
			        masque_plus_grand := La_donnee (table_routage_parcours,La_Cle(table_routage_parcours)).masque;
        		end if;
	        	passer_element_suivant(table_routage_parcours);
		

        	end loop;
        end Parcourir_table_routage;

Le principe de cette procédure est assez simple: il consiste à parcourir la table afin de trouver la règle compatible avec le paquet dont le masque est le plus grand. Pour cela, pour chaque règle de la table de routage, il faut appliquer le masque au paquet, et vérifier la compatibilité.

Après avoir déclaré les variables, nous initialisons les valeurs du masque stocké et du masque le plus long, et nous créons une copie de la table de routage en utilisant le package *LCA*. Cela permet de ne pas perdre le pointeur en tête de la liste chaînée.
L'idée de la variable *masque_le_plus_long* est de stocker le masque le plus long afin de le réutiliser lors de l'enregistrement de la règle dans le cache. En effet, cela permet de garantir la cohérence du cache.

Nous allons ensuite parcourir la table de routage afin de comparer la règle avec l'adresse à orienter (sur laquelle on a appliqué le masque correspondant). La boucle s'arrête à la fin du fichier.
Pour cela, nous utilisons les fonctions *Est_Vide* et *Est_Egal* définies respectivement dans les modules *LCA* et *Adresse_ip*.

Ici, la fonction *Est_Egal* prend notamment en paramètre *appliquer_masque( destination, La_donnee (table_routage_parcours, La_Cle(table_routage_parcours)).masque)*, qui utilise la procédure *appliquer_masque*. Cette dernière repose sur le ET logique appliqué entre la destination et le masque de la règle.

Si le masque de la règle correspondante est supérieur au masque stocké en mémoire, alors ce dernier prend la valeur du masque de la règle, et on enregistre la solution dans le fichier de résultats.
La procédure *Enregistrer* permet d'enregistrer la , elle est définie dans le module *LCA*.
> []modifier

De même, si le masque de la règle correspondante est supérieur au masque le plus grand enregistré, alors ce dernier prend la valeur du masque de la règle.

Finalement, il nous suffit d'avancer dans la table de routage à l'aide de la procédure *passer_element_suivant* qui se sert des pointeurs.

De même, la procédure *Parcourir_cache* est sensiblement identique, à la différence près qu'il n'est pas question dans ce sous-programme du masque plus grand.

#### Procédures de gestion du cache en LCA
Passons maintenant à la description des principaux algorithmes intervenant dans la gestion du cache en liste chaînée: *Mettre_a_jour* et *Modif_elem_cache*

procedure Mettre_a_jour(cache:in out T_LCA; regle_choisie:T_LCA; type_cache : T_cache)
begin
    case type_cache is 
        when FIFO => null;
        when LRU => Trier_date(cache,regle_choisie);
        when LFU => Trier_compteur(cache, regle_choisie);
        when others => null;
    end case;
end Mettre_a_jour;

*Mettre_a_jour* permet, comme son nom l'indique, de mettre à jour le cache tout en tenant compte de l'existence de différentes politiques. Pour ce faire, cette procedure appelle deux sous-programmes, à savoir: *Trier_date* et *Trier_compteur*. Ces deux sous-programmes modifient le cache de façon à satisfaire respectivement la politique LRU en agissant sur la donnée la moins récemment utilisée et la politique LFU en agissant sur la donnée la moins fréquemment utilisée.

## detaillez dire que cela a éviter des enregistrement de données et permet une seule facon de supprimer

procedure Modif_elem_cache(cache: in out T_LCA; regle_choisie: in T_LCA; type_cache: in T_Cache; masque_plus_grand: in T_adresse_ip; taille_cache: integer);
begin
    if Est_Plein(cache, taille_cache) then
        Supprimer(cache, La_Cle(cache));
    end if;
    Inserer_elem_cache(cache, regle_choisie, type_cache, masque_plus_grand);
end Modif_elem_cache;

*Modif_elem_cache* a pour objectif d'enregistrer la nouvelle donnée dans le cache tout en respectant la politique du cache dans le cas où ce dernier n'est pas plein, supprimer une donnée puis enregistrer dans le cas contraire. Ces opérations sont rendus possible grâce aux sous-programmes *Inserer_elem_cache* et *Supprimer*. *Inserer_elem_cache* est une version plus poussée de *Enregistrer* qui tient compte de la politique du cache.

1. Le module arbre binaire

Les differents types du module arbre binaire

type T_Regle_Cellule is record   
		interf : Unbounded_String;
		date_insertion: Time;
   	end record;	
	type P_Regle_Cellule is access  T_Regle_Cellule;

Le type T_regle_cellule est un enregistrement de l'interface et de la date_insertion de la règle. La variable date_insertion a un type time comme dans le mini-projet 1 extrait de la bibliothèque Ada_Calendar.
Ce type permet de distinguer les arbres contenant des règles à router des noeuds de transition. En effet, les noeuds de transition n'ont pas d'interface.
Le type P_regle_cellule est un pointeur sur le type T_regle_cellule.

    type T_Cellule is record   
		Branche_0 : T_Arbre_Binaire;
   		Branche_1: T_Arbre_Binaire; 
   		regle: P_Regle_Cellule;
   		adresse : T_adresse_IP;
		masque : T_adresse_IP;
   	end record;
   		
   	
   	type T_Arbre_Binaire is access  T_Cellule;

Le type T_cellule est un enregistrement constitué de deux pointeurs sur le type T_cellule respectivement sur branche 1 et branche 0, de deux types T_adresse_ip pour le masque et l'adresse et d'un pointeur sur le type T_regle_cellule.
Le type T_arbre_binaire est un pointeur sur T_cellule.

type T_regle_arbre_binaire is
	 record 
	 	adresse : T_adresse_IP;
		masque : T_adresse_IP;
		interf : Unbounded_String;
		date_insertion: Time;
	end record; 

## Manque le nom du type?
Le type est enregistrement avec toutes les informations d'une règle donc adresse, masque, interface et date_insertion. Il ne constitue pas les noeuds de l'arbre( voir ci dessus) mais permet d'enregistrer dans une variable toutes les informations de l'arbre.

Pour le module arbre binaire, nous allons détailler les trois algorithmes principaux que sont ajouter, rechercher et supprimer.

1. a.) La procédure ajouter
## h2traiter exception

La procédure ajouter est une fonction récursive qui a pour objectif d'ajouter dans le cache. La récursivité est réalisée sur le paramètre étage qui est par défaut à 31 pour le premier appel. Le principe général est d'enregistrer la règle à l'étage du premier bits discriminant. Nous avons créé un tableau *masque* de 33 adresses ip et qui permet de déterminer le premier bit discriminant.

## Formulation bizarre à revoir mdr
Dans le cas d'un arbre null( et de étage =0 très bizarre), nous créons un nouvelle cellule en initialisant les pointeurs des deux branches filles à null. Après, il faut regarder si la règle est au bon étage et doit être enregistrée.
Pour savoir si la règle est au bon etage, nous comparons le masque de l'étage avec le masque de la règle. Si il y a égalité, la règle est au bon etage et nous enregistrons la règle (adresse, masque, interface , date_insertion) à cette étage-là.
Sinon , nous enregistrons une adresse intermédiaire ( et entre l'adresse de la règle et le masque de l'étage) et nous regardons le bits suivant pour determiner si nous appelons récursivement sur la branche 0 ou 1 ce qui correspond à la valeur trouvée.

Dans le cas d'un arbre non null, il faut tester si l'adresse de la règle est égale à celle de l'arbre. Dans ce cas, il faut enregistrer à cette endroit la règle. Une exception se lève si une règle était déja enregistrée, ce qui en pratique ne devrait pas exister.
Sinon, il faut récupérer la valeur du bit correspondant à l'étage pour savoir si nous allons en 0 ou en 1 pour relancer l'appel récursif à l'étage en dessous.

1. b.) La fonction rechercher

Le but de la fonction est de retourner un pointeur sur regle_cellule (enregistrement d'interface et de date) correspondant à la destination passée en paramètre.
Dans le cadre d'un arbre null, la fonction retourne null. Le but est de trouver la meilleure règle, c'est-à-dire celle correspondant avec le masque le plus long, qui se trouve donc dans les étages les plus profonds. Il faut donc faire un appel recursif à la remontée, ce qui signifie tester en premier les valeurs les plus profondes. Pour cela, nous parcourons la branche, et quand nous sommes arrivés à la fin, nous remontons et nous testons à chaque étage.

1. c). La procedure supprimer_plus_ancienne

Le but de la procédure est de supprimer la règle la plus ancienne. Cette procedure utilise deux sous-programmes (rechercher_plus_ancien et supprimer_plus_ancienne que l'on va appeler suprimer_plus_ancienne_2 pour les différencier).
La fonction rechercher_plus_ancienne parcourt tout l'arbre pour renvoyer le pointeur sur l'arbre contenant la règle avec la date d'insertion la plus ancienne.
La procedure supprimer_plus_ancienne_2 est une procédure récursive qui supprime uniquement la règle: soit en libérant le pointeur de type P_regle_cellule, soit l'arbre en entier pour enlever les routes inutiles.
La procédure supprimer_plus_ancienne appelle seulement les deux fonctions à la suite.

d).

La procedure a.) La procédure ajouter

## enlever le parametre type LFU et possibement adapter pour Fifo en ligne de commande pour routeur LA ou enlever totalement et mettre que LRU

#### Programme principal

Après avoir décrit les principaux algorithmes composant le routeur, passons maintenant au programme principal.

Ce dernier commence par les fonctions retournant des compteurs utiles pour afficher les statistiques par la suite.

Le programme va parcourir le fichier contenant les paquets ligne par ligne. Il est découpé en fonction du type lu:

* Si c'est une adresse IP, on commence par regarder le cache avec la procédure *Parcourir_cache*. Si l'adresse recherchée se trouve dans le cache, sa règle correspondante est alors modifiée par la procédure, et le cache est mis à jour en fonction de la politique de cache choisie avec la procédure *Modif_eleme_cache*. Sinon, on recherche la règle à l'aide de la procédure *Parcourir_table_routage*, et on met à jour le cache avec *Mettre_a_jour*.
* Sinon, on lit le mot affiché( "fin", "stats, "cache", ou "table") et on effectue l'action associée.
* Si la ligne lue ne correspond à aucun des 2 précédents cas, le programme affiche une ligne indiquant une erreur de saisie, permettant la robustesse sur cette partie du programme.*

## Tests du programme

Le programme étant assez long et complexe, nous avons décidé de procéder par des tests unitaires : la majorité des sous-programmes non élementaire a été testé, ceux non testé sont appelé ces derniers.
Nous allons vous présenter la démarche adoptée pour chaque module que nous avons testé.

#### Module *adresse_ip*
Pour commencer, parlons du module *adresse_ip*. Nous avons testé les sous-programmes : *is_adresse_ip*, *Est_Egal*, *Est_Superieur*, *String_To_Adresse_IP* et *Adresse_IP_To_String*. L'idée est de vérifier que ces sous-programmes permettent effectivement de: vérifier que le contenu d'une chaîne de caractères correspond à une adresse ip, réaliser un test d'égalité et d'inégalité, convertir une chaîne de caractère en adresse ip et inversement.

__Nikola t'en es la!__

#### Module *gestion_regle_routage_lca*
Ensuite, nous avons testé le module *gestion_regle_routage_lca* afin de s'assurer que les fonctions *Lire_TR*, *Ecrire*, *Parcourir_table_routage*, *Est_Plein*, *Trier_compteur*, *Parcourir_cache*, *Mettre_a_jour*, *Trier_Date*, *Modif_elem_cache* et *inserer_eleme_cache* sont correctes.
Nous n'avons pas testé les procédures d'affichage, en considérant que ce ne sont pas des sous-programmes essentiels pour le bon fonctionnement du routeur, cependant ils aident à tester les résultats et à comprendre le fonctionnement des autres sous-programmes.

Pour cela, nous avons créé dans le fichier de test des fichiers contenant une table de routage, un cache, et des paquets.
Le but de ces tests va être de vérifier que ces sous-programmes font l'action voulue sur la table de routage, le cache, ou le fichier de resultats.

#### Module *Ligne_de_commande*
De même que nous n'avons pas testé les procédures d'affichage des modules précédents, nous ne testons pas le module *Ligne_de_commande*. En effet, nous l'avons testé directement en l'utilisant dans le programme principal.

## Bilan personnel

#### Loïc

#### Valentine

#### Nikola

c'est __incroyable__!
c'est *fou* wow

> Pour les paragraphes ou jsp
>> On sait jamais

- si vous voulez faire des listes

1) Ou numéroter jsp quoi