Fabien Priotto


  Web Kawa

Simulation d'un algorithme de routage inspiré de OSPF

Pour ce programme de simulation, Il a été acté le 15 avril que dans le cas d'une diffusion multicast, la mise en oeuvre du relais des paquets LSP n'est pas obligatoire.
La contrainte fondamentale de l'exercice est fondée sur la limite de connaissance du graphe de chaque routeur: seules les informations du voisinage direct sont connues.
En ce qui concerne le mécanisme de pannes, la diffusion se fait de proche en proche tel que cela est précisé dans l'énoncé au chapitre 3.5.
La simulation de rupture de lien est intrinsèque à chaque processus routeur.

L'adaptateur priority_queue constitue une file qui permet de garantir un ordre prioritaire entre les éléments. Cette fonctionnalité s'avère particulièrement intéressante pour mettre en oeuvre l'algorithme de Dijkstra sur des éléments qui associent un sommet à une distance (conteneur de classe pair).

2. Description de l'application


Cette application simule le fonctionnement de routeurs OSPF. Elle met en oeuvre un processus serveur et n processus routeurs.
Les routeurs sont associés aux sommets d'un graphe. Dans ce graphe, le coût des arêtes est représenté par la distance qui sépare les routeurs adjacents.
Cette application est conçue pour des systèmes Linux IPV4.
Le code source est réparti dans 3 fichiers:
Les fichiers sock.cc et sockdist.cc accompagnés de leurs fichiers d'entête .h constituent la librairie pour la communication par sockets.
Un fichier shell nommé compilation facilite la compilation sous Linux en tapant la commande la commande: ./compilation

Dans les commentaires du code source, les caractères accentués sont exclus pour des raisons de portabilité.
Les fichiers *.proj sont les fichiers de données qui peuvent être choisi par l'utilisateur au lancement du processus serveur.
Le fichier de données choisi (carte_5_sommets.proj par défaut) fourni la description du graphe.

2.a Description du processus serveur


Les roles du serveur sont les suivants:
1) Charger les données de localisation des routeurs.
2) Créer, mettre à jour et afficher une matrice d'état des routeurs.
Les routeurs sont associés à un identifiant de 0 à n.
Dans la diagonale est affiché l'état du routeur: 0 -> OFF, 2-> ON.
Une valeur de 1 dans la case [i][j] signifie que le routeur i est adjacent au routeur j.
3) Attribuer un identifiant aléatoire au routeur qui en fait la demande, l'enregistrer et lui retourner la liste de ses voisins directs.
Le format de la réponse du serveur est le suivant: "
NbSommets:IdAttribué, idVoisin1,adresse1:port1,distance1,degré;1+idVoisin2,adresse1:port1,distance1, degré1..."
4) Rester en ligne pour informer d'éventuels routeurs candidats que les inscriptions sont closes.

fig.1 Affichage du processus serveur

2. b Description du processus routeur


Les différents processus routeur peuvent être exécutés sur un même système à condition d'utiliser un port UDP distinct.
Le vecteur nombre MRout constitue une matrice valué par les distances qui est fondamentale au processus routeur.

fig.2 Affichage du processus routeur

Phase 1: Initialisation Le processus routeur se connecte au serveur, fournit son adresse (au format nom:port), récupère son id suivi des informations sur ses voisins que le serveur connaît à cet instant. Sur la base de ces informations, Il commence à construire sa liste de voisinage (Thread main).
Phase 2: Construction du voisinage La construction du voisinage se fait via une communication UDP de proche en proche.
Phase 2.A) Emission: transmet sa liste de voisins a ses voisins (Thread emission).
Le format du message est le suivant: "monId idVoisin1, adresse:port, distance, degré+idVoisin2, adresse:port, distance, degré+v3 etc."
Phase 2.B) Réception: reçoit les infos de la part de ses voisins. (Thread reception) et complète son voisinage (listVoisins) sur la base des réponses de ses voisins.
A ce stade, la connaissance du voisinage est encore incomplète car tous les routeurs n'ont pas forcément été initialisés.
Phase 3 : Mise à jour du voisinage
Pour la mise à jour, chaque routeur crée ses propres paquets LSP (Link State Packet) contenant les informations suivantes :
- Identité du routeur qui crée le LSP. - Liste des noeuds voisins avec le coût du lien associé;.
- Numéro de séquence. Dans cette simulation, nous n'utiliserons pas de champ temporisateur (TTL) pour la durée de vie des LSP.
La mise à jour du voisinage se fait via une communication multicast qui permet de diffuser l'information à un groupe de machine en réduisant le nombre de paquets émis.
L'adresse 239.9.3.5 est choisie comme adresse multicast de site. Elle joue le même rôle qu'une adresse privée, sa diffusion étant limitée au groupe.
L'affichage est donné sous la forme d'une matrice valuée qui permet de connaître les distances entre les différents routeurs selon en fonction de la connaissance acquise par le processus routeur courant.
Dans la diagonale de cette matrice, l'état du routeur est affiché : [0 -> OFF] [1 -> ON].
Ailleurs, une valeur comprise entre 0 et 1 précise le coût du lien entre deux routeurs adjacents. Les autres valeurs possibles sont : [-1 -> VOISIN A DISTANCE INCONNUE] [-2 ->ETAT INCONNU].
Phase 3.a) Emission multicast: Transmet a intervalles réguliers ses messages LSP (Thread emissionMulti) préparé par le thread prepareMaj. Les format d'un message LSP est le suivant : " monId,monNom:monPort idVoisin1,distance1+idVoisin2,distance2+idVoisin3... numeroSequence "
Phase 3.b) Réception multicast: Réceptionne les messages LSP et mémorise les informations en provenance de ses voisins (thread receptionMulti).
Complète sa connaissance du voisinage. Le voisinage se construit au fur a mesure des phases 2 et 3 en 2 étapes:
- Mémorisation de la table de routage dans le vecteur ListRoutes.
- Calcule et affichage des plus courts chemins via le Thread calculRoutes.
Table de routage La table de routage (base de données de transmission) est générée sur la base des données d'état de liens.
Chaque table de routage est unique et contient des informations sur ou et comment les paquets doivent être envoyés aux autres routeurs : Adresse du destinataire, routeur qui fait contact, coût (distance).

3. Compilation


Lancer le fichier compilation fourni dans le dossier sources en vérifiant au préalable les droits d'exécution sur celui-ci.
L'option pthread permet la prise en charge des thread.
L'option –lrt est nécessaire pour les calculs d'horloge.
Les commandes à exécuter pour compiler les fichiers sources sont les suivantes :
g++ -c sock.cc
g++ -c sockdist.cc
g++ sock.o sockdist.o routeur.cc -o routeur -pthread -lrt
g++ sock.o sockdist.o serveur.cc -o serveur -lrt

4. Lancement de l'application


4. a Lancement du processus serveur
Lancer ./serveur avec les options suivantes :
-f nom_fichier permet de spécifier le fichier de données (des fichiers .proj de 5, 10, 20 et 50 sommets sont disponibles).
-v pour le mode verbeux.
-h pour afficher le message d'aide.4. b Lancement des processus routeur
Lancer ./routeur avec les options suivantes :
-n nom_routeur permet de spécifier le nom de routeur. Par défaut, usage du nom système (hostname).
-p port_udp permet de spécifier le port UDP du routeur. Par défaut 10000.
-s permet de spécifier le temps de sommeil entre les différentes phases. Par défaut 3 secondes.
-d permet d'activer le processus de pannes.
-h Affiche le message d'aide.
-v pour le mode verbeux.
-P permet d’activer le simulateur de pannes.
-S permet de spécifier l’adresse du serveur. Exemple de commande : ./routeur –n r0 –p 8000 –s 10 –v soit un processus routeur d’adresse r0 :8000 avec 10 secondes d’attente entre chaque phase et en mode verbeux.

5. Simulation de pannes


Dans chaque processus routeur, un mécanisme de panne peut être activé pour simuler la perte aléatoire sur un lien donné. La distance avec le voisin considéré en panne est alors évaluée à l'Infini. La matrice affiche alors -1 à la place de la distance. Le calcul des plus courts chemins s'en trouve modifié. Chaque panne est temporisée afin qu'elle ait un véritable impact sur le calcul des routes. Pour activer la simulation de pannes, lancer routeur –P

6. Statistiques et mesure de performance


Chaque processus routeur mesure, pour un voisin donné, le nombre total de paquets émis, le nombre de paquets perdus et le taux de perte en précisant à chaque fois quel est le lien en panne. Les informations sont données sous les formes suivantes : PAQUETS:lienEnPanne;IdExpediteur;nbrePaquetsEmis;nbrePaquetsPerdus PERTE:lienEnPanne;IdExpediteur;%Pertes On peut donc visualiser la variation du taux de perte selon le nombre de paquets émis. Voir en annexe les résultats.

fig 3. Atténuation des pertes en fonction du nombre de paquets émis
(10 sommets sur un même système) En ce qui concerne les performances, le programme donne en nano secondes le temps écoulé à partir du déclenchement d’une panne jusqu’à ce que le voisinage soit complet. On peut donc connaître le temps que met un routeur à se rétablir de la rupture d’un lien.

7. Mise en oeuvre de l'algorithme de Dijkstra


Chaque routeur a une vision partielle du graphe. Pour chaque routeur, l'algorithme de Dijkstra gère un ensemble E de sommets dont les longueurs finales de plus court chemin avec monId sont connues (connaissance du voisinage = les voisins des voisins). A chaque itération, l'algorithme choisit le sommet u de S - E dont l'estimation de plus court chemin est minimale, ajoute u à l'ensemble E, puis relâche (abandonne en chemin) tous les arcs partant de u. DIJKSTRA(G,w,monId)
E = {}
F=S
Tant que F n'est pas vide
Faire
u = EXTRAIRE-MIN(F)
Ajouter u à E
Pour chaque v voisin de u
FAIRE
Relâcher(u,v,w)
Dans l'implémentation C++, le conteneur de classe pair permet d'associer une distance à un ID routeur que l'on peut alors gérer dans une priority_queue en prenant pour clé la valeur de la distance.

8. Sources


Thomas H. CORMEN - Charles E. LEISERSON - Ronald L. RIVEST - Clifford STEIN Introduction à l'algorithme Ed. Dunod
Robert SEDGEWICK Algorithm in C++ Ed. Addison-Wesley
Guy PUJOL Les réseaux Ed. Eyrolles