(OSPF) est un protocole de routage interne IP de type « à état de liens ». Il a été développé au sein de l'Internet Engineering Task Force (IETF) à partir de 1987. La version actuelle d'OSPFv2 est décrite dans la en 1997. Une version 3 est définie depuis 2008 dans la (initialement dans la en 1999) et permet l'utilisation d'OSPF dans un réseau IPv6.

Histoire Le groupe de travail OSPF a été formé au sein de l'IETF en 1987 pour remplacer RIP. Il est inspiré du protocole ARPANET développé par BBN. La version 1 est publiée dans la en 1990 (mais jamais implémentée). La version 2 est décrite en 1991. En 1992, l'Internet Engineering Steering Group (IESG) recommande OSPF comme IGP pour Internet dans la .

Fonctionnement général Dans OSPF, chaque routeur établit des relations d'adjacence avec ses voisins immédiats en envoyant des messages à intervalle régulier. Chaque routeur communique ensuite la liste des réseaux auxquels il est connecté par des messages Link-state advertisements (LSA) propagés de proche en proche à tous les routeurs du réseau. L'ensemble des LSA forme une base de données de l'état des liens (LSDB) pour chaque aire, qui est identique pour tous les routeurs participants dans cette aire. Chaque routeur utilise ensuite l'algorithme de Dijkstra, (SPF) pour déterminer la route la plus rapide vers chacun des réseaux connus dans la LSDB.

Le bon fonctionnement d'OSPF requiert donc une complète cohérence dans le calcul SPF, il n'est donc par exemple pas possible de filtrer des routes ou de les résumer à l'intérieur d'une aire.

En cas de changement de topologie, de nouveaux LSA sont propagés de proche en proche, et l'algorithme SPF est exécuté à nouveau sur chaque routeur.

Notion d'aire et types de routeurs Afin d'éviter de propager la totalité de la base de données des liens et de limiter l'impact négatif du bagottement ou (alternance rapide dans la disponibilité d'un lien), on segmente l'ensemble des routeurs en groupes connexes appelés aires, à la frontière desquels on peut procéder à des résumés. Chaque aire est distinguée par un nombre entier positif ou nul variant de 0 à , ce nombre est parfois exprimé en notation décimale pointée, de la même manière qu'une adresse IP. Chaque sous-réseau appartient à une seule aire.

Il existe toujours une aire dorsale (), area 0 ou encore area 0.0.0.0 à laquelle toutes les autres aires sont connectées.

Les aires sont logiquement contigües. Si les routeurs qui constituent une aire ne sont pas physiquement contigus, alors des liens virtuels sont configurés entre les routeurs qui ont en commun une aire de transit. Ces liens virtuels appartiennent à l'aire 0. Le protocole les traite comme des liens point-à-point non numérotés.

Chaque routeur est identifié à l'aide d'un router-id unique dans le réseau. Le router-id est un nombre positif codé sur 32 bits, il est habituellement représenté sous la forme d'une adresse IP. À défaut d'une configuration explicite, l'adresse IP locale la plus élevée sera utilisée, et s'il existe des interfaces de type loopback, l'adresse IP la plus élevée de celles-ci sera utilisée comme router-id. La détermination du router-id a lieu uniquement à l'initialisation du processus OSPF et persiste ensuite, indépendamment de la reconfiguration ou du changement d'état des interfaces.

Types de routeurs thumb|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. On distingue les types de routeurs suivants :

Routeur interne un routeur dont toutes les interfaces se trouvent dans la même aire ; (ABR) un routeur qui dispose d'interfaces dans des aires différentes ; (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.

Paquets OSPF et LSA thumb|En-tête du paquet OSPF (24 octets). thumb|En-tête du LSA (20 octets). OSPF fait usage du numéro de protocole 89 d'IP. Le TTL des paquets est fixé à 1 pour éviter leur propagation au-delà du sous-réseau et le champ ToS est fixé à 0. OSPF utilise des adresses multicast sur les réseaux de type broadcast et point à point.

Les paquets OSPF ont une taille qui peut aller jusqu'à 65535 octets et faire usage de la fragmentation IP si c'est nécessaire. Il est cependant recommandé de tenir compte du MTU du lien pour éviter la fragmentation en répartissant les LSA dans des messages LS Update plus petits que le MTU, si c'est possible.

Les LSA peuvent également atteindre 64 Ko, cependant ils sont généralement de petite taille à l'exception du type 1 (router LSA), qui peut être volumineux pour des routeurs avec de nombreuses interfaces OSPF.

Il existe de paquets OSPF : Hello (Type 1) découverte des voisins et maintien des adjacences ; Database Description (DBD, Type 2) description des LSA ; Link State Request (Type 3) requête d'un LSA ; Link State Update (LSU, Type 4) mise à jour d'un LSA; Link State Acknowledgement (Type 5) acquittement d'un LSA.

Le type 1 (hello) est utilisé pour l'établissement et le maintien des adjacences, les autres types sont utilisés pour la synchronisation de la LSDB.

Les Paquets LSA sont un sous-type de paquet LSU, les types suivants sont définis : Type 1 (router) diffusé par un routeur, décrit l'état de ses interfaces ; Type 2 (network) diffusé par un DR (Designated Router), décrit les routeurs attachés à un sous-réseau ; Type 3 (summary) résumé de route par un ABR ; Type 4 (interarea summary) route vers l'ASBR, généré par un ABR ; Type 5 (external) diffusé par un ASBR, décrit une route externe ; Type 6 (multicast group membership) utilisé par MOSPF ; Type 7 (external NSSA) route externe générée par un ASBR d'un NSSA.

Les types 1 et 2 constituent les routes internes d'une aire (intra-area), les types 3 et 4 sont des routes inter-area (IA). Les routeurs backbone sont responsables de la diffusion des informations de routage inter-area.

Les routes externes se subdivisent en : Type E1 le coût de l'accès à l'ASBR est ajouté à la métrique initiale de la route externe ; Type E2 le coût de la métrique est fixe et ne dépend pas du coût vers l'ASBR.

Les LSA sont identifiés par le routeur d'origine, le type de LSA et le LSA ID. La signification de ce dernier varie en fonction du type de LSA :

LSA Type LSA ID 1 Le router-id de l'émetteur 2 L'adresse IP de l'interface du DR 3 L'adresse du réseau de destination 4 Le router-id de l'ASBR 5 L'adresse du réseau externe

Le LSA de type 1 (router) se subdivise en quatre sous-types qui dépendent du type de réseau décrit.

+ Link type 1 Sous-type Description Link ID Link data 1 point-to-point router-id du voisin Adresse IP de l'interface ou MIB-II ifIndex si l'interface n'est pas numérotée 2 lien vers un réseau de transit adresse de l'interface du DR Adresse IP de l'interface 3 lien vers un réseau stub adresse du réseau masque réseau 4 lien virtuel router-id du voisin Adresse IP de l'interface

Tous les LSA sont accompagnés d'une somme de contrôle qui assure l'intégrité des données. Celle-ci est vérifiée à la réception du LSA, enregistrée dans la LSDB et transmise aux voisins sans modification. Elle est ensuite revérifiée à intervalle régulier pour s'assurer que le contenu de la LSDB n'a pas été corrompu.

Gestion des LSA Les LSA sont caractérisés par leur routeur d'origine, leur type et le LSA ID. Les numéros de séquence (entier signé sur 32 bits) augmentent de 1 à chaque changement, le premier numéro de séquence étant 0x80000001 (InitialSequenceNumber, -2+1) jusqu'à 0x7fffffff (2). Chaque version du LSA remplace les versions de numéro de séquence inférieur. En l'absence de changement, les LSA sont rafraîchis toutes les (LSRefreshTime). Un LSA qui atteint l'âge d'une heure (MaxAge) est éliminé de la LSDB. Le routeur d'origine du LSA peut spécifier que le LSA n'est pas rafraîchi en plaçant le bit DoNotAge à 1 dans les options.

Les LSA sont diffusés de façon fiable. Quand un routeur doit mettre à jour un LSA à la suite d'un changement de topologie, il incrémente son numéro de séquence et le diffuse à ses voisins adjacents sous forme d'un paquet Link-State Update (qui peut contenir plus d'un LSA). Les LSA font alors l'objet d'un acquittement explicite, faute de quoi ils sont retransmis. Les routeurs qui reçoivent le LSA comparent son numéro de séquence à celui qu'ils possèdent déjà, et s'il est plus élevé, ils enregistrent le LSA dans la LSDB et le transmettent également à leur voisin. Le champ LS Age est incrémenté à chaque transmission pour éviter les boucles infinies à la suite d'une erreur logicielle. Si un LSA est reçu avec un numéro de séquence identique à celui déjà présent dans la LSDB mais avec une différence d'âge inférieure à (MaxAgeDiff), le LSA sera ignoré.

Un routeur à l'origine d'un LSA qu'il veut faire disparaître de la LSDB le diffuse avec un LS Age = MaxAge, ce qui cause son élimination.

Les routeurs s'abstiennent de mettre à jour un LSA plus fréquemment que toutes les (MinLSInterval). Les routeurs rejettent les mises à jour d'un LSA qui a déjà fait l'objet d'une mise à jour il y a moins d'une seconde.

Types d'aires On distingue les types d'aires suivantes : aire 0 aire backbone ; regular area aire quelconque, l'aire backbone en étant une itération particulière ; stub area aire vers laquelle ne sont pas propagées les LSA de type 5 (routes externes) ; totally stub area aucun LSA de type 3, 4, 5 ou 7 n'y est propagée, à l'exception d'une route par défaut ; not-so-stubby area (NSSA) type de stub area qui permet l'injection de routes externes via un LSA de type 7. Le type 7 sera converti en type 5 quand il sera transmis en dehors de l'aire ; totally NSSA NSSA sans LSA 3 et 4 à l'exception d'une route par défaut.

Il n'est pas possible de créer des liens virtuels à travers une stub area, ni des ASBR internes à une stub area.

Types de réseaux Point-to-point le sous réseau correspond à un lien point à point ; Broadcast multiaccess le sous-réseau peut comporter plus de deux routeurs qui peuvent tous communiquer entre eux, une adresse broadcast est disponible ; Point-to-multipoint le sous-réseau est constitué d'un routeur central et d'autres routeurs qui ne communiquent pas entre eux. OSPF traite le réseau comme une collection de liens point-à-point ; NBMA (Non-broadcast multiaccess) le sous-réseau est constitué de routeurs qui peuvent communiquer entre eux mais il n'existe pas d'adresse broadcast. Dans ce type de réseau, OSPF émule le type broadcast en répliquant les LSA à tous les voisins adjacents ;

Point-to-point Broadcast Point-to-multipoint(non-broadcast) Point-to-multipoint(broadcast) NBMA DR/BDR non oui non non oui hello/dead 10s/40s 10s/40s 30s/120s 30s/120s 30s/120s découverte des voisins oui oui non oui non RFC 2328 oui oui oui Cisco oui

Formation des adjacences vignette|Diagramme d'état des adjacences. Dans un sous-réseau, les routeurs qui se découvrent grâce au protocole hello sont appelés voisins. Dans les réseaux de type point-à-multipoint et NBMA, les voisins sont configurés explicitement. Pour autant que les paramètres des voisins soient compatibles, ils tentent alors de former une relation d'adjacence. L'établissement de l'adjacence est requise avant l'échange d'information de routage.

L'adjacence peut prendre les états suivants : Down aucune information n'a été reçue sur ce segment ; Attempt sur les réseaux NBMA, indique qu'aucune information récente n'a été reçue du voisin configuré ; Init un paquet hello a été reçu ; 2-Way un paquet hello a été reçu et celui-ci contient son propre router-id, ce qui montre qu'il existe une communication bidirectionnelle. L'élection du DR et du BDR a lieu dans cet état. La décision de former une adjacence est prise au terme de cet état.