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
Le protocole Open Shortest Path First est un type de protocole différent de RIP de plusieurs façons.
Il est basé sur la transmission d'états de lien direct entre les routeurs et pas sur la transmission de vecteurs de distance entre tous les routeurs comme avec RIP. On dit donc qui connaît qui directement et pas juste qui peut joindre qui sur le papier.
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) c'est à dire A est en liaison directe avec B avec un coût de 1
(A-C, 10) c'est à dire A est en liaison directe avec C avec un coût de 10
Il reçoit les informations suivantes du réseau :
(B-C, 1)
(B-D, 10)
(C-D, 5)
(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 donc différent de RIP sur chacun des points suivants :
Bilan sur OSPF
Rôle : L'un des routeurs tient un rôle central : le Routeur Designé, DR Designed Router en anglais.
Les autres routeurs lui envoient les liaisons directes qu'ils viennent de détecter.
Ce routeur désigné tient à jour une base de donnée et transmet les changements reçus aux autres routeurs dès qu'il en reçoit une.
Ainsi, les messages échangés entre routeurs :
ne contiennent que le changement de liaison détecté
sont diffusés immédiatement
Métrique : La métrique est liée au le débit entre deux routeurs. OSPF préférera une route "fibre optique" en 5 sauts à une route "Ethernet" en 2 sauts.
Informations transmises : c'est un protocole à état de lien : chaque routeur transmet au routeur désigné un couple (liaison entre qui et qui, métrique de la liaison) lorsqu'un changement sur ces voisins apparaît.
Connaissance du réseau : chaque routeur OSPF reçoit toutes les nouvelles liaisons. Cela lui permet de connaître la structure exacte du système.
Taille : OSPF permet de gérer des systèmes autonomes de très grande taille. On peut monter à des systèmes de plus de 1000 routeurs.
Mise en place : la phase d'initialisation d'OSPF est rapide.
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 puissance de 10 en convertissant en bit.s-1.
02° Exprimer une bande passante (ou un débit) de 500 Mbit.s-1 en puissance de 10 en convertissant en bit.s-1.
03° Exprimer une bande passante (ou un débit) de 56 kbit.s-1 en puissance de 10 en convertissant en bit.s-1.
04° Exprimer une bande passante (ou un débit) de 3 Gbit.s-1 en puissance 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écisément l'inverse :
log(a) + log(b) = log(a x b)
log(a) - log(b) = log(a / b)
On rappelle que le logarithme et l'exponentielle sont des fonctions réciproques l'une de l'autre.
Métrique OSPF
OSPF (Open Shortest Path First) utilise la passe passante entre deux routeurs comme paramètre de sa métrique : plus la liaison est rapide, plus la valeur utilisée sera petite.
Formule pour calculer le coût
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. Cela correspond à considérer que les liaisons qui sont au moins en ADSL 10 Mbit.s-1 sont des routes de bonne qualité.
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. On ne peut donc pas avoir de coût inférieur à 1.
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.
Le choix de la valeur par défaut est donc importante car on ne différencie pas en terme de qualité les liaisons à partir de cette valeur de débit. On considère que toutes liaisons disposant au moins de ce débit sont de très bonne qualité et leur coût est estimé à 1.
05° Calculer la métrique OSPF d'une liaison Fibre puis FastEthernet puis Ethernet avec une valeur par défaut de 108.
05° Calculer la métrique OSPF d'une liaison Fibre puis FastEthernet puis Ethernet avec une valeur par défaut de 1010.
07° Quelle est la valeur par défaut qui ne provoque aucune différence de traitement entre Fibre et FastEthernet ? Le choix de la valeur par défaut a-t-il une influence sur les routes obtenues à travers le réseau ?
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 connaître 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 la table de routage que le routeur pourrait bâtir à partir de ces données.
On donne le nom des interfaces sur le graphe ci-dessous. Le nom des interfaces menant aux réseaux internes (non représentés ici) est toujours ES4 sur ce graphe.
Il faudra donc vous demander quelle est la route la plus courte pour atteindre le bon chemin.
IP Destinataire
Passerelle
Interface
Coût
A3
Localhost
Localhost
-
A
Accès réseau interne
ES 4
-
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.
3 - Initialisation et mises à jour des états de lien
Les routeurs OSPF disposent de trois tables en réalité :
Une table personnelle qui contient les états des liens que la machine a détecté sur ses voisins directs (les routeurs adjacents)
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é)
Une table de routage que le routeur a conçu à 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 ?
Deux choses :
il la place dans sa table personnelle et
il informe le Routeur Désigné. Le message contient l'adresse IP des deux machines concernées ainsi que le coût de cette liaison.
Que fait le routeur lorsqu'un de ses voisins ne communique plus depuis 40s ?
Deux choses :
il considère que le lien est non disponible et fait la mise à jour de sa table personnelle puis
il envoie un message au Routeur Désigné.
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.
C'est le responsable du système autonome qui fixe le numéro de priorité.
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.
On notera qu'il y a aussi un second routeur, qui joue le rôle de copie de sauvegarde de la base de donnée et qui pourra devenir Routeur Désigné en cas de panne de ce routeur.
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 ?
