Chapitre 9 - Partie 2 : Protocoles de routage

B.O. spécial n° 8 du 25 juillet 2019 - NSI Terminale

Contenus	Capacités attendues	Commentaires
Protocoles de routage.	Identifier, suivant le protocole de routage utilisé, la route empruntée par un paquet.	En mode débranché, les tables de routage étant données, on se réfère au nombre de sauts (protocole RIP) ou au coût des routes (protocole OSPF). Le lien avec les algorithmes de recherche de chemin sur un graphe est mis en évidence.

1. Rappels sur le routage

1.1 Le rôle des routeurs

En première, on a vu que les routeurs sont les équipements qui acheminent les paquets de données sur Internet. Chaque routeur possède une table de routage qui indique, pour chaque destination, vers quel routeur voisin transmettre le paquet.

1.2 Routage statique vs dynamique

Type	Description	Utilisation
Statique	Tables remplies manuellement par l'administrateur	Petits réseaux, configuration fixe
Dynamique	Tables mises à jour automatiquement par des protocoles	Internet, grands réseaux

Sur Internet (des centaines de milliers de routeurs), seul le routage dynamique est viable.

1.3 Systèmes autonomes (AS)

Internet est organisé en systèmes autonomes (Autonomous Systems, AS), chacun administré par une organisation (FAI, université, entreprise).

À l'intérieur d'un AS : protocoles de routage internes (IGP : Interior Gateway Protocol), comme RIP ou OSPF ;
Entre les AS : protocole de routage externe (EGP : Exterior Gateway Protocol), principalement BGP.

2. Le protocole RIP

2.1 Principe

RIP (Routing Information Protocol) est un protocole à vecteur de distance. Chaque routeur :

Connaît les réseaux directement connectés (distance = 1 saut) ;
Envoie périodiquement (toutes les 30 secondes) sa table de routage à ses voisins ;
Met à jour sa propre table en comparant les routes reçues avec celles qu'il connaît déjà.

La métrique est le nombre de sauts (nombre de routeurs à traverser pour atteindre la destination).

2.2 Règles de mise à jour

Quand un routeur A reçoit le vecteur de distance d'un voisin B :

Si la route vers un réseau n'existe pas dans la table de A → ajout (avec métrique = métrique de B + 1) ;
Si la route reçue est meilleure (moins de sauts) → mise à jour ;
Si la route reçue est moins bonne → elle est ignorée ;
Si une route n'est pas annoncée pendant 3 minutes → elle est supprimée (réseau considéré comme inaccessible).

2.3 Exemple détaillé

Considérons le réseau suivant :

    R1 ──── R2 ──── R3
    │               │
    R4 ──── R5 ──── R6

Table de routage de R1 (état initial) :

Destination	Prochain routeur	Nombre de sauts
R2	R2	1
R4	R4	1

Après échange avec R2 (qui connaît R3) :

Destination	Prochain routeur	Nombre de sauts
R2	R2	1
R3	R2	2
R4	R4	1

Après échange avec R4 (qui connaît R5) :

Destination	Prochain routeur	Nombre de sauts
R2	R2	1
R3	R2	2
R4	R4	1
R5	R4	2

Après plusieurs échanges, R1 connaît toutes les destinations et la route optimale (en nombre de sauts) pour chacune.

2.4 Avantages et limites de RIP

Avantages	Limites
Simple à mettre en œuvre	Métrique limitée à 15 sauts (16 = infini)
Supporté par tous les routeurs	Ne tient pas compte du débit des liens
Adapté aux petits réseaux	Convergence lente sur les grands réseaux

3. Le protocole OSPF

3.1 Principe

OSPF (Open Shortest Path First) est un protocole à état de lien. Contrairement à RIP, chaque routeur connaît la topologie complète du réseau et calcule lui-même la meilleure route.

Chaque routeur découvre ses voisins et mesure le coût de chaque lien ;
Il diffuse ces informations à tous les routeurs du réseau (inondation) ;
Chaque routeur construit une carte complète du réseau ;
Il calcule le plus court chemin vers chaque destination avec l'algorithme de Dijkstra.

3.2 La notion de coût

Le coût d'un lien dépend de son débit (bande passante). Plus le débit est élevé, plus le coût est faible.

$\text{coût} = \frac{\text{débit de référence}}{\text{débit du lien}}$

Avec un débit de référence de 10⁸ bit/s (100 Mbit/s) :

Type de lien	Débit	Coût
Ethernet 10 Mbit/s	10⁷ bit/s	10
Fast Ethernet 100 Mbit/s	10⁸ bit/s	1
Gigabit Ethernet 1 Gbit/s	10⁹ bit/s	0,1 → arrondi à 1
Liaison série 56 kbit/s	56 × 10³ bit/s	1 786

3.3 Exemple détaillé

Réseau avec des coûts sur les liens :

    R1 ──(1)── R2 ──(5)── R3
    │                      │
   (10)                   (1)
    │                      │
    R4 ──(1)── R5 ──(1)── R6

Pour aller de R1 à R6 :

Via R2 → R3 → R6 : coût = 1 + 5 + 1 = 7
Via R4 → R5 → R6 : coût = 10 + 1 + 1 = 12
Via R2 → R3 → R6 : coût = 7 (meilleure route)

Avec RIP, le chemin R4 → R5 → R6 serait choisi (3 sauts dans les deux cas, mais RIP ne voit pas les coûts). Avec OSPF, le chemin R2 → R3 → R6 est choisi car son coût total est inférieur.

3.4 Comparaison RIP vs OSPF

Critère	RIP	OSPF
Type	Vecteur de distance	État de lien
Métrique	Nombre de sauts	Coût (lié au débit)
Limite de taille	15 sauts max	Pas de limite
Connaissance du réseau	Voisins uniquement	Topologie complète
Convergence	Lente	Rapide
Prise en compte du débit	Non	Oui
Algorithme	Bellman-Ford distribué	Dijkstra
Complexité	Faible	Plus élevée

3.5 Lien avec les graphes

Le réseau peut être modélisé comme un graphe pondéré :

Sommets = routeurs ;
Arêtes = liens entre routeurs ;
Poids = coûts des liens (OSPF) ou nombre de sauts (RIP).

Le calcul du meilleur chemin est un problème classique de plus court chemin dans un graphe, résolu par l'algorithme de Dijkstra (OSPF) ou Bellman-Ford (RIP).

4. Exercice de routage pas à pas

4.1 Construction d'une table RIP

Réseau :

    A ──── B ──── C
    │             │
    D ──── E ──── F

État initial de A : A connaît ses voisins directs B et D.

Destination	Prochain	Sauts
B	B	1
D	D	1

B envoie son vecteur : B connaît A (1), C (1). → A ajoute C via B (2 sauts).

D envoie son vecteur : D connaît A (1), E (1). → A ajoute E via D (2 sauts).

Après convergence complète :

Destination	Prochain	Sauts
B	B	1
C	B	2
D	D	1
E	D	2
F	B	3 (via B → C → F) ou D

À retenir

Concept	Description
Table de routage	Table indiquant, pour chaque destination, le prochain routeur et le coût
RIP	Protocole à vecteur de distance, métrique = nombre de sauts (max 15)
OSPF	Protocole à état de lien, métrique = coût lié au débit
Convergence	Processus d'obtention de tables de routage optimales
Dijkstra	Algorithme de plus court chemin utilisé par OSPF
Système autonome	Ensemble de réseaux sous une même administration