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
Les grands principes de RIP (Routing Information Protocol) sont les suivants :
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
Métrique : La métrique utilisée pour définir les distances est simplement le nombre de sauts
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.
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.
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 !)
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 !
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:
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.
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.
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.
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.
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.
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.
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 le coût 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.
Un exemple
Reprenons l'exemple vu dans le cours RIP :
Établissons la table de routage du routeur A en nous basant sur le protocole OSPF :
Prenons l'exercice avec les débits suivants :
liaison routeur A - routeur B : 1 Mbps
liaison routeur A - routeur C : 10 Mbps
liaison routeur C - routeur B : 10 Mbps
Commençons par calculer les coûts des liaisons inter-routeurs
liaison routeur A - routeur B : 108/106 = 100
liaison routeur A - routeur C : 108/107 = 10
liaison routeur C - routeur B : 108/107 = 10
pour faire :
Routeur A -> Routeur C le coût est de 10
Routeur A -> Routeur B le coût est de 100
Routeur A -> Routeur C -> Routeur B le coût est 10+10=20
Routeur A -> Routeur B -> Routeur C le coût est 100+10=110
Ce qui nous donne la table de routage suivante :
réseau
moyen de l'atteindre
métrique
172.18.0.0/16
eth0
0
192.168.1.0/24
eth1
0
192.168.2.0/24
eth2
0
172.17.0.0/16
192.168.2.2/24
10
172.17.0.0/16
192.168.1.2/24
110
172.16.0.0/16
192.168.1.2/24
100
172.16.0.0/16
192.168.2.2/24
20
ou encore en se passant des adresses IP :
réseau
moyen de l'atteindre
métrique
R1
eth0
0
Réseau Routeur B
eth1
0
Réseau Routeur C
eth2
0
R2
Routeur C
10
R2
Routeur B
110
R3
Routeur B
100
R3
Routeur C
20
pour un paquet de données allant de R1 à R2, la route privilégiée sera donc : R1 -> Routeur A -> Routeur C -> R2.
pour un paquet de données allant de R1 à R3, la route privilégiée sera donc : R1 -> Routeur A -> Routeur C -> Routeur B -> R3 (on constate une différence avec ce que nous avions trouvé avec le protocole RIP).
On peut simplifier la table en ne gardant que le plus court chemin pour rejoindre les différent réseaux.
réseau
moyen de l'atteindre
métrique
R1
eth0
0
Réseau Routeur B
eth1
0
Réseau Routeur C
eth2
0
R2
Routeur C
10
R3
Routeur C
20
4 - 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é avec ses voisins directs (les routeurs adjacents notamment)
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 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é
C'est un routeur qui sert de référent dans une zone donnée.
A chaque fois qu'un 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.
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
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.
Activité publiée le 04 03 2021
Auteur : ows. h.
Modification : Andjekel
