Open Shortest Path FirstOpen Shortest Path First (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 RFC 2328[1] en 1997. Une version 3 est définie depuis 2008 dans la RFC 5340[2] (initialement dans la RFC 2740[3] en 1999) et permet l'utilisation d'OSPF dans un réseau IPv6. HistoireLe 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 RFC 1131[4] en 1990 (mais jamais implémentée). La version 2 est décrite RFC 1247[5] en 1991. En 1992, l'Internet Engineering Steering Group (IESG) recommande OSPF comme IGP pour Internet dans la RFC 1371[6]. Fonctionnement généralDans OSPF, chaque routeur établit des relations d'adjacence avec ses voisins immédiats en envoyant des messages hello à 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 Link-State Database (LSDB) pour chaque aire, qui est identique pour tous les routeurs participants dans cette aire. Chaque routeur utilise ensuite l'algorithme de Dijkstra, Shortest Path First (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 routeursAfin d'éviter de propager la totalité de la base de données des liens et de limiter l'impact négatif du bagottement ou flapping (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 à 4 294 967 295, 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 (backbone area), 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 routeursOn distingue les types de routeurs suivants :
Paquets OSPF et LSAOSPF 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 KB, 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 5 types de paquets OSPF :
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 :
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 :
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 :
Le LSA de type 1 (router) se subdivise en quatre sous-types qui dépendent du type de réseau décrit.
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 LSALes 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, -231+1) jusqu'à 0x7fffffff (231). 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 30 minutes (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 à 15 minutes (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 5 secondes (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'airesOn distingue les types d'aires suivantes :
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
Formation des adjacencesDans 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 :
Protocole helloLes messages hello sont envoyés à intervalle régulier sur les interfaces où OSPF est actif. Sur les liens point-à-point et les liens broadcast, ils sont diffusés sur l'adresse multicast 224.0.0.5 (AllSPFRouters), sur les liens sans broadcast, ils sont envoyés vers l'adresse IP unicast du voisin. Les informations suivantes se trouvent notamment dans le paquet hello :
Le numéro d'aire est inclus dans l'en-tête paquet OSPF. Une adjacence ne se forme pas si certains paramètres ne sont pas compatibles (numéro d'aire, type d'aire (stub ou non), périodes hello/dead, authentification). Adjacence sur un réseau à diffusionUne relation d'adjacence est nécessaire pour que les routeurs OSPF se partagent des informations de routage. Dans un réseau broadcast (Ethernet) si chaque routeur devait établir une adjacence avec chaque autre routeur et échanger des informations d’état de liens la charge serait excessive, le nombre d'adjacences étant de , soit en . Pour pallier ce problème, on choisit un DR (routeur désigné) qui va recevoir toutes les informations sur l'état des liens et les retransmettre aux autres routeurs. Celui-ci devenant un point critique du réseau, on désigne aussi un BDR (routeur désigné de secours). Le nombre d'adjacence est donc de 2n-1, soit en . Les autres routeurs sont qualifiés de DR Other. OSPF utilise uniquement du multicast pour communiquer, avec les deux adresses suivantes :
Seul le DR génère le network LSA (type 2) correspondant au sous-réseau. Le LSID de celui-ci vaudra l'adresse IP du DR dans le sous-réseau. Ce LSA liste également les routeurs attachés au sous-réseau. Élection du DRPour un sous-réseau déterminé de type broadcast ou NBMA, chaque routeur OSPF possède une valeur appelée 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. Les autres routeurs qui sont au moins dans l'état 2-Way 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 persiste. 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. On procède de même avec le DR, 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. Suivant cette procédure, si un routeur est ajouté au réseau alors qu'un DR et qu'un BDR existent déjà, alors les DR et BDR persistent même si la priorité du nouveau venu est plus élevée. SynchronisationUne fois l'adjacence établie, les routeurs vont déterminer un routeur primaire et un secondaire ainsi qu'un numéro de séquence initial. Le routeur primaire va envoyer des paquets Database Description (DBD) au secondaire, ceux-ci consistent en une liste des en-têtes de LSA (mais sans les données du LSA proprement dites), le secondaire va noter les LSA qu'il ne possède pas ou dont les numéros de séquence sont plus élevés que celui dans sa LSDB et va les réclamer ensuite au primaire avec des paquets Link State Requests. Le routeur primaire lui répond avec des paquets Link State Update qui contiennent les LSA demandés. Le secondaire envoie ensuite les paquets Link State Update qui correspondent aux LSA dont le primaire ne dispose pas ou qui sont plus à jour chez le secondaire. Une fois la synchronisation terminée, l'adjacence bascule dans l'état Full et les LSA sont diffusés normalement. Résumé de routesLes routes peuvent être résumées à deux niveaux dans OSPF :
MétriqueOSPF utilise une métrique numérique, basée sur un coût additif qui peut varier de 1 à 65535. La spécification ne donne pas de signification particulière à cette métrique, la contrainte étant qu'additionner les coûts de liens successifs pour déterminer le coût total doit avoir un sens. Cisco utilise une valeur par défaut du coût d'un lien qui vaut (108)/(bande passante du lien en bit/s). Un lien de 10 Mbit/s aura par exemple un coût de 10. Pour tenir compte des connexions à très haute vitesse (1 Gbit/s et plus), on peut fixer manuellement le coût de chaque lien, ou bien fixer une bande passante de référence supérieure à celle par défaut. Indépendamment de la métrique, les types de routes suivants sont préférés dans cet ordre :
OSPF est capable de répartir la charge sur plusieurs liens, pour autant que la métrique soit exactement identique pour chaque destination. AuthentificationLes paquets OSPF peuvent faire l'objet de deux formes d'authentification, la première consiste en un mot de passe transmis en clair dans le paquet, la seconde consiste en une fonction de hachage MD5 calculée sur le paquet et un mot de passe partagé. L’algorithme de DijkstraOSPF utilise l'algorithme de Dijkstra pour déterminer le meilleur chemin à prendre. On le nomme aussi algorithme SPF (Shortest Path First) ou algorithme du plus court chemin d’abord. Il a été formulé par Edsger Dijkstra. OSPF déclenche ses mises à jour à chaque changement dans la topologie du réseau, ce qui permet de réduire le temps de convergence. À partir d'une mise à jour, un routeur met en place une base de données topologique permettant le calcul de l'accessibilité aux réseaux grâce au calcul d'un arbre de la topologie dont le routeur est la racine. Avantages et inconvénientsAvantages d'OSPF
Inconvénients d'OSPF
Évolutions (OSPFv3)OSPFv2 ne fonctionne qu'avec et que pour IPv4. OSPFv3 a donc été défini dans la RFC 5340. OSPFv3 fonctionne sur des liens IPv6, et permet de router uniquement de l'IPv6 dans les RFC initiales. OSPFv3 abandonne l'authentification d'OSPFv2 au profit d'IPsec. OSPFv3 fonctionne sur des liens (adressés en IPv6, avec au moins des adresses Link-Local), plutôt que sur des subnets comme le faisait OSPFv2. De ce fait les LSA ID n'ont plus rien à voir avec l'adressage, lequel est du reste désormais transporté séparément dans de nouveaux LSA:
Par la suite, la RFC 5838[8] a introduit la notion d'Address Family, qui permet à OSPFv3 de transmettre simultanément des informations de routage et de topologie différentes pour différentes familles d'adresses, et notamment à la fois IPv4 et IPv6. Il est à noter qu'OSPFv3 tourne lui-même toujours sur des liens adressés en IPv6. Depuis cette RFC, OSPFv3 serait théoriquement en mesure de remplacer totalement OSPFv2 (toute notion de stabilité et de maturité d'implémentation mise à part). Références
Voir aussiArticles connexes
Bibliographie
Liens externes
|