Protocoles de routage par état de liaisons, OSPF

Ce document présente les protocoles de routage par état de liaison, en particulier le protocole OSPF (Open Shortest Path First). Il s’adresse aux étudiants et professionnels en réseaux informatiques souhaitant comprendre le fonctionnement, la configuration et les mécanismes internes d’OSPF ainsi que l’algorithme de Dijkstra utilisé pour le calcul des chemins les plus courts.

Routage par état de liaison

Les protocoles de routage par état de liaison, aussi appelés protocoles SPF (Shortest Path First), reposent sur l’algorithme de Dijkstra. Chaque routeur connaît ses propres liaisons et réseaux directement connectés, détecte ses voisins, puis crée un paquet LSP (Link-State Packet) décrivant l’état de ses liaisons. Ce LSP est diffusé à tous ses voisins, qui le stockent dans une base de données commune. Chaque routeur utilise cette base pour construire une carte complète de la topologie et calculer le chemin le plus court vers chaque réseau de destination.

Processus de routage par état de liaison

1. Étude des réseaux connectés directement : Chaque routeur identifie les réseaux auxquels il est directement connecté.
2. Découverte des voisins : Les routeurs échangent des paquets Hello pour détecter leurs voisins directs.
3. Création des LSP : Chaque routeur crée un LSP contenant l’état de ses liaisons.
4. Diffusion des LSP : Les LSP sont immédiatement inondés vers tous les voisins sans calcul intermédiaire, ce qui accélère la convergence par rapport aux protocoles à vecteur de distance.
5. Construction de la base de données : Tous les LSP reçus sont stockés dans une base de données d’état des liaisons.
6. Calcul de l’arborescence SPF : À partir de la base de données, chaque routeur calcule l’arborescence SPF pour déterminer les meilleurs chemins.

Un LSP est envoyé uniquement au démarrage du routeur ou lors d’une modification de la topologie (activation/désactivation d’une liaison ou changement de voisinage).

Exemple de diffusion des LSP

Le routeur R1 crée son LSP et le diffuse à ses voisins. Ces derniers stockent le LSP dans leur base de données et le propagent à leur tour, assurant ainsi une inondation rapide et complète des informations de topologie.

Élaboration de l’arborescence SPF

Chaque routeur utilise l’algorithme SPF pour construire une arborescence représentant les chemins les plus courts vers tous les réseaux connus. Par exemple, le routeur R1 calcule les chemins suivants :

• Réseau 10.5.0.0/16 via R2 (interface série 0/0/0), coût 22
• Réseau 10.6.0.0/16 via R3 (interface série 0/0/1), coût 7
• Réseau 10.7.0.0/16 via R3 (interface série 0/0/1), coût 15
• Réseau 10.8.0.0/16 via R3 (interface série 0/0/1), coût 17
• Réseau 10.9.0.0/16 via R2 (interface série 0/0/0), coût 30
• Réseau 10.10.0.0/16 via R3 (interface série 0/0/1), coût 25
• Réseau 10.11.0.0/16 via R3 (interface série 0/0/1), coût 27

Ces routes sont ensuite ajoutées à la table de routage du routeur.

Avantages des protocoles par état de liaison

• Chaque routeur crée sa propre carte topologique pour déterminer les chemins optimaux.
• L’inondation immédiate des LSP permet une convergence rapide.
• Les LSP sont envoyés uniquement en cas de modification de la topologie, réduisant le trafic inutile.
• Une architecture hiérarchique par zones améliore l’évolutivité.

Le protocole OSPF : format et fonctionnement

OSPF utilise plusieurs types de paquets, notamment les paquets Hello pour la découverte des voisins. L’intervalle Dead correspond au temps d’attente avant de déclarer un voisin hors service, généralement égal à 4 fois l’intervalle Hello (par exemple, Hello = 10 s, Dead = 40 s).

OSPF applique l’algorithme de Dijkstra pour calculer les chemins les plus courts à partir des informations contenues dans la base de données d’état des liaisons.

Configuration OSPF de base

Pour activer OSPF sur un routeur Cisco, la commande globale est :

router ospf process-id

Le process-id est un nombre local (entre 1 et 65535) choisi par l’administrateur et n’a pas besoin de correspondre sur tous les routeurs.

La commande network active OSPF sur les interfaces correspondant à une adresse réseau donnée :

Router(config-router)# network adresse_réseau masque_générique area area-id

Le masque générique est l’inverse du masque de sous-réseau. Par exemple, pour un masque /28 (255.255.255.240), le masque générique est 0.0.0.15.

La zone OSPF (area) regroupe les routeurs partageant la même base de données d’état des liaisons.

ID du routeur OSPF

L’ID de routeur OSPF identifie de manière unique chaque routeur dans un domaine OSPF. Il s’agit d’une adresse IP choisie selon l’ordre de priorité :

1. Adresse IP configurée manuellement avec la commande router-id.
2. Adresse IP la plus élevée parmi les interfaces de bouclage (loopback).
3. Adresse IP la plus élevée parmi les interfaces physiques actives.

Exemple :

• R1 : ID = 192.168.10.5 (supérieur à 172.16.1.17)
• R2 : ID = 192.168.10.9
• R3 : ID = 192.168.10.10

Les interfaces de bouclage sont des interfaces virtuelles toujours actives, configurées ainsi :

Router(config)# interface loopback number
Router(config-if)# ip address ip-address masque_sous_réseau

Autres commandes de vérification OSPF

• show ip protocols : affiche les protocoles de routage actifs.
• show ip ospf : affiche les informations OSPF globales.
• show ip ospf interface : détaille les interfaces OSPF et leurs états.

Examen de la table de routage OSPF

La table de routage contient les routes calculées par OSPF, avec les chemins optimaux vers chaque réseau connu, basés sur l’arborescence SPF.

Mesure OSPF : le coût

Le coût OSPF est une métrique associée à chaque interface de sortie d’un routeur, configurée par l’administrateur. Plus le coût est faible, plus l’interface est privilégiée pour acheminer le trafic.

Le coût est calculé par la formule :

coût = 10^8 / bande passante (en bits/s)

Par défaut, la bande passante de référence est 100 000 000 (100 Mbits/s), ce qui donne un coût de 1 pour les interfaces Fast Ethernet et supérieures.

Pour des réseaux plus rapides (Gigabit Ethernet, 10 Gigabit Ethernet), la bande passante de référence peut être modifiée avec la commande :

ospf auto-cost reference-bandwidth valeur

où valeur est exprimée en Mbits/s (par exemple 10 000 pour 10 Gigabit).

Modification du coût d’une liaison

Le coût peut aussi être modifié manuellement sur une interface pour influencer le choix des chemins OSPF.

OSPF et les réseaux à accès multiples

Dans les réseaux à accès multiple (ex. Ethernet), OSPF doit gérer :

• La création de contiguïtés multiples entre chaque paire de routeurs.
• La diffusion massive de LSA (Link-State Advertisements).

Pour résoudre ces problèmes, OSPF désigne :

• Un routeur désigné (DR) chargé de collecter et diffuser les LSA.
• Un routeur désigné de secours (BDR) prêt à prendre la relève en cas de panne du DR.
• Les autres routeurs sont appelés DROthers et n’envoient leurs LSA qu’au DR et BDR via l’adresse multicast 224.0.0.6 (ALLDRouters).

Le DR diffuse ensuite les LSA à tous les routeurs OSPF via l’adresse multicast 224.0.0.5 (AllSPFRouters).

Processus de sélection DR/BDR

La sélection du DR et du BDR ne s’applique pas aux réseaux point à point. Dans un réseau à accès multiple, la sélection se fait selon :

1. Le routeur avec la priorité d’interface OSPF la plus élevée devient DR.
2. Le routeur avec la seconde priorité la plus élevée devient BDR.
3. En cas d’égalité des priorités, c’est l’ID de routeur le plus élevé qui est choisi.

Exemple : Trois routeurs sur un réseau Ethernet 192.168.1.0/24 avec priorité OSPF par défaut (1). Le routeur avec l’ID le plus élevé devient DR, le second BDR, et le troisième DROther.

Modification de la priorité

La priorité OSPF d’une interface peut être modifiée pour forcer la sélection du DR ou BDR.

Algorithme de Dijkstra

OSPF utilise l’algorithme de Dijkstra pour calculer les chemins les plus courts dans le réseau. Contrairement à RIP (basé sur Bellman-Ford), OSPF évite les boucles en ayant une connaissance instantanée de la topologie grâce à l’inondation des états de liaison.

Le principe est :

• Chaque nœud connaît le coût de ses liens (un coût infini signifie un lien inactif).
• Le réseau est inondé par les états de liaison.
• On construit un arbre des chemins les plus courts depuis un nœud source vers tous les autres.

Pseudocode simplifié de Dijkstra

spf = {s}  # ensemble des nœuds dont le plus court chemin est connu
pour chaque nœud v adjacent à s:
    cost[v] = c(s, v)
pour les autres nœuds:
    cost[v] = ∞

répéter:
    choisir un nœud u non dans spf avec le coût minimal
    ajouter u à spf
    mettre à jour cost[v] pour tous les voisins v de u si un chemin plus court est trouvé
jusqu’à ce que tous les nœuds soient dans spf

Exemple d’application

Soit la source s = b, l’algorithme calcule progressivement les plus courts chemins vers les nœuds a, c, d, e, f, en mettant à jour les coûts et en ajoutant un nœud à la fois à l’ensemble spf.

Par exemple, le chemin le plus court de b vers f est :

f ← e ← c ← a ← b

Ce qui signifie que pour atteindre f depuis b, on passe par a, puis c, puis e.

Glossaire des termes clés

• OSPF (Open Shortest Path First) : protocole de routage par état de liaison utilisant l’algorithme de Dijkstra.
• LSP (Link-State Packet) : paquet contenant l’état des liaisons d’un routeur, diffusé à ses voisins.
• SPF (Shortest Path First) : algorithme de calcul des chemins les plus courts, aussi appelé algorithme de Dijkstra.
• DR (Designated Router) : routeur désigné chargé de collecter et diffuser les LSA dans un réseau à accès multiple.
• BDR (Backup Designated Router) : routeur désigné de secours prêt à prendre la place du DR en cas de panne.
• DROther : routeurs autres que DR et BDR dans un réseau à accès multiple.
• ID de routeur OSPF : identifiant unique d’un routeur dans un domaine OSPF, généralement une adresse IP.
• Coût OSPF : métrique utilisée pour évaluer la qualité d’une liaison, inversement proportionnelle à la bande passante.
• Base de données d’état des liaisons : ensemble des LSP reçus et stockés par un routeur pour construire la topologie réseau.
• Paquets Hello : paquets échangés périodiquement pour découvrir et maintenir les voisins OSPF.

Points clés à retenir

• Les protocoles par état de liaison comme OSPF utilisent l’algorithme de Dijkstra pour calculer les chemins les plus courts.
• Chaque routeur construit une carte complète de la topologie réseau à partir des LSP diffusés par tous les routeurs.
• La diffusion rapide et ciblée des LSP permet une convergence plus rapide qu’avec les protocoles à vecteur de distance.
• OSPF utilise une architecture hiérarchique avec des zones pour améliorer l’évolutivité.
• Dans les réseaux à accès multiple, un routeur désigné (DR) et un routeur désigné de secours (BDR) sont élus pour gérer la diffusion des LSA.
• Le coût OSPF est calculé en fonction de la bande passante, et peut être ajusté pour refléter les débits réels des interfaces.
• L’ID de routeur OSPF est essentiel pour l’identification unique et la sélection du DR/BDR.