Le routage

Objectifs du routage

Le but d’un protocole de routage est très simple : fournir l’information nécessaire pour effectuer un routage, c’est-à-dire la détermination d’un chemin à travers le réseau entre une machine émettrice et une machine réceptrice, toutes deux identifiées par leur adresse. Les protocoles de routage établissent des règles d’échange entre routeurs pour mettre à jour leurs tables selon des critères de coût comme, par exemple, la distance, l’état de la liaison, le débit. Ils améliorent ainsi l’efficacité du routage. La diversité des réseaux et de leurs services fait du routage un élément clé de leur bon fonctionnement. Il y a de très nombreux problèmes à résoudre. L’un des problèmes fondamentaux à éviter réside dans les boucles de routage (le message peut « tourner en rond » dans le réseau et ne jamais atteindre son destinataire). L’autre apparaît lorsqu’il y a une panne dans le réseau et qu’il faut optimiser le calcul des nouvelles routes : une fois la panne détectée, il faut transmettre l’information sur l’événement le plus rapidement possible pour que les différents routeurs recalculent par où faire passer leurs messages en contournant la liaison en panne. Le premier protocole de routage sur Internet fut RIP (Routing Information Protocol). On lui préfère aujourd’hui une version plus élaborée, OSPF (Open Shortest Path First). Le premier s’appuie sur un algorithme de la famille à vecteurs de distance. Le second utilise un algorithmes de la famille à état des liens. Dans les deux cas, les algorithmes de base sont issus de la théorie des graphes (Bellman1 -Ford, pour RIP, et Dijkstra2 , pour OSPF). La difficulté est de les mettre en œuvre dans des environnements réels avec efficacité, tout en minimisant la consommation des ressources réseau. Les tables de routage s’accroissent au fur et à mesure de la taille du réseau. Cela augmente l’espace mémoire nécessaire dans les routeurs et les ressources processeur. D’autre part, cela contribue à diminuer les performances du réseau, puisque celui-ci doit propager un important trafic entre les routeurs eux-mêmes. On découpe alors le réseau en sousensembles régionaux. À l’intérieur d’une région, les tables de routage contiennent une entrée par routeur (voir figure 8.1). De cette façon, l’interconnexion de réseaux différents est aisée. Une hiérarchisation à plusieurs niveaux peut s’envisager pour les très gros réseaux, même si la distance parcourue entre régions n’est pas globalement optimale. Le réseau Internet est ainsi organisé comme une collection de « systèmes autonomes », et une seule autorité administre en général chacun d’entre eux. On appelle système autonome, ou SA, un ensemble de réseaux interconnectés partageant la même 1. Richard Bellman (1920-1984), mathématicien américain, connu pour la programmation dynamique. 2. Edsger Dijkstra (1930-2002), chercheur hollandais, l’un des plus influents dans le domaine de l’informatique, récompensé par le prix ACM Turing. Figure 8.1 Un routeur A et sa table de routage. Réseau X A Réseau Z B Interface1 Interface2 Pour aller à Passer par Interface X Y Z _ _ B 1 2 2 Réseau Y Le routage 201 8 Chapitre stratégie de routage : tous les routeurs internes à un système autonome respectent le même protocole de routage régi par une autorité administrative (un département responsable spécifique comme un fournisseur d’accès ou toute autre organisation) [voir figure 8.2]. On désigne comme protocole interne aux routeurs, le protocole de routage ou IGP (Interior Gateway Protocol) utilisé à l’intérieur d’un système autonome. Par opposition, un protocole externe appelé EGP (Exterior Gateway Protocol) transfère les informations de routage entre les différents systèmes autonomes. 2 Principaux protocoles de routage Nous décrivons succinctement dans cette section les protocoles de routage internes RIP et OSPF puis le protocole externe BGP.

 RIP (ROUTING INFORMATION PROTOCOL)

On a conçu RIP (Routing Information Protocol) pour fonctionner en tant que protocole interne dans des systèmes autonomes de taille modérée. Sa première version fut standardisée en 1988 (RFC 1058). La RFC 1723 propose des améliorations depuis 1994. RIP recherche le plus court chemin selon un critère de coût simple : le nombre de routeurs traversés. Cela revient à affecter un coût unitaire à la traversée de chaque routeur. RIP appartient à la famille des protocoles à vecteurs de distance, puisqu’il calcule la distance, en nombre de routeurs traversés, entre origine et destination. Figure 8.2 Systèmes autonomes et protocoles de routage internes et externes. Sytème autonome Sytème autonome Sytème autonome Routeur interne Routeur externe 202 Architecture des réseaux Principe de fonctionnement Le protocole est limité aux réseaux dont le plus long chemin (qu’on appelle couramment le diamètre du réseau) implique quinze routeurs au maximum. Il est mal adapté au traitement des boucles dans les chemins et utilise des mesures du coût des chemins (ou métriques) fixes pour comparer les routes alternatives. Les situations où les routes doivent être choisies en fonction de paramètres mesurés en temps réel comme un délai, une fiabilité ou une charge, se prêtent mal à ce type de traitement. Un routeur RIP calcule des chemins pour différentes destinations, lesquelles sont spécifiées par leurs adresses IP, c’est-à-dire qu’une entrée dans la table peut représenter soit un réseau, soit un sous-réseau ou encore un nœud isolé. RIP ne spécifie pas le type de l’adresse : les routeurs découvrent la nature du destinataire en analysant les adresses transmises. Les routeurs RIP sont actifs ou passifs. Actifs, ils transmettent et reçoivent les routes : ils diffusent leurs informations aux autres routeurs. Passifs, ils ne font qu’attendre la réception des informations. En fonction de celles-ci, ils calculent leurs tables de routage mais ne partagent pas les résultats de leurs calculs avec d’autres routeurs. Le routeur RIP actif permet aux autres routeurs de mettre à jour leurs tables de routage toutes les 30 secondes. Si un routeur ne reçoit aucune mise à jour d’un autre routeur dans un délai de 180 secondes, il marque les routes desservies par ce dernier comme inutilisables. S’il n’y a aucune mise à jour après 240 secondes, le protocole RIP supprime toutes les entrées correspondant au routeur qui ne répond pas. Chaque diffusion RIP contient des paires adresses IP/nombre de routeurs à traverser (ou nombre de sauts). Comme le nombre de sauts est la seule mesure utilisée par le protocole, RIP ne garantit pas que le chemin sélectionné soit le plus rapide : un chemin court mais embouteillé peut être un mauvais choix par rapport à un chemin plus long mais totalement dégagé. Lorsqu’un événement dans le réseau provoque un changement dans la table de routage d’un routeur actif, celui-ci envoie un message de mise à jour à ses voisins. Si cet événement a un impact sur les voisins, ceux-ci propagent l’information. On utilise une temporisation afin de stabiliser l’état du réseau et garantir que tous les messages de mise à jour ont été pris en compte avant de renvoyer une nouvelle mise à jour. Variantes et améliorations Des variantes procurent des améliorations au fonctionnement du protocole. Au lieu de diffuser le même message sur toutes les liaisons qui les relient, les routeurs composent des versions différentes de leurs informations, pour tenir compte des destinations atteintes via chaque liaison. Par exemple, si un routeur A envoie, via B, les messages à destination de X, c’est inutile pour B d’essayer d’atteindre X via A. Deux variantes sont possibles : • Les routeurs ne donnent pas les informations sur les destinations atteintes à travers la liaison. Cette stratégie, dite « horizon partagé » (Split-Horizon), est la plus simple à implanter. • Les routeurs indiquent dans leurs messages toutes les destinations possibles mais ils affectent une distance infinie pour celles situées en aval de ce nœud. Cette variante, dite « horizon partagé avec retour empoisonné » (Split-Horizon with Poison-Reverse), élimine immédiatement toute boucle de longueur 2. Malgré ces améliorations, on ne supprime pas entièrement les risques de boucles. Exemple Soit un ensemble de trois routeurs A, B, C, illustrés à la figure 8.3, avec les tables de routage suivantes : routage(A) = [(A, 0, –) ; (B, 1, B) ; (C, 2, B)]. routage(B) = [(A, 1, A) ; (B, 0, –) ; (C, 1, C)]. routage(C) = [(A, 2, B) ; (B, 1, B) ; (C, 0, –)]. Le routage 203 8 Chapitre Le triplet (X, distance, Y) signifie « pour aller à X, passer par Y, le chemin est de longueur distance ». Si la liaison entre B et C tombe en panne, la table de B devient routage(B) = [(A, 1, A) ; (B, 0, –) ; (C, 16, C)]. En effet, 16 est considéré comme une destination inaccessible puisque le plus long chemin est de longueur 15. Quand A envoie sa table à B, celui-ci constate que A connaît une route de longueur 2 pour aller à C. Il met à jour sa propre table qui devient : (B) = [(A, 1, A) ; (B, 0, –) ; (C, 3, A)]. Cela crée une boucle puisque, pour aller à C, le routeur A envoie les messages vers B et le routeur B les renvoie vers A… La nouvelle version RIPv2 fonctionne sur le même principe. Ce protocole véhicule simplement des informations supplémentaires, comme une étiquette qui fait la distinction entre les routes internes apprises nativement par RIP et les routes externes apprises par un autre protocole de routage. Il transporte de même le masque de sous-réseau qui permet d’affiner les routes avec la connaissance des sous-réseaux ou de l’agrégation des adresses3 . Ces informations allègent la taille des tables de routage et participent à une meilleure efficacité du routage. D’autres fonctionnalités ont été proposées pour améliorer le fonctionnement du routage. On a cherché, par exemple, des moyens de rompre la synchronisation (les routeurs se mettent tous à diffuser leurs informations au même moment, et provoquent une rafale de trafic qui peut être insupportable). Puisque RIP utilise le protocole de transport UDP, on a imaginé des moyens d’acquitter de manière sûre la mise à jour, mais aussi de supporter plusieurs métriques, de rompre les boucles… Finalement, on a retenu une autre solution dans Internet : celle d’utiliser les protocoles à état des liens comme OSPF, considérés comme supérieurs aux protocoles à vecteurs de distance et que nous présentons à la section suivante. 

OSPF (OPEN SHORTEST PATH FIRST)

L’algorithme SPF (Shortest Path First) calcule le plus court chemin vers toutes les destinations de la zone ou du système autonome, en partant du routeur où s’effectue le calcul (à partir de sa base de données topologiques). Il utilise un algorithme conçu par Dijkstra et calcule le plus court chemin, selon un critère de coût où interviennent de multiples paramètres : l’état des liens, l’encombrement du réseau et des mémoires des routeurs intermédiaires. Figure 8.3 Trois routeurs et une boucle potentielle. 3. Cette expression désigne le regroupement du plus grand nombre de bits communs à deux ou plusieurs adresses IP. Par exemple, les adresses réseau : 195.67.65.0 et 195.67.127.0 ont leurs 17 premiers bits en commun. Pour un routeur donné, si le chemin pour atteindre les deux réseaux passe par le même routeur suivant, sa table de routage ne contiendra qu’une seule entrée pour les deux réseaux. Remarque Du point de vue de l’architecture en couches, le routage RIP est une application ; il utilise UDP comme protocole de transport avec le numéro de port 520. Un routeur RIP est donc une machine avec une architecture complète de protocoles, y compris Transport et Application. A B C 204 Architecture des réseaux Principe de fonctionnement Le calcul du plus court chemin est effectué de manière indépendante par tous les routeurs internes d’un système autonome SA. Grâce à cet algorithme, un routeur peut connaître le prochain routeur qui transmettra le message : il trouve les plus courts chemins (en termes de coût) d’un point à un autre, pour que le message arrive de manière optimale à son destinataire, puis il effectue la mise à jour de sa table de routage. Chaque mise à jour de la base de données entraîne celle de la table de routage. Il y a, comme précédemment, communication entre les routeurs. Celle-ci est régie par le protocole OSPF. Ce protocole définit les règles et les formats de messages entre routeurs OSPF internes à un système autonome. Il a la particularité de s’appuyer directement sur IP (et non sur UDP comme le protocole RIP). C’est une nette amélioration, car le routage devient un traitement interne à la couche réseau et n’est plus considéré comme une application. De plus, le fonctionnement d’OSPF est optimisé si le SA est découpé en zones ; OSPF prévoit un découpage avec une hiérarchie à deux niveaux de zones. La zone de niveau le plus élevé est l’épine dorsale (ou backbone zone). Elle interconnecte les « routeurs de bordure » (edge routers). À l’intérieur de chaque zone du second niveau, les routeurs ne connaissent – et ne diffusent – que des informations internes à leur zone. Un routeur de bordure dans chaque zone assure le lien avec l’épine dorsale, comme le montre la figure 8.4. Messages du protocole OSPF On distingue cinq messages OSPF : hello, description de base de données, requête d’état de lien, mise à jour d’état de lien, acquittement d’état de lien. Ils transportent des informations sur l’état des liaisons du SA et servent à déterminer une fonction de coût plus efficace que dans RIP. Un routeur OSPF émet des messages hello à intervalles réguliers (environ toutes les dix secondes), sur chacune de ses interfaces. Ces messages établissent les relations d’adjacence4 avec les routeurs directement liés à l’émetteur de ces messages. Les routeurs qui les ont reçus vérifient que les chemins restent disponibles. Sur un réseau possédant au moins deux routeurs, on élit un routeur désigné, c’est-à-dire le responsable qui échange avec les routeurs des réseaux voisins. Il s’occupe de la distribution des messages de mise à jour d’état de lien. Son choix se fait sur la base de la plus petite Figure 8.4 Hiérarchie d’organisation des zones OSPF. 4. Dans la théorie des graphes, deux nœuds sont adjacents s’ils sont directement reliés. Ici, la notion d’adjacence est légèrement différente, puisqu’elle ajoute une règle supplémentaire : le routeur désigné est adjacent à tous les autres. C’est l’efficacité qui prévaut : dans un réseau local, il est inutile que tous les routeurs participent au routage. Seul l’un entre eux est le routeur désigné, tous les autres lui sont adjacents. Routeur de bordure (protocole BGP par exemple) Système autonome Zone OSPF épine dorsale Zone OSPF de niveau inférieur Le routage 205 8 Chapitre adresse IP parmi les routeurs susceptibles d’assumer ce rôle. Deux routeurs R1 et R2 établissent une relation d’adjacence si et seulement s’ils sont reliés par un lien direct ou si l’un d’entre eux est routeur désigné. Lorsqu’une nouvelle adjacence s’établit entre deux routeurs, ils synchronisent leurs bases de données d’état des liens par le message description de base de données. Il est très important de protéger la base de données contre des erreurs (accidentelles ou dues à la malveillance), pour garantir la cohérence des calculs de chemins. Pour cela, on a prévu plusieurs précautions : acquittement, transmission sécurisée et temporisation des messages sur chaque liaison. Le message acquittement d’état de lien accuse réception d’une mise à jour : le routeur qui a envoyé ses indications de coût vers ses voisins sait que le message est bien parvenu. La transmission des messages de description de base de données est sécurisée : chaque enregistrement est protégé par un total de contrôle et tous les messages sont authentifiés. Cela évite d’éventuels messages qui contiendraient des informations erronées (éventuellement malveillantes, afin de détourner le trafic dans le réseau, par exemple). Enfin, on associe une temporisation à tout enregistrement : l’information contenue dans l’entrée de la table de routage sera supprimée si elle n’a pas été rafraîchie récemment : on préfère n’avoir aucune information momentanément plutôt qu’une information ancienne et inutilisable. Quand un routeur constate qu’une ou plusieurs des entrées de sa base de données sont périmées, il envoie une requête d’état de lien aux routeurs voisins pour faire la mise à jour des données. OSPF est aujourd’hui le protocole interne le plus utilisé dans Internet. La qualité des informations transportées et la sécurité associée sont ses principaux atouts.