Algorithmes de routage

Les algorithmes de routage calculent les chemins que les paquets empruntent à travers un réseau, généralement en identifiant les routes de moindre coût sur un graphe de routeurs et de liaisons, soit à l'aide d'une vue globale de l'état des liaisons, soit par un calcul distribué de vecteur de distance, voisin par voisin.

Definition

Un algorithme de routage est une procédure qui détermine les chemins de moindre coût (ou autrement préférés) à travers un réseau modélisé comme un graphe pondéré, produisant les décisions de transfert que les routeurs utilisent pour acheminer les paquets vers leurs destinations.

Scope

Ce sujet aborde les algorithmes qui remplissent les tables de routage (ou de transfert) : le modèle de graphe d'un réseau avec les coûts des liaisons ; le routage par état de liens utilisant l'algorithme de Dijkstra pour le chemin le plus court avec une topologie partagée globalement ; le routage par vecteur de distance utilisant le calcul distribué de Bellman-Ford avec des échanges entre voisins ; leur comportement de convergence et leurs pathologies, telles que le problème du « count-to-infinity » ; et le routage hiérarchique pour l'évolutivité. Il traite les algorithmes de manière abstraite, laissant les protocoles concrets (OSPF, RIP, BGP) et leur organisation intra/inter-domaine au sujet des protocoles de routage.

Core questions

• Comment un réseau est-il modélisé comme un graphe pondéré pour le routage ?
• Comment un algorithme à état de liens calcule-t-il les chemins les plus courts à partir d'une vue complète de la topologie ?
• Comment un algorithme à vecteur de distance converge-t-il en utilisant uniquement des échanges entre voisins ?
• Quels sont les problèmes de convergence et de stabilité, tels que le « count-to-infinity », et comment sont-ils atténués ?
• Pourquoi le routage est-il rendu hiérarchique, et comment cela affecte-t-il l'optimalité des chemins ?

Key concepts

• graphe de réseau pondéré
• chemins de moindre coût
• routage par état de liens
• algorithme de Dijkstra
• routage par vecteur de distance
• équation de Bellman-Ford
• problème du « count-to-infinity »
• horizon partagé (split horizon) et inversion empoisonnée (poisoned reverse)
• routage hiérarchique

Key theories

Link-state routing (Dijkstra)

Chaque routeur diffuse les coûts de ses liaisons afin que tous les routeurs partagent la topologie complète, puis exécute indépendamment l'algorithme de Dijkstra pour calculer les chemins les plus courts ; cela converge rapidement et de manière prévisible, mais nécessite un échange d'informations global.

Distance-vector routing (Bellman-Ford)

Les routeurs échangent leurs estimations actuelles de moindre coût vers chaque destination avec leurs voisins et les mettent à jour via l'équation de Bellman-Ford ; le calcul est distribué et n'utilise que des informations locales, mais peut converger lentement et souffrir du problème du « count-to-infinity ».

Hierarchical routing

Étant donné que le routage « plat » (flat routing) ne s'adapte pas à l'ensemble d'Internet, les routeurs sont regroupés en régions (systèmes autonomes) avec un routage géré localement à l'intérieur de chaque région et résumé entre elles, échangeant une certaine optimalité de chemin contre l'évolutivité et l'autonomie administrative.

Clinical relevance

Les algorithmes de routage déterminent l'efficacité et la fiabilité du flux de trafic : les algorithmes à état de liens sous-tendent les protocoles internes tels qu'OSPF qui convergent rapidement après des pannes, tandis que les concepts de vecteur de distance apparaissent dans RIP et dans l'approche de vecteur de chemin de BGP. Comprendre leur comportement de convergence est essentiel pour concevoir des réseaux stables et diagnostiquer les boucles de routage et la lenteur de la récupération après des pannes de liaison ou de routeur.

History

Les algorithmes de chemin le plus court, au cœur du routage, sont antérieurs aux réseaux informatiques : les travaux de Bellman et Ford sur les problèmes de routage à la fin des années 1950 et l'algorithme de Dijkstra de 1959 pour le chemin le plus court. À mesure que les réseaux à commutation de paquets se sont développés, ceux-ci ont été adaptés au routage par vecteur de distance et par état de liens, et la structuration hiérarchique en systèmes autonomes a permis au routage de s'étendre à l'Internet mondial.

Debates

Link-state versus distance-vector routing

Le routage par état de liens converge rapidement et évite le « count-to-infinity » mais exige que chaque routeur détienne la topologie complète et effectue plus de calculs, tandis que le vecteur de distance est plus simple et plus local mais peut converger lentement et former des boucles transitoires ; les réseaux réels combinent les deux approches à différentes échelles.

Key figures

• Edsger W. Dijkstra
• Richard Bellman
• Lester Ford

Seminal works

• dijkstra1959
• bellman1958
• kurose2021

Frequently asked questions

Qu'est-ce que le problème du « count-to-infinity » ?

C'est une pathologie du routage par vecteur de distance dans laquelle, après la défaillance d'une liaison, les routeurs augmentent lentement leurs estimations de distance vers une destination inaccessible en échangeant des informations obsolètes, croyant à tort qu'un chemin existe toujours à travers l'un l'autre. Les atténuations incluent l'horizon partagé (split horizon), l'inversion empoisonnée (poisoned reverse) et la limitation de la distance maximale.

Pourquoi les routages par état de liens et par vecteur de distance sont-ils tous deux utilisés ?

Ils conviennent à des portées différentes. Les protocoles à état de liens comme OSPF offrent une convergence rapide et sans boucle au sein d'un même domaine administratif où le partage de la topologie complète est acceptable. Les approches par vecteur de distance et par vecteur de chemin s'adaptent mieux et révèlent moins de détails internes entre les domaines, c'est pourquoi BGP utilise une conception par vecteur de chemin entre les réseaux.