Les protocoles de routage OSPF et EIGRP

Fonctionnement gnral d'OSPF

F. Nolot

Master 2 Professionnel STIC-Informatique Module ARS

Les principes d'OSPF

Le protocole OSPF est un protocole de routage tat de lien Mme objectif que les algorithmes vecteurs distance
Obtenir une table de routage avec les meilleurs routes Converger au plus vite vers une table de routage optimale

Avec un protocole vecteur distance

Un routeur connat ses voisins uniquement lors de la transmission de mise jour de leur part Lors d'un envoi d'une mise jour un voisin, ce voisin ne retourne aucune confirmation l'expditeur

Avec un protocole tat de lien

Beaucoup d'informations sont transmises et ncessitent beaucoup de ressources
F. Nolot

Chaque routeur doit connatre ses voisins avant d'changer des informations
Master 2 Professionnel STIC-Informatique Module ARS

Ide du fonctionnement

cot 100 cot 10 10.1.1.0/24 cot 10 cot 100

C E D

cot 100

B
cot 100

cot 100

cot 10

Dans les protocoles tat de lien, B ne va pas donner A le cot de la liaison mais la carte qu'il connat du rseau avec les masques associs Ainsi, A va pouvoir calculer les meilleurs routes vers tous les sous-rseaux en se basant sur les informations topologiques transmises par B
F. Nolot

Comparativement aux protocoles vecteur distance, les protocoles tats de liens doivent calculer les cots vers toutes les sous-rseaux
Master 2 Professionnel STIC-Informatique Module ARS

Ide du fonctionnement

cot 100 cot 10 10.1.1.0/24 cot 10 cot 100

C E D

cot 100

B
cot 100

cot 100

cot 10

Avec les vecteurs distances, B dit A : sous-rseaux 10.1.1.0, metric 3 Avec les tats de liens : A va apprendre puis calculer
A vers 10.1.1.0/24 : par C, cot 220 A vers 10.1.1.0/24 : par D, cot 310
F. Nolot

Rsultat : A mettra dans sa table de routage la route vers 10.1.1.0/24 par C

Master 2 Professionnel STIC-Informatique Module ARS

Ide du fonctionnement
L'algorithme utilis pour trouver les meilleurs routes est appel Shortest Path First algorithm : SPF Appel galement Dijkstra SPF algorithm ou bien simplement Dijkstra algorithm du nom de son concepteur Les changes d'informations ne se font pas ds le dpart par un broadcast Initialisation du processus par une recherche des voisins Aprs qu'un routeur ait identifi un voisin, les routeurs s'changent leurs informations topologiques 4 types de paquets sont utiliss dont Link-state updates packets (LSU) dcrivent les changements de topologie Database Description packets (DD) contient un rsum de la base de donnes de chaque routeur dont les noms des routeurs connus Link-state advertisements (LSA) qui contient le sous-rseau, le masque, la mtrique et d'autres informations sur les sous-rseaux
F. Nolot

Hello packet permet de dcouvrir ses voisins et d'avertir son entourage de sa prsence
Master 2 Professionnel STIC-Informatique Module ARS

Fonctionnement dtaill d'OSPF

Le droulement complet d'OSPF est le suivant :

Chaque routeur dcouvre son voisinage et conserve une liste de tous ses voisins Chaque routeur utilise un protocole fiable pour changer les informations topologiques (LSA) avec ses voisins Chaque routeur stocke les informations topologiques apprises dans leur base de donnes Chaque routeur excute l'algorithme SPF pour calculer les meilleurs routes Chaque routeur place ensuite la meilleur route vers chaque sous-rseau dans sa table de routage

Chaque routeur possde donc

Une table de ses voisins,
F. Nolot

Une base de donnes de la topologie du rseau Une table de routage

Master 2 Professionnel STIC-Informatique Module ARS

Les protocoles de routage OSPF et EIGRP

Fonctionnement dtaill d'OSPF

F. Nolot

Master 2 Professionnel STIC-Informatique Module ARS

Identification d'un routeur

La base de donnes de la topologie du rseau contient la liste de tous les sousrseaux, appel lien, connu du routeur et de l'identit du routeur permettant de faire la liaison avec ce lien Il est facile d'identifier un sous-rseau et son masque associ par contre identifier un routeur est plus compliqu ! La solution utilise doit permettre d'identifier, de faon unique sur le rseau un routeur par un identifiant appel RID La solution choisie est de se baser sur les adresses IP de ceux-ci Si le routeur possde un adresse loopback, il prendra l'adresse la plus grande parmi ses adresses de loopback Sinon, il choisira la plus grande adresse IP de ses interfaces oprationnelles Chaque routeur choisit son OSPF RID l'initialisation
F. Nolot

Attention : le RID ne change pas, mme si une nouvelle interface s'active. Les changements n'ont lieu que si le processus OSPF est rinitilis (clear ip ospf process)
Master 2 Professionnel STIC-Informatique Module ARS

Dcouverte des voisins

2 routeurs OSPF deviennent voisins s'ils possdent une interface sur le mme sous-rseau Pour dcouvrir d'autres routeurs OSPF, un routeur OSPF diffuse par multicast un message du type OSPF Hello Le message Hello suit l'en-tte IP avec le champ type gale 89 (valeur dcimale) Les paquets Hello sont envoys en multicast l'adresse 224.0.0.5, c'est dire tous les routeurs qui parlent OSPF Ces paquets contiennent le RID de l'expditeur, l'ID de la zone appel Area ID, le hello interval, le dead interval, la priorit du routeur, le routeur dsign, le routeur dsign de secour et la liste de voisin que l'expditeur connat dj sur le sous-rseau
F. Nolot

Nous verrons dans la suite la signification de toutes ces donnes

Master 2 Professionnel STIC-Informatique Module ARS

Dcouverte des voisins

Chaque routeur a besoin de savoir si l'expdition de son message Hello est bien arriv destination Pour cela, si un routeur A reoit d'un routeur B un message Hello
Il va prvenir B qu'il a bien reu son message Hello en ajoutant B dans la liste de ses voisins dans le prochain message Hello qu'il expdiera B Ensuite, B fera de mme en ajoutant A dans la liste de ses voisins dans son prochain message Hello

Ds qu'un routeur voit son propre RID dans la liste des voisins incluse dans un message Hello provenant d'un autre routeur, il sait qu'une communication bi-directionnelle aussi appel twowaycommunication est faite. A partir de cet instant, des informations LSA sont susceptibles d'tre changes
F. Nolot

Master 2 Professionnel STIC-Informatique Module ARS

10

Voisins coup sur ?

Pour tre voisin, 2 routeurs doivent avoir les paramtres suivants identiques Masque de rseau utilis Numro du sous-rseau Hello Interval Dead Interval OSPF area ID Rsumons le fonctionnement d'OSPF jusque maintenant Initialisation et recherche du RID Dcouverte du voisinage par change de messages Hello Connaissance du voisinage ds qu'une communication bidirectionnelle a eut lieu
F. Nolot

Maintenant, les routeurs peuvent commencer s'changer des informations topologiques mais peuvent aussi utiliser un routeur dsign
Master 2 Professionnel STIC-Informatique Module ARS

11

Le Designated Router

Afin de diminuer le trafic rseaux entre tous les routeurs, dans certains cas, un routeur dsign est lu Ainsi, tous les changes ne se font qu'avec ce routeur dsign
Pas de routeur dsign DR

Aprs l'lection du DR, les Database Description packets vont vers le DR qui les retransmets tous Sans DR sur un rseau de 10 routeurs, il y a 45 couples diffrents de routeurs entre lesquels des echanges devront avoir lieu !
DR

F. Nolot

Master 2 Professionnel STIC-Informatique Module ARS

12

lection du Designated Router

Le DR est lu suivant le principe suivant :

Le routeur qui envoie un message Hello avec la plus grande priorit OSPF est lu DR Si deux ou plus possdent la plus haute priorit, celui avec le plus grand RID est lu RID Gnralement, celui avec la 2me plus grande priorit devient BDR Les valeurs des priorits varient entre 1 et 255 Si un DR est lu et qu'un routeur apparat dans le rseau avec une priorit suprieure, le DR ne sera rlu que si une dfaillance du DR ou du BDR a lieu Si le DR est en panne, le BDR devient DR et une nouveau BDR est lu Si le BDR est en panne, un nouveau BDR est lu
F. Nolot

Master 2 Professionnel STIC-Informatique Module ARS

13

changes des donnes

Sur une interface sans DR (liaison point point par exemple) Les mises jour OSPF sont envoyes directement tous les voisins Sur une interface avec un DR, les routeurs non DR envoient leurs mises jour au DR et BDR en utilisant l'adresse multicast 224.0.0.6 Cette adresse dsigne tous les routeurs OSPF DR, ce qui signifie que le DR et le BDR doivent tre en coute de cette adresse Le DR relaie les mises jour tous les routeurs OSPF en utilisant l'adresse 224.0.0.5 Le BDR reoit les mises jour mais ne les forward pas. Il se tient juste prs au cas o le DR tombe en panne Les routeurs voisins changent alors leur base de donnes topologiques entre-eux. Ds qu'un routeur a fait cet change, il est dans dit tre dans l'tat Full state Un routeur full state change des LSU avec ses voisins Par consquent, un routeur sera full-state avec un DR ou un BDR et 2 way state avec les autres non-DR
F. Nolot

Master 2 Professionnel STIC-Informatique Module ARS

14

Les autres mcanismes ?

Quand un routeur ne reoit plus de messages Hello de la part d'un autre, au bout de l'intervalle de temps dead interval, le routeur silencieux est considr comme mort
Le dead interval par dfaut est de 4 *hello interval

Les boucles de routage sont naturellement supprimes grce l'algorithme SPF

Ds qu'un routeur est dtect dfaillant, tout le monde est immdiatement averti L'algorithme OSPF peut converger aussi vite que 5 secondes aprs dtection d'une dfaillance dans la plupart des cas

F. Nolot

Master 2 Professionnel STIC-Informatique Module ARS

15

Les protocoles de routage OSPF et EIGRP

Passage l'chelle d'OSPF

F. Nolot

Master 2 Professionnel STIC-Informatique Module ARS

16

Sur grand rseau ?

OSPF peut tre utilis sur de trs petits rseaux comme les exemples prsents jusqu' prsent Sur de grands rseaux, les ingnieurs doivent tudier la mise en place d'OSPF pour tirer au mieux parti de ses fonctionnalits Prenons l'exemple suivant 10.1.6.0 10.1.7.0 10.1.8.0 10.1.9.0
F. Nolot

Master 2 Professionnel STIC-Informatique Module ARS

17

Nouvelle fonctionnalit ?

Dans ce type de rseau, la topologie rseau est suffisamment petite pour tre stocke sur tous les routeurs Supposons maintenant que nous avons 900 routeurs !
Plus le rseau est grand, plus il faudra de mmoire pour stocker la topologie du rseau La rsolution de l'algorithme SPF ncessitera plus de ressources de calcul Un simple changement de status forcera r-xcuter sur tous les routeurs l'algo. SPF

C'est pour cela que des solutions de passage l'chelle permette de rsoudre ces problmes

F. Nolot

Master 2 Professionnel STIC-Informatique Module ARS

18

Le zone OSPF

Les zones OSPF permettent d'isoler des parties du rseau afin de diminuer la taille de la topologie rseau mmoriser sur chaque routeur Zone 1 10.1.6.0 10.1.7.0 10.1.8.0 10.1.9.0
Area Border Router
F. Nolot

Zone 0

Master 2 Professionnel STIC-Informatique Module ARS

19

Le zone OSPF
Area Border Router

Zone 1

Zone 0

10.1.6.0 10.1.7.0 10.1.8.0 10.1.9.0

Zone 1 peut tre vu ainsi :

10.1.6.0 10.1.7.0 10.1.8.0 10.1.9.0

Important : le routeur ABR a toujours besoin des informations des 2 zones

F. Nolot

Master 2 Professionnel STIC-Informatique Module ARS

20

Conclusion sur OSPF

Fonctionnalit Temps de convergence Suppression des boucles Besoin en Mmoire et CPU Ncessite des efforts de conception pour les grands rseaux Protocole public ou propritaire

Link State Rapide Inhrent au protocole Peut tre important Oui OSPF publique

Distance Vector Lent cause de la dtection des boucles Ncessite des mcanismes spcifiques Faible Non RIP public, IGRP propritaire

F. Nolot

Master 2 Professionnel STIC-Informatique Module ARS

21

Les protocoles de routage OSPF et EIGRP

EIGRP ou un protocole hybride

F. Nolot

Master 2 Professionnel STIC-Informatique Module ARS

22

Les concepts

Un protocole de routage dynamique est dit tre hybride quand celui-ci possde la fois des fonctionnalits d'algorithmes de routage vecteur distance et tats de liens EIGRP est une version avance d'IGRP
Converge plus vite qu'IGRP Tous 2 propritaires de Cisco EIGRP envoie d'abord toutes ses informations de routage un voisin et ensuite seulement desmises jour IGRP envoie rgulirement (toutes les 90 s.) toute sa table de routage EIGRP fonctionne avec Novell IPX et Apple AppleTalk, en plus d'IP contrairement IGRP

F. Nolot

Master 2 Professionnel STIC-Informatique Module ARS

23

Les tables EIGRP

Dcouverte des routeurs voisins attachs un mme sous-rseau et stockage de leur identit dans une table appel EIGRP neighbor table Echange et stockage des informations topologiques dans une table appel EIGRP topology table Aprs analyse des informations topologiques, les routes de mtriques les plus faibles sont stockes dans la table de routage Comme EIGRP fonctionne la fois avec IP, IPX et Appletalk et que chacune de ces 3 tables est dpendante du protocole rseau de couche 3 utilis, le routeur doit maintenir constamment jour 9 tables

F. Nolot

Master 2 Professionnel STIC-Informatique Module ARS

24

Voisinage et information topologique

Quand 2 routeurs se sont mutuellement dcouvert voisins, ils changent compltement leur table de routage. Ensuite, des messages Hello sont constamment changs afin de manifester sa prsence, comme OSPF. L'intervalle de temps sparant 2 messages Hello est par dfaut de
5 secondes sur un LAN ou connexion PPP 60 secondes sur un WAN multi-points comme Frame Relay

Quand une modification topologique est constate, seules les nouveauts sont changes, comme OSPF,
par multicast l'adresse 224.0.0.10, si plusieurs routeurs doivent tre prvenus par unicast dans le cas contraire
F. Nolot

Les mises jour sont envoy via le protocole RTP (Reliable Transport Protocol)
Master 2 Professionnel STIC-Informatique Module ARS

25

Suppression des boucles

Les boucles sont supprimes grce aux informations topologiques conservs en mmoire du routeur Quand plusieurs routes sont dcouvertes vers un mme sous-rseau, celle de meilleur mtrique est mise dans la table de routage et les autres sont conserves parmi les informations topologiques La deuxime meilleur route est conserve et est appele feasible successor
En cas de dfaillance de la meilleur route, la feasible successor sera alors mise dans la table de routage

F. Nolot

Master 2 Professionnel STIC-Informatique Module ARS

26