C13.4 : Protocoles RIP et OSPF

Généralités

Lorsqu'on souhaite relier plusieurs réseaux locaux entre eux, il faut utiliser des routeurs. Un routeur peut être vu comme une machine constituée de plusieurs cartes réseaux.

Chaque routeur doit disposer des informations qui lui permettent de transmettre les données pour les faire progresser jusqu'à leur destination.

Ainsi, lorsqu'il reçoit un paquet, un routeur récupère l'adresse IP de destination et, en fonction de cette adresse, envoie le paquet au routeur voisin le plus approprié.

Les routeurs se basent sur leurs tables de routage pour choisir le routeur voisin de plus approprié.

C'est en échangeant régulièrement des informations entre eux que les routeurs construisent et mettent à jour leur table de routage. Ces échanges sont gérés automatiquement par les algorithmes des protocoles de routage.

Protocole RIP

Présentation

Dans le protocole RIP (Routing Information Protocole), le choix du routeur voisin le plus approprié est basé sur la distance, c'est-à-dire sur le nombre de routeurs qu'il faut traverser pour atteindre la destination.

Tables de routage

La table de routage se présente sensiblement ainsi :

Destination	Passerelle	Interface	Distance

Pour chaque ligne :

- la destination est l'adresse IP de la machine à qui les données sont destinées (ou un ensemble d'adresses IP),
- la passerelle est l'adresse IP du routeur voisin à qui envoyer les données,
- l'interface est la référence au port du routeur qui doit être utilisé,
- la distance est le nombre de routeurs à traverser pour atteindre la destination.

Construction et mise à jour des tables de routage

A intervalles de temps régulier, chaque routeur transmet à ses voisins les informations dont il dispose.

Lorsqu'un routeur reçoit les informations d'un autre routeur, il incrémente les distances de 1 et traite les informations de la façon suivante :

• s'il reçoit la référence à un ensemble d'adresses qui lui étaient inconnues, il ajoute une ligne à sa table ;
• s'il reçoit la référence à un ensemble d'adresses connues, mais avec une distance plus courte, il met la ligne correspondante à jour ;
• s'il reçoit la référence à un ensemble d'adresses connues, mais avec une distance plus grande :

- si c'est en provenance d'un routeur différent de celui de sa table, il l'ignore,
- si c'est en provenance d'un routeur identique à celui de sa table, cela signifie qu'il y a eu un problème sur le réseau, il met à jour la distance de la ligne correspondante ;

----

Voici quelques remarques supplémentaires sur le protocole RIP :

- Les distances sont limitées à 15, entres autres pour éviter les boucles mais également pour que le temps au bout duquel tous les routeurs sont opérationnels (temps de convergence) ne soit pas trop long.
- Lorsqu'un routeur n'a pas de réponse d'un de ses voisins, il envoie l'information à tous ses autres voisins avec une distance infinie.

Applications

Application n° 1

Considérons le réseau ci-dessous où tous les masques ont pour valeur 255.255.255.0.

1) Indiquer la passerelle des machines du LAN 192.168.1.0.

2) En ne considérant comme destinations que les deux LAN, donner les tables de routage des routeurs \(R_A\), \(R_B\) \(R_C\) et \(R_D\).

Afficher la correction

La passerelle des machines du LAN 192.168.1.0 est : 192.168.1.254.

Table de routage du routeur R_A
Destination	Routeur suivant	Distance
192.168.1.0	-	0
192.168.6.0	R_B	2

Table de routage du routeur R_B
Destination	Routeur suivant	Distance
192.168.1.0	R_B	1
192.168.6.0	R_D	1

Table de routage du routeur R_C
Destination	Routeur suivant	Distance
192.168.1.0	R_B	2
192.168.6.0	R_D	1

Table de routage du routeur R_D
Destination	Routeur suivant	Distance
192.168.1.0	R_B	2
192.168.6.0	-	0

Application n° 2

On s'intéresse à un réseau composé de sept routeurs \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) et \(G\). Le réseau est programmé à l'aide du protocole RIP.

On donne les tables de routage suivantes :

Table de routage du routeur \(A\)
Destination	Routeur suivant	Distance
B	B	1
C	C	1
D	D	1
E	C	2
F	C	2
G	C	3

Table de routage du routeur \(B\)
Destination	Routeur suivant	Distance
A	A	1
C	A	2
D	D	1
E	D	2
F	A	3
G	D	3

Table de routage du routeur \(C\)
Destination	Routeur suivant	Distance
A	A	1
B	A	2
D	E	2
E	E	1
F	F	1
G	F	2

Table de routage du routeur \(D\)
Destination	Routeur suivant	Distance
A	A	1
B	B	1
C	E	2
E	E	1
F	A	3
G	E	2

Table de routage du routeur \(E\)
Destination	Routeur suivant	Distance
A	C	2
B	D	2
C	C	1
D	D	1
F	G	2
G	G	1

Table de routage du routeur \(F\)
Destination	Routeur suivant	Distance
A	C	2
B	C	3
C	C	1
D	C	3
E	G	2
G	G	1

1) Déterminer le trajet parcouru par un paquet pour aller du routeur \(A\) au routeur \(G\).

2) Déterminer une table de routage possible pour le routeur \(G\).

3) Proposer une représentation du réseau.

Afficher la correction

Les trajet parcouru par le paquet se détermine de proche en proche avec les tables de routage.

Ce trajet est : A -> C -> F -> G

On peut raisonner en regardant les ligne du routeur G dans les autres tables de routage.

Table de routage du routeur \(F\)
Destination	Routeur suivant	Distance
A	C	3
B	C	3
C	E	2
D	E	2
E	E	1
F	F	1

Protocole OSPF

Débit d'une liaison

Le débit est une mesure de la quantité de données numériques transmises par unité de temps. Il s'exprime en général en \(\pu{bit/s}\) ou éventuellement en \(\pu{o/s}\).

Quelques valeurs :

• Par cable :

I2C 3.0 : \(\pu{3,4 Mbit/s}\)
USB 1.1 : \(\pu{12 Mbit/s}\)
USB 2.0 : \(\pu{480 Mbit/s}\)
USB 3.0 : \(\pu{5 Gbit/s}\)

• Sans fil :

Wi-Fi : \(\pu{11 Mbit/s}\) à \(\pu{1,3 Gbit/s}\) (802.11ac)
5G : \(\pu{1 Gbit/s}\)

• Réseaux :

Fast Ethernet : \(\pu{100 Mbit/s}\)

CPL : \(\pu{14}\) / \(\pu{85}\) / \(\pu{200}\) / \(\pu{500}\) / \(\pu{1000 Mbit/s}\)

Présentation du protocole OSPF

Dans le protocole OSPF (Open Shortest Path First), le choix du routeur voisin le plus approprié prend en compte les bandes passantes (débits) de l'ensemble des liaisons du réseau.

Ainsi, à chaque liaison entre routeurs est attribué un coût \(C\) définit par une relation du type : \(C = \dfrac{D_{ref}}{D}\) où \(D_{ref}\) est le débit de référence et \(D\) est le débit de la liaison, en \(\pu{bits/s}\).

Remarque : en général, on prend \(D_{réf} = \pu{10^8 bits/s}\), mais d'autres valeurs sont possibles.

Le coût d'une succession de liaisons est la somme des coûts des différentes liaisons.

Table de routage

La table de routage se présente sensiblement ainsi :

Destination	Passerelle	Interface	Coût

Pour chaque ligne :

- la destination est l'adresse IP de la machine à qui les données sont destinées (ou un ensemble d'adresses IP),
- la passerelle est l'adresse IP du routeur voisin à qui envoyer les données,
- l'interface est la référence au port du routeur qui doit être utilisé,
- le coût déterminé à partir de la connaissance des débits des différentes liaisions.

Applications

Application n° 1

Voici quelques débits théoriques.

Technologie	Bande passante	Coût
Bluetooth	\(\pu{4 Mbit/s}\)
Ethernet		\(10\)
Wifi	\(\pu{10 Gbit/s}\)
4G	\(\pu{100 Mbit/s}\)
FastEthernet		\(1\)

Question : Compléter le tableau en utilisant la relation \(C = \dfrac{10^8}{D}\) où \(C\) est le coût et \(D\) le débit en \(\pu{bit/s}\).

Afficher la correction

Pour calculer le coût : \(C = \dfrac{10^8}{D}\)

Pour calculer le débit : \(D = \dfrac{10^8}{C}\).

Technologie	Bande passante	Coût
Bluetooth	\(4 pu{Mbit/s}\)	\(\dfrac{10^8}{\pu{4E6 bit/s}} = \pu{25}\)
Ethernet	\(\dfrac{10^8}{10} = \pu{1E7 bit/s} = \pu{10 Mbits/s}\)	10
Wifi	10 Gbit/s	\(\dfrac{10^8}{\pu{10E9 bit/s}} = \pu{0,01}\)
4G	100 Mbit/s	\(\dfrac{10^8}{\pu{100E6 bit/s}} = \pu{1}\)
FastEthernet	\(\dfrac{10^8}{1} = \pu{1E8 bit/s} = \pu{100 Mbits/s}\)	1

Application n° 2

On considère le réseau schématisé ci-dessous, où \(A\), \(B\) et \(C\) sont trois routeurs.

Le coût a été programmé avec la relation \(C = \dfrac{10^8}{D}\) où \(C\) est le coût et \(D\) le débit en \(\pu{bit/s}\).

Question : Déterminer, en justifiant, la route empruntée par les paquets pour aller de A à B selon le protocole OSPF.

Afficher la correction

Calcul du coût des différentes liaisons :

Liaison A - B : \(C_{A-B} = \dfrac{10^8}{\pu{1E3 b/s}} = \pu{10^5}\)
Liaison A - C : \(C_{A-C} = \dfrac{10^8}{\pu{10E6 b/s}} = \pu{10}\)
Liaison B - C : \(C_{B-C} = \dfrac{10^8}{\pu{10E6 b/s}} = \pu{10}\)

Calcul du coût de tous les chemins pour aller de A à B :

Chemin A -> B : coût = \(10^5\)
Chemin A -> C -> B : coût = 10 + 10 = 20

Conclusion : le meilleur chemin est A -> C -> B

Application n° 3

On considère le réseau représenté ci-dessous où chaque rond est un routeur, chaque trait une liaison et chaque nombre le coût de la liaison.

Les coûts \(C\) ont été calculés avec la relation \(C = \dfrac{10^8}{D}\) où D est le débit en \(\pu{bits/s}\).

1) Le débit de la connexion entre C et D est de \(\pu{20 Mbit/s}\). Calculer le coût de cette connexion.

2) Par quelle route les routeurs vont-il acheminer les données de G à E ?

3) Donner la table de routage complète du routeur B.

Destination	Passerelle	Coût

4) Un nouveau routeur :

On connecte un nouveau réseau au réseau précédent par l'intermédiaire d'un routeur R.

On donne la table de routage du routeur R :

Destination	Passerelle	Coût
C	D	8
D	D	3
...	...	...
I	I	2
J	J	2
K	I	6
L	J	3
M	J	7

4.1) Représenter une topologie possible du réseau mystère avec les réseaux I, J, K, L et M ainsi que les coûts des liaisons.

4.2) Donner la nouvelle table de routage complète du routeur B.

Afficher la correction

\(C = \dfrac{10^8}{\pu{20E6 bit/s}} = 50\)

Il existe 3 chemins pour aller de G à E.

Calculons le coût de chacun de ces chemins :

Chemin G-H-E : coût = 5 + 4 = 9
Chemin G-B-A-F-E : coût = 1 + 3 + 2 + 1 = 7
Chemin G-B-C-D-E : coût = 1 + 2 + 50 + 3 = 56

Table du routeur B
Destination	Passerelle	Coût
A	A	3
C	C	2
D	A	9
E	A	6
F	A	5
G	G	1
H	G	6

4.1)

4.1)

Table du routeur B
Destination	Passerelle	Coût
A	A	3
...	...	...
I	A	14
J	A	14
K	A	18
L	A	15
M	A	19