Spécialité NSI - Année 2024 - 2025

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 (hops), c'est à dire en nombre de routeurs traversés pour aller au réseau demandé.

Déroulé de l'algorithme :

1. Chaque routeur a, dans sa table, les réseaux directement accessibles sans passer par un autre routeur (donc à une distance de 0)

2. Périodiquement, toutes les 30s, chaque machine écoute les annonces des passerelles (gateways 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.

3. Si un réseau n’apparaît plus dans les annonces, au bout d'un certain temps (3 mn), il est supprimé des tables.

Les 3 caractéristiques principales qui distinguent l'algorithme RIP de OSPF sont :

1. la distance est mesurée en nombre de sauts et ne tient pas compte de la bande passante de chaque liaison ;

2. chaque routeur n'a d'information que sur ses voisins donc n'a pas de vision globale du réseau (on parle de routing by rumor) ;

3. il y a une distance maximale permise de 15 sauts (16 représente l'infini) et les tables ont 25 entrées au maximum.

Ainsi, cet algorithme ne peut s'appliquer qu'à de petits réseaux et est sensible à certaines attaques...

OSPF a été implémenté pour palier aux faiblesses de RIP énoncées au dessus. Son fonctionnement est donc plus efficace mais aussi plus complexe.

Voici les 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 liaison reliant 2 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ées en kbps ou kb/s (kilobits par seconde) ou MB/s (megabit par seconde).

Chaque réseau peut-être schématisé par un graphe. Ainsi donc, les routeurs et les switches sont les sommets, leurs liaisons sont les arêtes, les étiquettes des arêtes sont les coûts. Si on reprend le réseau de la page suivante, on peut le représenter ainsi :

On peut appliquer l'algorithme de Dijkstra (voir ci-dessous) pour obtenir les routes les moins coûteuses et sans cycle. Chaque routeur devient alors la racine d'un arbre qui contient les meilleurs routes.