Le protocole OSPF - mootse.telecom-st-etienne.fr · 3 4 OSPF Notion de coûts • 5 OSPF Idée de fonctionnement •Un routeur doit: —découvrir ses routeurs voisins (apprendre

1

0

Le protocole OSPF

1

Le protocole OSPF Open Shortest Path First (SPF)

OSPF est un protocole défini par l'IETF à la fin des années 80

Il a fait l'objet d'un historique relativement complexe de RFCs

Algorithme utilisé type état de liens

Algorithme de routage dynamique: adaptation aux modifications du réseau

Algorithme distribué et global: Les routeurs ont une vision global du réseau

Il utilise l'algorithme SPF pour Shortest Path First, plus connu sous le

nom d'algorithme de Dijkstra, afin d'élire la meilleure route vers une

destination donnée

2

2

OSPF Notion de coûts

• Supposons que du routeur R1 on cherche à atteindre le réseau

192.168.1.0.

— Le protocole RIP aurait élu la route passant par R5 puisque c'est la plus courte en termes de saut.

— Cependant, imaginez que les liens représentés sous forme d'éclairs soient «rapides» (de type FastEthernet à 100 Mbps par exemple) et que les liens représentés sous formes de segments droits soient «lents» (de type Ethernet à 10 Mbps par exemple). Le choix du protocole RIP n'est plus du tout pertinent !

3


• Le protocole OSPF fonctionne différemment:

— Il attribue un coût à chaque liaison (appelée lien dans le jargon OSPF)

afin de privilégier l'élection de certaines routes. Plus le coût est

faible, plus le lien est intéressant. Par défaut, les coûts suivants

sont utilisés en fonction de la bande passante du lien

Type de réseau Coût par défaut

FDDI, FastEthernet 1

Ethernet 10 Mbps 10

E1 (2,048 Mbps) 48

T1 (1,544 Mbps) 65

64 Kbps 1562

56 Kbps 1758

19.2 Kbps 5208

3

4


•

5

OSPF Idée de fonctionnement

• Un routeur doit:

— découvrir ses routeurs voisins (apprendre leurs identificateurs

appelés RID )

— apprendre la distance et le type de lien vers chacun des voisins

— construire un paquet spécial disant tout ce qu'il vient

d'apprendre de ses voisins

— envoyer ce paquet spécial à tous les routeurs

— A partir des paquets spéciaux reçus, calculer le plus court

chemin vers tous les autres routeurs (algorithme Dijkstra)

4

6

OSPF Idée plus précise de fonctionnement

• 1. Chaque routeur prend connaissance de ses propres liaisons, de ses

propres réseaux directement connectés. Il le fait en détectant qu’une

interface est à l’état actif.

• 2. Chaque routeur est responsable de la détection de ses voisins sur les

réseaux connectés directement. Les routeurs effectuent cette détection

en échangeant des paquets Hello avec d’autres routeurs situés sur des

réseaux directement connectés.

• 3. Chaque routeur crée un LSP (Link-State Packet) contenant l’état de

chaque liaison directement connectée. Il procède en enregistrant toutes

les informations pertinentes sur chaque voisin, notamment l’ID du

voisin, le type de liaison et la bande passante.

7

• 4. Chaque routeur diffuse son LSP à l’ensemble de ses voisins, qui

stockent tous les LSP qu’ils reçoivent dans une base de données

(base de données topologiques ou Link State DataBase). Les

voisins diffusent ensuite le LSP à leurs voisins, jusqu’à ce que tous

les routeurs de la zone aient reçu le LSP.

• 5. Chaque routeur utilise la base de données pour élaborer une

carte complète de la topologie. Le routeur possède ainsi une carte

complète s’apparentant à une carte routière de l’ensemble des

destinations de la topologie et des routes pour les atteindre.

L’algorithme SPF sert à déterminer le meilleur chemin vers chaque

réseau.

OSPF Idée plus précise de fonctionnement (suite)

5

8

OSPF La base de données topologique

Link State DataBase

• Avec le protocole OSPF, chaque routeur d'une même «zone» dans

le vocabulaire OSPF possède une base de données topologique

identique

Arc Coût

R1, R2 1

R1, R5 10

R2, R3 1

R3, R4 10

R3, R5 1

R4, R5 10

R4,

192.168.1.0 10

9

OSPF L’élection de la meilleure route

• L'algorithme SPF de Dijsktra va traiter cette base de données afin

de déterminer les routes les moins coûteuses.

• Une fois le traitement réalisé, chaque routeur se voit comme la

racine d'un arbre contenant les meilleures routes.

• Dans l'exemple, entre R1 et

192.168.1.0, la meilleure route passe

par R2, R3 et R4 pour un coût total de

1 + 1 + 10 + 10 soit 22

6

10

OSPF La détermination d’un table de routage

• La base de données topologique décrit le réseau mais ne

sert pas directement au routage.

• La table de routage est déterminée par l'application de

l'algorithme du SPF sur la base topologique.

• Sur R1, voici un extrait de la table de routage calculée par

SPF au sujet du réseau 192.168.1.0 :

Réseau de destination Moyen de l'atteindre Coût

192.168.1.0 R2 22

11

OSPF Structure de données

• Le protocole OSPF crée et met à jour trois bases de données :

— Base de données de contiguïté - table de voisinage

— Base de données d'états de liens (LSDB) - table topologique

— Base de données de réacheminement - table de routage

7

12

OSPF Détermination de l’ID d’un routeur

• La base de données de la topologie du réseau contient la liste de tous les

sous réseaux, appelé lien, connu du routeur et de l'identité du routeur

permettant de faire la liaison avec ce lien

• La solution utilisée doit permettre d'identifier, de façon unique sur le réseau

un routeur par un identifiant appelé RID

• La solution choisie est de se baser sur les adresses IP de ceux-ci

— Si le routeur possède 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 opérationnelles

• Chaque routeur choisit son OSPF RID à l'initialisation

• Attention: le RID ne change pas, même si une nouvelle interface

s'active. Les changements n'ont lieu que si le processus OSPF est

réinitialisé (clear ip ospf process)

13

Protocole OSPF sur une architecture de routeurs avec des liaisons point à point

Protocole en 4 phases pour chaque routeur:

1.Découvrir ses routeurs voisins

2.Remplir sa base de données topologiques

3.Elire les routes à utiliser

4.Maintenir sa base de données topologiques

Liaison point à point

8

14


1. Découvrir les routeurs voisins

• Les routeurs OSPF sont bien « élevés »:

— Dès qu'ils sont activés, ils n'ont qu'une hâte : se présenter et faire connaissance avec leurs voisins.

Hello, my name is R1 and I'm an OSPF router

• Lorsque le processus de routage est lancé sur R1 (commande router ospf), des paquets de données (appelés paquets HELLO) sont envoyés sur chaque interface où le routage dynamique a été activé (commande network).

C’est le protocole Hello

• L'adresse multicast 224.0.0.5 est utilisée, tout routeur OSPF se considère comme destinataire. Ces paquets ont pour but de s'annoncer auprès de ses voisins. Deux routeurs sont dits voisins s'ils ont au moins un lien en commun.

15

• Lorsque le processus de routage OSPF est lancé sur R2: — Celui-ci récupère les paquets HELLO émis par R1 toutes les 10 secondes

(valeur par défaut du temporisateur appelé hello interval).

— R2 intègre l’ID de R1 dans une base de données appelée «base d'adjacences» (adjacencies database) ou table des voisins . Cette base contient les adresses des routeurs voisins.

— On peut voir son contenu grâce à la commande show ip ospf neighbor.

— R2 répond à R1 par un paquet IP unicast.

— R1 intègre l’ID de R2 dans sa propre base d'adjacences.

• Ce processus se répète à l'ensemble des routeurs de la zone.

• Cette phase de découverte des voisins est fondamentale puisque OSPF est un protocole à état de liens:

Il lui faut connaître ses voisins pour déterminer s'ils sont toujours joignables et donc déterminer l'état du lien qui les relie.


1. Découvrir les routeurs voisins (suite)

9

16

Paquet OSPF Type1:paquet Hello



17

Etat des interfaces



Etat interface envoyant son

paquet Hello

• Etat interface ayant envoyé son paquet Hello et ayant reçu un paquet

Hello de l’interface d’en face communication bidirectionnelle établie

• Cette état est transitoire dans une liaison point à point et l’interface

passe dans l’état suivant Exstart

10

18

— C’est le routeur qui a le RID le plus élevé (routeur maître) qui envoie en premier sa base de donnée

échange de paquets appelés DBD


2. Remplir la base de données topologiques

• Synchronisation des bases de données initiale

19

échange de paquets appelés LSR et LSU


2. Remplir la base de données topologiques

• Protocole d’échange: obtenir des informations

de routes supplémentaires

11

20


3. Elire les routes à utiliser

• Lorsque le routeur est en possession de la

base de données topologique, il est en

mesure de créer la table de routage.

• L'algorithme du SPF est appliqué sur la

base de données topologiques. Il en

ressort une table de routage contenant les

routes les moins coûteuses.

• Il faut noter que sur une base de données

topologique importante, le calcul consomme

pas mal de ressources CPU car l'algorithme

est relativement complexe.

Base de données

topologiques

21


4. Maintenir la base de données topologique

• Lorsqu'un routeur détecte un changement de l'état d'un lien (cette détection se fait grâce aux paquets HELLO adressés périodiquement par le routeur à ses voisins), celui-ci émet un paquet LSU sur l'adresse multicast 224.0.0.6 qui est rediffusé par les autres routeurs et ainsi de suite

C'est le protocole d'inondation.

• Toute modification de la topologie déclenche une nouvelle exécution de l'algorithme du SPF et une nouvelle table de routage est constituée.

• Donc tout changement de route n’est déclenché que sur une modification de topologie

12

22

Protocole OSPF sur une architecture de routeurs avec des liaisons multidiffusion

Protocole en 5 phases pour chaque routeur:

1.Découvrir les routeurs voisins (même démarche que précédemment)

2.Elire le routeur désigné et le routeur désigné de secours

3.Constituer la base de données topologiques

4.Elire les routes à utiliser (même démarche que précédemment)

5.Maintenir la base de donnée topologique

23

• Le «routeur désigné» (DR) est un routeur particulier qui sert de

référent pour la base de données topologique représentant le

réseau.

• Pourquoi élire un routeur désigné ?

— réduire le trafic lié à l'échange d'informations sur l'état des liens (car il

n'y a pas d'échange entre tous les routeurs mais entre chaque routeur

et le DR),

— améliorer l'intégrité de la base de données topologique (car cette base

de données doit être unique),


2. Elire le routeur désigné et le routeur désigné de secours

13

24



Comment élire le DR ?

• le routeur élu est celui qui a la plus grande priorité (Router ID

ou RID):

— La priorité est un nombre sur 8 bits fixé par défaut à 1 sur tous les

routeurs.

— Pour départager les routeurs ayant la même priorité, celui qui est élu a

la plus grande adresse IP sur une interface de boucle locale (loopback

interface) ou sur un autre type d'interface active.

• Le BDR sera le routeur avec la deuxième plus grande priorité.

• Pour changer la priorité: la commande ospf priority.

— faire ceci avant d'activer le processus de routage sur les routeurs car,

une fois élu, le DR n'est jamais remis en cause même si un routeur

avec une priorité plus grande apparaît dans la zone.

25



Paquet OSPF

14

26

• Protocole d’échange

— Le DR initie l'échange en transmettant aux routeurs un résumé de sa base de données topologique via des paquets de données appelés LSA (Link State Advertisement): – Ces paquets comprennent essentiellement l'adresse du routeur, le

coût du lien et un numéro de séquence. Ce numéro est un moyen

pour déterminer l'ancienneté des informations reçues.

— Si les LSA reçus sont plus récents que ceux dans sa base topologique, le routeur demande une information plus complète par un paquet LSR (Link State Request).

— Le DR répond par des paquets LSU (Link State Update) contenant l'intégralité de l'information demandée.

— le routeur (non DR ou BDR) transmet les routes meilleures ou inconnues au DR.


2. Constituer la base de données topologique

(Link State DataBase ou LSDB)

27


4. Maintenir la base de données topologique

• Lorsqu'un routeur détecte un changement de l'état d'un lien (cette détection se fait grâce aux paquets HELLO adressés périodiquement par le routeur à ses voisins), celui-ci émet un paquet LSU sur l'adresse multicast 224.0.0.6 : le DR et le BDR de la zone se considèrent comme destinataires.

• Le DR et le BDR intègrent cette information à leur base topologique.

• Le DR diffuse l'information sur l'adresse 224.0.0.5 (tous les routeurs

OSPF sans distinction). C'est le protocole d'inondation.

• Toute modification de la topologie déclenche une nouvelle exécution de l'algorithme du SPF et une nouvelle table de routage est constituée.

15

28

Le protocole OSPF Le concept de zone (area)

• Contrairement à RIP, OSPF a été pensé pour supporter de très grands

réseaux.

• Qui dit grand réseau, dit nombreuses routes.

• Afin de rendre moins volumineuses les LSBD (base de données

topologiques) pour faciliter les gestion de celles-ci par les ressources

matérielles du routeur (CPU, mémoire) SPF introduit le concept de

zone (area). Le réseau est divisé en plusieurs zones de routage qui

contiennent des routeurs et des hôtes.

29


• Chaque zone, identifiée par un numéro, possède sa propre topologie et ne connaît pas la topologie des autres zones:

— Une base de données topologiques différente par zone

• Chaque routeur d'une zone donnée ne connaît que les routeurs de sa propre zone ainsi que la façon d'atteindre une zone particulière, la zone numéro 0.

• Toutes les zones doivent être connectées physiquement à la zone 0 (appelée backbone ou réseau fédérateur).

— Elle est constituée de plusieurs routeurs interconnectés.

— Le backbone est chargé de diffuser les informations de routage qu'il reçoit d'une zone aux autres zones.

— Tout routage basé sur OSPF doit posséder une zone 0.

16

30


• Intérêt des zones

— limiter le trafic de routage

— réduire la fréquence des calculs du plus court chemin par l'algorithme SPF ainsi que d'avoir une table de routage plus petite (ce qui accélère la convergence).

• Les routeurs R1 et R4 sont particuliers puisqu'ils sont «à cheval» entre plusieurs zones (on les appelle ABR pour Area Border Router ou routeur de bordure de zone):

— Ces routeurs maintiennent une base de données topologique pour chaque zone à laquelle il sont connectés.

— Les ABR sont des points de sortie pour les zones ce qui signifie que les informations de routage destinées aux autres zones doivent passer par l'ABR local à la zone.

— L'ABR se charge alors de retransmettre les informations de routage au backbone.

• Les ABRs du backbone ensuite redistribueront ces informations aux autres zones auxquelles ils sont connectés.

31

OSPF exemple d’étude

17

32

OSPF les différentes étapes de configuration

1. Configuration des adresse IP des interfaces

2. Activation du routage OSPF

— Router(config)# router ospf process-id

– Process-id entre 1 et 65535

– Signification locale uniquement

– Permet d'avoir plusieurs processus OSPF

33

OSPF les différentes étapes de configuration

3. Définition du réseau

— network adresse wildcard_mask area_id

– adresse : réseau devant être utilisé pour diffuser et écouter

les messages OSPF

– wildcard : l'inverse du masque (255.255.255.255-masque)

– area_id : zone dans laquelle le réseau figure (doit être le

même partout dans la zone)

18

34

Configuration OSPF vérification de la table de routage

• La commande show ip route permet de visualiser les

routes apprises par OSPF

• La lettre O en début de ligne indique que la route a été

apprise par OSPF

35

Configuration OSPF vérification des métriques

• OSPF calcule le coût d'un lien par la formule108 / bande

passante

• Le meilleur route sera la route avec le plus petit coût

• La référence pour la bande passante est 100 Mb/s

— Possibilité de la modifier avec la commande

– auto-cost reference-bandwidth

19

36

Configuration OSPF vérification des métriques

• Le coût total d'une route est la somme des coûts de

chaque lien

37

Configuration OSPF vérification du coût d’un lien

• La commande show interface permet de visualiser la

bande passante définie sur une interface

20

38

Configuration OSPF modification du coût d’un lien

• Les 2 interfaces extrémités d'une liaison série doivent

être configurées avec la même bande passante

— Router(config-if)# bandwidth bandwidth-kbps

• La commande ip ospf cost permet de définir

directement le cout d'une interface

39

Configuration OSPF vérification de la table des voisins

• Visualiser les Neighbor adjacency table

Router# show ip ospf neighbor

• L'absence de voisin est indiquée par

— Une absence de Router ID

— Un état FULL non affiché

• Conséquence d'une absence de voisin

— Aucune information link state ne sera échangée

— L'arbre SPF et les tables de routages ne seront pas justes

21

40

Configuration OSPF visualisation des router ID

Visualiser le Router ID 3 solutions :

— show ip protocols

— show ip ospf

— show ip ospf interface

41

Configuration OSPF configuration de l’interface de loopback

• Le Router ID (RID) est déterminé par soit l'adresse de

loopback, soit par l'adresse IP d'une interface

• Avantage d'utiliser une adresse de loopback

— Une interface de Loopback ne peut pas devenir défaillante

— Apporte une plus grande stabilité à OSPF

— L'administrateur peut «indiquer» le DR

• Pour faire prendre en compte une modification de RID

— Router#clear ip ospf process

22

42

Configuration OSPF la commande ospf priority

• Par défaut la priorité est 1

• Un routeur avec priorité 0 ne sera jamais élu DR

• La plus grande priorité gagne

Router(config)# interface FastEthernet 0/0

Router(interface-config)# ip ospf priority

Documents

Le protocole OSPF - mootse.telecom-st-etienne.fr · 3 4 OSPF Notion de coûts • 5 OSPF Idée de fonctionnement •Un routeur doit: —découvrir ses routeurs voisins (apprendre