L3 ISTIC/Université de Rennes 1 2023-2024
COUCHE RESEAU : LE ROUTAGE
1. GENERALITES
1.1. Définition
Le routage est le processus qui consiste, dans un réseau, ou au travers de différents réseaux, à
trouver un chemin entre une source et une destination. C’est l'une des fonctionnalités
principales de la couche réseau. On appelle routeur un équipement relié à au moins deux réseaux et
dont le rôle est de réémettre des paquets venus d'une de ses interfaces vers une autre.
Schématiquement, on peut représenter l'Internet comme une hiérarchie de routeurs. On appelle
système autonome (Autonomous System ou AS) un ensemble de routeurs et de réseaux contrôlés par
une même autorité administrative ; on peut donc voir l’Internet comme un ensemble d'AS. On
distingue les routeurs situés à l'intérieur d'un même AS de ceux qui permettent de relier entre eux
différents AS. A l'intérieur d'un AS, on parle de protocoles de routage intra-domaine (Interior
Gateway Protocol ou IGP) ; entre différents AS, il s'agit de protocoles de routage inter-domaines
(Exterior Gateway Protocol ou EGP). Dans le cadre de ce TD, nous nous intéresserons
exclusivement aux protocoles intra-domaine.
Le routage (intra-domaine) est réalisé grâce aux protocoles de routage qui maintiennent des tables
de routage dans les routeurs (et commutateurs) du réseau. Une table de routage comporte au moins
deux colonnes : la première pour la destination (ou pour le réseau de destination) et la seconde pour
l'adresse de l'élément réseau correspondant au « saut » suivant (next hop) sur le « meilleur » chemin
vers la destination souhaitée. Lorsqu'un paquet arrive sur un routeur (ou lorsqu'un paquet d'appel
arrive sur un commutateur), le routeur (le commutateur) consulte sa table de routage pour décider
du prochain saut pour ce paquet.
1.2. Exercice
1.2.1. Quelles sont les propriétés que doit posséder un « bon » protocole de routage ?
F 1.2.2. Proposez des critères permettant une classification des protocoles de routage.
Le routage est, par essence, un problème de la théorie des graphes : il s'agit de trouver le chemin
de coût minimum entre deux nœuds quelconques, sachant que le coût d'un chemin est la somme des
coûts des liens qui le composent.
Il existe plusieurs classes de techniques de routage :
Le routage isolé : cette classe regroupe des techniques qui ne nécessitent aucun échange
d'information entre les nœuds et ne construisent pas de table de routage. Comme exemple de
routage isolé, on peut citer le routage par inondation dans lequel chaque nœud retransmet
toujours tous les paquets sur toutes ses interfaces, sauf l'interface entrante.
1
L3 ISTIC/Université de Rennes 1 2023-2024
Le routage centralisé : on dispose d'un centre de contrôle de routage qui reçoit
périodiquement des informations décrivant l'encombrement du réseau. Il en déduit les tables
de routage de chaque routeur et les leur expédie.
Le routage distribué : chaque routeur échange périodiquement des informations avec ses
voisins et recalcule sa table de routage. Deux types d'algorithmes de routage distribué sont
largement utilisés :
– Le routage à vecteurs de distance (Ex : Routing Information Protocol ou RIP) ;
– Le routage à état des liens (Ex: Open Shortest Path First ou OSPF).
Dans ce TD nous nous intéresserons principalement aux algorithmes à vecteurs de distance. Leurs
caractéristiques sont les suivantes :
ils supposent que chaque routeur connaît l'adresse de chacun de ses voisins, ainsi que le
« coût » pour l'atteindre ;
ils permettent à chaque routeur de déterminer l'information de routage globale, i.e. le prochain
nœud pour atteindre chaque destination possible sur la route la plus courte, en échangeant de
l'information de routage seulement avec ses voisins.
2. ALGORITHMES A VECTEURS DE DISTANCE
2.1. Principe
L'algorithme de base est dû à Bellman-Ford. Chaque nœud est supposé connaître la « distance » (ou
le « coût ») qui le sépare de chacun de ses voisins (une liaison hors service a un coût infini).
Périodiquement, chaque nœud envoie à chacun de ses voisins la liste des distances estimées vers
chaque nœud du réseau : c'est le vecteur de distance. Il reçoit en retour une liste similaire de chacun
de ses voisins.
Lorsque le nœud i reçoit le vecteur de distance Vj de son nœud voisin j, Vj(k) lui donne la distance
(estimée par j) pour aller de j à k, et il sait donc qu'il peut atteindre k via j, avec un coût de Vj(k)
augmenté du coût de sa liaison à j. En poursuivant ce calcul pour chacun de ses voisins, i peut
déterminer l'estimation qui lui semble la meilleure pour atteindre chaque destination, et inscrire
cette estimation ainsi que la liaison correspondante dans sa table de routage.
2.2. Exercices
2.2.1. Soit le réseau composé des 5 nœuds A, B, C, D et E, et des 6 liaisons Vab, Vad, Vbc, Vbe,
Vce et Vde. A chaque liaison, supposée symétrique, est associée une distance égale à 1.
L'algorithme utilisé par le protocole de routage est de type Bellman-Ford.
Vab Vbc
A B C
Vad Vbe Vce
D E
Vde
a. On supposera que le réseau vient d'être mis en service et que chaque nœud n'a qu'une
connaissance locale de la topologie du réseau (il ne connaît que ses voisins). Donner les
tables de routage initiales des différents nœuds.
2
L3 ISTIC/Université de Rennes 1 2023-2024
b. On considèrera la séquence d'échange de vecteurs de distance suivante :
T1 B, D reçoivent VA (vecteur de distance de A)
T2 A, C, E reçoivent VB
T3 A, E reçoivent VD
T4 B, D reçoivent VA, VE
T5 B, E reçoivent VC
T6 A reçoit VB
T7 C, D reçoivent VE
Donnez la table de routage (incluant les distances) de chaque nœud, obtenue une fois que
l'algorithme de routage a convergé.
3
L3 ISTIC/Université de Rennes 1 2023-2024
c. La liaison Vab est rompue. Montrez comment les tables de routage de chaque nœud sont
mises à jour. Que remarquez-vous à l'issue de la séquence d'échanges des vecteurs de
distance suivante ?
T1 A et B détectent que Vab est rompue
T2 D reçoit VA ; C, E reçoivent VB
T3 E reçoit VD
T4 B, C, D reçoivent VE
T5 A reçoit VD
4
L3 ISTIC/Université de Rennes 1 2023-2024
2.2.2. On considère le même réseau que dans l’exercice précédent, excepté que la liaison Vce a un
coût de 10 (les autres liaisons gardant un coût unitaire). On suppose qu’après convergence des
algorithmes de routage, les tables obtenues sont les suivantes :
5
L3 ISTIC/Université de Rennes 1 2023-2024
A B C D E
dest next dist dest next dist dest next dist dest next dist dest next dist
A - 0 A A 1 A B 2 A A 1 A B 2
B B 1 B - 0 B B 1 B A 2 B B 1
C B 2 C C 1 C - 0 C A 3 C B 2
D D 1 D A 2 D B 3 D - 0 D D 1
E B 2 E E 1 E B 2 E E 1 E - 0
La liaison Vbc est alors rompue. B détecte la rupture, mais avant qu'il n'ait eu le temps
d'envoyer son vecteur de distance, A a déjà diffusé le sien. La séquence d'échange est donc la
suivante :
T1 B détecte que Vbc est rompue
T2 B reçoit VA
T3 A, E reçoivent VB
Que se passe-t-il ?
6
L3 ISTIC/Université de Rennes 1 2023-2024
Plusieurs solutions permettent de pallier le problème du comptage à l’infini :
Le vecteur de chemin : chaque entrée du vecteur de distance contient le chemin complet
associé à la valeur ; C'est une technique utilisée dans BGP, mais qui présente l'inconvénient
de générer des tables volumineuses. (Il est à noter que BGP, Border Gateway Protocol, est un
protocole de routage inter-AS.)
L'horizon partagé (split horizon) : un routeur ne communique jamais le coût vers une
destination à son voisin N, si N est le prochain nœud vers cette destination.
L'horizon partagé avec antidote (split horizon with poisonous reverse) : Un routeur
communique toujours un coût infini vers une destination à son voisin N, dès l’instant où N est
le prochain nœud vers cette destination. Cela se traduit par une modification mineure du
protocole de vecteurs de distance ; au lieu de diffuser le même vecteur sur toutes leurs
liaisons, les nœuds devront en composer des versions différentes, pour tenir compte des
destinations qui sont atteintes via chacune de ces liaisons. C'est la technique utilisée dans RIP.
2.2.3. Qu’induisent ces différentes solutions sur l’exemple de l’exercice 2.2.3 ?
3. ROUTAGE ET COMMUTATION
3.1. Rappels
Nous avons vu qu'un commutateur est un équipement permettant d'interconnecter des liaisons de
façon à former un réseau. Cet équipement, possédant plusieurs ports en entrée et plusieurs ports en
sortie, a pour rôle de transférer un paquet qu'il reçoit sur un port d'entrée vers un port de sortie. La
question qui se pose alors est de savoir comment le (bon) port de sortie est déterminé. La réponse se
trouve bien évidemment dans l'en-tête du paquet, mais sous quelle forme ? Deux approches sont
possibles :
dans la commutation en mode non connecté (datagramme), le paquet est réacheminé sur la
base de son adresse de destination ;
dans la commutation en mode connecté (circuit virtuel), le paquet est réacheminé sur la
base de son identificateur de circuit virtuel.
7
L3 ISTIC/Université de Rennes 1 2023-2024
3.2. Exercice
3.2.1. Quelle est la propriété intrinsèque d'un circuit virtuel ?
3.2.2. Quelles sont les principales caractéristiques du mode d'acheminement :
– par voie logique ;
– par datagramme ?
Qu'induisent-elles comme avantages et inconvénients ?
3.2.4. On considère la topologie réseau suivante ; S1 , S2 et S3 étant des commutateurs de circuits
virtuels et les numéros indiqués étant des numéros de port :
B C D
2 2 2
1 3 1 3 1 3
A S1 S2 S3 E
Les tables de commutation sont les suivantes :
S1 S2 S3
port VL port VL port VL port VL port VL port VL
1 2 3 1 1 1 3 3 1 3 2 1
1 1 2 3 1 2 3 2 1 2 3 1
2 1 3 2
Sachant que les connexions sont bidirectionnelles, donner tous les circuits virtuels établis en
indiquant les commutateurs traversés.
