Protocoles de routage

Rappels de première : réseaux et adressage

Adressage IP et masque de sous-réseau

Une adresse IPv4 est un identifiant numérique attribué à chaque interface réseau d’une machine. Elle est codée sur 32 bits et notée sous la forme de quatre octets séparés par des points, par exemple 192.168.1.42.

À chaque adresse IP est associé un masque de sous-réseau qui permet de distinguer la partie réseau (commune à toutes les machines du même réseau local) de la partie hôte (propre à chaque machine). Par exemple, avec le masque 255.255.255.0, les 24 premiers bits identifient le réseau. On utilise la notation CIDR : 192.168.1.0/24.

Adressage IP et masque de sous-réseau (suite)

Définition (adresse réseau) : l’adresse réseau s’obtient par un ET logique bit à bit entre l’adresse IP d’une machine et son masque de sous-réseau. Deux machines appartiennent au même réseau local si et seulement si elles partagent la même adresse réseau.

Exemple : soit la machine d’adresse 172.16.5.130/16. Le masque /16 correspond à 255.255.0.0. L’adresse réseau est donc 172.16.0.0/16. Toute machine dont l’adresse commence par 172.16.x.x (avec le même masque) appartient au même réseau local.

Le modèle TCP/IP et l’encapsulation

Le modèle TCP/IP organise les communications réseau en quatre couches :

1. couche accès réseau (liaison) : gère la transmission physique des données sur le support (Ethernet, Wi-Fi) et utilise les adresses MAC ;
2. couche internet : assure le routage des paquets entre réseaux grâce au protocole IP et aux adresses IP ;
3. couche transport : garantit (TCP) ou non (UDP) la fiabilité de la communication de bout en bout ;
4. couche application : regroupe les protocoles utilisés directement par les logiciels (HTTP, DNS, SMTP, etc.).

Le modèle TCP/IP et l’encapsulation (suite)

Définition (encapsulation) : lors de l’envoi de données, chaque couche ajoute un en-tête contenant les informations nécessaires à son fonctionnement. On parle d’encapsulation. À la réception, chaque couche retire l’en-tête qui lui correspond : c’est la désencapsulation.

Routeurs et switchs

Un switch (commutateur) relie les machines d’un même réseau local en utilisant les adresses MAC. Un routeur interconnecte plusieurs réseaux locaux en s’appuyant sur les adresses IP. Internet résulte de l’interconnexion de réseaux par des routeurs.

Un routeur possède plusieurs interfaces réseau, chacune connectée à un réseau différent. Chaque interface a sa propre adresse IP et sa propre adresse MAC.

Tables de routage

Principe

Lorsqu’un routeur reçoit un paquet, il consulte sa table de routage pour déterminer vers quelle interface (et éventuellement quel routeur voisin) transmettre le paquet afin qu’il se rapproche de sa destination.

Définition (table de routage) : une table de routage est un tableau associant à chaque réseau de destination connu les informations suivantes : l’adresse du réseau de destination, le moyen de l’atteindre (interface de sortie ou adresse du routeur suivant, appelé passerelle ou gateway), et une métrique mesurant le coût de la route.

Principe (suite)

Une table réelle comporte aussi une route par défaut, 0.0.0.0/0 (notée default), qui capte toute destination absente de la table, et une colonne interface de sortie ; la fiche « La table de routage » (bouton ci-dessus) détaille la lecture d’une telle table et la règle du préfixe le plus long.

Exemple

Considérons le réseau suivant avec deux routeurs A et G :

• le routeur A possède trois interfaces : eth0 (172.16.255.254/16), eth1 (192.168.7.1/24) et eth2 (172.17.255.254/16) ;
• le routeur G possède deux interfaces : eth0 (10.255.255.254/8) et eth1 (192.168.7.2/24).

Exemple (suite)

Table de routage simplifiée du routeur A :

Les réseaux directement connectés ont une métrique de 0. Le réseau 10.0.0.0/8 n’est pas directement relié au routeur A, mais celui-ci sait qu’il faut transmettre les paquets au routeur G pour l’atteindre (métrique de 1).

Exercice : table de routage du routeur G

En vous inspirant de la table de routage du routeur A ci-dessus, déterminez la table de routage du routeur G.

Routage statique et routage dynamique

Il existe deux manières de remplir une table de routage :

• le routage statique : l’administrateur configure manuellement chaque entrée. C’est simple mais inadapté aux grands réseaux et incapable de s’adapter aux pannes ;
• le routage dynamique : des protocoles permettent aux routeurs d’échanger automatiquement des informations et de mettre à jour leurs tables. C’est la méthode utilisée sur Internet.

Le protocole RIP

Principe

Le protocole RIP (Routing Information Protocol) est un protocole de routage à vecteur de distances. Sa métrique est le nombre de sauts (hops), c’est-à-dire le nombre de routeurs à traverser pour atteindre le réseau de destination.

Définition (vecteur de distance) : un vecteur de distance est un couple (destination, distance). Chaque routeur maintient un tableau de ces vecteurs constituant sa table de routage.

Fonctionnement

1. Initialisation : chaque routeur connaît uniquement les réseaux directement connectés à ses interfaces (distance 0).
2. Échange périodique : toutes les 30 secondes, chaque routeur envoie sa table de routage complète à ses voisins directs. Chaque route est surveillée par un temporisateur : si aucune annonce ne la confirme pendant 180 secondes (six échanges manqués), elle est déclarée invalide (distance 16) puis retirée de la table.

Fonctionnement (suite)

3. Mise à jour : à la réception d’une table voisine, un routeur applique les règles suivantes :
   • si un réseau inconnu apparaît, il l’ajoute à sa table (distance reçue + 1) ;
   • si un chemin plus court est découvert vers un réseau connu, il met à jour l’entrée ;
   • si un chemin plus long est reçu du même routeur voisin déjà enregistré, il met à jour (la topologie a changé) ;
   • sinon, il ignore l’information.
4. Convergence : après plusieurs cycles d’échanges, toutes les tables se stabilisent.

L’algorithme sous-jacent est l’algorithme de Bellman-Ford.

Limites de RIP

• La distance maximale est de 15 sauts (16 signifie « inaccessible »).
• L’envoi périodique des tables complètes génère un trafic réseau important.
• La convergence peut être lente sur de grands réseaux.
• RIP ne tient pas compte de la qualité des liaisons (débit, latence).

Remarque (routing by rumor) : avec RIP, chaque routeur ne connaît que ses voisins directs et construit sa vision du réseau de proche en proche, par « rumeur ». Il n’a jamais de vision globale du réseau.

Exemple détaillé

Considérons un réseau avec trois routeurs A, B et C reliés entre eux, avec chacun un réseau local propre. Les six réseaux en jeu sont : le réseau local de A, 172.18.0.0/16 ; celui de B, 172.16.0.0/16 ; celui de C, 172.17.0.0/16 ; la liaison A–B, 172.19.0.0/16 ; la liaison A–C, 172.20.0.0/16 ; la liaison B–C, 172.21.0.0/16.

Exemple détaillé (suite)

Table de routage du routeur A avec RIP (après convergence) :

Exercice : table de routage RIP

Soit le réseau décrit ci-dessus (trois routeurs A, B et C tous interconnectés).

1. Déterminez la table de routage du routeur B avec le protocole RIP.
2. Quel chemin est emprunté par un paquet allant de 172.18.1.1 vers 172.16.5.3 ?
3. Si la liaison directe entre A et B tombe en panne, quel nouveau chemin serait emprunté ?

Le protocole OSPF

Principe

Le protocole OSPF (Open Shortest Path First) est un protocole de routage à état de liens. Contrairement à RIP, chaque routeur possède une vision globale du réseau et calcule les chemins optimaux en tenant compte du débit des liaisons.

Définition (coût d’une liaison OSPF) : le coût d’une liaison est défini par la formule :

\[\text{coût} = \frac{10^8}{\text{débit en bit/s}}\]

Plus le débit est élevé, plus le coût est faible. Le coût total d’une route est la somme des coûts de chaque liaison traversée.

Principe (suite)

Exemple de calcul de coûts :

Fonctionnement

1. Découverte des voisins : chaque routeur envoie des messages hello à ses voisins pour identifier les routeurs adjacents et le débit de chaque liaison. Ces messages sont envoyés toutes les 10 secondes ; un voisin silencieux pendant 40 secondes est déclaré injoignable et les routes sont recalculées.

Fonctionnement (suite)

2. Diffusion de l’état des liens : chaque routeur envoie sa table de voisinage à tous les routeurs du réseau (pas seulement aux voisins). Ainsi, chaque routeur dispose d’une carte complète du réseau.
3. Calcul des routes : chaque routeur applique l’algorithme de Dijkstra sur le graphe pondéré du réseau pour déterminer les chemins de coût minimal vers chaque destination.

Fonctionnement (suite)

Comparaison avec RIP : OSPF se distingue de RIP sur trois points fondamentaux : chaque routeur possède une vision globale du réseau (et non locale) ; la métrique est le coût basé sur le débit (et non le nombre de sauts) ; les mises à jour ne sont envoyées que lorsqu’un changement intervient (et non périodiquement toutes les 30 secondes).

Exemple détaillé

Reprenons le réseau à trois routeurs A, B et C avec les débits suivants : A–B à 1 Mbit/s, A–C à 10 Mbit/s, B–C à 10 Mbit/s.

Calcul des coûts :

Exemple détaillé (suite)

Pour aller de A à B :

• chemin direct A → B : coût de 100 ;
• chemin A → C → B : coût de \(10 + 10\), soit 20.

OSPF choisit le chemin A → C → B (coût 20), bien qu’il comporte un saut supplémentaire. RIP aurait choisi le chemin direct A → B (1 seul saut) alors que son coût est cinq fois plus élevé (100 contre 20).

Exercice : comparaison RIP et OSPF

Soit le réseau ci-dessus avec les débits indiqués.

1. Déterminez la table de routage du routeur A avec le protocole RIP.
2. Déterminez la table de routage du routeur A avec le protocole OSPF.
3. Quel chemin choisit chaque protocole pour acheminer un paquet du réseau de A vers le réseau de B ? Justifiez.
4. Dans quelle situation RIP pourrait-il donner un meilleur résultat qu’OSPF ?

L'essentiel à retenir

• Une table de routage associe à chaque réseau de destination une passerelle et une métrique ; elle peut être remplie manuellement (routage statique) ou automatiquement (routage dynamique).
• Le protocole RIP utilise le nombre de sauts comme métrique et l’algorithme de Bellman-Ford ; chaque routeur n’a qu’une vision locale et la limite est de 15 sauts.

L'essentiel à retenir (suite)

• Le protocole OSPF utilise un coût inversement proportionnel au débit et l’algorithme de Dijkstra ; chaque routeur possède une vision globale du réseau modélisé comme un graphe pondéré .
• En pratique, OSPF est préféré pour les réseaux de taille moyenne à grande car il tient compte de la qualité des liaisons et converge plus rapidement.

Synthèse : RIP vs OSPF

Exercice de synthèse

1. Expliquez pourquoi le protocole RIP n’est pas adapté aux grands réseaux comme Internet.
2. Un réseau utilise des liaisons exclusivement à 100 Mbit/s. Les deux protocoles donneraient-ils les mêmes routes ? Justifiez.
3. Expliquez en quoi la modélisation d’un réseau par un graphe pondéré est pertinente pour le protocole OSPF.

Vérifiez votre compréhension

1. Avec le protocole RIP, un routeur connaît-il la topologie complète du réseau ? Et avec OSPF ?
   Réponse

   Non, avec RIP, chaque routeur n'a qu'une vision locale : il ne connaît que ses voisins directs et les distances transmises de proche en proche (routing by rumor). Avec OSPF, chaque routeur possède une vision globale du réseau grâce à la diffusion de l'état de tous les liens, ce qui lui permet de calculer les routes optimales.
2. Deux routeurs A et B sont reliés par une liaison à 1 Mbit/s. Il existe aussi un chemin A → C → B où chaque liaison est à 100 Mbit/s. Quel chemin choisit RIP ? Et OSPF ?
   Réponse

   RIP choisit le chemin direct A → B (1 saut contre 2). OSPF choisit A → C → B car son coût est 1 + 1 = 2, bien inférieur au coût du chemin direct qui est 100 (10⁸/10⁶). OSPF tient compte du débit, pas RIP.
3. Quel algorithme classique sur les graphes est utilisé par OSPF pour calculer les routes optimales ?
   Réponse

   L'algorithme de Dijkstra, qui calcule les plus courts chemins dans un graphe pondéré à poids positifs. Chaque routeur l'applique sur le graphe complet du réseau pour déterminer le chemin de coût minimal vers chaque destination.