Protocoles de routage
Un réseau de réseaux comportant des routeurs peut être modélisé par un graphe : chaque routeur est un sommet et chaque liaison entre les routeurs ou entre un routeur et un switch est une arête. Les algorithmes utilisés par les protocoles de routages sont donc issus de la théorie de graphes.
Protocole RIP
Le protocole RIP (Routing Information Protocol) est un des premiers algorithmes utilisés pour établir les tables de routage des routeurs interconnectant des réseaux.
Il comporte les 3 règles suivantes :
1 Initialement (à la mise sous tension), la table de routage d’un routeur contient uniquement des informations sur ses voisins directs (ceux auxquels il est connecté).
Exemple :
Initialement (mise sous tension) la table de routage de R1 contient uniquement les réseaux 192.168.1.0 /24 et 10.1.1.0 /30.
| Table de routage de R1 |
|||
| Réseau destination | Passerelle | Interface | Métrique |
| 192.168.1.0 /24 | wlan0 | 1 | |
| 10.1.1.0 /30 | eth1 | 1 | |
Aucune passerelle n’est spécifiée car le routeur peut atteindre le réseau destination directement.
2 Chaque routeur envoie périodiquement (toutes les 30 secondes), à tous ses voisins (routeurs adjacents), un message contenant :
- la liste de toutes les adresses de réseaux qu’il connaît (ses voisins directs et ceux qu’il a reçu auparavant)
- leur métrique (le nombre de sauts pour les atteindre)
Ce couple d’informations (réseau, métrique) est appelé vecteur de distance.
3 À chaque réception d’un message de ce type, un routeur met à jour sa table de routage avec les informations reçues. Quatre cas peuvent se présenter :
- il découvre une nouvelle route vers un sous réseau qu’il ne connaissait pas encore
il l’ajoute à sa table - il découvre une nouvelle route plus courte vers un sous réseau qu’il connaissait déjà
il remplace l’ancienne route par la nouvelle - il reçoit une nouvelle route plus longue vers un sous réseau qu’il connaissait déjà
il ne fait rien - il reçoit une route existante dans sa table (passant par le même voisin), mais plus longue. Cela signifie que la route s’est allongée (panne ?).
il met sa table à jour
Pour renseigner la colonne « métrique », le protocole utilise le nombre de sauts, autrement dit, le nombre de routeurs qui doivent être traversés pour atteindre le réseau cible.
Exemple : le routeur R1 reçoit des messages de la part de son seul voisin R3. Ce message contient les vecteurs de distance suivants :
-
- (10.1.2.0 /30 , 1)
- (10.1.3.0 /30 , 1)
- (10.1.4.0 /30 , 1)
- et tous les vecteurs de distance concernant les autres réseaux qu’il « connait ».
Du point de vue de R1, R3 (d’adresse 10.1.1.2 /30) est une passerelle.
Sa table de routage devient alors :
| Table de routage de R1 |
|||
| Réseau destination | Passerelle | Interface | Métrique |
| 192.168.1.0 /24 | wlan0 | 1 | |
| 10.1.1.0 /30 | eth1 | 1 | |
| 10.1.2.0 /30 | 10.1.1.2 /30 | eth1 |
2 |
| 10.1.3.0 /30 | 10.1.1.2 /30 | eth1 |
2 |
| 10.1.4.0 /30 | 10.1.1.2 /30 | eth1 | 2 |
Le protocole RIP s’appuie sur l’algorithme de Bellman-Ford (algorithme qui permet de calculer les plus courts chemins dans un graphe).
L'activité suivante propose de réaliser un réseau constitué de tous les élèves de la classe.
Il est très important pour la réussite de cet exercice que chacun garde le silence et ne communique pas oralement, ni avec ses "réseaux voisins", ni avec quiconque !
Chaque élève joue le rôle d'un routeur et se voit attribuer un identifiant (une lettre), ainsi qu'une table de routage et des fiche de message (
PDF à télécharger)
Initialisation :
Le professeur désigne à chaque élève 2 à 3 "routeurs" voisins (physiquement proches).
Chaque élève initialise sa table de routage en y inscrivant ses voisins.
Exemple pour le routeur C :
Élaboration des messages :
À intervalle de temps régulier (au signal donné par le professeur), chaque élève prépare un message RIP contenant :
- la liste de toutes les identifiants réseaux qu'il connaît (ses voisins directs et ceux qu'il a reçu auparavant)
- leur métrique (le nombre de sauts pour les atteindre)
et le fait passer tour à tour à chacun de ses voisins.
Exemple pour le routeur C, au 1er tour :
Quand le voisin a terminé de mettre à jour sa table, il raye son nom sur le message et le rend au routeur d'origine.... qui le fait passer au prochain voisin.
Mise à jour des tables :
À la réception d'un message, chaque élève met à jour sa table de routage, selon les cas de figure suivants :
- il découvre une nouvelle route vers un sous réseau qu'il ne connaissait pas encore
il l'ajoute à sa table - il découvre une nouvelle route plus courte vers un sous réseau qu'il connaissait déjà
il remplace l'ancienne route par la nouvelle - il reçoit une nouvelle route plus longue vers un sous réseau qu'il connaissait déjà
il ne fait rien - il reçoit une route existante dans sa table (passant par le même voisin), mais plus longue. Cela signifie que la route s'est allongée (panne ?).
il met sa table à jour
Exemple pour le routeur B, après le premier message de la part de C :
Soit le réseau suivant :
La liaison entre les routeurs B et C devient défaillante.
Délai de convergence
On appelle délai de convergence le temps nécessaire à ce que l’ensemble des routeurs soient configurés pour offrir les meilleurs routes possible. À chaque modification du réseau (ajout ou suppression de routeurs), il faut un certain temps pour que les échanges de messages RIP mènent à une situation stable.
C’est pour limiter ce délai de convergence que le protocole RIP est limité à 15 sauts.
Détection des pannes
Lorsqu’un routeur ne reçoit pas de réponse de la part d’un autre routeur à une demande RIP (après un certain laps de temps, 3 minutes), il considère que le routeur en question est en panne.
Afin qu’aucun paquet ne soit plus dirigé dans cette direction, il prévient ses voisins en leur envoyant une métrique égale à 16 (plus grande valeur possible pour le protocole RIP) concernant toutes les routes passant par le routeur qui ne répond pas.
Boucle de routage
Une boucle de routage est le phénomène qui se produit lorsqu’un paquet tourne en boucle et ne peut jamais atteindre sa destination.
Différentes règles dans le protocole RIP permettent d’éviter que cela se produise, et notamment la règle split horizon, qui interdit à un routeur d’envoyer une information de routage via le routeur qui lui a envoyé.
Le protocole RIP est aujourd’hui très rarement utilisé dans les grandes infrastructures car il génère, du fait de l’envoi périodique de messages, un trafic réseau important (surtout si les tables de routages contiennent beaucoup d’entrées). De plus, le protocole RIP est limité à 15 sauts (on traverse au maximum 15 routeurs pour atteindre sa destination). On lui préfère donc souvent le protocole OSPF.
Le protocole OSPF
Dans le protocole OSPF (Open Shortest Path First), comme dans le cas du protocole RIP, les routeurs échangent entre eux des informations, mais ces échanges sont plus « intelligents » dans le cas d’OSPF, permettant ainsi de réduire l’occupation du réseau.
- Tous les routeurs ont une vision globale et identique du réseau : pour cela, ils reçoivent des informations depuis tout le réseau
- Les distances prennent en compte le nombre de routeur à traverser (nombre de sauts), mais également le débit binaire de chaque « câble » (appelé aussi bande passante), exprimé en bits/s.
Le protocole OSPF permet à chaque routeur de connaître le graphe complet des liaisons entre tous les routeurs du réseau, avec leur débits.
Ainsi, le « meilleur » chemin n’est pas forcément le plus court, mais le plus rapide.
Exemple : sur le réseau ci-dessous, considérons un paquet qui doit être transmis de F à C
-
- le protocole RIP choisirait la route comportant le moins de sauts possible, soit F→H→C
- le protocole OSPF en revanche choisira la route F→E→D→C,
La valeur de métrique retenue par le protocole OSPF n’est en réalité pas le débit, mais le coût, un nombre entier obtenu par la formule suivante :
\(\Large{\text{coût}=\frac{\textrm{débit maximal de référence}}{\textrm{bande passante [bits/s]}}}\)
ATTENTION : le coût est un nombre entier compris entre 1 et 65535 : il ne peut pas être nul. On arrondira à 1 tous les résultats inférieurs à 1.
En pratique, le débit maximal de référence vaut souvent \(10^8\) bits/s.
Ainsi, le coût d’une route est l’addition des coûts des liaisons pour arriver à la destination.
Remarque : ainsi, comme pour le protocole RIP, plus la métrique est petite, meilleure est la route.
Exemple : avec un débit maximal de référence de \(10^8\) bits/s
coût de la route de F à C = 2 + 1 + 1 = 4
Sources :
https://pixees.fr/informatiquelycee/n_site/nsi_term_archi_routage.html
https://www.editions-ellipses.fr/acc ueil/10445-20818-specialite-numerique-et-sciences-informatiques-lecons-avec-exercices-corriges-terminale-nouveaux-programmes-9782340038554.html#/1-format_disponible-broche
