Il est impossible au niveau d’Internet ou même de gros réseaux d’entreprise de définir statiquement les tables de routages de milliers voire de milliards de machines. Des algorithmes pour automatiser cette tâche sont employés.
I. Routage et taille des réseaux
Les protocoles de routage dépendent de la taille du réseau. Nous n’étudierons que les réseaux de petite ou moyenne taille.
Dans des réseaux plus complexes (par exemple Internet), il est difficile de maintenir voire de mettre en œuvre un routage statique. Internet est lui-même divisé en systèmes autonomes (autonomous systems, AS) à travers le monde. Il y en avait 36 000 en 2011, 96 000 en mai 2020 (27 629 aux USA, 4 en Mauritanie…).
Les routeurs mettent à jour leurs tables en fonction des tables des routeurs voisins. Il existe deux grands groupes d’algorithmes au programme de Terminale parmi les routeurs appartenant à un même AS.
II. Algorithme à vecteur de distances RIP (Routing Information Protocol)
C’est historiquement le premier algorithme de routage. L’idée est que chaque routeur associe à chaque destination possible la plus courte distance en sauts (hop), c’est-à-dire en nombre de routeurs traversés pour aller au réseau.
Chaque routeur a d’abord dans sa table les réseaux directement accessibles sans passer par un autre routeur (donc à une distance 0).
Ensuite, périodiquement (toutes les 30 s), chaque machine écoute les annonces des passerelles (les gateaways, qui permettent de sortir du réseau local) publiant leurs tables : elle met ainsi à jour ses propres tables si des chemins plus courts ou de nouvelles destinations apparaissent. Les distances sont mises à jour ainsi que le nom du premier routeur qu’il faut joindre pour accéder au réseau : distance + direction = vecteur.
Si un réseau n’apparaît plus dans les annonces, au bout d’un certain temps (3 minutes) il est supprimé des tables.
Les trois caractéristiques principales qui distinguent l’algorithme RIP de l’algorithme alternatif OSPF sont :
- la distance est mesurée en nombre de sauts ;
- chaque routeur n’a d’information que sur ses voisins (en terme de saut : next hop) donc n’a pas de vision globale du réseau (on parle de routing by rumor) ;
- il y a une distance maximum permise de 15 sauts (16 représente l’infini) et les tables ont 25 entrées au maximum.
À noter
Cet algorithme ne peut s’appliquer qu’à de petits réseaux et est sensible à certaines attaques.
III. Algorithme à état de liaison OSPF (Open Shortest Path First )
OSPF a été mis au point pour pallier certaines faiblesses de RIP. Son fonctionnement est plus efficace mais plus complexe.
Retenons seulement quelques grands principes :
Les routeurs ont une « vision » globale du réseau car ils reçoivent des informations de tout le réseau (mais de manière intelligente et efficace). Tous les routeurs ont donc une connaissance identique du réseau.
Les distances sont mesurées de manière plus fine : on tient compte du nombre de sauts mais aussi du débit de chaque « câble » reliant deux routeurs par exemple, en général c’est le rapport entre une bande passante de référence et celle du câble exprimées dans la même unité. Les débits binaires sont souvent donnés en kbps ou kb/s (kilobits par seconde) ou Mb/s (megabit par seconde).
Chaque réseau peut être schématisé par un graphe (vision topologique du réseau). Dans l’exemple de la fiche https://www.annabac.com/revision-bac/le-routage, les routeurs et les switchs sont les sommets, leurs liaisons sont les arêtes, les étiquettes des arêtes sont les coûts. Voici la représentation topologique du réseau permettant de déterminer le chemin de la machine 192.168.0.101 vers Internet :
On applique alors l’algorithme de Dijkstra pour obtenir les routes les moins coûteuses et sans cycle. Chaque routeur devient alors la racine d’un arbre qui contient les meilleures routes.