Exercice Routage OSPF TP Routage OSPF "Open Shortest Path First"

Le but de ce problème est d'étudier le protocole internet OSPF. C'est un protocole de routage réparti dans 

lequel chaque routeur gère une base de données de l'ensemble des liaisons d'un réseau (topologie du réseau) et calcule à partir de cette base les plus courts chemins par l'algorithme de Dijsktra. Cette base de donnée est mise à jour par diffusion en inondation par chaque routeur de l'état de ses liaisons aux autres routeurs. Il entre dans la classe des protocoles baptisés "à état des liaisons" ou "linkstate". 

Par exemple soit un réseau de 7 routeurs A, B, C, D, E, F, G dont la topologie est la suivante (les coûts de transit pour chaque liaison sont supposés égaux dans chaque direction et sont mentionnés sur l'arc
représentant la liaison).

La base de données (topologie ou carte du réseau) qui doit être connue de chaque routeur donne principalement les coûts en point à point pour chaque liaison. D'autres informations sont également stockées dans cette table. Certaines de ces informations seront introduites dans la suite.

La base de données (topologie ou carte du réseau) qui doit être connue de chaque routeur donne principalement les coûts en point à point pour chaque liaison. D'autres informations sont également stockées dans cette table. Certaines de ces informations seront introduites dans la suite.

Cette base de données est construite par échange d'informations entre les routeurs. Pour cela le protocole suivant est effectué. Son déclenchement peut répondre à différentes stratégies de mise à jour : 

- périodiquement
- lorsqu'un routeur nouveau s'initialise
- lorsqu'un routeur s'aperçoit qu'il a un nouveau voisin
- lorsque le coût d'une liaison avec un voisin a changé

• Étape 1 : 

Chaque routeur construit un paquet appelé "paquet d'état des liaisons" ou LSP ("Link State Packet")  qui contient des coûts de liaison que le routeur souhaite faire connaître. Un LSP comporte principalement une liste de noms  de routeurs (voisins d'un routeur) et les coûts pour les atteindre. Les LSP émis par un même routeur sont numérotés au moyen d'un numéro de séquence. Pour simplifier on ne se préoccupe pas du retour à zéro des compteurs utilisés trop longtemps.

• Étape 2 : 

Le paquet LSP est transmis à tous les routeurs voisins et chaque routeur enregistre les informations du LSP généré le plus récemment. Plus précisément chaque voisin effectue le traitement suivant: 

- Recevoir le paquet LSP.
- Consulter la base existante.
- Si l'entrée (la liaison et son coût) n'est pas présente, ajouter cette entrée et diffuser l'information à tous les voisins sauf l'émetteur du LSP.
- Si l'entrée est présente et si le numéro de séquence du LSP est plus grand que celui correspondant à l'entrée modifier l'entrée et diffuser l'information à tous les voisins sauf le ré-émetteur du LSP.
- Si l'entrée est présente et si le numéro de séquence du LSP est plus petit ou égal à celui correspondant à l'entrée: ne rien faire.

Question 1

Les protocoles d e routage de type vecteurs de distance dont l'exemple type est le protocole Internet RIP ("Routing Information Protocol") se distinguent des protocoles de type Internet OSPF (à état de liaison).
Rappeler en quelques lignes l'algorithme que doit suivre chaque routeur pour le protocole RIP.

Question 2

A quoi pourrait servir la retransmission du LSP à son émetteur ?
Pourquoi un paquet LSP n'est-il pas renvoyé à son émetteur ?

Question 3

A quoi sert le Numéro de Séquence émetteur du point de vue du réseau internet qui est à datagramme ?
A quoi sert le Numéro de Séquence émetteur du point de vue du protocole de diffusion des informations d'état de liaison ?

En plus du Numéro de Séquence, chaque information concernant une liaison possède une date de péremption (variable baptisée dans OSPF "age") qui apparait aussi bien dans les paquets LSP échangés que dans les bases de données. Toute information dépassant sa date est systématiquement détruite.

Citer plusieurs types de problèmes qu'une telle datation solutionne.

Question 4

On suppose que la liaison de A vers B est coupée. On a alors le réseau : 

A ayant détecté la coupure, A prépare un LSP de la forme : "de A à B, coût = infini , numéro de séquence," 

On suppose que ce LSP est le premier généré (au début il est le seul).
Indiquer ce qui se passe alors dans le réseau. Quelle est la base de données obtenue par les différents noeuds à la fin du processus d'inondation ?

On suppose qu'ensuite B prépare et transmet son LSP concernant A-B.
Quelle est la base de données obtenue ?

Question 5

On suppose que la liaison de D à E tombe en panne (on suppose que les 2 noeuds D et E se sont aperçus de cette rupture et envoient les LSP correspondants).

Indiquer la (ou les) bases de données obtenues à l'issue de l'algorithme distribué de transmission de l'état des liaisons par chacun des noeuds.

Question 6

A partir des bases de données trouvées à la question précédente et du réseau suivant on suppose que la liaison de B à C tombe en panne et amène au réseau : 

Indiquer les bases de données obtenues par chaque routeur.

Question 7

Par la suite la liaison de D à E est rétablie avec un coût de 2 rendant de nouveau le réseau connexe. On obtient alors le réseau ci -dessous.
On exécute l'algorithme de diffusion en supposant que D et E informent le réseau du rétablissement de cette connexion. 

Quelle est  la valeur du coût de la liaison de B à C pour les sites A, D et pour les sites B, C, E, F ?
Quel est le risque encouru dans cette situation ?
Comment détecter efficacement la situation ? Sur quel type de site ? (on suggère une utilisation du numéro de séquence)
Comment faire pour mettre en œuvre une solution de "réconciliation" basée sur le numéro de séquence ?

Question 8

La technique de diffusion par inondation de l'état des liaisons est inconcevable telle que pour le réseau Internet. Pourquoi ?
Que fait-on pour appliquer quand même OSPF à l'internet ?