TD 5 : 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" (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. Ainsi comme dans l'Internet, toute interface réseau d'une machine ou d'un routeur a un identifiant unique qui sera codé comme une suite de caractères terminée par un 0 (plutôt que comme une suite de quatre octets pour IPv4). 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 plusieur. Il est donc important de pouvoir identifier chaque interface (et pas seulement chaque noeud du réseau).

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 pas 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=1 id=1]
Temps=1207 Noeud=C  :  TRAFIC bien recu : DATA[CHAINE3.A1 -> CHAINE3.C1 ttl=15 nbhops=1 id=2]
Temps=2087 Noeud=C  :  TRAFIC bien recu : DATA[CHAINE3.A1 -> CHAINE3.C1 ttl=15 nbhops=1 id=3]
Temps=2957 Noeud=C  :  TRAFIC bien recu : DATA[CHAINE3.A1 -> CHAINE3.C1 ttl=15 nbhops=1 id=4]
Temps=12697 Noeud=C  :  TRAFIC bien recu : DATA[CHAINE3.A1 -> CHAINE3.C1 ttl=15 nbhops=1 id=16]
Temps=13457 Noeud=C  :  TRAFIC bien recu : DATA[CHAINE3.A1 -> CHAINE3.C1 ttl=15 nbhops=1 id=17]
Temps=14447 Noeud=C  :  TRAFIC bien recu : DATA[CHAINE3.A1 -> CHAINE3.C1 ttl=15 nbhops=1 id=18]

chaine3.txt définit un réseau de nom CHAINE3 et de la forme A -- B -- C (seul le noeud B a deux interfaces), avec des envois de paquets de CHAINE3.A1 (l'interface de A) vers CHAINE3.C1 (l'interface de C) et avec 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).

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 en utilisant au besoin l'annexe A qui donne plus de détails sur :

Éxécuter :

java Reseau complex.txt 3000 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 :

#            |-- 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.

Tester avec complex.txt.

Le routage par vecteurs de distances en quelques mots

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 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

Mettez vous d'accord avec votre voisin sur une manière de se détecter l'un l'autre et sur un format de paquet, et échangez des vecteurs de chemins pour le routage inter-réseaux. Un chemin sera une suite de noms de réseaux pour atteindre un réseau. (Entre réseaux, on ne s'échange que des informations sur les connexions entre réseaux.) 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.

Connectez tous vos réseaux sur les deux classes de TD, vous obtenez un internet... Même en ayant des formats d'échanges différents sur les différents liens inter-réseau, ça doit pouvoir marcher (certains propriétaires de réseau risquent alors d'avoir à gérer plusieurs formats d'échanges).

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 faireToutesLesSecondes (long t) ; // m'ethode appel'ee toutes les 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 :

Annexe A.2 Les adresses

Une classe Adresse permet de décomposer une adresse en son nom de réseau et son nom d'interface :

class Address 
{
    String nomRes ;
    String nomInterf ;

    Address (String r, String i) // "R" et "I"
    Address (String addr)  // sous la forme "R.I"
    public String toString() // -> nomRes + "." + nomInterf
}

Annexe A.3 Les paquets

Une classe Paquet permet de représenter des paquets de données, c'est à dire une suite de byte de longueur inférieure à Paquet.MTU.

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

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

Format des paquets

Le premier byte d'un paquet codera toujours le type du paquet. Seul le type Paquet.DATA est défini dans l'énoncé. Libre à vous de définir de nouveaux types ainsi que les formats de contenu associés.

Un paquet de type Paquet.DATA sera toujours constitué ainsi :

Lecture d'un paquet

Pour lire le contenu d'un paquet on utilisera les méthodes readInt8(), readInt8(), et readString(). Pour lire un paquet de données, on pourra ainsi exécuter :

	int code = p.readInt8 () ; // doit valoir Paquet.DATA
	String dest = new Address (p.readString ()) ;
	String orig = new Address (p.readString ()) ;
	int ttl = p.readInt8 () ;
	int nbhops = p.readInt8 () ;
	int id = p.readInt16 () ;

Pour reprendre la lecture d'un paquet depuis le début, il faut exécuter :

	p.rewind () ;

Ecriture d'un paquet

Pour construire plus facilement des paquets, une classe WritePaquet est fournie. On peut construire un paquet de type Paquet.DATA ainsi :

        WritePaquet p = new WritePaquet () ; 
	p.writeInt8 (Paquet.DATA) ; // Code DATA
	p.writeString (to) ; // adresse destination
	p.writeString (from) ; // adresse origine
	p.writeInt8 (ttl) ; // TTL
	p.writeInt8 (nbhops) ; // Nombre de sauts
	p.writeInt16 (id) ; // Contenu

Forwarder un paquet de type Paquet.DATA

Pour manier plus facilement encore les paquets de type Paquet.DATA, on pourra utiliser la classe :

class DataPaquet
{
    Address orig, dest ;
    int ttl, nbhops ;
    int nb ;

    DataPaquet (Address to, Address from, int ttl, int nbhops, int id) ;
    DataPaquet (Paquet p)

    Paquet toPaquet () 
    Paquet oneMoreHopPaquet ()
}

Pour retransmettre un paquet p de type Paquet.DATA, on peut construire le paquet similaire avec le champs TTL incrémenté et le champs nbhops décrémenté ainsi :

    Paquet next = (new DataPaquet (p)).oneMoreHopPaquet () ;

Annexe A.4 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: Sun Feb 15 17:03:50 CET 2004