Il s'agit de deux protocoles de routage, c'est à dire des règles permettant aux routeurs de décider quelle chemin choisir pour transmettre les paquets de données vers leurs destinations.

Utilise l'algorithme de Bellman et Ford pour déterminer un plus court chemin – Il s'agit d'un exemple de programmation dynamique.

On peut se contente ici du principe en se basant sur cet exemple :

• Les routeurs de A à G sont connectés les uns aux autres,
• Toutes les connexions ont bien sûr une adresse IP mais ce qui nous intéresse surtout est de pouvoir atteindre les sous-réseaux auxquels certains routeurs sont connectés.
  Par exemple B est relié au sous-réseau 172.16.x.x. Une requête vers ce sous-réseau doit passer par B.
  Le sous réseau 57.x.x.x peut être atteint par G et D.

Maintenant voyons comment les routeurs vont calculer leurs chemins.

• Aucun routeur n'a de vision globale du réseau. Il ne communique qu'avec ses voisins.
• Chaque routeur entretient une table de routage précisant la distance qui le sépare d'un réseau IP, cette distance étant exprimée en sauts – hops en anglais.
  • Par exemple B sait qu'il est à une distance de 0 du réseau 172.16.x.x.
  • Au début, F ne sait pas à quelle distance il est de 172.16.x.x mais après des échanges, il saura qu'il peut atteindre B et donc 172.16.x.x en 2 sauts.
• Les routeurs échangent leur table de routage avec leurs voisins. Voyons un exemple :
  • F avait dans sa table de routage l'information qu'il pouvait atteindre 172.16.x.x en 3 sauts en passant par E.
  • G, sait qu'il peut atteindre 172.16.x.x en 1 saut. Il passe l'information à ses voisins.
  • F reçoit le message. Il en déduit qu'il pourra, en passant par G, atteindre 172.16.x.x en 2 sauts, ce qui est mieux.
  • F modifie donc sa table et indique qu'il peut atteindre 172.16.x.x en 2 sauts en passant par G.
  • Comme F a amélioré sa table, il en informe ses voisins en transmettant sa table.
• Un chemin de plus de 15 sauts n'est pas enregistré

Un aspect important d'un réseau est sa capacité à s'adapter automatiquement à la défaillance d'un de ses éléments. Si un routeur tombe en panne, les paquets de données doivent pouvoir continuer à trouver leur chemin.

On ajoute donc des règles au protocole :

• Toutes les 30 secondes, les routeurs diffusent leur table de routage.
• Si une route connaît un problème prolongé, elle est supprimée de la table.
• Si un routeur ne diffuse rien pendant 3 minutes, il est considéré en panne et les routes passant par lui sont supprimées.

Les réseaux étant gros et les échanges permanents, il faut envisager des cas à problèmes. Supposons que :

• C dit que G est en panne
• B dit qu'il a une route passant par G

C et G risque de s'échanger en boucle cette information contradictoire :

• C ayant reçu le message de B, il se met dire que G fonctionne diffuse l'information
• B qui vient d'entendre que G est en panne modifie sa route et diffuse l'information “G en panne”

Pour éviter ce problème, on donne la priorité à l'information “en panne” et on empêche les allers-retours entre deux routeurs : B ne répète pas vers C ce que C vient de lui dire.

Ce protocole est déjà ancien (années 1990) et permet de gérer des réseau plus grands avec des routeurs plus puissants.

Avec OSPF on cherchera le chemin le plus court dans le réseau mais en tenant compte du débit. Pour mieux dire, on choisira le chemin au débit le plus élevé.

Supposons que l'on ait les débits suivants :

• 100 Mb/s : B – C ; C – E
• 10 Mb/s : A – B ; B – G ; E – F
• 1 Mb/s : A – D ; F – G ; C – D
• 100 kb/s : E – G ; D – F

Alors le transfert d'un paquet de 1 Gb sur la route F → E → C → B prendra

• 100 s pour F → E
• 10 s pour E → C
• 10 s pour C → B

Le même transfert sur F → G → B prendra

• 1000 s sur F → G
• 100 s sur G → B

Le premier chemin est nettement meilleur.