Home

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 de type "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 A -- B -- C
reseau CHAINE3 3
# noeuds :
noeud A 1 A1
noeud B 2 B1 B2
noeud C 1 C1
# liens :
lien A1 vers 1 interfaces B1
lien B1 vers 1 interfaces A1
lien B2 vers 1 interfaces C1
lien C1 vers 1 interfaces 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. Seul le noeud B a deux interfaces. La syntaxe permet de relier une interface à plusieurs autres (comme dans un réseau Ethernet). 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 premiers paquets qui arrivent~?

#            |-- 1A2 --1C3-----|
#            |        /2       |-- 1H
#            |-- 1B2 /         |
#            |            G2 --|
# I1 -- 3D1--|           /1
#        2\            1/
#          \--- 1E2 --2F
#
# A1 B1 D1 sont reli'ees par un ethernet : l'emission
#  depuis une interface est recue par les deux autres.
# C3 G2 H1 sont reli'ees par un ethernet.
# les autres liaisons sont point `a point.
#
reseau COMP 9
#
...
trafic COMP.I1 COMP.H1 10 800
#
...

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 vecteur de distances, le numéro d'interface qui permet de discuter avec lui, le port de son interface (voir la documentation de faireReception(), et interf.send() dans l'annexe sur les routeurs). Il est suggéré d'utiliser une liste pour stocker les vecteurs distance ( une Hashtable demande pas mal de consultation de documentation, ce qui peut s'avérer plus long à utiliser).

Tester avec chaine3.txt puis complex.txt. (Votre protocol doit surmonter les pannes dans le réseau complex. Pour tracer une exécution, on pourra par exemple utiliser :

java Reseau complex.txt 30000 2 > /tmp/o
less /tmp/o

Le routage par vecteurs de distances en quelques mots

Une solution.

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

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 vers 1 interfaces B1
lien B1 vers 1 interfaces A1
lien B2 vers 1 interfaces C1
lien C1 vers 1 interfaces B2
lien C2 vers 1 interfaces 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 vers 1 interfaces B1
lien B1 vers 1 interfaces A1
lien B2 vers 1 interfaces C1
lien C1 vers 1 interfaces B2
lien C2 vers 1 interfaces ext:machine1.ici.fr:12345 # lien inter-r'eseaux
trafic CHAINE3_LA.A1 CHAINE3_ICI.A1 16 800 # trafic inter-r'eseaux

Seuls des liens point-à-point sont possibles entre deux réseau, on pourra donc utilser interf.send (p, 0) pour envoyer un paquet p vers l'autre réseau sur une telle interface interf.

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, int sourcePort) ; 
                               //  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.content, p.length) ;
       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 est similaire à celle construite au TD 1. 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

    byte[] content ;     // Comme dans un datagram packet
    int length ; 

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

    int readInt8 ()          // lecture d'un entier sur 1 octet
    String readString8 ()    // lecture d'une cha^ine pr'efix'ee 
                             //    de sa longueur (cod'ee sur un octet)
    void writeInt8 (int)      // 'ecriture d'un entier sur 1 octet
    void writeString8 (String)// 'ecriture d'une cha^ine pr'efix'ee 
                              //    de sa longueur (cod'ee sur un octet)

    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 vers 1 interfaces B1
lien B1 vers 1 interfaces A1
lien B2 vers 1 interfaces C1
lien C1 vers 1 interfaces 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 3 00:50:41 CET 2006