OSPF : Open Shortest Path First
Le routage dynamique avec RIP
Introduction
Le routage statique consiste à indiquer l'adresse IP des réseaux que l'on cherche à atteindre. On associe à chaque adresse, le nom de l'interface du routeur ou l'adresse IP du routeur voisin se situant sur la route vers ces réseaux de destination. Si le réseau global est complexe, la configuration peut être fastidieuse et source d'erreurs. De plus, lorsqu'un nouveau réseau est ajouté, il faut reconfigurer l'ensemble. Enfin, pour prévenir tout dysfonctionnement (panne d'un routeur, ligne coupée, etc.), il faut effectuer une surveillance permanente et reconfigurer chaque routeur le cas échéant. Si la route est rétablie, il faut recommencer la manipulation.
L'idée générale du routage dynamique est la suivante : plutôt que de centraliser la configuration du routage dans les mains d'un individu dont le temps de réaction est fatalement long et les risques d'erreurs importants, nous allons délocaliser cette tâche au niveau des routeurs. En effet, chaque appareil n'est-il pas le mieux placé pour connaître les adresses des réseaux auxquels il est directement relié puisque chacune de ses interfaces possède une adresse IP ? De plus, étant directement au contact des supports de communication, il peut établir un diagnostic sur l'état des liaisons. Ces informations, il n'a plus qu'à les partager avec ses voisins. De proche en proche, les nouvelles se répandront à chaque routeur du réseau. L'intervention humaine se situera en amont dans la définition de directives et de règles à appliquer par les routeurs pour la diffusion des routes.
Le protocole RIP
Comme toujours, pour qu'une communication puisse s'établir, chaque interlocuteur doit parler la même langue. Il a donc été nécessaire de concevoir un protocole. RIP a été défini, pour sa version 1 dans la RFC 1058 et pour sa version 2 dans la RFC 2453. Par la suite, nous ne verrons que RIPv2. Toutefois, avant de passer à la partie pratique, nous évoquerons rapidement les différences entre ces deux versions.
Quelles informations de routage s'échanger ?
Le principe général est très simple. Un routeur RIP transmet à ses voisins les adresses réseau qu'il connaît (soit les adresses de ses interfaces, soit les adresses découvertes via les autres routeurs) ainsi que la distance pour les atteindre. Ces couples adresse/distance sont appelés vecteurs de distance.
La notion de distance
Nous touchons ici au concept de métrique, fondamental dans le domaine du routage. En effet, il arrive fréquemment (c'est même une situation recherchée pour des raisons de tolérance aux pannes) que le réseau ait une topologie maillée. Dans ce cas, plusieurs routes mènent à la même destination. Le routeur doit alors choisir la route qu'il considère la meilleure vers une destination donnée.
La seule métrique utilisée par RIP est la distance correspondant au nombre de routeurs à traverser (hop ou nombre de sauts) avant d'atteindre un réseau. Pour chaque route, RIP calcule la distance. Ensuite, si des routes redondantes apparaissent, RIP retient celle qui traverse le moins de routeur (donc avec la distance la plus faible).
Du fait de la méthode utilisée pour diffuser les routes, la longueur d'une route (et par voie de conséquence le diamètre du réseau) est limitée. La norme limite la distance maximale d'une route à quinze. Cela signifie que deux réseaux ne peuvent être éloignés de plus de quinze routeurs. Nous verrons ci-après qu'une distance égale à seize (distance "infinie" pour RIP) joue un rôle particulier en indiquant qu'une route est devenue inaccessible.
Etablir la liste des routeurs voisins : Hello, my name is R1 and I'm an OSPF router.
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. En effet, 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). 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. Par exemple, sur la figure 1, R1 et R2 sont voisins mais pas R1 et R3.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'adresse IP de R1 dans une base de données appelée "base d'adjacences" (adjacencies database). Cette base contient les adresses des routeurs voisins. Vous pourrez visionner son contenu grâce à la commande show ip ospf neighbor. R2 répond à R1 par un paquet IP unicast. R1 intègre l'adresse IP de R2 dans sa propre base d'adjacences. Ensuite, généralisez ce processus à 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.
Elire le routeur désigné : c'est moi le chef !
Dans une zone OSPF, l'un des routeurs doit être élu "routeur désigné" (DR pour Designated Router) et un autre "routeur désigné de secours" (BDR pour Backup Designated Router). Le DR est un routeur particulier qui sert de référent au sujet de la base de données topologique représentant le réseau.
Pourquoi élire un routeur désigné ? Cela répond à trois objectifs :
-
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 il y a une base de données unique) ;
-
accélérer la convergence (souvenez-vous, c'était le talon d'Achille de RIP).
Comment élire le DR ? Autrement dit, qui va se taper la corvée d'expliquer à ses petits camarades la topologie du réseau ? On ne demande pas qui sait parler anglais ou couper les cheveux comme au temps de la conscription Mais comme il faut bien un critère, le routeur élu est celui qui a la plus grande priorité. 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é, c'est celui avec la plus grande adresse IP qui est élu. Le BDR sera le routeur avec la deuxième plus grande priorité. Afin de s'assurer que votre routeur préféré sera élu DR, il suffit de lui affecter une priorité supérieure à 1 avec la commande ospf priority. Vous devrez 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.
Découvrir les routes
Il faut maintenant constituer la base de données topologique. Les routeurs communiquent automatiquement les routes pour les réseaux qui participent au routage dynamique (ceux déclarés avec la commande network). Zebra étant multiprotocole, il peut également diffuser des routes provenant d'autres sources que OSPF, grâce à la commande redistribute.
Chaque routeur (non DR ou BDR) établit une relation maître/esclave avec le DR. Le DR initie l'échange en transmettant au routeur 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. Ensuite, le routeur (non DR ou BDR) transmet les routes meilleures ou inconnues du DR.
L'administrateur peut consulter la base de données topologique grâce à la commande show ip ospf database.
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 topologique. 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.
Maintenir la base 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ègre cette information à sa base topologique et 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.
Voilà pour les principes fondamentaux d'OSPF mais des notions importantes restent à évoquer si vous souhaitez déployer OSPF sur de grands réseaux (en particulier sur le fonctionnement d'OSPF sur un réseau point à point et sur l'agrégation de routes). Si vous voulez approfondir, reportez-vous au livre de C. Huitema cité en bibliographie qui, bien qu'un peu ancien est très complet sur la question. Bien sûr, vous pouvez toujours vous plonger dans les différentes RFC qui constituent OSPF (la RFC 2328 en particulier) et dont la lecture est toujours aussi agréable et passionnante ! (je plaisante, bien sûr).
Avant d'attaquer la pratique, un dernier concept : les zones OSPF.
Le concept de zone (area)
Contrairement à RIP, OSPF a été pensé pour supporter de très grands réseaux. Mais, qui dit grand réseau, dit nombreuses routes. Donc, afin d'éviter que la bande passante ne soit engloutie dans la diffusion des routes, OSPF introduit le concept de zone (area). Le réseau est divisé en plusieurs zones de routage qui contiennent des routeurs et des hôtes. Chaque zone, identifiée par un numéro, possède sa propre topologie et ne connaît pas la topologie des autres zones. 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.
Contrairement à RIP, OSPF a été pensé pour supporter de très grands réseaux. Mais, qui dit grand réseau, dit nombreuses routes. Donc, afin d'éviter que la bande passante ne soit engloutie dans la diffusion des routes, OSPF introduit le concept de zone (area). Le réseau est divisé en plusieurs zones de routage qui contiennent des routeurs et des hôtes. Chaque zone, identifiée par un numéro, possède sa propre topologie et ne connaît pas la topologie des autres zones. 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.
Historique
Open Shortest Path First 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 dans le but de remplacer RIP.
La version actuelle d'OSPFv2 est décrite dans la RFC 23281 en 1997. Une version 3 est définie depuis 2008 dans la RFC 53402 (initialement dans la RFC 27403 en 1999) et permet l'utilisation d'OSPF dans un réseau IPv6.
En 1992, l'Internet Engineering Steering Group (IESG) recommande OSPF comme IGP pour Internet dans la RFC 13716.
Il a été inspiré du protocole ARPANET développé par BBN.
Conclusion
OSPF est un protocole de routage dynamique moderne, robuste et conçu pour les grands réseaux. On constate qu'il est nettement plus complexe que RIP. Pas forcément dans sa configuration mais dans son fonctionnement interne. Un inconvénient de ce protocole est qu'il peut être gourmand en puissance de calcul et en mémoire lorsque le réseau comporte beaucoup de routes ou qu'il y a de fréquentes modifications de topologie.
OSPF est un protocole IGP (Interior Gateway Protocol), c'est-à-dire qu'il agit au sein d'un système autonome. Un AS (Autonomous System) est un ensemble de réseaux gérés par un administrateur commun. Chaque système autonome possède un numéro identifiant sur 16 bits délivré par l'IANA (Internet Assigned Numbers Authority) ou ses délégations. Classiquement, les multinationales, les opérateurs de télécom ou les fournisseurs d'accès à Internet détiennent un système autonome. Pour assurer le routage entre les systèmes autonomes, un protocole de type EGP (Exterior Gateway Protocol) doit être mis en oeuvre. Dans le cas d'Internet, c'est généralement BGP (Border Gateway Protocol) qui assume cette mission. BGP, protocole supporté par Zebra, constitue un vaste terrain d'apprentissage.