Initiation au routage

Les grands principes d’OSPF

OSPF est un protocole de routage dynamique déﬁni par l’IETF à la ﬁn des années 80. Il a fait l’objet d’un historique relativement complexe de RFCs (Voir ospf RFC List). Ce protocole a deux caractéristiques essentielles :
• Il est ouvert : c’est le sens du terme Open de OSPF. Son fonctionnement est connu de tous.
• Il utilise l’algorithme SPF pour Shortest Path First, plus connu sous le nom d’algorithme de Dijkstra, aﬁn d’élire la meilleure route vers une destination donnée. Examinons une topologie qui nous servira de support pour les explications :
Exemple de topologie Figure 1. Exemple de topologie 3.1. La notion de coût Supposons que du routeur R1 on cherche à atteindre le réseau 192.168.1.0. Dans une telle situation, Le protocole RIP aurait élu la route passant par R5 puisque c’est la plus courte en termes de saut. Cependant, imaginez que les liens représentés sous forme d’éclairs soient «rapides» (de type FastEthernet à 100 Mbps par exemple) et que les liens représentés sous formes de segments droits soient «lents» (de type Ethernet à 10 Mbps par exemple). Le choix du protocole RIP n’est plus du tout pertinent ! Le protocole OSPF fonctionne différemment. Il attribue un coût à chaque liaison (appelée lien dans le jargon OSPF) aﬁn de privilégier l’élection de certaines routes. Plus le coût est faible, plus le lien est intéressant. Dans le cas où l’on utilise des interfaces avec un débit supérieur, il est possible de redéﬁnir la référence avec une commande du type auto-cost reference-bandwidth 1000 pour la valeur 10^9. Le protocole OSPF privilégie les routes qui ont un coût faible, donc celles qui sont supposées rapides en terme de débit théorique.

La base de données topologique

Avec le protocole OSPF, tous les routeurs d’un même réseau (on parle de «zone» dans le vocabulaire OSPF, ceci vous sera expliqué avant la mise en pratique) travaillent sur une base de données topologique identique qui décrit le réseau. Cette base a été constituée pendant une première phase de découverte qui vous sera expliquée un peu plus loin. Examinons la base de données suivante qui décrit la topologie de la Figure 1, « Exemple de topologie » :
Arc Coût R1, R2 1 R1, R5 10 R2, R3 1 R3, R4 10 R3, R5 1 R4, R5 10 R4, 192.168.1.0 10

L’élection des meilleures routes

L ‘algorithme SPF de Dijsktra va traiter cette base de données aﬁn de déterminer les routes les moins coûteuses. Une fois le traitement réalisé, chaque routeur se voit comme la racine d’un arbre contenant les meilleures routes.

Le fonctionnement d’OSPF

Un peu plus en détail Pour administrer un réseau OSPF correctement, il est indispensable de comprendre le fonctionnement interne du protocole. à l’intérieur d’une même zone, les routeurs fonctionnant sous OSPF doivent préalablement remplir les tâches suivantes avant de pouvoir effectuer leur travail de routage : 1. Section 4.2, « Établir la liste des routeurs voisins : Hello, my name is R1 and I’m an OSPF router. », 2. Section 4.3, « Élire le routeur désigné et le routeur désigné de secours », 3. Section 4.4, « Découvrir les routes », 4. Section 4.5, « Élire les routes à utiliser », 5. Section 4.6, « Maintenir la base topologique ».

État initial

Le processus de routage OSPF est inactif sur tous les routeurs de la Figure 1, « Exemple de topologie ».

Établir 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, « Exemple de topologie », 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.

Élire le routeur désigné et le routeur désigné de secours

Dans une zone OSPF composée de réseaux de diffusion (broadcast networks) ou de réseaux à accès multiples sans diffusion (NBMA ou non broadcast multiple access networks), pour chacun de ces deux types de réseau, un routeur doit être élu «routeur désigné» (DR ou Designated Router) et un autre «routeur désigné de secours» (BDR ou Backup Designated Router). Le «routeur désigné» (DR) est un routeur particulier qui sert de référent pour la base de données topologique représentant le réseau. Pourquoi élire un routeur désigné ? Cela répond à trois objectifs : • réduire le traﬁc lié à l’échange d’informations sur l’état des liens (car il n’y a pas d’échange entre tous les routeurs mais entre chaque routeur et le DR), • améliorer l’intégrité de la base de données topologique (car cette base de données doit être unique), • 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é (Router ID ou RID). La priorité est un nombre sur 8 bits ﬁxé par défaut à 1 sur tous les routeurs. Pour départager les routeurs ayant la même priorité, celui qui est élu a la plus grande adresse IP sur une interface de boucle locale (loopback interface) ou sur un autre type d’interface active. Le BDR sera le routeur avec la deuxième plus grande priorité. Aﬁn de s’assurer que votre routeur préféré sera élu DR, il sufﬁt 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 et son successeur Quagga étant multiprotocoles, ils peuvent é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.

Élire 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. 4.6. 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ègrent cette information à leur base topologique. Le DR et diffuse l’information sur l’adresse 224.0.0.5 (tous les routeurs OSPF sans distinction). C’est le protocole d’inondation. Toute modiﬁcation de la topologie déclenche une nouvelle exécution de l’algorithme du SPF et une nouvelle table de routage est constituée.

Conclusion partielle

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 RFC2328 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, aﬁn 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, identiﬁé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.