Archi OSPF

Identification

Infoforall

20 - Routage dynamique OSPF


Voyons un autre moyen de parvenir à avoir un système de routage dynamique.

Le protocole OSPF est assez complexe, notamment car il possède un grand nombre d'options et de réglages variables. Nous allons simplement en voir les grands principes sans rentrer dans les détails.

Ne soyez donc pas surpris si vous trouvez sur le Web des possibilités non évoquées ici.

Prérequis : remplir une table de routage et avoir vu RIP

Evaluation ✎ : questions -

Documents de cours : open document ou pdf

1 - Rappel sur RIP

Les grands principes de RIP (Routing Information Protocol) sont les suivants :

  1. Rôle : aucun routeur n'a de rôle prépondérant dans le système autonome (à part le fait que certains soient en liaison avec l'extérieur par exemple) : RIP utilise un algorithme totalement réparti
  2. Métrique : La métrique utilisée pour définir les distances est simplement le nombre de sauts
  3. Informations transmises : c'est un protocole à vecteur de distance : chaque routeur transmet toutes les 30s à ses voisins directs l'ensemble des couples (destination;distance) qu'il connait. Chaque routeur reçoit les informations de ses voisins, rajoute simplement 1 à leurs métriques (pour prendre en compte le saut supplémentaire vers eux) et garde les meilleurs choix de passerelles pour les différentes destinations : celles dont la métrique est la plus basse.
  4. Connaissance du réseau : RIP ne permet pas aux routeurs d'avoir une vision globale du réseau et de choisir certains chemins : on décide juste de la passerelle suivante à qui on transmet le paquet. Chaque routeur ne connait donc que ses voisins directs et sait auquel transmettre un paquet IP pour une destination donnée. Ici, le routeur A ne connait rien du réseau entre lui et D : il sait juste qu'il doit transmettre à B.
  5. Taille : RIP ne permet pas de gérer des systèmes autonomes comportant des routeurs situés à plus de 15 sauts l'un de l'autre (sinon, le réseau serait encombré par les messages RIP et n'aurait plus le temps de gérer les vrais messages !)
  6. Mise en place : RIP met du temps à se mettre en place car la connaissance des nouvelles routes se fait de proche en proche, un nouveau saut uniquement toutes les 30s. Ici le routeur central va mettre 90s à apprendre l'existence des routeurs Gauche et Droite. Et le routeur Droite va donc devoir attendre encore 90s pour apprendre l'existence du routeur Gauche !

2 - Protocole OSPF Open Shortest Path First

Le protocole Open Shortest Path First est un autre type de protocole.

Exemple de cours : un routeur A dispose des informations suivantes sur les routeurs B et C avec lesquels il est en liaison directe : (A-B, 1), (A-C, 10). Il reçoit les informations suivantes du réseau : (B-C, 1), (B-D, 10), (C-D, 5) et (D-E, 100).

A partir de ces informations, le routeur A peut donc représenter le réseau sous forme d’un graphe où les sommets sont les routeurs et les arcs les liaisons :

Le principe est totalement donc différent de RIP:

  1. Rôle : l'un des routeurs tient un rôle central. Il porte le nom de Routeur Designé (DR Designed Router en anglais). Tous les autres routeurs du système autonome lui envoient leurs informations de liaison. C'est donc ce routeur qui contient toute la base de données du réseau. Le routeur tient à jour la base de donnée et transmet à son tour uniquement le changement sur le réseau aux autres routeurs dès qu'il en reçoit une. Deux différences avec RIP donc : le message ne contient que le changement (pas toutes les tables) et il est diffusé immédiatement, et pas toutes les 30 secondes uniquement.
  2. Métrique : La métrique utilisée pour définir les distances est liée au le débit de la connexion entre deux routeurs (voir plus bas). OSPF préférera une route "fibre optique" en 5 sauts à une route "Ethernet" en 2 sauts.
  3. Informations transmises : c'est un protocole à état de lien : chaque routeur transmet au routeur désigné l'état de la connexion qu'il a établit avec l'un de ses voisins directs. Le Routeur Désigné reçoit donc des connaissances précises des liens entre les routeurs qu'ils gèrent.
  4. Connaissance du réseau : OSPF permet aux routeurs de connaître précisement les liens entre tous les routeurs du système autonome, ainsi que la qualité de leurs liaisons. Contrairement à RIP, les routeurs en OSPF connaissent le chemin exact que devrait prendre le paquet IP, pas uniquement le prochain routeur à qui transmettre.
  5. Taille : OSPF permet de gérer des systèmes autonomes de très grande taille. Il dispose même d'un système de zones qui lui permet de découper le système autonome en zones semi-autonomes reliées à une zone centrale (nommé Epine Dorsale, Backbone). On peut ainsi monter à des systèmes de plus de 1000 routeurs.
  6. Mise en place : la phase d'initialation d'OSPF est beaucoup plus rapide que celle de RIP puisqu'un routeur envoie un message d'état de lien dès qu'il détecte un changement et pas toutes les 30s uniquement. Même en tenant compte des élections pour désigner le Routeur Désigné, le routage converge rapidement.

3 - Métrique d'OSPF

Bande Passante et débit

La bande passante caractérise la valeur maximale d'une communication entre deux ordinateurs, exprimée en bit.s-1.

Le débit caractérise lui la valeur réelle de cette capacité de transmission. Le débit est donc inférieur à la bande passante.

Selon les technologies employées, il est possible que la bande passante et le débit ne puissent pas être les mêmes dans les deux sens :

  • on parle de débit descendant (download) lorsqu'on télécharge vers l'ordinateur
  • on parle de débit montant (updload) lorsqu'on téléverse des données depuis l'ordinateur vers un autre ordinateur.
Unité de la bande passante et du débit

L'unité du débit est le bit par seconde : bit.s-1

Rappel : 1 octet = 8 bits.

Les sous-unités courantes sont :

  • Le kilo-bit par seconde : kbit.s-1
    • 1 kbit.s-1 = 1 000 bit.s-1 = 1.103 bit.s-1
    • kilo signifie donc mille
    • Modem (pour modulateur-démodulateur) : 56 kbit.s-1 en PS Descendante et 48 kbit.s-1 en BP montante
  • Le Mega-bit par seconde : Mbit.s-1
    • 1 Mbit.s-1 = 1 000 000 bit.s-1 = 1.106 bit.s-1
    • Mega signifie donc million
    • Valeurs typiques pour
      • Certaines versions Bluetooth (environ 3 Mbit.s-1)
      • Certaines versions Ethernet (les cables typiques) (à partir de 10 Mbit.s-1)
      • Certaines versions Wifi (à partie de 10 Mbit.s-1)
      • ADSL : 13 Mbit.s-1 en descendant et 1 Mbit.-1 en montant
      • Satellite : 50 Mbit.s-1 en descendant et 1 Mbit.s-1 en montant
      • 4G : 100 Mbit.s-1 en descendant et 50 Mbit.s-1 en montant
      • FastEthernet : 100 Mbit.s-1
  • Le Giga-bit par seconde : Gbit.s-1
    • 1 Gbit.s-1 = 1 000 000 000 bit.s-1 = 1.109 bit.s-1
    • Giga signifie donc milliard
    • Valeurs typiques pour
      • 5G : 1 Gbit.s-1 en descendant et 300 Mbit.s-1 en montant
      • FTTH (Fiber To The Home) : 10 Gbit.s-1

01° Exprimer une bande passante (ou un débit) de 20 Mbit.s-1 en puisance de 10 en convertissant en bit.s-1.

02° Exprimer une bande passante (ou un débit) de 500 Mbit.s-1 en puisance de 10 en convertissant en bit.s-1.

03° Exprimer une bande passante (ou un débit) de 56 kbit.s-1 en puisance de 10 en convertissant en bit.s-1.

04° Exprimer une bande passante (ou un débit) de 3 Gbit.s-1 en puisance de 10 en convertissant en bit.s-1.

On notera que (10a) x (10b) = 10a+b

De même (10a) / (10b) = 10a-b

Globalement, cela correspond donc à la fonction exponentielle :

On notera que (ea) x (eb) = ea+b

De même (ea) / (eb) = ea-b

D'ailleurs, notons au passage que la fonction logarithme fait précisement l'inverse :

log(a) + log(b) = log(a x b)

log(a) - log(b) = log(a / b)

Métrique OSPF

OSPF (Open Shortest Path First) utilise la passe bassante entre deux routeurs comme paramètre de sa métrique : plus la liaison est rapide, plus la valeur utilisée sera petite.

Pour calculer le cout C d'une liaison, on divise une valeur de référence par le débit D de la liaison.

Sur la plupart des systèmes travaillant en OSPF, la valeur de référence par défaut est actuellement de  1.108 .

Avec cette valeur de référence, on obtient alors :

Particularité d'OSPF : on arrondit les coûts à l'entier. Le coût des liaisons transmises_ est un entier compris entre 1 et 65535.

Par exemple :

  • Un débit d de 108 donnera un coût de 1 :
  • Un débit d de 107 donnera un coût de 10 :
  • Un débit d de 109 donnera un coût de 1 et pas 0.1 : la plus petite valeur possible en OSPF est 1. Il ramène donc à 1 toute valeur inférieure.

05° Calculer la métrique OSPF d'une liaison Fibre avec une valeur par défaut de 108 puis 1010.

06° Calculer la métrique OSPF d'une liaison FastEthernet avec une valeur par défaut de 108 puis 1010.

07° Calculer la métrique OSPF d'une liaison Ethernet avec une valeur par défaut de 108 puis 1010.

08° Que vaut la bande passante d'une liaison dont le coût OSPF est de 50 avec une valeur de référence de 108.

09° Un routeur A3 fonctionnant sous OSPF reçoit les informations suivantes :

  • Liaison A - B avec un coût de 1
  • Liaison A - C avec un coût de 1000
  • Liaison A - D avec un coût de 100
  • Liaison B - D avec un coût de 10
  • Liaison C - E avec un coût de 200
  • Liaison C - F avec un coût de 100
  • Liaison D - E avec un coût de 1
  • Liaison E - G avec un coût de 100
  • Liaison F - G avec un coût de 10

Représenter le tout sous forme d'un graphe où les sommets sont les routeurs et les arcs portent les coûts.

...CORRECTION...

On obtient ceci par exemple :

10° Quel est le coût de la liaison AE ? Calculer toutes les routes possibles et choisir celle qui présente le coût le plus faible.

Question supplémentaire : contrairement au cas RIP, le routeur A a-t-il les moyens de connaitre la route que va suivre le paquet le long du trajet A vers E ?

...CORRECTION...

On choisit le chemin dont le coût est le plus faible.

A-B-D-E coûte 1+10+1 = 12.

A-D-E coûte 100+1 = 101.

A-C-E coûte 1000+100 = 1100.

A-C-F-G-E coûte 1000+100+10+100 = 1210.

On prend donc le chemin A-B-D-E.

On voit donc que contrairement à RIP, OSPF va parvenir à prévoir le chemin du paquet... tant qu'il reste dans le système autonome auquel le routeur appartient.

11° Ecrire alors la table de routage que le routeur pourraît batir à partir de ces données.

On donnera aux interfaces des noms basés sur le nom du routeur suivi d'une simple indication G (gauche) - D (droite) - H (haut) - B (bas)...

Si on donne des noms aux interfaces d'entrée-sortie, on pourrait alors avoir ceci :

Il faudra donc vous demander quelle est la route la plus courte pour atteindre le bon chemin.

Le message est pour
IP Destinataire
Transmettre à la passerelle
(intermédiaire de communication)
Interface à utiliser
(carte réseau)
Coût
A Localhost Localhost 1
B B E/S 1 1

12° Même question mais cette fois, le routeur A doit éviter pour des raisons de sécurité d'envoyer des paquets passant par E sauf pour les paquets destinés à E. OSPF est-il capable d'intégrer cette contrainte pour réaliser une nouvelle table de routage ? Réaliser cette nouvelle table.

13° Expliquer pourquoi les informations reçues par A dans le cadre de RIP ne lui permettent pas de faire de même.

Comme vous le voyez réaliser les tables prend du temps. Et encore, notre réseau est relativement modeste. Lors de l'étude des graphes, nous verrons qu'il existe des algorithmes permettant de trouver le plus court chemin entre deux sommets. L'algorithme permettant d'automatiser cette tâche de recherche est l'algorithme de Dijkstra. Nous en verrons le principe dans la partie algorithmique appliquée aux graphes.

4 - Initialisation et mises à jour des états de lien

Les tables d'un routeur OSPF

Les routeurs OSPF disposent de trois tables en réalité :

  1. Une table personnelle qui contient les états des liens que la machine a détecté avec ses voisins directs (les routeurs adjacents notamment)
  2. Une table qui contient les états des liens qu'elle a reçue du réseau (soit par le Routeur Désigné, soit en faisant passer un état de lien d'un autre routeur à destination du Routeur Désigné)
  3. Une table de routage que le routeur a concu à partir de l'état des liens qu'il connaît sur le réseau : calculer la table de routage est long, on ne relance les calculs que si les états de liens ont été modifiés. Sans modification ou nouvelle liaison, le routage regarde simplement sa table de routage.

Message HELLO et mise à jour de l'état des liens

Comme pour RIP, il existe une phase d'initialisation à respecter, les routeurs ne se connaissant pas au départ.

Chaque routeur envoie des messages HELLO sur ses interfaces toutes les 10 secondes généralement (contrairement aux 30 secondes de RIP). Il peut donc rapidement détecter la présence d'un nouveau routeur. Si l'ordinateur de l'autre côté appartient bien au même réseau, il répond alors en fournissant son adresse IP et les deux ordinateurs connaissent alors le coût de la liaison entre eux Que fait le routeur lorsqu'il détecte une nouvelle liaison directe ? Il la place dans sa table personnelle et en informe le Routeur Désigné. Le message contient l'adresse IP des deux machines concernées ainsi que le coût de cette liaison.

De la même manière, lorsqu'un routeur OSPF ne reçoit rien d'un de ses voisins au bout de 40s, il considère que le lien est non disponible, fait la mise à jour de sa table personnelle et envoie un message au Routeur Désigné.

Il doit également lancer les calculs pour obtenir une table de routage prenant en compte les modifications.

On rappelle qu'un routeur RIP envoie toutes les 30s à tous ses voisins directs l'ensemble (destination connue - coût) qu'il connait. Cela encombre rapidement beaucoup plus le réseau.

Routeur Désigné

Quel est le routeur élu en tant que Routeur Désigné ? Celui qui possède le plus grand priorité pour le devenir et en cas d'égalité, celui qui a le plus grand numéro par exemple.

A chaque fois que le routeur détecte un nouveau voisin, il en informe le Routeur Désigné. Il reçoit aussi de sa part soit la base de données des états des liens s'il ne la possède pas encore ou les mises à jour que le Routeur Désigné reçoit lui-même des autres routeurs.

Chaque routeur informe le Routeur Désigné uniquement des changements dans les états des liens. En retour, le Routeur Désigné informe tous les autres routeurs des modifications qu'il reçoit.

5 - Exercice

On considère le système autonome suivant comportant 6 routeurs.

A10 est relié à A20 avec une liaison de Bande Passante 10 Gbit.s-1.

A10 est relié à A30 avec une liaison de Bande Passante 10 Mbit.s-1.

A10 est relié à A40 avec une liaison de Bande Passante 100 Mbit.s-1.

A10 est relié à A90 avec une liaison de Bande Passante 10 Gbit.s-1.

A20 est relié à A40 avec une liaison de Bande Passante 1 Gbit.s-1.

A20 est relié à A90 avec une liaison de Bande Passante 10 Gbit.s-1.

A30 est relié à A50 avec une liaison de Bande Passante 100 Mbit.s-1.

A30 est relié à A90 avec une liaison de Bande Passante 100 Mbit.s-1.

A50 est relié à A90 avec une liaison de Bande Passante 10 Mbit.s-1.

14° Quel routeur a été choisi comme routeur désigné visiblement ?

15° Représenter les liaisons via un graphe. Placer les Bandes Passantes sur les arcs.

16° Calculer les coûts OSPF des liaisons.

On prendra une valeur par défaut de 108, certains coûts devront donc être évalués à 1 même si leurs valeurs réelles sont inférieures à 1.

17° Représenter alors le graphe en plaçant ces coûts sur les arcs.

18° Déterminer la route choisie par OSPF entre le routeur A40 et le routeur A50.

19° A90 tombe en panne. Que va le remplacer en tant que routeur désigné ?

20° A90 tombe en panne. Quelle route prendre entre A40 et A50. Le résultat aura-t-il était le même si on avait pris une valeur de référence de 10 Gbit.s-1 ?

6 - FAQ

Rien pour le moment

Activité publiée le 26 10 2020
Dernière modification : 01 02 2021
Auteur : ows. h.