TNSI : Le Protocole OSPF
& Protocoles à États de Liens

Repères Historiques

Le protocole OSPF - Open Shortest Path First est un protocole développé au sein de l'IETF - Internet Engineering Task Force à partir de \(1987\). Le groupe de travail OSPF a été formé au sein de l'IETF - Internet Engineering Task Force en \(1987\) pour remplacer RIP. Il est inspiré du protocole ARPANET développé par BBN. En \(1992\), l'IESG - Internet Engineering Steering Group recommande OSPF comme protocole de routage interne (IGP) pour internet (RFC 1371). Il existe une version OSPFv3 (RFC 5340) pour IPv6 (compatible avec IPv4) depuis \(1999\): IPv6 n'étant pas encore totalement adopté par tous les FAI ³ .., nous nous concentrerons sur la version OSPFv2 (RFC 2328) qui utilise IPv4.

Protocoles à États de Liens

Introduction Vidéo

Le protocole OSPF - Open Shortest Path First¹ rentre dans la catégorie plus générale des protocoles à États de Lien.

Claude Chaudet, Maître de Conférence IMT - Institut Mines-Télécom
Protocoles à État de Lien (\(6\) min \(03\)), & Algorithme de Dijkstra (de \(2\) min \(34 \rightarrow\) \(4\) min \(31\) environ)

Comparaison avec Protocoles à Vecteurs de Distance

Rappelons que dans le cas d'un Protocole à Vecteur de Distance (e.g. RIP) de la leçon précédente :

• Un routeur demandait à tous ses voisins directs, à quelle distance il se trouvait de chaque destination
• Il prenait une décision en comparant ces annonces
• On cherchait à minimiser le nombre de sauts, mais sans aucune garantie que le chemin emprunté soit en réalité le plus performant (en termes de débit par exemple).
• Chaque routeur ne connaît que ses voisins directs, donc chaque routeur n'a qu'une connaissance partielle, locale, du réseau (Topologie Locale).
• Aucun routeur n'a une connaissance complète de l'ensemble du réseau (Topologie Globale): Il n'en a pas besoin pour trouver les meilleurs chemins. Comme toute information transmise représente un coût en termes de bande passante, cette stratégie peut s'avérer économique dans certains réseaux
• Enfin, le protocole RIP est limité aux petits réseaux (15 routeurs maximum) et est assez gourmand en termes de bande passante puisqu'il nécessite l'échange d'un volume de données assez important (envoie des tables de routage complètes)

Résumé

Les protocoles à Vecteur de Distance envoient un gros volume d'information (les tables de routage complètes) à ses seuls voisins directs

Protocoles à États de Liens

Le principe général résumé des Protocoles de Routage à États de Liens / Link-State Protocols est différent:

• Chaque routeur commence par déterminer ses propres Voisins et par les stocker dans une Table de Voisins/Voisinage qui contient :
  • les Links / Liens (quels routeurs sont-ils connectés entre eux?)
  • les States / États des liens: qualité des liens (débit, bande passante, etc..)
• Chaque routeur envoie une copie de sa table de voisins à TOUS les routeurs du réseau.
• Chaque routeur a la même connaissance complète du réseau : on parle de Topologie Globale du réseau
• Chaque routeur calcule le plus court chemin (SPF- Shortest Path First) à tous les réseaux connus grâce à l'Algorithme de Dijkstra (\(1959\)). Seule la meilleure route est conservée, les autres sont oubliées.

Analogie avec un GPS

On peut faire un parallèle entre le fonctionnement d'un protocole à état de lien avec les logiciels de guidage par GPS. En effet, dans ce type de logiciels :

• l'ensemble de la carte de France et de ses routes est connue du logiciel
• le type de chaque route est renseigné ainsi que la vitesse autorisée sur la route
• le calcul d'itinéraire va permettre le calcul d'un chemin permettant par exemple d'emprunter les routes sur lesquelles la vitesse est la plus importante (temps le plus court).

Exemples de Protocoles à Etats de Liens

Des exemples classiques de protocoles à États de Liens sont :

• OSPF - Open Shortest Path First ¹ : Au Programme de TNSI
• IS-IS / Intermediate System to Intermediate System (RFC 1195) : PAS au programme de TNSI

Exemples de Débits Théoriques / Bandes Passantes

On peut, approximativement, classer les types de liaison suivant ce tableau de débits théoriques :

Technologie	BP descendante	BP montante
Modem	56 kbit/s	48 kbit/s
Bluetooth	3 Mbit/s	3 Mbit/s
Ethernet	10 Mbit/s	10 Mbit/s
Wi-Fi	10 Mbit/s ~ 10 Gbits/s	10 Mbit/s ~ 10 Gbits/s
ADSL	13 Mbit/s	1 Mbit/s
4G	100 Mbit/s	50 Mbit/s
Satellite	50 Mbit/s	1 Mbit/s
Fast Ethernet	100 Mbit/s	100 Mbit/s
FFTH (fibre)	10 Gbit/s	10 Gbit/s
5G	20 Gbit/s	10 Gbit/s

Principe Général du Protocole OSPF

Introduction Vidéo à OSPF

Le protocole OSPF - Open Shortest Path First rentre dans la catégorie des protocoles à États de Liens.

Claude Chaudet, Maître de Conférence, IMT - Institut Mines-Télécom
OSPF - Open Shortest Path First (\(8\) min \(11\))

Principe Général OSPF

• Chaque routeur commence par déterminer :
  • chacun de ses voisins directs (y compris les sous-réseaux directement connectés), ainsi que
  • la qualité de leur lien, est traduit en termes de coût/métrique (qui tient compte du débit, du délai, de la bande passante, etc.. ou de tout autre critère numérique). OSPF est un protocole qui donne la priorité aux Plus Courts Chemins (SPF - Shortest Path First) (meilleure est la communication, moins ça me coûte)
    Plus grand est le débit/bande passante/qualité de la liaison, plus petit est le coût/métrique. En pratique, on calcule souvent le coût par le quotient d'une constante, par exemple \(10^8\) bits /s (souvent, mais pas tout le temps) par le débit (en bits/s) :

  Exemple de Calcul du Coût en fonction du Débit

  \(Coût = \dfrac {10^8 \,\, (b/s)}{débit \,\, (b/s)} = \dfrac {100 \,\, (Mb/s)}{débit \,\, (Mb/s)}\) \(\,\) où \(Mb/s =\) Méga bits par seconde

  Cela revient à prendre un coût \(=1\) pour un débit de \(100 \,Mb/s\).

• Pour cela, Périodiquement toutes les \(10s\) (dans les réseaux muti-accès ou point-à-point, ou bien toutes les \(40s\) dans les réseaux NBMA): OSPF envoie des messages souvent appelés des messages Hello, car ils ne contiennent pas beaucoup plus d'information qu'un simple bonjour. Les messages Hello sont envoyés en multicast sur 224.0.0.5 (AllSPFRouteurs) en IPv\(4\) ou FF02::5 en IPv\(6\).
• Au bout d'un certain temps le routeur aura identifié tous ses voisins directs grâce à ces paquets Hello: Chaque routeur commence donc par se construire sa propre Table des Voisins/Voisinage (les links/liens) contenant également la qualité/coût de chaque lien.

• Ensuite Chaque routeur envoie sa Table des Voisins, à TOUS les routeurs du réseau (et non pas seulement à ses voisins directs, comme pour les protocoles à Vecteurs de Distance). Plus précisément, chaque routeur envoie sa table de voisins par des messages LSP - Link-State Packets / Paquets d'États de Liens , eux mêmes subdivisés en LSA - Link-State Advertisements / Annonce des États de Liens , à tous ses voisins, qui le retransmettent de proche en proche à tous leurs voisins (s'ils ne l'ont pas déjà vu passer) jusqu'à inonder tout le réseau de LSAs (principe appelé flooding). Pour transmettre ses Tables de Voisins à tous les routeurs du réseau, (chaque routeur) OSPF utilise \(4\) Types de messages ou Types de paquets LSP. Périodiquement :

  • Les paquets DBD - DataBase Description contiennent un résumé de la Base de Données LSDB, càd le nom de tous les routeurs connus (le nom d'un routeur est souvent l'adresse IP de l'une de ses interfaces: en général, on choisit la plus grande). Lorsqu'un routeur \(R2\) apprend l'existence d'un nouveau routeur \(R1\) (qu'il ne connaît pas encore), grâce à la réception d'un tel paquet DBD, alors \(R2\) demande spécifiquement à l'émetteur \(R1\) du paquet de lui en dire plus, en lui envoyant une requête via un paquet LSR:
  • Un paquet LSR - Link-State Request est une demande d'information supplémentaire. Le nouveau routeur \(R1\) reçoit la requête de \(R2\), et lui répondra par un paquet LSU de mise à jour/update.
  • Un paquet LSU - Link-State Update est un paquet qui contiendra les informations détaillées du nouveau routeur (\(R1\)) pour mettre à jour la base de Données LSDB du demandeur (\(R2\)). Ces informations détaillées contiennent les liens du nouveau routeur \(R1\), ainsi que la qualité/coût des liens qui le relie (\(R1\)) aux autres routeurs. Le routeur \(R2\) reçoit le paquet LSU d'Update et envoie un paquet de bonne réception LSAck à \(R1\)
  • Un paquet LSAck - Link-State Acknowledgement est un paquet de bonne réception (du LSU): On dira que le routeur (\(R2\)) acquitte la bonne réception (du paquet LSU). La transmission des messages de description de la cartographie complète du réseau sont donc fiables.

• Chaque routeur conserve le paquet LSP le plus récent (reçu de la part de chaque autre routeur), et se crée ainsi une base de données LSDB - Link-State DataBase, modélisant la cartographie complète de tout le réseau : TOUS les routeurs du réseau disposeront donc des mêmes informations (Topologie Globale)

• Ensuite Chaque routeur calcule par ses propres moyens (puissance CPU, RAM) le meilleur chemin (à coût minimum ou shortest path), depuis lui-même vers toute destination du réseau: OSPF est un Protocole Distribué. Pour cela, Les protocoles à état de lien utilisent en général l'Algorithme de Dijstra (\(1959\)).
• Complexité des Adjacences et DR/BBR : Dans certains réseaux, le volume de trafic de contrôle généré par ce processus risque d'être important, en particulier: Plus le nombre \(n\) de routeur augmente, plus le nombre de messages Hello et d'Annonces DBD augmentera. Pour limiter cette charge, les routeurs OSPF ont l'option d'élire un routeur particulier que l'on appellera un DR - Designated Router / Routeur Désigné qui sera en charge de recevoir l'ensemble des informations brutes transmises par les routeurs, et de les disséminer tels quels ensuite. Il reviendra alors à chaque routeur d'effectuer ses propres calculs.
  • L'élection du DR est effectuée au moyen des paquets Hello:
    • On définit d'abord un critère, permettant de comparer deux routeurs candidats pour devenir un DR.
    • Le plus souvent, on choisit les ID des routeurs, càd leurs noms: le plus grand ID est gagnant sur le plus petit
    • Chaque paquet Hello contient alors l'identité du routeur de celui qu'il estime être le DR
    • Un routeur recevant un paquet Hello, avec un meilleur DR tiendra compte de cette information en remplaçant son ancien DR, et il changera lui-même ses propres annonces
    • Au bout d'un certain temps, tous les routeurs du réseau auront identifié le même DR
  • On élit également un BDR - Backup Designated Routeur / Routeur Désigné de Secours/de Sauvegarde au cas où le DR tombe en panne
• Areas / Aires / Zones: OSPF est un protocole supportant une mise à l'échelle, qui fontionne aussi bien dans les petits réseaux que dans les grands. Pour cela, OSPF permet de diviser un grand réseau en plusieurs petits réseaux appelés des Areas / Aires / Zones . Il revient à l'Administrateur réseau de déterminer la composition des aires: Quel routeur appartient à quelle aire?
  Une fois le réseau subdivisé en aires, OSPF s'exécutera indépendamment dans chacune des aires, comme s'il s'agissait de réseaux distincts.
  

Des routeurs placés à la frontière de chaque aire devront alors se synchroniser entre eux, pour échanger des informations permettant de calculer des routes dans le réseau global. Pour cela, les routeurs situés à la frontière de chaque aire, construisent une nouvelle aire particulière appelée Backbone / Épine Dorsale . Cette division permet de limiter le nombre de récepteurs concernés par chaque émission, ainsi que la taille de la Base de Données des Liens LSDB gérée par chaque routeur. Il s'agit d'une technique classique consistant à diviser un problème en sous-problèmes indépendants, pour en réduire la complexité.

• En cas de changement de topologie du réseau (comme la perte de connectivité sur une interface) :
  • de nouveaux paquets d'états de liens (LSP) sont instantanément diffusés à tout le réseau..
  • Tous les routeurs recalculent leur table de routage
• La Convergence est assez rapide : le facteur limitant étant le nombre des routeurs car il est nécessaire de:
  • acquérir les voisins de chacun d'entre eux, avant de pouvoir
  • transmettre leurs table de voisinage à chaque routeur
  • calculer finalement les meilleures routes

Résumé

Les protocoles à États de Liens envoient de petits paquets, contenant assez peu d'informations, mais doit les envoyer à tous les routeurs du réseau

Il n'y a pas dans l'absolu de meilleure stratégie (par rapport aux protocoles à Vecteurs de Distance), tout dépend du réseau auquel on a affaire, et du critère sur lequel on se base: un protocole pourra être plus réactif au changement de topologie (état de liens), mais au prix d'un plus gros trafic.

Le Protocole OSPF Détaillé

Liens & États de Liens

États & Liens

• un Link / Lien désigne une interface connectée du routeur
• un Link-State / État de Lien est une description de (l'état de) cette interface et la relation qu'elle entretient avec ses routeurs voisins : par ex. son adresse IP, le masque, le type de réseau connecté (la qualité du lien), les voisins (routeurs connectés), etc..

Base de Données LSDB - Link-State DataBase

Définition LSDB

Base de Données LSDB - Link-State DataBase

• Pour permettre à chaque routeur de découvrir son voisinage, et de le disséminer à tous les autres routeurs, OSPF se charge de créer et maintenir une Base de Données propre à chaque routeur, nommée LSDB - Link-State DataBase / Base de Données des États de Liens , ou quelquefois Topological Table / Table Topologique
• C'est la LSDB qui sera transmise à TOUS les autres routeurs du réseau (de l'aire)
• Cette Base de Données LSDB contient l'ensemble de la cartographie complète du Réseau:
  • L'ensemble des routeurs composant le réseau
  • L'ensemble des Liens entre ces routeurs
    (quels routeurs sont-ils connectés entre eux?)
  • la Qualité/Coût de leur connexion (en termes de la métrique choisie)
• Une LSDB est subdivisée en plusieurs LSA - Link-State Advertisements, qui peuvent être vues comme des unités d'informations thématiques de la LSDB. Ce sont ces LSA, petites briques élémentaires thématiques de la LSDB, qui sont envoyées commes annonces via le réseau, pour synchroniser entre elles les différentes LSDB des routeurs, via certains types de messages (voir le & Types de messages OSPF)

Gestion de la LSDB

Gestion de la LSDB

• Création et Maintien des Adjacences: Chaque routeur crée et maintient (mises à jour) sa Base de Données LSDB petit à petit grâce à la réception de :
  • Type \(1\) : Paquets de contrôle / Paquets Hello, (en tenant compte de ses propres voisins)
• Synchronisation Périodiquement, chaque routeur synchronise sa base LSDB petit à petit, depuis d'autres routeurs, grâce à la réception de:
  • Type \(2\) : Paquets DBD - DataBase Description
  • Type \(3\) : Paquets LSR - Link-State Request
  • Type \(4\) : Paquets LSU - Link-State Update
  • Type \(5\) : Paquets LSAck - Link-State Acknowledgement

Utilisation de la LSDB

De manière pratique et ultime, Chaque routeur utilise sa LSDB et l'Algorithme de Dijkstra (\(1959\)) pour construire la Table de Routage du routeur.

LSA - Link-State Advertisement

Définition d'un LSA

Nous avons dit que l'ensemble des états de liens d'un routeur forme sa LSDB - Link-State DataBase / Base de Données à État de Liens: La LSDB est propre à chaque routeur, stockée sur chaque routeur. Elle est amenée à être synchronisée avec tous les autres routeurs du réseau (en fait de l'aire). La LSDB peut être volumineuse: pour être transmise aux autres routeurs du réseau, elle est classiquement subdivisée en petites unités élémentaires d'informations de routage, thématiques appelées les LSA - Link-State Advertisements / Annonces des États de Liens .

Annonces des États de Liens / LSA - Link-State Advertisement

Le protocole OSPF envoie des LSA - Link-State Advertisements / Annonces d'État des Liens qui sont des unités élémentaires d'informations de routage,thématiques, à la base de toute communication entre routeurs OSPF.

Utilisation des LSA

Les informations de routage LSA sont utilisées, lors de différents types de messages(/paquets) OSPF / LSP - Link-State Packets, notamment pour :

• créer une relation d'adjacence entre routeurs
• synchroniser les LSDB

Entête / Header d'un LSA

0               1               2               3                
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7  
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|             LSAge             |    Options    |    LSType     |
+---------------+---------------+---------------+---------------+
|                         Link-State ID                         |
+-------------------------------+-------------------------------+
|                       Advertising Router                      |
+-------------------------------+-------------------------------+
|                      LS Sequence Number                       |
+-------------------------------+-------------------------------+
|   Checksum / Somme Contrôle   |            Length             |
+-------------------------------+-------------------------------+

Chaque ligne¹¹ prend \(4\) octets \(= 32\) bits, donc l'entête/header d'un LSA prend en tout \(5 \times 4\) octets \(=20\) octets.

où:

• LSAge : est le délai écoulé, en secondes, après la création du LSA
• Options :
  • E: les LSA de Type \(5\) sont inondés/flooded
  • MC : diffusion multicast
  • N/P: LSA de type 7 sont traités/processed
  • DC : les Liens On-Demand sont traités
• LS Type : numéro de type LSA (entier entre \(1\) et \(7\))
• Link-State ID (LSID) : décrit le LSA dans l'AS: en général une IP
• Advertising Router : L'ID du Routeur source/émetteur du LSA
• LS Sequence Number : Un numéro de séquence (une numérotation) des LSA: Au départ 0x80000001, maximum : 0x7fffffff. Des routeurs voisins peuvent utiliser cette numérotation pour identifier le tout dernier LSA
• LS Checksum / Somme de Contrôle: pour vérifier l'intégrité du LSA (tout sauf le champ LSAge)
• Length : Longueur du LSA, entête inclue, en octets

Types de LSA

OSPF utilise des Annonces des États de Liens ou LSA - Link-State Advertisements pour communiquer entre routeurs OSPF. Il existe plusieurs types d'annonces LSA qui sont utilisées dans les différents types de paquets OSPF. Ces annonces sont stockées dans une Base de Données LSDB - LSDB - Link-State DataBase.

Par exemple, un routeur envoie un packet Hello pour créer et maintenir (mises à jour) une relation de voisinage avec ses voisins (routeurs OSPF). Les autres types de packets vont être utile pour syncrhoniser (mettre à jour et maintenir) la LSDB (Link-State Database).

Il existe plusieurs types d'Annonces LSA ⁵ :

Numéro du Type LSA	Type LSA
1	Router
2	Network
3	Summary
4	Summary ASBR
5	Autonomous System External
6	Multicast OSPF
7	Not-So-Stubby Area (NSSA)
8	External Attribute LSA for BGP

Pour être complet, il faudrait dire qu'il existe \(11\) types d'annonces LSA dans OSPF... (Voir référence⁷)

LSA Type \(1\) : Router

Le LSA Type \(1\) est généré par tous les routeurs d'une même zone/area pour informer les autres routeurs de cette même area des liens qui sont directement connectés à lui. Ce sont les routes intra-area. Dans votre table de routage, la route sera précédée de la lettre O. Autorise sur toutes les aires OSPF.

LSA Type \(2\) : Network

Le LSA Type \(2\) est généré par le DR (Designated Router) pour lister tous les routeurs adjacents dans une area. Il renseigne le champ LSID (Link State Identifier ) qui correspond à l'adresse IP RID dans un premier temps, si celle-ci est absente, il se basera sur l'interface loopback de votre routeur et si celle-ci est elle aussi absente, ce sera l'adresse IP la plus grande de l'interface de votre routeur. Autorisé sur toutes les aires OSPF.

LSA Type \(3\) : Network Summary

Le LSA Type \(3\) est généré par un routeur ABR (Area Border Router, routeur qui fait la correspondance entre votre area \(0\) -backbone- et les autres areas) pour délivrer ses routes resumés par lui même. Le type 3 fonctionne sur toutes les aires OSPF sauf pour les aires totally stub et totally NSSA stub. Lorsqu'une route traverse un routeur ABR, la route est connue comme une route intra-area. Dans votre table de routage, la route sera précédée par inter-area ou O IA pour OSPF Inter-Area.

LSA Type \(4\) : ASBR Summary

Le LSA Type \(4\) est généré par un routeur ASBR (Autonomous System Boundary Router, routeur connecté directement à votre ISP) et est injecté dans la backbone area par les routeurs ABR pour avertir de la présence de routeur ASBR dans cette area. Autorisé dans toutes les aires OSPF sauf pour les aires totally stub et totally NSSA stub, il décrit les routes aux ASBRs (résumé interarea des routes).

LSA Type \(5\) : AS External

Le LSA Type \(5\) est généré par un routeur ABR qui va flooder toutes les aires pour indiquer qu'il connait une route externe (redistribuée d'un autre protocole par exemple). Il fonctionne pour tout le domaine OSPF sauf pour les aires stub, totally stub, NSSA, totally NSSA.

LSA Type \(6\) Group Membership

Le LSA Type \(6\) n'est pas supporté par les routeurs Cisco. Il est défini pour MOSPF.

LSA Type \(7\) : NSSA External

Le LSA Type \(7\) est généré par un routeur ASBR pour remplacer le LSA de type \(5\) dans le cas où vous disposez d'une aire NSSA ou totally NSSA. Les routes seront donc connues comme NSSA externe de type \(1\) ou \(2\). Dans votre table de routage, vos routes seront précédées de O N1 et O N2.

Gestion des LSA

• Les LSA sont ré-émis toutes les \(30\) minutes (LSRefreshTime)
• Un LSA plus ancien que MaxAge n’est plus utilisé pour le calcul SPF
• Numéro de séquence : au départ 0x80000001, maximum : 0x7fffffff
• LSAge est incrémenté à chaque retransmission lors de l’inondation.

Types de Messages OSPF & leurs Formats

messages Multicast & Unicast

Un protocole à vecteur de distance comme RIP (ou IGRP) utilise aveuglément le Broadcast ou le Multicast en envoyant par chaque interface la table de routage complète toutes les 30 secondes (par défaut).

Par opposition, pour construire leurs routes, les routeurs OSPF entretiennent des relations de voisinage et s’échangent toute une série de types de messages différents pour:

• identifier leurs voisins
• mettre à jour les informations de routage à état de lien (LSDB)

Pour cela, OSPF utilise l’Unicast (pour l'acquittement) et deux adresses Multicast pour livrer ces messages :

• 224.0.0.5 (AllSPFRouters), ou FF02::5 en IPv6: TOUS les routeurs OSPF écoutent sur cette adresse multicast
• 224.0.0.6 (AllDRouters), ou FF02::6 en IPv6, Tous les routeurs DR/BDR OSPF écoutent sur cette adresse multicast

Types de Messages OSPF

Il existe \(5\) Types de messages OSPF, correspondant chacun à un numéro entier:

Numéro du Type Message	Type Message	A quoi sert-il?
\(1\)	Paquet Hello	Établit et maintient les informations d'adjacence/contigüité (adjacency information) avec les voisins.
\(2\)	DBD - DataBase Description	Décrit le contenu des Bases de Données des États des Liens LSDB - Link-State DataBase des routeurs OSPF: En fait, Description contenue dans des LSA.
\(3\)	LSR - Link-State Request	Demande/Requête des éléments spécifiques des Bases de Données d’État de Liens LSDB - Link-State DataBase aux routeurs OSPF: En fait, Requête via un LSA
\(4\)	LSU - Link-State Update	Mise à jour de la LSDB des routeurs voisins. En fait, les màj sont envoyées dans des LSA. Un LSU peut contenir plusieurs LSA - Link-State Advertisements
\(5\)	LSAck - Link-State Acknowledgement	LSA d'Accusé de réception (=Acquittement) des voisins.

Quel Type de message pour quelle utilisation?

• Le Type 1 (messages Hello) est utilisé pour l'établissement et le maintien des adjacences,
• les autres Types sont utilisés pour la synchronisation de la LSDB.

Entête / Header des messages OSPF

Les \(5\) types de paquets OSPF ont le même Entête-Header ( RFC 2328, page 189)

0               1               2               3                
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7  
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version Number|  Message Type |     Packet Length (octets)    |
+---------------+---------------+---------------+---------------+
|                    Source OSPF Router ID                      |
+-------------------------------+-------------------------------+
|                       Area ID / ID de Zone                    |
+-------------------------------+-------------------------------+
|     Checksum / Somme Contrôle |     Authentification Type     |
+-------------------------------+-------------------------------+
|                     Authentification Data                     |
+---------------------------------------------------------------+
|                     Authentification Data                     |
+---------------------------------------------------------------+

Chaque ligne prend \(4\) octets \(=32\) bits, donc l'entête /header complet prend \(6\times 4\) octets \(=24\) octets.

où l'on a posé :

• Version Number est le Numéro de Version du protocole OSPF : \(2\) pour OSPFv2 (\(3\) pour OSPFv3)
• Message Type est le Type de Message du paquet sous forme d'un entier de \(1\) à \(5\) inclus (cf le § Types de Messages OSPF)
• Packet Length est la Longueur du Paquet (en octets), y compris l'entête. Un paquet OSPF peut peser jusqu'à \(65\)Ko.
• RID - Router ID ou Source OSPF Router ID est un IDentifiant unique de \(32\) bits du routeur source, dans l'AS - Système Autonome. En pratique, pour déterminer le RID, OSPF chosit dans l'ordre:
  • Configuration Manuelle (si elle existe)
  • Plus grande/haute adresse IP sur une interface de Loopback (si elle existe)
  • Plus grande/haute adresse IP sur une interface physique (non-loopback) (dans tous les autres cas)
• Area ID (sur 32 bits): un IDentifiant unique de l'entité logique (contenant ce routeur) appelé Area / Zone : ce sont des retroupements logiques de routeurs. Notation de l'Area ID: Décimale 0 ou décimale pointée 0.0.0.0
• Checksum / Somme de Contrôle vérifie l'intégrité du paquet: y-a-t-il eu des erreurs de transmission? et tentative de correction: et si oui (des erreurs) lesquelles?
• Authenticaton Type ⁴ est le Type d'Authentification: en pratique un entier avec une signification standard:

Authentication Type	Signification
\(0\)	No Authentication
\(1\)	Simple Password Clear Text Mot de Passe en Texte Clair
\(2\)	MD5
AUK	Si vous activez l'authentification Vous verrez des infos ici

• Authenticaton Data sont les Données d'Authentification, sur \(8\) octets \(=64\) bits. Par exemple: le mot de passe en clair... dans le cas où : Authentification Type \(=1\)...

Exemples

• Capture de Paquet OSPF avec Authentification Simple (Mot de Passe en Clair), Cloudshark
• Capture de Paquet OSPF avec Authentification MD5, Cloudshark
• Capture d'un Paquet OSPF avec Vérification de Sécurité TTL, sur Cloudshare
• Autres Exemples de Captures OSPF, sur Packetlife.net

Type \(1\) : Paquet Hello

Quand/Pour quoi sont-ils utilisés?

Quand un routeur commence un processus de routage OSPF sur une interface, il envoie périodiquement des paquets Hello :

• Toutes les \(10s\) (Hello Interval) par défaut sur un réseau multi-accès et point à point, ou bien,
• Toutes les \(30s\) sur un réseau NBMA¹⁰ (Non Broadcast Multi Access: type de réseau à relayage direct -unicast- entre deux hôtes sans besoin de diffusion/broadcast).

Les routeurs OSPF utilisent ces paquets Hello pour initier de nouvelles adjacences (jusqu'à l'état two-way state) et pour s’assurer que les routeurs voisins sont et restent fonctionnels. Ces paquets Hello sont plus particulièrement utilisés dans les états de voisinage Init et Two-way.

À la Couche \(3\) du modèle OSI, les paquets Hello sont adressés en multicast 224.0.0.5 (ou FF02::5 en IPv6). Ces adresses correspondent à “Tous les routeurs OSPF” / AllSPFRouters .

Dans un réseau multi-accès, c'est le protocole Hello qui élit un DR et un BDR.

Charge Utile du paquet Hello

Un paquet Hello transporte des informations (dans sa partie Charge Utile) que tous les voisins doivent agréer avant qu’une adjacence ne soit formée et avant que les informations d’état de lien ne soient échangées. Les délais configurés sur les interfaces doivent également correspondre : autrement le processus d’adjacence ne peut pas continuer. Sa charge utile est ( RFC 2338, page 193-194 ) :

0               1               2               3                
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7  
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                              ...                              |
|                 Entête / Header OSPF (24 octets)              |
|                              ...                              |
+-------------------------------+-------------------------------+
|                Network Mask / Masque Sous-Réseau              |
+---------------+---------------+---------------+---------------+
|         Hello Interval        |      Options  |Router Priority|
+-------------------------------+-------------------------------+
|                      Router Dead Interval                     |
+-------------------------------+-------------------------------+
|                       Designated Router                       |
+-------------------------------+-------------------------------+
|                   Backup Designated Router                    |
+-------------------------------+-------------------------------+
|                      Neighbor / Voisin                        |
+-------------------------------+-------------------------------+
|                              ...                              |

où l'on a posé :

• Entête / Header, à \(24\) octets, a été décrit ci-dessus
• Network Mask / Masque de Sous-Réseau: le masque de sous-réseau associé à l'interface. Par exemple un masque 255.255.255.0 sera écrit en hexadécimal 0xffffff00
• Hello Interval / Intervalle Hello est le nombre de secondes entre deux envois de paquets Hello (sur les réseaux Ethernet et les liaisons point à point). Par défaut : \(10s\) (Dans le cas très particulier des NBMA -Frame Relay-, cette durée vaut \(30\) secondes).
• Options sont des Options de protocole OSPF: E-bit, MC- bit,... (see A.2 of RFC 2328)
• Router Priority / Priorité du Routeur: Un entier utilisé pour l'élection du DR et du BDR. Si la valeur vaut 0, alors ce routeur sera inéligible pour devenir un DR (resp. un BDR).
• Router Dead Interval est le nombre de secondes avant qu'OSPF déclare “dead/down/mort” un routeur silencieux. Par défaut : \(4\) x le délai Hello \(=4\times 10\) sec \(= 40\) sec (resp. \(120\) secondes en NBMA). Cela veut dire que l'on peut perdre \(4\) paquets Hello avant que le lien ne soit déclaré invalide par OSPF.
• Designated Router / Routeur Désigné : L'ID du Router Désigné (càd l'adresse IP de son interface) sur le réseau, par rapport au routeur émetteur (Advertising Router). Au cas où il n'y ait PAS (encore?) de DR, cette valeur est fixée à : 0.0.0.0
• Backup Designated Router / Routeur Désigné de Sauvegarde : L'ID du Router Désigné de Secours/de Sauvegarde (càd l'adresse IP de son interface) sur le réseau, par rapport au routeur émetteur (Advertising Router). Au cas où il n'y ait PAS (encore?) de BDR, cette valeur est fixée à : 0.0.0.0
• Neighbor / Voisin: La Liste des Voisins (un voisin par ligne "Neighbor/Voisin") : Chaque ligne désigne le Routeur ID (son "nom") de chaque routeur dont on a vu passer récemment sur le réseau, des paquets Hello valides.Récemment voulant dire depuis moins de DeadInterval secondes (du routeur)

Type \(2\) : Paquet DBD - DataBase Description

Les paquets DBD - DataBase Description contiennent un résumé de la Base de Données LSDB, sous forme de ses composants élémentaires LSA. Ils sont diffusés périodiquement.

Utilisation d'un paquet DBD

Ce sont des paquets OSPF de Type \(2\). Ils sont utilisés lors de l'initialisation du processus d'ajacence de deux routeurs : cf le § Voisinage & Adjacence. Les paquets DBD décrivent le contenu de la Base de Données LSDB, sous forme de plusieurs paquets contenant des LSA. Pour cela, au moment de l'état ExStart, une procédure de poll/response (sondage/réponse) est engagée:

• L'un des routeurs est désigné comme Maître (celiu ayant la Routeur ID -une IP- la plus grande en général)
• L'autre routeur est désigné comme Esclave

Les routeurs entrent alors dans l'état Exchange.

Le maître envoie des paquets DBD (polls/sondages) et l'esclave acquitte (répond) par des paquets DBD (responses/réponses). Les réponses sont numérotées par paramètre DD Sequence Number. Chacun des routeurs peut donc comparer la base de données de liens (LSDB) de l'autre dans les détails : Chacun des routeurs compare les informations qu’il reçoit avec ce qu’il sait déjà.

Si des DBDs annoncent des nouveaux états de lien ou des mises à jour d’état de lien, le routeur qui les reçoit entre alors en état Loading et envoie des paquets LSR - Link-State Request (Type 3) à propos des nouvelles informations.

(Header et) Charge Utile d'un paquet DBD

Ces descriptions admettent la charge utile suivante ( RFC 2328, page 195 ) :

0                   1                   2                   3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                              ...                              |
|                 Entête / Header OSPF (24 octets)              |
|                              ...                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|         Interface MTU         |    Options    |0|0|0|0|0|I|M|MS
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                     DD sequence number                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
+-                                                             -+
|                                                               |
+-                Un Entête LSA / An LSA Header                -+
|                                                               |
+-                                                             -+
|                                                               |
+-                                                             -+
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                              ...                              |

où

• Interface MTU - Maximum Transmission Unit / MTU de l'Interface : est le plus grand nombre d'octets du datagram IP pouvant être envoyé sur l'interface associée, sans devoir utiliser la fragmentation.
• Options sont des Options.. (décrites ici)
• DD Sequence Number : est un numéro de séquence (une numérotation) des paquets DD
• An LSA Header / Un entête LSA: contient l'entête d'un LSA (uniquement). Le ou les LSA (des éléments de la LSDB) seront inclus dans le LSU.

Type 3 : Paquet LSR - Link State Request

Utilisation

Ce sont des paquets OSPF de Type \(3\). Ils sont utilisés lors de l'initialisation du processus d'ajacence de deux routeurs : cf le § Voisinage & Adjacence. Après l'échange de paquet DBD avec l'un de ses voisins, un routeur (dans l'état Loading) peut se rendre compte que des parties de sa Base de Données LSDB est obsolète. Le paquet LSR - Link-State Request est alors utilisé pour demander/requêter une mise à jour des parties de la LSDB de l'autre routeur qui sont plus récentes (que celles qu'il connaît). Il arrive usuellement que l'envoi de plusieurs LSR soient necéssaires.

L’autre routeur enverra des informations complètes de ses états de lien des paquets LSU - Link-State Update (Type 4).

(Header et) Charge Utile d'un paquet LSR

Ces descriptions admettent la charge utile suivante ( RFC 2328, page 197 ) :

0                   1                   2                   3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                              ...                              |
|                 Entête / Header OSPF (24 octets)              |
|                              ...                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                          LS type                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       Link State ID                           |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                     Advertising Router                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                              ...                              |

Chaque LSA demandé est spécifié par:

• LS Type / Type de LS: le Type du LSA, nous avons dit qu'il en existait \(11\).
• LSID / Link-State ID / ID de l'État de Liens :
  • Si elle existe, une configuration manuelle
  • si celui-ci est absent, ce sera la plus grande/haute adresse IP sur une interface loopback durouteur. Rappel : une interface loopback = une interface logicielle de l'OS du routeur
  • si celle-ci aussi est absente, ce sera l'adresse IP la plus grande parmi les interfaces de votre routeur.
• Advertising Router est le Routeur émetteur

Type 4 : Paquet LSU - Link State Update

Utilisation

Ce sont des paquets OSPF de Type \(4\). Ils sont utilisés lors de l'initialisation du processus d'ajacence de deux routeurs : cf le § Voisinage & Adjacence. Ces paquets implémentant l'inondation (flooding) des LSAs. Chaque paquet LSU transporte une collection de plusieurs LSA, situés à un hop/saut au delà de leur origine.

Les LSUs transportent des états de lien, sous forme de LSAs.

Les routeurs acquittent (accusent la bonne réception des) les LSUs en envoyant des paquets LSAck - Link-State Acknowledgement (Type 5), qui contiennent une correspondance aux numéros de séquences envoyés dans les LSAs.

(Header et) Charge Utile d'un paquet LSU

Ces descriptions admettent la charge utile suivante ( RFC 2328, page 199 ) :

0                   1                   2                   3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                              ...                              |
|                 Entête / Header OSPF (24 octets)              |
|                              ...                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|          Nombre de LSAs / Number of LSAs / # LSAs             |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
+-                                                            +-+
|                             LSAs                              |
+-                                                            +-+
|                              ...                              |

où

• # LSAs : c'est le Nombre de LSAs inclus dans ce paquet LSU
• plusieurs LSAs sont inclues dans le corps du paquet LSU
• Chaque LSA commence par son entête LSA de \(20\) octets

Type 5 : Paquet LSAck - Link State Acknowledgment

Utilisation

Ce sont des paquets OSPF de Type \(5\). Ils sont utilisés lors de l'initialisation du processus d'ajacence de deux routeurs : cf le § Voisinage & Adjacence.

Les routeurs acquittent (accusent la bonne réception des) les LSUs en envoyant des paquets LSAck - Link-State Acknowledgement (Type \(5\)), qui contiennent une correspondance aux numéros de séquences envoyés dans les LSAs.

Quand l’état Loading est terminé, les routeurs entrent en Full Adjacency. Il faudra qu’ils entrent dans cet état avant de créer leur table de routage et de router le trafic. À ce moment, les routeurs d’une même zone ont une base de données d’état de lien identique.

(Header et) Charge Utile d'un paquet LSAck

Ces descriptions admettent la charge utile suivante ( RFC 2328, page 201 ) :

0                   1                   2                   3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                              ...                              |
|                 Entête / Header OSPF (24 octets)              |
|                              ...                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
+-                                                             -+
|                                                               |
+-                Un Entête LSA / An LSA Header                -+
|                                                               |
+-                                                             -+
|                                                               |
+-                                                             -+
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                              ...                              |

où

• L'Entête / Header LSA correspond au LSA qui est acquitté (dont on accuse bonne réception).

Encapsulation de paquets OSPF

OSPF, comme tous les protocoles de routage dynamiques, opère sur la couche Application du modèle TCP/IP, même si OSPF est encapsulé directement sur le protocole IP ( RFC 2328, page 184 ). Les paquets OSPF sont encapsulés uniquement par le protocole IP (numéro 89) et par des Entêtes de messages OSPF. OSPF utilise son propre protocole, en particulier : le protocole OSPF n'utilise PAS de protococole de transport comme TCP, ou UDP. OSPF est néanmoins fiable (de manière remarquable, il n'a pas besoin d'utiliser TCP pour cela).

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   Entête Trame / Frame Header   |    Entête IP / IP Header   |   paquet OSPF   |   Charge Utile / Payload   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

OSPF ne définit pas la manière dont doivent être fragmentés ses paquets OSPF, si bien que la fragmentation OSPF est basée sur la fragmentation IP pour transmettre des paquets dont la taille est supérieure au MTU - Maximum Transmission Unit du réseau (le MTU est la taille maximale d'un paquet pouvant être transmis en une seule fois, sans fragmentation).
En cas de besoin, la longueur/taille des paquets OSPF peut aller jusqu'à \(65\,535\) octets, y compris la longueur/taille de l'entête IP.
Les Types de paquets OSPF qui sont potentiellement grands sont les suivants (tous sauf les paquets Hello - Type 1):

• les paquets DBD - DataBase Description Packets,
• LSR - Link-State Requests,
• LSU - Link-State Update,
• LSAck - Link-State Ackonowledgment

Ces \(4\) types de paquets OSPF potentiellement grands peuvent usuellement être divisés en plusieurs paquets de protocole OSPF, sans perte de fonctionnalité. Il est recommendé d'éviter la fragmentation IP tant que possible (il est recommendé en particulier que la taille des paquets OSPF envoyés via des liens virtuels ne dépasse pas 576 octets, sauf si on utilise la méthode du Path MTU Discovery est en cours d'utilisation)

Voisinage & Adjacence

C'est quoi être Voisins ?

Chaque interface d'un routeur appartient à des sous-réseaux différents: un routeur peut donc être vu comme l'élément matérialisant la frontière entre plusieurs sous-réseaux. Le routeur lui-même faut partie de chacun de ses sous-réseaux.

Routeurs Voisins

Deux routeurs sont dits voisins l'un de l'autre lorsqu'ils appartiennent à un même sous-réseau

Des interfaces de routeurs voisins peuvent être:

• soit connectés directement par un câble
• soit séparés par (un réseau composé uniquement) de.s switchs (couche \(2\) du modèle OSI)

États de Relation

Être voisins n'est pas à proprement parler un état de relation entre des routeurs.
Il existe plusieurs (états de) relations entre voisins⁴, dont deux qui sont abouti.e.s :

• Two-way State / Double Sens: \(1\)ère relation aboutie, la plus basique/simple
• Full Adjacency / Adjacence Complète: \(2\)ème relation aboutie, la plus complète

Les autres (états de) relation intermédiaires servent de transitions pour mener vers ces états abouti.e.s.

État des Liens	Signification
Down	Pas de voisins détectés pour le moment
Init	Paquets Hello reçus
Two-way	Réception de son propre nom (ID) dans le champ voisin du paquet Hello réponse
Exstart	Rôles master/slave maître/esclave déterminés
Exchange	Envoi de paquets DBD - DataBase Description
Loading	Échange des paquets LSR - Link-State Requests et LSU - Link-State Update
Full	Les routeurs OSPF ont maintenant une adjacence établie

Two-Way State

La question ici est de comprendre comment fait OSPF pour qu'un nouveau routeur découvre ses voisins directs, puis pour établir une relation aboutie (d'abord Two-Way State, puis Adjacence) avec des routeurs voisins.

Le processus de découverte et de validation des états de ses voisins directs se fait grâce notamment à des messages/paquets Hello (mais pas exclusivement), qui sont envoyés périodiquement sur chaque sous-réseau auquel le routeur est connecté, sur l'adresse multicast 224.0.0.5 (AllSPFRouters) en IPv4 (ou FF02::5 en IPv6), ce qui permet d'atteindre l'ensemble des routeurs OSPF, et eux seulement. Ce processus de découverte et de validation est réalisé en faisant passer les routeurs par plusieurs états de communication de leur lien mutuel (interface).

Down Mode -> Two-way State

On se place dans la situation où on ajoute un nouveau routeur \(R1\), en OSPF, dans le réseau :

• \(R1\) est configuré en OSPF. Il est initialement dans l'état Down Mode
• \(R1\) envoie des paquets de découverte Hello en multicast 224.0.0.5, contenant la liste de ses voisins
• \(R2\) reçoit le paquet Hello, et entre \(R1\) dans sa table de voisinage
• \(R1\) passe à l'état Init State
• \(R2\) doit répondre à \(R1\) avec un paquet Hello:
  • Le paquet de réponse n'est pas envoyé en multicast, mais en unicast
  • Le paquet de réponse de \(R2\) contient également TOUS les voisins de \(R2\)
  • \(R1\) verra son propre nom dans le champ des voisins reçus: passage à l'état Two-Way State (communication à double sens)

Voisins au sens OSPF

Deux routeurs sont voisins OSPF, ou voisins au sens OSPF, s'ils se trouvent dans l'état Two-way State, càd :

• en état de communication bidirectionnelle (avec des paquets Hello)
• chacun apparaît dans la liste des voisins de l'autre

Je retiens

• Les routeurs découvrent et approuvent de nouveaux voisins grâce à des paquets Hello
• Arèrs réception et traitement des paquets Hello dans les deux sens, les routeurs sont voisins OSPF (dans l'état Two-way State)
• Les paquets Hello servent également à vérifier que les liens sont, et restent, fonctionnels
• L'élection du DR et du BDR a lieu juste après le Two-way State

Adjacence

Le Two-Way State est la relation la plus basique qu’un voisin OSPF puisse établir, mais dans cette relation aucune information de routage n’est partagée. Pour apprendre l’état des liens des autres routeurs et construire une table de routage, chaque routeur doit former une relation d'Adjacence/Contiguïté complète - Full Adjacency. Une Adjacence / Contigüité / Adjacency est une relation avancée entre des routeurs OSPF qui implique une série d’états progressifs qui n'utilisent pas seulement des paquets Hello (Type \(1\) , mais aussi les \(4\) autres Types de paquets OSPF. Les routeurs qui tentent de devenir contigüs ou adjacents avec un autre, échangent des annonces d'états de liens / informations de routage (LSA) avant que toute adjacence soit entièrement établie.

Two-way State -> Adjacence

On se place dans la situation où deux routeurs \(R1\) et \(R2\) sont en état Two-way State, en OSPF, dans le réseau :

• ExStart State : Techniquement, quand un routeur entre en Exstart State, la conversation est caractérisée par une contiguïté (adjacency) mais les routeurs ne sont pas encore entièrement adjacents (Full Adjacency). L’ExStart est établi en utilisant des paquets de Type 2 DBD - DataBase Description. Les deux routeurs voisins utilisent ces paquets pour négocier qui sera le "maître" et qui sera l'"esclave" dans la relation :
  • Le routeur avec la plus haute OSPF ID "gagnera" et deviendra "maître"
• Exchange State : Une fois ces rôles définis, l’état Exchange intervient, et l’échange d’informations de routage bidirectionnels, entre routeurs voisins, peut commencer grâce à des paquets DBD - DataBase Description (Type \(2\)) qui détaille leurs LSDB
• Loading State :
  • Dans l'état Loading State, si un routeur apprend des informations sur des liens qu’il ne possède pas, il demande une mise à jour complète à son voisin avec un paquet LSR - Link-State Request (Type \(3\)).
  • Quand un routeur reçoit un LSR, il répond avec une mise à jour en utilisant un paquet LSU - Link-State Update (Type 4).
  • Ces paquets LSU (Type 4) contiennent les LSA- Link-State Advertisements qui sont le coeur du protocole de routage à état de lien.
  • Les LSU sont Accusés de Réception (on dit acquittés) par des LSAcks - Link-State Acknowledgments.

• Full-Adjacency / Adjacence Complète :
  • Lorsque le Loading State est complet, les routeurs sont entièrement adjacents.
  • Chaque routeur garde une liste de ses routeurs voisins appelée Adjacency DataBase / Table d'Adjacence, qui ne doit pas être confondue avec la LSDB - Link-State DataBase (ou la Forwarding DataBase)

P

Table de Voisins/Voisinage

Table de Voisins/Voisinage

OSPF a besoin de connaître la topologie du réseau ainsi que la qualité de chaque lien en terme de bande passante. Pour cela, chaque routeur va fabriquer une Table de Voisins/Voisinage, il s'agit d'un tableau permettant d'identifier :

• Tous les routeurs et sous-réseaux directement connectés
• La qualité/coût des Liens qui tient compte des bandes passantes, débits, etc.. associés à chaque lien.

Pour obtenir ces informations, le routeur échange périodiquement des messages Hello avec ses voisins.

Voisin	Qualité du Lien
\(B\)	\(1\) Gb/s
\(C\)	\(10\) Gb/s

Une fois tous ses voisins directs identifiés, le routeur va envoyer sa table de voisinage à tous les autres routeurs du réseau. Il va recevoir des autres routeurs leurs tables de voisinages (la liste de leurs voisins) et ainsi pouvoir constituer une cartographie complète du réseau.

Routeurs DR / BDR / DROTHER

Complexité des Adjacences et Notion de DR / BDR / DROTHER

Une relation d'Adjacence est nécessaire pour que les routeurs OSPF se partagent des informations de routage. Dans un réseau broadcast (Ethernet) ayant \(n\) routeurs, si chaque routeur devait établir une adjacence avec chaque autre routeur pour échanger des informations d’état de liens, la charge (pour le réseau d'une part, et en termes de CPU/RAM d'autres part) serait excessive, en effet le nombre d'adjacences possibles étant de ⁹ :

\(\dfrac {n(n-1)}{2}\) \(\quad \quad \) càd en \(O \left( n^2 \right)\)

Pour pallier ce problème, le protocole OSPF définit/élit :

DR - Designated Router

Un DR - Designated Router / Routeur Désigné est en charge de recevoir (de manière un peu centralisée, donc) toutes les informations sur l'état des liens et les retransmettre aux autres routeurs.

Un DR ayant un rôle critique pour le réseau, OSPF définit/élit également :

BDR - Backup Designated Router

Un BDR - Backup Designated Router / Routeur Désigné de Sauvegarde/de Secours est une sorte de deuxième DR, qui joue globalement des rôles semblables au DR, mais qui peuvent être distincts ponctuellement.

Adjacences avec un DR

Grâce à l'utilisation d'un DR, Le nombre d'adjacences d'un routeur est donc de :

\(2n-1\) \(\quad \quad\) càd en \(O ( n )\)

DROTHER

Un routeur "normal" en OSPF, qui n'est NI un DR, NI un BDR, est appelé un DRO / DROTHER / DR-Other.

Élection du DR et du BDR

Pour un sous-réseau déterminé de type broadcast ou NBMA, chaque routeur OSPF possède une valeur appelée Routeur Priority comprise entre \(0\) et \(255\) ⁹:

• Si la priorité est configurée à \(0\), le routeur ne participe pas à l'élection et ne peut donc devenir ni DR, ni BDR
• La valeur \(255\) est (presque) certaine d'être élue DR.. (sauf égalité)
• Tous les autres routeurs qui sont au moins dans l'état Two-Way State sont éligibles

L'élection commence par le BDR

• S'il existe déjà plusieurs routeurs qui indiquent être le BDR dans leurs paquets hello, celui qui a la priorité la plus haute sera retenu comme BDR, et
• S'il existe plusieurs routeurs avec la priorité la plus haute, alors celui dont le router-ID est le plus élevé est retenu comme BDR
• S'il n'existe qu'un routeur qui indique être le BDR, ce choix est retenu.
• Si la liste des candidats est vide, alors le BDR est le routeur éligible non-DR dont la priorité est la plus élevée, et
• s'il en existe plusieurs, alors celui dont le router-id le plus élevé est retenu.

L'élection du DR est identique à celle du BDR

• S'il n'y a pas de candidat DR, alors le BDR est promu en DR et on recommence l'élection du BDR comme au paragraphe précédent.
• Les autres routeurs sont adjacents au DR et au BDR
• En cas de défaillance du DR, le BDR devient DR et on procède à une nouvelle élection du BDR.

Si les trois routeurs sont démarrés simultanément, R2 deviendra le DR en raison du router-id plus élevé et R1 le BDR. R3 ne participe pas à l'élection du DR car sa priority vaut 0.

Types de Routeurs OSPF

On distingue les types de routeurs suivants, qui sont liés à leur position/rôle par rapport aux aires OSPF:

Type Routeur OSPF	Définition
Routeur Interne (IR)	Un routeur dont toutes les interfaces se trouvent dans la même aire
Area Border Router (ABR)	un routeur qui dispose d'interfaces dans des aires différentes
Autonomous System Boundary Router (ASBR)	Un routeur qui injecte dans OSPF des routes qui proviennent d'autres protocoles de routage ou des routes statiques
Routeur Backbone	Un routeur dont au moins une interface appartient à l'aire \(0\). Tous les ABR sont des routeurs Backbone.

Exemples de Types de routeurs R1, R2 et R3 sont des routeurs backbone. R1, R2 et R4 sont des ABR. R4 et R8 sont des ASBR. L'area 3 est connectée à l'area 0 grâce à un virtual link.

Areas / Aires / Zones

Une Area / Zone, c'est quoi?

Area / Zone

Les protocoles à État de Lien utilisent des Areas / Aires / Zones qui sont des regroupements logiques de routeurs, permettant de diviser un gros réseau en plusieurs sous-réseaux logiquement indépendants. Une Area est une zone de diffusion/synchronisation des LSDB. On distinguera alors:

• Des communications intra-area / intra-aires / intra-zones
• Des communications inter-area / inter-aires / inter-zones

Pourquoi créer des Areas / Zones ?

L'utilisation d'Areas permet de rendre OSPF scalable, et d'accélerer notablement sa convergence. Une Area / Zone permet de réduire la charge CPU / RAM, en effet les opérations suivantes (usuelles pour tout protocole à état de lien, d'une manière générale) sont très gourmandes :

• Détection et Maintien des voisins : Les LSA \(1\) et \(2\), utilisés pour les messages Hello, ne sortent donc pas d'une Aire
• Synchronisation LSDB
• Calcul des Tables de Routage (en particulier Dijkstra/SPF)

En effet, le calcul des routes se fait alors uniquement entre les routeurs d'une même aire/zone. Lors de la mise en place du protocole OSPF, la conception de l'infrastructure réseau est donc très importante.

Les Types d'Aires

OSPF définit plusieurs types d'aires¹⁴¹⁵ :

Nom Aire	Pour quoi faire?
Backbone Aire \(0\)	C'est l'aire centrale. La seule obligatoire. Toutes les autres aires y sont reliées en étoile
Standard Area Aire Standard	Le Type de zone par défaut. Les LSA de type \(1\) et \(2\) ne sortent pas de la zone (comme toujours). Chaque routeur connait les préférés dans l’aire. Ils ont tous la même table topologique LSDB.
Stubby Area Stub Area Aire Stub Aire Boutiste	Aire qui n’accepte pas les LSA Type \(4\) ou \(5\) (Summary). Ils sont remplacés par une route par défaut. Cela protège les routeurs afin qu’ils n’aient pas trop d’informations sur les routes extérieures.
Totally Stubby Area Aire Totalement Boutiste	N’accepte pas les LSA des autres aires. Les LSA de type \(3\), \(4\), \(5\) ne sont pas acceptées. Ils sont remplacés par une route par défaut (Propriétaire CISCO). Les routeurs de l’Area ne connaîtront que les réseaux internes à l’Area.
NSSA - Not-So-Stubby-Area Aire Non Totalement Boutiste	Le but est de permettre la présence d’un ASBR dans une Stubby Area ou une Totally Stubby Area. Quel est le problème? En Stubby ou Totally Stubby : les LSA de types \(4\) et \(5\) ne circulent pas donc l’ASBR ne pourra donc pas redistribuer de routes externes. En mode NSSA, l’ASBR utilisera le LSA de type \(7\) pour remplacer les LSA de type \(4\) et \(5\)

OSPF Standard Area

OSPF Stubby Area

OSPF Totally Stubby Area

OSPF NSSA

Propriétés des Aires

Contraintes Aires & Sous-réseaux

• Un même sous-réseau doit appartenir à une même aire
• Un aire peut contenir plusieurs sous-réseaux

Aires et OSPF

• Les aires servent à :
  • diminuer la «portée» des LSU (Update),
  • alléger les charges CPU/RAM
  • Augmenter la convergence
• Les LSA sont propagés au sein des aires
• Les ABR (Area Border Router) créent des Summary-LSAs, qui donnent leur distance au réseau en question
• Stub-area / Aire stub / Aire boutiste : un seul point d’accrochage. Les routes externes n’y sont pas propagées (route par défaut à la place)

L'Algorithme de Dijkstra

L'algorithme de Dijkstra datant de \(1959\) permet de trouver le chemin le plus court sur un graphe.

Avantages / Désavantages

Avantages

Désavantages

Un Exemple Expliqué

Considérons le réseau suivant. Après échanges de messages hello, la cartographie suivante du réseau a été constituée :

Nous cherchons à déterminer le chemin le plus rapide entre R1 et R7. L'outil graphonline vous permet de le faire visuellement via le menu Algorithmes / plus court chemin avec l'algorithme de Djisktra.

Contrairement à RIP, le chemin qu'OSPF nous indiquera sera R1 => R2 => R3 => R5 => R4 => R6 => R7. Ce chemin n'est clairement pas le plus efficace en termes de sauts mais est le plus rapide en termes de débit car il n'exploite pratiquement que des liaisons à 10 Gb/s.

Application à notre exemple

Djisktra permet de minimiser la longueur d'un chemin, or nous souhaitons maximiser le débit sur nos liaisons. Nous allons donc considérer l'inverse de la bande passante de nos liens pour appliquer Djisktra : maximiser les débit revient à minimiser l'inverse des débits :

• \(1\) Gb/s sera affecté du poids \(1\)
• \(10\) Gb/s sera affecté du poids \(0.1\)
• \(100\) Mb/s sera affecté du poids \(10\)

Nous allons ensuite constituer notre tableau. A chaque nouvelle ligne, on calcule les distances totales vers les destinations possibles et on ne retient que la plus petite (en gras) que l'on marque sur une nouvelle ligne.

Pour empêcher les retours, une fois une destination choisie (en gras), on désactive tout le reste de la colonne (avec des x)

R1	R2	R3	R4	R5	R6	R7
0 - R1
0 - R1	0.1 - R1	1 - R1
x	0.1 - R1	0.2 - R2	1.1 R2
x	x	0.2 - R2	0.3 - R3
x	x	x	0.4 - R5	0.3 - R3	1.3 - R5	10.3 - R5
x	x	x	0.4 - R5	x	0.5 - R4
x	x	x	x	x	0.5 - R4	1.5 - R6
x	x	x	x	x	x	1.5 - R6

Dans le tableau, on indique des couples distance - origine : ainsi 0.5 - R4 dans la colonne R6 signifie que R6 est à une distance minimum de 0,5 du départ en provenance de R4. On peut ainsi reconstituer l'itinéraire optimal en partant de R7 et en remontant à l'envers en utilisant le champ origine :

R1 => R2 => R3 => R5 => R4 => R6 => R7 avec un poids total minimum de 1,5.

A vous de jouer

On supprime la liaison R4-R5. Réappliquez l'algorithme de Dijkstra pour déterminer un chemin optimal entre R1 et R7.

Conclusion

OSPF peut s'adapter à la qualité des liens mais dans une certaine mesure uniquement : Si un lien à n10 Gb/s est saturé, il vaut mieux emprunter un lien à 1 Gb/s sous utilisé, mais OSPF n'en a pas connaissance.

Il n'y a pas dans l'absolut de meilleur algorithme de routage, tout dépend du réseau auquel on a affaire. Un protocole sera plus réactif face aux changements de topologie mais au prix d'un plus gros volume échangé. Un autre sera plus efficace si les liaisons au sein du réseau sont très hétérogènes.

RFCs, Références & Notes

RFCs

Les spécifications du protocole OSPF sont détaillées dans les RFC suivantes (en ) :

RFC	qui détaille ..	Date
RFC 1131	The OSPF Specification (fichier .ps uniquement)	Octobre 1989 remplacé par RFC 1247
RFC 1247	OSPF Version 2	Juillet 1997 mis à jour dans RFC 1349 remplacé par RFC 1583
RFC 1349	OSPF Version 2 Additional Information Appendix A	Juillet \(1992\) remplacé par RFC 2474
RFC 1583	OSPF Version 2	Mars \(1994\) remplacé par RFC 2178 remplace RFC 1247
RFC 1584	OSPF Version 2 Multicast Option	Mars \(1994\) étend la RFC 1583
RFC 1587	OSPF Version 2 NSSA Option	Mars \(1994\) remplacé par RFC 3101 étend la RFC 1583
RFC 2178	OSPF Version 2	Juillet \(1997\) remplacé par RFC 2328 remplace RFC 1583
RFC 2328 En ici	OSPF version 2	Avril \(1998\) remplace RFC 2178
RFC 2740	OSPF version 3 for IPv6	Décembre \(1999\) remplacé par RFC 5340
RFC 3101 En ici	OSPF version 2 NSSA Option	Janvier \(2003\) remplace RFC 1587
RFC 5340	OSPF version 3 for IPv6 compatible IPv4	Juillet \(2008\) remplace RFC 2740
RFC 6549	OSPF version 2 Multi-Instance Extensions	Mars \(2012\) met à jour RFC 2328
RFC 8042	OSPF version 2 Two-part Metric	Mars \(2016\) met à jour RFC 2328
RFC 8362	OSPF version 3 LAS - Link State Advertisement Extensibility	Avril \(2018\) met à jour RFC 5340 & RFC 5838

Références

• Algorithmes Distribués de plus court chemin, RIP & OSPF, Johanne Cohen, LORIA/CNRS, Nancy, France
• Routage OSPF, Goffinet, CCNA :
  • Introduction au Protocole de routage Dynamique
  • Config d'OSPFv2 et OSPFv3 sur Cisco IOS
  • Messages OSPF
  • Etats de Voisinage OSPF
  • Maintien des informations de routage OSPF
• developpez.com, Cours Introduction à TCP/IP, RIP & OSPF
• Traduction de la RFC 2328, par Claude Brière de L'isle
• Portail Francophone de Traduction des RFC
• IBM i 7.1, OSPF Packet Types
• Introduction à OSPF, au.int
• Cours OSPF, membres IMAG

Notes

---

1. lecluse.fr, Protocoles de Routage, OPSF d'Olivier Lecluse ↩↩

2. OSPF Design Guide, Cisco ↩

3. blog.ataxya.net, Cécile MORANGE ↩

4. Network Lessons, OSPF ↩↩

5. Les Différents Types de LSA, Microsoft touch Community ↩

6. Les Areas / Zones OSPF, IT-connect.fr ↩

7. LSA OSPF, wikipedia ↩

8. afnog.org, Intro à OSPF ↩

9. OSPF, wikipedia ↩↩

10. What is an NBMA Network in OSPF? techtarget.com ↩

11. Entête / Header d'un LSA, Huawei Support Enterprise ↩

12. OSPF Packet Format, Huawei Support Enterprise ↩

13. Voisinnage & Adjacence OSPF, iplogos.fr ↩

14. OSPF Area Types, networklife.net ↩

15. OSPF Area Types, packetlife.net ↩