Les protocoles de routage
En réseau, les protocoles de routage assurent l'acheminement des paquets entre les différents routeurs. En NSI, nous en étudions 2 spécifiques :
- Le protocole RIP ;
- Le protocole OSPF.
Avant d'étudier les protocoles, il est important de schématiser des réseaux de façon simple, à l'aide de graphes.
- Graphe
- Sommet
- Arête
Dessin, schéma, représentant un ensemble de sommets, reliés entre eux par un ensemble d’arêtes, modélisant des situations.
Représenté par un cercle avec une valeur dedans, il représente un élément d'une situation que l’on souhaite modéliser.
Ici, un sommet représente un routeur (on ne compte pas les ordinateurs).
Liaison entre 2 sommets, schématise le lien qu'il peut y avoir entre des sommets, dans la situation à modéliser.
Ici, une arête entre 2 sommets représente la connexion entre 2 routeurs.
Prenons le réseau suivant :
Pour le transformer en graphe, on va dans un premier temps mettre en avant les routeurs présents :
Puis, on peut dessiner des sommets, dans lesquels on marque le numéro/nom du routeur, en les reliant comme le proposait le montage initial :
Les graphes (petit spoiler) utilisent différents algorithmes permettant d'effectuer des recherches de chemins (le chemin le plus court, le chemin le moins coûteux, ...).
De ce fait, acheminer des données dans un réseau revient à chercher des chemins entre des routeurs, qui soient le plus court, voire le moins coûteux, et donc la modélisation sous la forme d'un graphe simplifie le travail.
Le protocole RIP
Le protocole RIP (Routing Information Protocol) reprend l'algorithme de Bellman-Ford, et consiste à chercher le chemin le plus court en déterminant le nombre de sauts à effectuer entre un routeur de départ et un routeur d'arrivé.
On souhaite aller du routeur 1 au routeur 4. Il existe 2 chemins possibles :
- 1 - 2 - 4 : on effectue 2 sauts ;
- 1 - 3 - 2 - 4 : on effectue 3 sauts.
Le protocole RIP va prendre le chemin où l'on effectue le moins de sauts.
En réseau, chaque routeur va donc avoir une table de sauts, associant pour chaque routeur :
- Un routeur de destination ;
- Le routeur par lequel il faudra passer pour arriver à celui de destination ;
- Le nombre de sauts nécessaires pour aller au routeur de destination.
Pour l'exemple donné, on aurait :
- Routeur 1
- Routeur 2
- Routeur 3
- Routeur 4
| Destination | Routeur suivant | Saut |
|---|---|---|
| Routeur 2 | Routeur 2 | 1 |
| Routeur 3 | Routeur 3 | 1 |
| Routeur 4 | Routeur 2 | 2 |
| Destination | Routeur suivant | Saut |
|---|---|---|
| Routeur 1 | Routeur 1 | 1 |
| Routeur 3 | Routeur 3 | 1 |
| Routeur 4 | Routeur 4 | 1 |
| Destination | Routeur suivant | Saut |
|---|---|---|
| Routeur 1 | Routeur 1 | 1 |
| Routeur 2 | Routeur 2 | 1 |
| Routeur 4 | Routeur 2 | 2 |
| Destination | Routeur suivant | Saut |
|---|---|---|
| Routeur 1 | Routeur 2 | 2 |
| Routeur 2 | Routeur 2 | 1 |
| Routeur 3 | Routeur 2 | 2 |
Pour éviter que les paquets ne tournent en boucle sur le réseau et le surchargent, le nombre maximal de sauts possibles est de 15.
Une fois les 15 sauts atteints, les paquets sont détruits.
À partir du graphe suivant :
Écrire les tables de saut pour chaque routeur.
Le protocole OSPF
Le protocole OSPF (Open Shortest Path First) reprend l'algorithme de Dijkstra, et consiste à chercher le chemin le moins coûteux, c'est-à-dire celui dont la somme des arêtes entre le routeur de départ et celui d'arrivé est la plus faible.
Les graphes sont valués, leurs arêtes possèdent un poids représenté ici par le débit de transfert entre un routeur A et un routeur B.
Concrètement, une valeur sera associée à chaque arête, correspondant à la vitesse de transfert entre 2 routeurs.
On souhaite aller du routeur 1 au routeur 4. Il existe 2 chemins possibles :
- 1 - 2 - 4 : la somme des arêtes de ce chemin est de 5 ;
- 1 - 3 - 2 - 4 : la somme des arêtes de ce chemin est de 4.
Le protocole OSPF va prendre le chemin où l'on prend le moins de temps de transfert possibles.
L’algorithme de Dijkstra permet de déterminer le chemin le moins coûteux entre un sommet de départ et un sommet d’arrivée.
Pour cela, on utilise un tableau de coûts :
- chaque colonne correspond à un sommet ;
- chaque valeur représente le coût minimal connu pour atteindre ce sommet depuis le sommet de départ.
Initialisation
- on met le coût du sommet de départ à 0 ;
- on met le coût de tous les autres sommets à ∞ ;
- le sommet de départ est le sommet courant.
Étape répétée (itération)
À chaque itération, on effectue toujours les mêmes actions :
-
Mettre à jour les sommets voisins du sommet courant
Pour chaque voisin :- on calcule
nouveau coût = coût du sommet courant + poids de l’arête - si ce nouveau coût est plus petit que le coût actuel du voisin, alors on remplace la valeur ;
- sinon, on conserve la valeur existante.
- on calcule
-
Marquer le sommet courant comme traité
Une fois traité, on ne reviendra plus sur ce sommet.
-
Choisir le prochain sommet courant
On choisit, parmi les sommets non traités, celui qui possède le plus petit coût.
Arrêt de l’algorithme
L’algorithme s’arrête lorsque le sommet d’arrivée est choisi comme sommet courant (ou lorsque tous les sommets ont été traités).
Pour l'exemple donné, on souhaiterait aller du routeur 1 au routeur 4 :
- Initialisation
- Ité. 1
- Ité. 2
- Ité. 3
| Itération | Routeur 1 | Routeur 2 | Routeur 3 | Routeur 4 | Routeur choisi |
|---|---|---|---|---|---|
| Init | 0 | ∞ | ∞ | ∞ | 1 |
À l'initialisation, on met la valeur 0 au routeur 1, et ∞ aux autres sommets.
| Itération | Routeur 1 | Routeur 2 | Routeur 3 | Routeur 4 | Routeur choisi |
|---|---|---|---|---|---|
| Init | 0 | ∞ | ∞ | ∞ | 1 |
| 1 | | 3 | 1 | ∞ | 3 |
On démarre depuis le routeur 1.
- On calcule le coût pour aller aux routeurs voisins du routeur choisi (1) en prenant la valeur du routeur 1 + la valeur de l'arête.
- Les coûts calculés sont plus petits que ceux existants (∞), on remplace la valeur.
- On marque le routeur 1 comme traité (on peut mettre du noir dans les cases).
- On choisit le routeur 3 comme nouveau sommet courant car il a le plus petit coût.
| Itération | Routeur 1 | Routeur 2 | Routeur 3 | Routeur 4 | Routeur choisi |
|---|---|---|---|---|---|
| Init | 0 | ∞ | ∞ | ∞ | 1 |
| 1 | | 3 | 1 | ∞ | 3 |
| 2 | | 2 | | ∞ | 2 |
On démarre depuis le routeur 3.
- On ne peut aller qu'au routeur 2. On calcule le coût pour y aller depuis le routeur 3 en prenant la valeur du routeur 3 + la valeur de l'arête.
- Le coût obtenu est plus petit que celui existant pour aller au routeur 2, on remplace la valeur.
- On marque le routeur 3 comme traité.
- On choisit le routeur 2 comme nouveau sommet courant car il a le plus petit coût.
| Itération | Routeur 1 | Routeur 2 | Routeur 3 | Routeur 4 | Routeur choisi |
|---|---|---|---|---|---|
| Init | 0 | ∞ | ∞ | ∞ | 1 |
| 1 | | 3 | 1 | ∞ | 3 |
| 2 | | 2 | | ∞ | 2 |
| 3 | | | | 5 | 4 |
On démarre depuis le routeur 2.
- On ne peut aller qu'au routeur 4. On calcule le coût pour y aller depuis le routeur 2 en prenant la valeur du routeur 2 + la valeur de l'arête.
- Le coût obtenu est plus petit que celui existant, on remplace la valeur.
- On marque le routeur 2 comme traité.
- On choisit le routeur 4 comme nouveau sommet courant car il a le plus petit coût.
L'algorithme se termine car le routeur choisi est celui d'arrivée.
Dans un réseau, le poids des arêtes possèdent pour unité une bande passante, s'exprimant en bits/s.
Il faut d’abord calculer les coûts des arêtes en utilisant la formule suivante :
cout = 108/d
où d représente la bande passante entre 2 routeurs (donc le poids d’une arête).
Le coût représente le temps (en secondes) que mettra un fichier de 100mb à être transféré entre deux routeurs.
En général, les coûts les plus faibles sont des débits de l’ordre du Gbits/s (fibre optique par exemple).