Protocoles de routage

Le but du TD est de mettre en oeuvre quelques protocoles de routage. Pour cela un émulateur de réseau très simplifié est fourni. L'essentiel du TD consiste à programmer les routeurs du réseau.

L'émulateur permet de simuler un réseau de plusieur routeurs. En lançant plusieurs émulateurs (éventuellement sur des machines différentes), on peut faire interagir plusieurs réseaux.

Dans un premier temps, on se limitera au routage à l'intérieur d'un seul réseau avec une solution de type "distance vector" (vecteur de distances) puis avec une solution de type "link state" (état des liens). La fin de l'énoncé s'intéresse au routage entre réseaux avec une solution similaire à "Border Gateway Protocol" (par vecteur de chemins).

Exercice 1. Installation de l'émulateur

Les adresses dans notre Internet virtuel seront de la forme R.IR est le nom du réseau et I le nom de l'interface. Rappelons que si les machines sur lesquelles nous travaillons n'ont en général qu'une seule interface, les routeurs en ont généralement plusieurs. Il est donc important de pouvoir identifier chaque interface (et pas seulement chaque noeud du réseau). Ainsi comme dans l'Internet, toute interface réseau d'une machine ou d'un routeur a un identifiant unique : son adresse. Chaque routeur possède de plus un identifiant utilisé uniquement à l'intérieur de son réseau.

Comme dans le cas de IP, nous devons fixer un format pour les paquets de données (nos paquets IP) :

  +------+-----+--------+---------+------------+----------+------------+------+
  | code | ttl | nbhops | res dst | interf dst |  res src | interf src |  id  |
  +------+-----+--------+---------+------------+----------+------------+------+

Les trois premiers champs seront commun à tous les types de paquets. Les champs suivants ne concernent que les paquets de données. Vous devrez définir vous-même les formats des paquets utilisés par vos protocoles de routage.

Récupérer et compiler Reseau.java. Ce programme lit une configuration de réseau dans un fichier tel que chaine3.txt. Pour lancer l'émulation, il faut indiquer le nom du fichier spécifiant le réseau, la durée de l'émulation en millisecondes et un niveau de verbosité (0 pour peu de messages et 10 pour voir tous les détails de l'émulation) :

java Reseau chaine3.txt 15000 0
Temps=427 Noeud=C  :  TRAFIC bien recu : DATA[CHAINE3.A1 -> CHAINE3.C1 ttl=15 nbhops=2 id=1]
Temps=1207 Noeud=C  :  TRAFIC bien recu : DATA[CHAINE3.A1 -> CHAINE3.C1 ttl=15 nbhops=2 id=2]
Temps=2087 Noeud=C  :  TRAFIC bien recu : DATA[CHAINE3.A1 -> CHAINE3.C1 ttl=15 nbhops=2 id=3]
Temps=2957 Noeud=C  :  TRAFIC bien recu : DATA[CHAINE3.A1 -> CHAINE3.C1 ttl=15 nbhops=2 id=4]
Temps=12697 Noeud=C  :  TRAFIC bien recu : DATA[CHAINE3.A1 -> CHAINE3.C1 ttl=15 nbhops=2 id=16]
Temps=13457 Noeud=C  :  TRAFIC bien recu : DATA[CHAINE3.A1 -> CHAINE3.C1 ttl=15 nbhops=2 id=17]
Temps=14447 Noeud=C  :  TRAFIC bien recu : DATA[CHAINE3.A1 -> CHAINE3.C1 ttl=15 nbhops=2 id=18]

chaine3.txt définit un réseau de nom CHAINE3 et de la forme A -- B -- C :

# chaine A1 -- 1B2 -- 1C
reseau CHAINE3 3
# noeuds :
noeud A 1 A1
noeud B 2 B1 B2
noeud C 1 C1
# liens :
lien A1 B1
lien B1 A1
lien B2 C1
lien C1 B2
# evenements :
trafic CHAINE3.A1 CHAINE3.C1 16 800 # trafic de CHAINE3.A1 vers CHAINE3.C1 ttl=16 
#                                        toutes les 800 millisec.
panne B2 3000 # panne de B2 au temps 3s
repare B2 12000 # reparation de B2 au temps 12000 millisec.

Les # marquent des commentaires. La syntaxe permet de spécifier les interfaces de chaque noeud puis d'indiquer les liaisons point à point entre les interfaces. (Seul le noeud B a deux interfaces, B1 à gauche et B2 à droite.) La dernière partie décrit une suite d'évènements que l'émulateur doit lancer : l'envoi de paquets de CHAINE3.A1 (l'interface de A) vers CHAINE3.C1 (l'interface de C) et une panne : une interface de B tombe en panne au bout de 3000 millisecondes et revient au bout de 12000 millisecondes (d'où l'interruption pendant un temps de l'arrivée de paquets en C dans la trace précédente).

Reseau.java contient pour l'instant un routeur très simple (classe InondRouteur) qui consiste à retransmettre un paquet de donnée reçu sur une interface du routeur sur toutes les autres interfaces. Ainsi chaque paquet "inonde" le réseau puisqu'il va transiter sur chaque lien et finira donc par arriver à destination (mais à quel prix!). Chaque routeur émet de plus régulièrement des messages "hello" qui ne sont pas utilisés ici mais dont on peut voir la réception avec une verbosité de 1 (java Reseau chaine3.txt 15000 1).

Comprendre le fonctionnement de la classe InondRouteur. Les exercices demandés dans ce TD consistent à programmer des déclinaisons différentes de cette classe. Pour plus d'information sur l'émulateur, utiliser au besoin l'annexe A qui donne plus de détails sur :

Éxécuter :

java Reseau complex.txt 2000 0

Et expliquer les nombres de sauts observés à l'arrivée pour le routage par "inondation" (donné par InondRouteur) lorsqu'on envoie des paquets de I1 vers H1 dans le réseau de complex.txt dessiné ci-dessous : quels sont les chemins suivis par les paquets~?

#        |------ 1A2 --1C3----------| 
#        |            /2            1 
#        |   |-- 1B2 /             2H 
#        4   |            G2 -----/ 
# I1 -- 3D1--|           /1 
#        2\            1/ 
#          \--- 1E2 --2F 
#                                 
# Toutes les liaisons sont point `a point. 
#
reseau COMP 9
#
...
trafic COMP.I1 COMP.H1 10 800
#
panne C1 3000 # une seule route
panne B1 9000 # il faut passer par la longue route par G
repare C1 15000
panne G1 15001 # toujours une seule route
repare G1 21000
repare B1 24000

Exercice 2. Routage par vecteur de distances

En vous inspirant de la classe InondRouteur, écrire une classe DVRouteur qui construit les tables de routage par échange de vecteurs de distances. Il est conseillé de retenir pour chaque voisin un record des informations utiles le concernant comme son nom, le numéro d'interface qui permet de discuter avec lui, la date de son dernier message. De même on retiendra pour chaque entrée de la table de routage, le réseau et l'interface destination, le nombre de sauts pour l'atteindre et le voisin permettant de l'atteindre. Un vecteur de distance pourra aussi être représenté par un ensemble de telles entrées (avec le voisin suivant non utilisé).

Tester avec chaine3.txt puis complex.txt. Votre protocol doit surmonter les pannes dans le réseau complex ou bout d'un délai raisonnable.

Le routage par vecteurs de distances en quelques mots

Proposition de choix d'implémentation

On pourra stocker dans une table de hachage pour chaque destination (codée par la concaténation du nom de réseau, de ".", et du nom d'interface), une entrée contenant le numéro d'interface où faire suivre les paquets pour cette destination et le nombre de sauts estimé jusqu'à cette destination.

Dans un premier temps, on pourra supposer qu'il n'y aucune panne et que les routeurs s'allumant les uns après les autres doivent finir par obtenir des tables de routage correctes.

Dans un deuxième temps, on pourra retenir pour chaque voisin la date de son dernier message et décider qu'il est en panne si l'on ne reçoit aucun message pendant plusieurs périodes d'envoi de message de vecteur de distances. Il faudra alors retirer de la table toutes les entrées utilisant ce voisin pour atteindre la destination correspondante. Pour pouvoir recalculer les routes, immédiatement, on pourra stocker pour chaque voisin (encore valide) son dernier vecteur de distances.

Une solution.

Une autre.

Une minimaliste.

Exercice 3. Routage par état des liens

Écrire une classe LSRouteur qui construit les tables de routage par diffusion de l'état des liens.

Le routage par état des liens en quelques mots

Proposition de choix d'implémentation

On pourra stocker dans une table de hachage la liste des noms des voisins d'un noeud donné (en supposant pour cet exercice qu'il n'y a qu'un seul réseau). La liste obtenue dans un nouveau message d'état de liens viendra remplacer la précédente. Cette liste pourra aussi contenir les destinations (codées par la concaténation du nom de réseau, de ".", et du nom d'interface) accessibles par le noeud.

La table de routage sera régulièrement calculée par un calcul de plus courts chemins sur le graphe ainsi codé. (Remarquons qu'un simple BFS convient.)

Dans un premier temps, on pourra supposer qu'il n'y aucune panne et que les routeurs s'allumant les uns après les autres doivent finir par obtenir des tables de routage correctes.

On pourra tout d'abord faire des inondations non optimisées sans retenir les numéros de séquences déjà retransmis. Attention, seul le TTL permettra alors de limiter le nombre de messages générés par une inondation.

Une solution.

Exercice 4. Routage inter-réseaux

L'émulateur peut réellement envoyer les paquets sur le réseau physique. Pour cela il faut spécifier un port d'écoute UDP pour chaque interface qui doit recevoir des paquets inter-réseaux. Dans la définition d'un lien, on peut spécifier un nom de machine et un port UDP pour envoyer des paquets vers cette interface. Vous pouvez ainsi de relier votre réseau avec celui de votre voisin.

Par exemple, les deux fichiers de configuration suivants permettent de relier par les noeuds C deux chaînes de la forme A -- B -- C de deux réseaux CHAINE3_ICI et CHAINE3_LA émulés respectivement sur des machines réelles de noms machine1.ici.fr et machine2.la.fr :

reseau CHAINE3_ICI 3
noeud A 1 A1
noeud B 2 B1 B2
noeud C 2 C1 C2:12345 # sp'ecification d'un port d''ecoute pour C2
lien A1 B1
lien B1 A1
lien B2 C1
lien C1 B2
lien C2 ext:machine2.la.fr:12346 # lien inter-r'eseaux
trafic CHAINE3_ICI.A1 CHAINE3_LA.A1 16 800 # trafic inter-r'eseaux

et

reseau CHAINE3_LA 3
noeud A 1 A1
noeud B 2 B1 B2
noeud C 2 C1 C2:12346 # sp'ecification d'un port d''ecoute pour C2
lien A1 B1
lien B1 A1
lien B2 C1
lien C1 B2
lien C2 ext:machine1.ici.fr:12345 # lien inter-r'eseaux
trafic CHAINE3_LA.A1 CHAINE3_ICI.A1 16 800 # trafic inter-r'eseaux

Nous proposons le format suivant pour l'échange de messages entre réseaux :

  +------+-----+-----+------------+---------+------------+-------------+---------------+-----
  | 127  |  0  |  1  | nb chemins | res dst |  long chem | res inter 1 |  res inter 2  | ... 
  +------+-----+-----+------------+---------+------------+-------------+---------------+-----

Le code est 127, le ttl vaut 0 (ne pas retransmettre) et le nombre de sauts est 1. Le reste constitue simplement une suite de chemins : pour chaque réseau destination connu sont donnés la longueur du chemin pour l'atteindre suivant des réseaux à traverser pour cela. (Le réseau du routeur source d'un tel message apparaîtra avec un chemin vide de longueur 0.) Une longueur de 255 indique un réseau inaccessible (le chemin qui suit est alors vide). Pour router, on atteint d'abord le réseau de la destination, ensuite les routeurs internes au réseau sauront comment router vers l'interface précise qu'on veut atteindre. La première difficulté pour votre routeur consiste à différencier ses voisins intra-réseau et ses voisins d'autres réseaux.

Connectez votre réseau aux réseaux de deux ou trois voisins, vous obtiendrez ainsi un internet... Une difficulté supplémentaire intervient lorsque deux routeurs différents du réseaux doivent s'échanger leur informations concernant l'extérieur du réseau.

Annexe A. Présentation détaillée de l'émulateur

Annexe A.1 Les routeurs

Une instance de type Routeur est associée à chaque routeur du réseau :

interface Routeur
{
    void initialiser (Reseau r, Noeud n) ; // associe le routeur au noeud n du reseau r
    void faireTousLesDixiemesDeSecondes (long t) ; // m'ethode appel'ee tous les 
                               //    dixi`emes de secondes (pour les envois de messages r'eguliers)
    void faireReception (long t, int numInterf, Paquet p) ; 
                               //  m'ethode appel'ee lors de la r'eception d'un paquet
}

Votre travail consiste à programmer votre propre classe routeur : class MonRouteur implements Routeur { ... } qui doit définir les trois méthodes ci-dessus de l'interface Routeur :

Les seules interactions possibles entre routeurs se font par l'envoi de paquets. Votre programme doit réussir à router les paquets quelque soit le fichier de configuration passé en argument lors de l'exécution. Ce que vous devez savoir sur les classes Reseau, Noeud et Interface qui constituent le coeur de l'émulateur se résume à :

Une fois que vous avez programmé votre propre classe routeur (vous pouvez vous inspirer de InondRouteur), il ne reste plus qu'à modifier une ligne dans Reseau.java pour que vos routeurs soient utilisés :

Pour la culture, chaque interface interf possède un DatagramSocket sock, interf.send(p) revient en gros à la suite d'appels suivants :

       DatagramPacket dp = new DatagramPacket (p.buf.array(), p.buf.limit()) ;
       dp.setAddress (recepAddr) ; // adresse IPv4 de l''emulateur destination
       dp.setPort (recepPort) ;    // port associ'e `a l'interface destination
       interf.sock.send (dp) ;

Annexe A.2 Les paquets

La classe Paquet incluse dans Reseau.java utilise un ByteBuffer de manière similaire au TD 2. Elle inclut de plus une longueur maximale de paquet Paquet.MTU et quelques fonctions pour manier les paquets de type DATA (remarquer en particulier oneMoreHop() qui est utile pour mettre à jour les champs ttl et nbhops avant retransmettre un paquet).

class Paquet
{
    final static int DATA = 1 ; // Code d'un paquet de donn'ees
    final static int MTU = 256 ; // Taille maximale de paquet

    ByteBuffer buf ; // Contenu du paquet


    Paquet (int)   // constructeur : allocation d'un nouveau paquet

    int getInt8 ()           // lecture d'un entier sur 1 octet (entre 0 et 255)
    void putInt8 (int)       // 'ecriture d'un entier sur 1 octet

    String getString8 ()     // lecture d'une cha^ine pr'efix'ee 
                             //    de sa longueur (cod'ee sur un octet)
    void putString8 (String) // 'ecriture d'une cha^ine pr'efix'ee 
                             //    de sa longueur (cod'ee sur un octet)

    void rewind ()     // remettre la position de lecture `a 0

    String toString () // pour afficher le contenu d'un paquet
                       //   les paquets DATA sont d'ecod'es

    void oneMoreHop () // d'ecr'emente l'octet ttl
                       //    et incr'emente l'octet nbhops
}

Annexe A.3 Le fichier de configuration du réseau

# chaine A -- B -- C
reseau CHAINE3 3
# noeuds :
noeud A 1 A1
noeud B 2 B1 B2
noeud C 1 C1
# liens :
lien A1 B1
lien B1 A1
lien B2 C1
lien C1 B2
# evenements :
trafic CHAINE3.A1 CHAINE3.C1 16 800 # trafic de CHAINE3.A1 vers CHAINE3.C1 ttl=16 
#                                            toutes les 800 millisec.
panne B2 3000 # panne de B2 au temps 3s
repare B2 12000 # reparation de B2 au temps 12000 millisec.

Last modified: Fri Feb 9 01:38:08 CET 2007