Protocoles de Routage
Représentation d'un réseau
Internet est une interconnexion de réseaux locaux. Pour acheminer un paquet de données d'un point A à un point B, il doit traverser plusieurs routeurs. En informatique, on modélise cette structure par un graphe :
- Les sommets représentent les routeurs.
- Les arêtes représentent les liaisons physiques entre les routeurs.
Le routage est le processus qui consiste à choisir un chemin à travers ce graphe, permettant d'acheminer un paquet de données d'un routeur X à un routeur Y.
Tables de routage
Chaque routeur possède une table de routage. C'est un carnet d'adresses qui lui indique, pour chaque destination, quelle direction prendre.
Par exemple, pour le routeur A du graphe précédent :
| Table de routage du routeur A | |
|---|---|
| Destination | Routeur suivant |
| B | B |
| C | C |
| D | C |
| K | K |
| M | K |
| J | B |
| ... | ... |
En pratique, ces tables contiennent les informations suivantes :
Vocabulaire
Destination : L'adresse du réseau que l'on veut contacter.
Interface : La porte de sortie physique du routeur (ex: Ethernet0, wifi1, etc.) ou sa propre adresse IP à utiliser.
Passerelle (Gateway) : L'adresse IP du prochain routeur sur le chemin.
Dans un réseau simple, l'administrateur peut remplir les tables de routage à la main. C'est le routage statique.
| Table de routage du routeur 3 | ||
|---|---|---|
| Destination | Interface | Passerelle |
| 192.168.20.0/30 | 192.168.20.2 | - |
| 172.16.36.0/30 | 172.16.36.1 | - |
| 192.168.10.0/30 | 192.168.20.2 | 192.168.20.1 |
| 10.194.36.0/24 | 172.16.36.1 | 172.16.36.2 |
| 192.168.30.0/30 | 172.16.36.1 | 172.16.36.2 |
Routage dynamique : Le protocole RIP
Remplir les tables à la main est faisable pour un petit réseau, mais devient compliqué à grande échelle. Mais surtout, cette méthode n'est pas résiliente : si un câble est coupé ou qu'un routeur tombe en panne, le réseau ne sait pas s'adapter seul. C'est là qu'interviennent les protocoles de routage dynamique.
Le protocole RIP (Routing Information Protocol) est l'un d'entre eux. Pour déterminer le meilleur chemin à utiliser, il utilise une métrique qui est le nombre de sauts entre deux routeurs.
Fonctionnement : La "Rumeur"
Protocole RIP
RIP utilise l'algorithme de Bellman-Ford. Il ne possède pas la carte globale du réseau :
- Toutes les 30 secondes, chaque routeur envoie sa table de routage complète à ses voisins directs.
- En recevant les tables de ses voisins, un routeur met à jour la sienne s'il découvre un chemin plus court (moins de sauts).
Étape 1 : Les tables des routeurs R1, R4 et R5 ne contiennent que les réseaux auxquels ils sont physiquement reliés
| Table de routage R1 | |||
|---|---|---|---|
| Dest. | Inter. | Pass. | Coût |
| 192.168.10.0/30 | i1 | - | 0 |
| 192.168.20.0/30 | i2 | - | 0 |
| 192.168.30.0/30 | i3 | - | 0 |
| Table de routage R4 | |||
|---|---|---|---|
| Dest. | Inter. | Pass. | Coût |
| 192.168.30.0/30 | i1 | - | 0 |
| 172.16.36.0/30 | i2 | - | 0 |
| 10.194.36.0/24 | i3 | - | 0 |
| Table de routage R5 | |||
|---|---|---|---|
| Dest. | Inter. | Pass. | Coût |
| 10.194.36.0/24 | i1 | - | 0 |
Le protocole RIP a cependant des inconvénients :
D'abord, il ignore la qualité des liaisons : Il préférera un lien direct très lent à un chemin de deux sauts en fibre optique.
Ensuite, il fait une confiance aveugle à ses voisins et n'a pas de vision d'ensemble du réseau. Il est donc lent à s'adapter en cas de changement lointain. Pire, cela peut amener à créer des boucles infinies en cas de panne.
Pour éviter ce phénomène, RIP considère qu'un réseau à plus de 15 sauts est inaccessible, et n'est donc utilisable que dans des "petits" réseaux.
Le Protocole OSPF
Le protocole OSPF (Open Shortest Path First) permet de surmonter les inconvénients du protocole RIP.
Fonctionnement : La vision d'ensemble
Protocole OSPF
Chaque routeur connaît la topologie complète du réseau, et utilise l'algorithme de Dijkstra pour faire sa table de routage.
- Lorsqu'un changement survient, l'information est diffusée très rapidement à tout le monde.
- Le coût d'une liaison se calcule généralement avec la formule suivante : coût = 108/débit (en bits/s). Ainsi, plus la liaison est bonne, et plus le coût est faible.
- Chaque routeur utilise alors l'algorithme de Dijkstra pour calculer les chemins les plus courts vers toutes les destinations.
| Table de routage du routeur A | ||
|---|---|---|
| Destination | Passerelle | Coût |
| Réseau B | B | 1 |
| Réseau C | C | 0.01 |
| Réseau D | C | 1.03 |
| Réseau E | C | 0.03 |
| Réseau F | C | 0.02 |
Inconvénient : Ce protocole demande plus de mémoire et de puissance de calcul aux routeurs pour stocker le graphe et exécuter Dijkstra.
A retenir
- Un réseau est un maillage de routeurs qui relient des sous-réseaux entre eux.
- Un protocole de routage est une méthode permettant de déterminer un chemin pour amener les paquets d'un sous-réseau à un autre.
- Deux protocoles sont à retenir :
- Le protocole RIP qui utilise l'algorithme de Bellman-Ford, se focalise sur le nombre de sauts entre deux retours et n'a pas de vue d'ensemble du réseau,
- Le protocole OSPF dans lequel chaque routeur utilise l'algorithme de Dijkstra sur l'ensemble du graphe pour trouver le meilleur chemin, en prenant en compte la qualité des liaisons