Protocoles de routage

1 Commutation de paquets

On appelle client un ordinateur qui demande une ressource

à un autre ordinateur appelé serveur
Imaginons qu’un client (en haut de l’image) veuille téléchar-
ger un document relativement volumineux (un pdf de plusieurs
pages) chez un serveur S (en bas à gauche)
Le document est découpé en paquets étiquetés et numérotés
puis ces paquets vont suivre des trajectoires indépendantes
le long du trajet du serveur au client.
Les routeurs R (symboles avec 4 flèches comme des carrefours)
font la circulation des paquets, de manière autonome à l’aide
d’algorithmes
On a dessiné pour l’exemple deux trajectoires différentes pour
les paquets 1 et 2
Ensuite chez le client le document est reconstitué en tenant
1
compte de la numérotation des paquets.
l’idée de la commutation des paquets signifie donc que :
1. Le document au delà d’une certaine taille (1500 octets) est
découpée en paquets
2. Ces paquets sont commutés (aiguillés) indépendamment
les uns des autres en fonction de la densité de circulation
sur le réseau

2 Systèmes autonomes

La connexion entre un client et un serveur n’est pas directe,

il existe de nombreux relais entre le client et le serveur on ap-
pelle ces relais des routeurs et leur rôle est fondamental dans
l’acheminement des données entre le client et le serveur grâce à
l’adressage IP
Dans un terminal si on entre la commande traceroute example.com
ou tracert example.com, on observe la suite des routeurs re-
liant la box 192.168.1.1 au serveur 93.184.216.34 hébergeant le
domaine example.com
A l’aide du site RIPEstat on peut ranger les routeurs en trois
groupes ou systèmes autonomes le premier celui de ORANGE,
le second celui de TELIA et enfin le dernier celui de EDGE-
CAST
Il existe plus de 50 000 systèmes autonomes, on peut voir ici les
principaux systèmes autonomes http://as-rank.caida.org.

2
Au lieu de regarder Internet comme un ensemble d’or-
dinateurs interconnectés dans le monde on peut regar-
der Internet comme un ensemble de réseaux (les sys-
tèmes autonomes) interconnectés
Un organisme (Center for Applied Internet Data Analysis ) a
proposé une visualisation d’Internet à partir des systèmes au-
tonomes (Voir http://caida.org)
La circulation des paquets entre plusieurs systèmes auto-
nomes nécessite un protocole de routage externe aux sys-
tèmes autonomes comme le protocole BGP (Border Gateway
Protocol)
Nous allons nous intéresser cette année aux proto-
coles de routage des paquets uniquement à l’intérieur
des systèmes autonomes, les protocoles RIP (Routing
Information Protocol) et OSPF (Open Shortest Path
First)

3
3 Tables de routage

Il existe une analogie entre la circulation des paquets dans

l’Internet et la circulation routière
Un rond-point ressemble d’une certaine manière à un routeur.
Imaginons que l’on cherche à rejoindre Paris en voiture et que
l’on se trouve près de Bordeaux
Avant d’entrer dans un rond-point (entrée 0) un logiciel de
navigation va nous conseiller de prendre la première sortie du
rond-point pour rejoindre la direction de Paris
Les entrées-sorties du rond-point sont les équivalents des in-
terfaces d’un routeur, les entrées sorties du routeur

Chaque interface d’un routeur est caractérisée par une adresse

IP, ce qui fait qu’un routeur a plusieurs adresses IP, une par
interface
Lorsque deux routeurs R1 et R2 sont connectés, ils sont
alors dans le même réseau et dans ce réseau caractérisé par
une adresse réseau, ils ont chacun une adresse IP , adr(R1) et
adr(R2)
Si R1 doit relayer un paquet à destination de l’adresse IP
a.b.c.d en passant par R2 alors dans la table de routage
de R1 il y aura une ligne comme

4
 IP de destinantion Masque Passerelle suivante Via l’interface
a.b.c.d ..... adr(R2) adr(R1)
Regardons cela plus en détail dans l’exemple suivant où le
routeur R remplace le rond-point précédent
Si un paquet part du serveur 192.168.0.10 en destination du
client 192.168.1.10, il n’y a qu’une seule route possible en
passant par les routeurs R0 puis R puis R1

Pour relayer ce paquet dans la table de routage de R0 il y

aura
IP de destinantion Masque Passerelle suivante Via l’interface
192.168.1.10 255.255.255.0 10.0.0.1 10.0.0.2
En effet le paquet doit "sortir" de R0 par son interface 10.0.0.2
pour suivre la direction, la passerelle 10.0.0.1
Puis le routeur R va relayer ce paquet grâce à une ligne
IP de destinantion Masque Passerelle suivante Via l’interface
192.168.1.10 255.255.255.0 10.0.1.1 10.0.1.2
En effet pour le routeur R il y a plusieurs sorties possibles
5
mais pour aller vers R1, il faut prendre l’interface 10.0.1.1 puis
la passerelle 10.0.1.2
Ce n’est pas le cas dans notre exemple mais dans la réa-
lité à une interface il peut y avoir plusieurs passerelles
possibles
Enfin dans la réalité il existe plusieurs routes pos-
sibles d’où les problèmes suivants
1. Comment choisir telle route plutôt que telle autre ?
2. Qui décide du choix ?
3. Comment gérer les pannes de connexion entre les rou-
teurs ?
On aurait pu laisser à une autorité centrale le soin de rem-
plir les tables de routage et de réparer les pannes. (routage
centralisé et statique)
On a préféré mettre au point des protocoles, nécessitant
l’échange d’informations entre les routeurs et s’appuyant
ensuite sur des algorithmes exécutés régulièrement sur chaque
routeur, pour mettre à jour les tables de routage (routage
dynamique)

4 Le protocole RIP ou protocole à vecteur de distance

Le protocole RIP (Routing Information Protocol) est un pro-

tocole de routage consistant à minimiser le nombre de sauts
entre les routeurs pour acheminer un paquet d’une machine
à une autre
Chaque routeur envoie régulièrement à ses voisins les vec-
teurs (adresse réseaux ,nombre de sauts) qu’il connaît
Lorsqu’un routeur reçoit une telle information

6
1. s’il ne connaît pas le réseau il rajoute le vecteur dans sa
table de routage en ajoutant un au nombre de sauts et
conserve l’information de l’expéditeur qui est la passerelle
2. s’il connaît déjà le réseau, il y a plusieurs cas possibles :
(a) La passerelle est différente et le nombre de sauts
est supérieur à celui qu’il a dans sa table, dans ce
cas il ignore cette information
(b) La passerelle est différente et le nombre de sauts
est strictement inférieur à celui qu’il a dans sa
table, dans ce cas il efface l’ancienne information et
conserve la nouvelle passerelle et le nombre de sauts +
1
(c) La passerelle est identique mais le nombre de
sauts est strictement supérieur à ce qu’il a dans
sa table cela signifie qu’une panne est apparue sur cette
route, dans ce cas il efface l’ancienne information et
conserve la passerelle et le nombre de sauts + 1
Regardons cela sur un exemple

7
 Un nouveau routeur R7 associé au réseau 10.0.1.0/24 est relié
à R1
R7 étant directement relié à ce réseau 10.0.1.0/24, il n’y a
pas de passerelle et le coût en nombre de sauts est 1
Dans la table de routage de R7 il y a donc une ligne comme
celle-ci
Réseau Passerelle suivante Nombre de sauts
10.0.1.0/24 ... 1
1. R7 "signale" sa présence à R1 en lui signifiant aussi qu’il
est associé à un réseau d’adresse 10.0.1.0/24 (flèche rouge)
R1 ne connaît pas ce réseau donc ajoute dans sa table
Réseau Passerelle suivante Nombre de sauts
10.0.1.0/24 R7 2
2. R1 communique à ses voisins l’information qu’il connaît
un réseau 10.0.1.0/24 qui est à deux sauts
R7 reçoit cette information et ajoute un au nombre de
sauts, autrement dit il y a un réseau 10.0.1.0/24 qui est à
3 sauts et qui passe par R1 mais dans sa table de routage
il y a mieux puisque le réseau 10.0.1.0/24 est directement
accessible, donc il ne modifie pas sa table de routage
R2 reçoit cette information et donc met dans sa table
Réseau Passerelle suivante Nombre de sauts
10.0.1.0/24 R1 3
De même pour R3
Réseau Passerelle suivante Nombre de sauts
10.0.1.0/24 R1 3
3. L’information va se propager de proche en proche et ainsi
R5 va recevoir de R4 le vecteur suivant (10.0.1.0/24, 4)
et de R3 le vecteur (10.0.1.0/24, 3) d’où la nouvelle ligne
dans la table de R5
8
 Réseau Passerelle suivante Nombre de sauts
10.0.1.0/24 R3 4
4. Finalement R6 aura dans sa table de routage
Réseau Passerelle suivante Nombre de sauts
10.0.1.0/24 R3 4
Maintenant supposons que la connexion entre les rou-
teurs R3 et R6 tombe en panne
R6 se rendra compte de cela au bout d’un certain temps
parce qu’il ne recevra plus d’information provenant de R3
Dans ce cas dans la table de routage de R6 il y aura cette
modification
Réseau Passerelle suivante Nombre de sauts
10.0.1.0/24 R3 16
Pourquoi 16 ?
Le protocole RIP limite à 15 le nombre de sauts possible par
conséquent d’une certaine manière la valeur 16 représente un
"infini"

Cependant R5 communique régulièrement avec R6 et lui an-

9
nonce le vecteur (10.0.1.0/24, 4) donc rapidement R6 va mettre
à jour sa table de routage
Réseau Passerelle suivante Nombre de sauts
10.0.1.0/24 R5 5
Regardons un autre cas de panne
Supposons cette fois ci que la connexion entre R1 et R2 tombe
en panne donc R2 met à jour sa table de routage
Réseau Passerelle suivante Nombre de sauts
10.0.1.0/24 R1 16
R4 reçoit de R2 le vecteur (10.0.1.0/24, 16) or dans la table
de routage de R4 la passerelle pour atteindre 10.0.1.0/24 est
R2, cela signifie qu’il y a un problème sur la route de R4 à
10.0.1.0/24
Donc R4 met à jour sa table de routage
Réseau Passerelle suivante Nombre de sauts
10.0.1.0/24 R2 16

10
 Au bout d’un moment R4 va recevoir de R5 le vecteur (10.0.1.0/24,
4) et donc mettre à jour sa table de routage
Réseau Passerelle suivante Nombre de sauts
10.0.1.0/24 R5 5
Finalement R2 va recevoir de R4 le vecteur (10.0.1.0/24, 5)
et donc mettre à jour sa table de routage
Réseau Passerelle suivante Nombre de sauts
10.0.1.0/24 R4 6

5 Boucles de routage

Lorsqu’un paquet tourne en boucle dans un réseau sans ar-

river à destination on parle alors de boucle de routage
Déjà le protocole IP a un mécanisme pour éviter un tel phé-
nomène, basé sur un compteur de durée de vie d’un paquet
appelé TTL (Time To Live) .
Un paquet a une durée de vie qui est un entier, égal au
nombre maximum de routeurs que le paquet peut traverser.
Cette durée de vie est diminuée de 1 à chaque fois que le pa-
quet traverse un routeur
Lorsqu’un routeur reçoit un paquet de durée vie égale à 0, il
le détruit.
On rappelle que le protocole TCP associe à chaque paquet
un accusé de réception de telle sorte qu’un paquet détruit sera
renvoyé par l’expéditeur
Le protocole RIP ajoute des règles pour éviter les boucles de
routage

11
6 Le protocole OSPF ou protocole à état de liens

Le protocole RIP ne tient pas compte de l’état des liens

entre les routeurs
Le protocole OSPF (pour Open Short Path First) prend en
compte le débit d’information sur les liens entre les routeurs
(On appelle cela la bande passante exprimée en bit/s )
A la différence du protocole RIP ou le coût d’une liaison entre
deux routeurs est le nombre de sauts, pour le protocole OSPF
le coût d’une liaison est défini par
108
coût =
bande passante
Le nombre 108 a été choisi pour que le coût d’une liaison
FastEthernet, dont la bande passante est 108 bit/s, soit égale à
1
Voici quelques coûts :
— Pour une liaison Ethernet, la bande passante est 107 bit/s
le coût est donc de 10
— Pour une liaison Fibre, la bande passante est 109 bit/s le
coût est donc de 0,1

6.1 Echange d’informations

Dans le cadre d’un protocole de routage décentralisé et dy-

namique il faut au préalable un échange d’informations entre
les routeurs

12
1. Dans un premier temps chaque routeur échange avec
ses voisins (ceux qui partagent avec lui un même sous-
réseau, sans être directement reliés par un câble car entre
eux il peut y avoir des commutateurs) des paquets "Hello"
Ce sont des petits paquets d’informations, émis régulière-
ment (toutes les 10 ou 30 secondes)
Cela permet à chaque routeur de connaître la qualité des
liens (en bande passante) qu’il a avec ses voisins et aussi
éventuellement de détecter rapidement des pannes (quelques
minutes)
Par exemple le routeur R3 aura au bout d’un moment la
connaissance suivante de ses voisins

13
 Routeur Voisin Coût
R1 1
R5 0,1
R6 1
2. Dans un second temps chaque routeur diffuse à l’en-
semble de son réseau (un système autonome) la table de
coût des liaisons avec ses voisins de telle sorte que chaque
routeur ait au bout d’un certain temps une cartographie
de l’ensemble du réseau auquel il appartient (un tableau
de coûts à deux dimensions)

6.2 Algorithme de plus court chemins dans un graphe pondéré :

Une fois que chaque routeur a la cartographie de son réseau,

il exécute l’algorithme de Dijkstra pour trouver les chemins les
plus courts partant de lui et à destination des autres routeurs
Ainsi par exemple pour le routeur R3 on aura la table des
chemins les plus courts
Routeur Route Coût
R1 R3-R1 1
R2 R3-R1-R2 2
R4 R3-R5-R4 0,2
R5 R3-R5 0,1
R6 R3-R5-R6 0,2
R7 R3-R1-R7 2
Cette table va servir à la construction de la table de routage
de R3
L’algorithme de Dijkstra assure qu’il n’y a pas de boucle de
routage

14
7 Surcout des protocoles

On appelle surcout d’un protocole le volume d’informations

échangées entre les routeurs qui ne sont pas des données
Avec le protocole RIP chaque routeur envoie régulièrement
à ses voisins sa table de routage ce qui représente un quantité
conséquente d’informations
A l’inverse avec le protocole OSPF chaque routeur envoie
régulièrement peu d’informations (paquet "Hello") à ses voisins
directs et de temps à autre il envoie à tous les routeurs de
son réseau la table de coût des liaisons avec ses voisins, ce qui
représente dans l’ensemble un surcoût moindre que le protocole
RIP

8 Exercices

Ex 1
On considère une machine d’adresse IPv4 10.38.133.5/16
1. Donner l’adresse réseau dans lequel se trouve cette ma-
chine
2. Donner l’adresse de diffusion (broadcast) de ce réseau
3. Donner le nombre maximal de machines que l’on peut
connecter sur ce réseau
4. On souhaite ajouter une machine sur ce réseau, proposer
une adresse IPv4 possible pour cette machine
Ex 2
Est ce que les machines d’adresses IPv4 192.168.203.15/21 et
192.168.200.65 sont dans le même sous-réseau ?

15
 Ex 3
Le modèle TCP/IP de communication entre des ordinateurs
est constitué de différentes couches citées ci-après dans le désordre :
Réseau, Application, Lien, Transport
Compléter le schéma suivant en ajoutant pour chaque couche
au moins un protocole

Ex 4

Sans utiliser de protocole donner toutes les routes valides

allant du routeur R7 au routeur R5

16
 Ex 5
Internet est régulé par l’IETF (Internet Engineering Task
Force)
Des notes appelées RFC (Requests For Comments) émises
par l’IETF décrivent les technologies utilisées pour Internet
Par exemple voici un extrait du RFC 2453 à propos du pro-
tocole RIP version 2
De quoi parle cet extrait ?

Ex 6
On représente ci-dessous un réseau dans lequel R1, R2, R3,
R4 et R5 sont des routeurs

17
 L’ordinateur 192.168.96.225 ainsi que le routeur R1 font par-
tie du réseau 192.168.96.0/20
L’interface du routeur R1 vers le réseau 192.168.96.0/20 est
192.168.96.1
La passerelle de l’ordinateur 192.168.96.225 pour sortir du ré-
seau 192.168.96.0/20 en passant par le routeur R1 est 192.168.96.1

1. Un paquet part de l’ordinateur 192.168.96.225 vers l’ordi-

nateur 192.168.0.10. En supposant que ce réseau utilise le
protocole RIP donner la succession des routeurs traversés
par ce paquet (argumenter)
2. Ajouter dans la table de routage de chaque routeur tra-
versé deux lignes (l’une pour l’aller du réseau 192.168.96.0
vers 192.168.0.0, et l’autre pour le retour ) sous la forme
suivante :
Table du routeur R.... :
Réseau destinataire | Passerelle | Interface
.................................|.....................|...............
3. Dans un terminal de l’ordinateur 192.168.96.225 on entre
la commande

18
 traceroute 192.168.0.10 et on observe alors

Expliquer le résultat obtenu

4. Pour tenir compte du débit des liaisons on décide d’utiliser
maintenant le protocole OSPF pour effectuer le routage
Le coût des liaisons entre les routeurs est donné par le
tableau suivant : :
Liaison R1-R2 R1-R3 R3-R5 R2-R3 R3-R4 R4-R5
Coût 10 100 ? 10 10 10
(a) Le coût d’une liaison est donné par la formule :
109
C=
BP
où BP est la bande passante de la connexion en bps (bit
par seconde)
Sachant que la bande passante de la liaison R3-R5 est
de 100 Mbps, calculer le coût correspondant
(b) Déterminer le chemin parcouru par un paquet partant
de la machine A pour aller vers la machine B en utilisant
le protocole OSPF (argumenter)
(c) Faut il modifier la table de routage du routeur R1 ? Si
oui le faire

19