Routage - Routing

Le routage est le processus de sélection d'un chemin pour le trafic dans un réseau ou entre ou à travers plusieurs réseaux. D'une manière générale, le routage est effectué dans de nombreux types de réseaux, y compris les réseaux à commutation de circuits , tels que le réseau téléphonique public commuté (PSTN), et les réseaux informatiques , tels qu'Internet .

Dans les réseaux à commutation de paquets, le routage est la prise de décision de niveau supérieur qui dirige les paquets réseau de leur source vers leur destination via des nœuds de réseau intermédiaires par des mécanismes de transfert de paquets spécifiques. Le transfert de paquets est le transit de paquets réseau d'une interface réseau à une autre. Les nœuds intermédiaires sont généralement des périphériques matériels de réseau tels que des routeurs , des passerelles , des pare - feu ou des commutateurs . Les ordinateurs à usage général transfèrent également les paquets et effectuent le routage, bien qu'ils ne disposent pas de matériel spécialement optimisé pour la tâche.

Le processus de routage dirige généralement le transfert sur la base de tables de routage . Les tables de routage conservent un enregistrement des routes vers diverses destinations du réseau. Les tables de routage peuvent être spécifiées par un administrateur, apprises en observant le trafic réseau ou construites à l'aide de protocoles de routage .

Le routage, dans un sens plus étroit du terme, fait souvent référence au routage IP et s'oppose au pontage . Le routage IP suppose que les adresses réseau sont structurées et que des adresses similaires impliquent une proximité au sein du réseau. Les adresses structurées permettent à une seule entrée de table de routage de représenter la route vers un groupe de périphériques. Dans les grands réseaux, l'adressage structuré (routage, au sens étroit) surpasse l'adressage non structuré (bridging). Le routage est devenu la forme dominante d'adressage sur Internet. Le pontage est encore largement utilisé au sein des réseaux locaux .

Schémas de livraison

Schémas de routage
Monodiffusion

Unicast.svg

Diffuser

Diffusion.svg

Multidiffusion

Multidiffusion.svg

Anycast

Anycast-BM.svg

Les schémas de routage diffèrent dans la manière dont ils transmettent les messages :

  • Unicast délivre un message à un seul nœud spécifique en utilisant une association un-à-un entre un expéditeur et une destination : chaque adresse de destination identifie de manière unique un seul point de terminaison récepteur.
  • La diffusion transmet un message à tous les nœuds du réseau à l'aide d'une association un-à-tous ; un seul datagramme (ou paquet ) d'un expéditeur est acheminé vers tous les points de terminaison éventuellement multiples associés à l' adresse de diffusion . Le réseau réplique automatiquement les datagrammes selon les besoins pour atteindre tous les destinataires dans le cadre de la diffusion, qui est généralement un sous- réseau entier .
  • La multidiffusion délivre un message à un groupe de nœuds qui ont exprimé leur intérêt à recevoir le message en utilisant une association un-plusieurs-plusieurs ou plusieurs-plusieurs-plusieurs ; les datagrammes sont routés simultanément en une seule transmission à plusieurs destinataires. La multidiffusion diffère de la diffusion en ce que l'adresse de destination désigne un sous-ensemble, pas nécessairement la totalité, des nœuds accessibles.
  • Anycast délivre un message à n'importe quel nœud d'un groupe de nœuds, généralement le plus proche de la source à l'aide d'une association un-à-un-plusieurs où les datagrammes sont acheminés vers un seul membre d'un groupe de récepteurs potentiels qui sont tous identifié par la même adresse de destination. L'algorithme de routage sélectionne le récepteur unique dans le groupe en fonction de celui qui est le plus proche en fonction d'une distance ou d'une mesure de coût.

La monodiffusion est la forme dominante de livraison de messages sur Internet. Cet article se concentre sur les algorithmes de routage unicast.

Répartition de la topologie

Avec le routage statique , les petits réseaux peuvent utiliser des tables de routage configurées manuellement. Les grands réseaux ont des topologies complexes qui peuvent changer rapidement, rendant la construction manuelle de tables de routage irréalisable. Néanmoins, la plupart du réseau téléphonique public commuté (RTC) utilise des tables de routage pré-calculées, avec des routes de repli si la route la plus directe est bloquée (voir routage dans le RTC ).

Le routage dynamique tente de résoudre ce problème en construisant automatiquement des tables de routage, sur la base des informations véhiculées par les protocoles de routage , permettant au réseau d'agir de manière presque autonome en évitant les pannes et les blocages du réseau. Le routage dynamique domine Internet. Des exemples de protocoles et d'algorithmes de routage dynamique incluent le protocole d'information de routage (RIP), l' OSPF ( Open Shortest Path First ) et le protocole de routage de passerelle intérieure amélioré (EIGRP).

Algorithmes vectoriels de distance

Les algorithmes à vecteur de distance utilisent l'algorithme de Bellman-Ford . Cette approche attribue un numéro de coût à chacun des liens entre chaque nœud du réseau. Les nœuds envoient des informations du point A au point B via le chemin qui conduit au coût total le plus faible (c'est-à-dire la somme des coûts des liens entre les nœuds utilisés).

Lorsqu'un nœud démarre pour la première fois, il ne connaît que ses voisins immédiats et le coût direct impliqué pour les atteindre. (Ces informations - la liste des destinations, le coût total pour chacune et le prochain saut pour envoyer des données pour y arriver - constituent la table de routage, ou table de distance .) Chaque nœud, sur une base régulière, envoie à chaque nœud voisin sa propre évaluation actuelle du coût total pour se rendre à toutes les destinations qu'il connaît. Les nœuds voisins examinent ces informations et les comparent à ce qu'ils connaissent déjà ; tout ce qui représente une amélioration par rapport à ce qu'ils ont déjà, ils l'insèrent dans leur propre tableau. Au fil du temps, tous les nœuds du réseau découvrent le meilleur saut suivant et le meilleur coût total pour toutes les destinations.

Lorsqu'un nœud de réseau tombe en panne, tous les nœuds qui l'ont utilisé comme leur prochain saut suppriment l'entrée et transmettent les informations de routage mises à jour à tous les nœuds adjacents, qui à leur tour répètent le processus. Finalement, tous les nœuds du réseau reçoivent les mises à jour et découvrent de nouveaux chemins vers toutes les destinations qui n'impliquent pas le nœud descendant.

Algorithmes d'état de lien

Lors de l'application d'algorithmes d'état de liens, une carte graphique du réseau constitue les données fondamentales utilisées pour chaque nœud. Pour produire sa carte, chaque nœud inonde l'ensemble du réseau d'informations sur les autres nœuds auxquels il peut se connecter. Chaque nœud assemble ensuite indépendamment ces informations dans une carte. À l'aide de cette carte, chaque routeur détermine indépendamment le chemin le moins coûteux de lui-même à chaque autre nœud en utilisant un algorithme standard des chemins les plus courts tel que l'algorithme de Dijkstra . Le résultat est un graphe arborescent enraciné au nœud actuel, de sorte que le chemin à travers l'arbre de la racine à tout autre nœud est le chemin le moins coûteux vers ce nœud. Cet arbre sert ensuite à construire la table de routage, qui spécifie le meilleur prochain saut à passer du nœud actuel à tout autre nœud.

Algorithme de routage d'état de lien optimisé

Un algorithme de routage à état de lien optimisé pour les réseaux mobiles ad hoc est le protocole OLSR (Link State Routing Protocol) optimisé. OLSR est proactif; il utilise des messages Hello et Topology Control (TC) pour découvrir et diffuser des informations sur l'état des liens via le réseau mobile ad hoc. À l'aide de messages Hello, chaque nœud découvre des informations de voisin à 2 sauts et élit un ensemble de relais multipoints (MPR). Les MPR distinguent OLSR des autres protocoles de routage à état de liens.

Protocole chemin-vecteur

Le routage à vecteur de distance et à état de lien sont tous deux des protocoles de routage intra-domaine. Ils sont utilisés à l'intérieur d'un système autonome , mais pas entre systèmes autonomes. Ces deux protocoles de routage deviennent insolubles dans les grands réseaux et ne peuvent pas être utilisés dans le routage inter-domaines . Le routage à vecteur de distance est sujet à instabilité s'il y a plus de quelques sauts dans le domaine. Le routage par état des liens nécessite des ressources importantes pour calculer les tables de routage. Il crée également un trafic intense en raison des inondations.

Le routage à vecteur de chemin est utilisé pour le routage inter-domaines. Il est similaire au routage à vecteur de distance. Le routage à vecteur de chemin suppose qu'un nœud (il peut y en avoir plusieurs) dans chaque système autonome agit au nom de l'ensemble du système autonome. Ce nœud est appelé nœud locuteur. Le nœud locuteur crée une table de routage et l'annonce aux nœuds locuteurs voisins dans les systèmes autonomes voisins. L'idée est la même que le routage à vecteur de distance, sauf que seuls les nœuds de haut-parleur de chaque système autonome peuvent communiquer entre eux. Le nœud locuteur annonce le chemin, et non la métrique, des nœuds de son système autonome ou d'autres systèmes autonomes.

L'algorithme de routage à vecteur de chemin est similaire à l'algorithme à vecteur de distance dans le sens où chaque routeur frontière annonce les destinations qu'il peut atteindre à son routeur voisin. Cependant, au lieu d'annoncer les réseaux en termes de destination et de distance jusqu'à cette destination, les réseaux sont annoncés en tant qu'adresses de destination et descriptions de chemin pour atteindre ces destinations. Le chemin, exprimé en termes de domaines (ou confédérations) traversés jusqu'à présent, est transporté dans un attribut de chemin spécial qui enregistre la séquence de domaines de routage par lesquels les informations d'accessibilité sont passées. Une route est définie comme un appariement entre une destination et les attributs du chemin vers cette destination, donc le nom, chemin-vecteur de routage ; Les routeurs reçoivent un vecteur qui contient des chemins vers un ensemble de destinations.

Sélection du chemin

La sélection de chemin implique l'application d'une métrique de routage à plusieurs routes pour sélectionner (ou prédire) la meilleure route. La plupart des algorithmes de routage n'utilisent qu'un seul chemin réseau à la fois. Le routage multivoies et en particulier les techniques de routage multivoies à coût égal permettent l'utilisation de plusieurs chemins alternatifs.

Dans les réseaux informatiques, la métrique est calculée par un algorithme de routage et peut couvrir des informations telles que la bande passante , le délai du réseau , le nombre de sauts , le coût du chemin, la charge, l' unité de transmission maximale , la fiabilité et le coût de communication. La table de routage ne stocke que les meilleurs itinéraires possibles, tandis que les bases de données d' état des liens ou topologiques peuvent également stocker toutes les autres informations.

En cas de chevauchement ou d'égalité des routes, les algorithmes prennent en compte les éléments suivants en priorité pour décider des routes à installer dans la table de routage :

  1. Longueur du préfixe : une entrée de table de routage correspondante avec un masque de sous-réseau plus long est toujours préférable car elle spécifie la destination plus précisément.
  2. Métrique : Lors de la comparaison des routes apprises via le même protocole de routage, une métrique inférieure est préférée. Les métriques ne peuvent pas être comparées entre les routes apprises à partir de différents protocoles de routage.
  3. Distance administrative : lors de la comparaison des entrées de la table de routage provenant de différentes sources telles que différents protocoles de routage et configuration statique, une distance administrative inférieure indique une source plus fiable et donc une route préférée.

Parce qu'une métrique de routage est spécifique à un protocole de routage donné, les routeurs multi-protocoles doivent utiliser une heuristique externe pour sélectionner entre les routes apprises à partir de différents protocoles de routage. Les routeurs Cisco , par exemple, attribuent une valeur connue sous le nom de distance administrative à chaque route, où des distances administratives plus petites indiquent des routes apprises à partir d'un protocole supposé être plus fiable.

Un administrateur local peut configurer des routes spécifiques à l'hôte qui offrent plus de contrôle sur l'utilisation du réseau, autorisent les tests et améliorent la sécurité globale. Ceci est utile pour déboguer les connexions réseau ou les tables de routage.

Dans certains petits systèmes, un seul périphérique central décide à l'avance du chemin complet de chaque paquet. Dans certains autres petits systèmes, quel que soit le périphérique de périphérie qui injecte un paquet dans le réseau, décide à l'avance du chemin complet de ce paquet particulier. Dans les deux cas, l'appareil de planification d'itinéraire doit connaître de nombreuses informations sur les appareils connectés au réseau et sur la manière dont ils sont connectés les uns aux autres. Une fois qu'il dispose de ces informations, il peut utiliser un algorithme tel que l' algorithme de recherche A* pour trouver le meilleur chemin.

Dans les systèmes à grande vitesse, il y a tellement de paquets transmis chaque seconde qu'il est impossible pour un seul appareil de calculer le chemin complet pour chaque paquet. Les premiers systèmes à grande vitesse traitaient cela de la commutation de circuits en établissant un chemin une fois pour le premier paquet entre une source et une destination ; les paquets ultérieurs entre cette même source et cette même destination continuent à suivre le même chemin sans recalculer jusqu'au démontage du circuit . Les systèmes à grande vitesse ultérieurs injectent des paquets dans le réseau sans qu'aucun périphérique ne calcule jamais un chemin complet pour les paquets.

Dans les grands systèmes, il y a tellement de connexions entre les appareils, et ces connexions changent si fréquemment, qu'il est impossible pour un appareil de savoir comment tous les appareils sont connectés les uns aux autres, et encore moins de calculer un chemin complet à travers eux. De tels systèmes utilisent généralement le routage de saut suivant .

La plupart des systèmes utilisent un algorithme de routage dynamique déterministe . Lorsqu'un appareil choisit un chemin vers une destination finale particulière, cet appareil choisit toujours le même chemin vers cette destination jusqu'à ce qu'il reçoive des informations qui lui font penser qu'un autre chemin est meilleur.

Quelques algorithmes de routage n'utilisent pas d'algorithme déterministe pour trouver le meilleur lien pour un paquet à obtenir de sa source d'origine à sa destination finale. Au lieu de cela, pour éviter les points chauds de congestion dans les systèmes de paquets, quelques algorithmes utilisent un algorithme aléatoire - le paradigme de Valiant - qui achemine un chemin vers une destination intermédiaire choisie au hasard, et de là vers sa véritable destination finale. Dans de nombreux premiers commutateurs téléphoniques, un randomiseur était souvent utilisé pour sélectionner le début d'un chemin à travers une matrice de commutation à plusieurs étages .

Selon l'application pour laquelle la sélection de chemin est effectuée, différentes métriques peuvent être utilisées. Par exemple, pour les requêtes Web, on peut utiliser des chemins de latence minimum pour minimiser le temps de chargement des pages Web, ou pour les transferts de données en masse, on peut choisir le chemin le moins utilisé pour équilibrer la charge sur le réseau et augmenter le débit. Un objectif de sélection de chemin populaire est de réduire les temps d'achèvement moyens des flux de trafic et la consommation totale de bande passante du réseau. Récemment, une métrique de sélection de chemin a été proposée qui calcule le nombre total d'octets programmés sur les bords par chemin en tant que métrique de sélection. Une analyse empirique de plusieurs métriques de sélection de chemin, y compris cette nouvelle proposition, a été rendue disponible.

Agents multiples

Dans certains réseaux, le routage est compliqué par le fait qu'aucune entité n'est responsable de la sélection des chemins ; au lieu de cela, plusieurs entités sont impliquées dans la sélection de chemins ou même de parties d'un seul chemin. Des complications ou une inefficacité peuvent survenir si ces entités choisissent des voies pour optimiser leurs propres objectifs, ce qui peut entrer en conflit avec les objectifs des autres participants.

Un exemple classique concerne le trafic dans un système routier, dans lequel chaque conducteur choisit un chemin qui minimise son temps de trajet. Avec un tel routage, les itinéraires d' équilibre peuvent être plus longs qu'optimaux pour tous les conducteurs. En particulier, le paradoxe de Braess montre que l'ajout d'une nouvelle route peut allonger les temps de trajet pour tous les conducteurs.

Dans un modèle mono-agent utilisé par exemple pour le routage de véhicules à guidage automatique (AGV) sur un terminal, des réservations sont effectuées pour chaque véhicule afin d'éviter l'utilisation simultanée d'une même partie d'une infrastructure. Cette approche est également appelée routage contextuel.

Internet est divisé en systèmes autonomes (AS) tels que les fournisseurs de services Internet (FAI), dont chacun contrôle les routes impliquant son réseau. Le routage se produit à plusieurs niveaux. Tout d'abord, les chemins de niveau AS sont sélectionnés via le protocole BGP qui produit une séquence d'AS à travers laquelle les paquets circulent. Chaque AS peut avoir plusieurs chemins, proposés par des AS voisins, parmi lesquels choisir. Ces décisions de routage sont souvent en corrélation avec les relations commerciales avec ces AS voisins, qui peuvent être sans rapport avec la qualité du chemin ou la latence. Deuxièmement, une fois qu'un chemin au niveau AS a été sélectionné, il existe souvent plusieurs chemins correspondants au niveau du routeur parmi lesquels choisir. Cela est dû en partie au fait que deux FAI peuvent être connectés via plusieurs connexions. En choisissant le chemin unique au niveau du routeur, il est courant pour chaque FAI d'utiliser le routage hot-potate : envoyer le trafic le long du chemin qui minimise la distance à travers le propre réseau du FAI, même si ce chemin allonge la distance totale jusqu'à la destination.

Par exemple, considérons deux FAI, A et B . Chacun a une présence à New York , relié par une liaison rapide avec latencems — et chacun a une présence à Londres reliée par une liaison de 5 ms. Supposons que les deux fournisseurs d' accès Internet ont des liens transatlantiques qui relient leurs deux réseaux, mais un « lien de latence a 100 ms et B » a une latence de 120 ms s. Lors de l' acheminement d' un message à partir d' une source dans un « réseau de Londres à destination de B » réseau de New York s, A peut choisir d'envoyer immédiatement le message à B à Londres. Cela évite à A de l'envoyer le long d'une liaison transatlantique coûteuse, mais provoque une latence du message de 125 ms alors que l'autre route aurait été 20 ms plus rapide.

Une étude de mesure des routes Internet de 2003 a révélé qu'entre des paires de FAI voisins, plus de 30 % des chemins avaient une latence gonflée en raison du routage de la patate chaude, avec 5 % des chemins retardés d'au moins 12 ms. L'inflation due à la sélection de chemin au niveau de l'AS, bien que substantielle, a été attribuée principalement à l'absence de mécanisme de BGP pour optimiser directement la latence, plutôt qu'à des politiques de routage égoïstes. Il a également été suggéré que, si un mécanisme approprié était en place, les FAI seraient disposés à coopérer pour réduire la latence plutôt que d'utiliser le routage de la patate chaude. Un tel mécanisme a ensuite été publié par les mêmes auteurs, d'abord pour le cas de deux FAI puis pour le cas global.

Analyse d'itinéraire

Comme Internet et les réseaux IP sont devenus des outils commerciaux critiques , il y a eu un intérêt accru pour les techniques et les méthodes de surveillance de la position de routage des réseaux. Des problèmes de routage ou de routage incorrects entraînent une dégradation indésirable des performances, des battements ou des temps d'arrêt. La surveillance du routage dans un réseau est réalisée à l'aide d' outils et de techniques d' analyse de route .

Routage centralisé

Dans les réseaux où un contrôle logiquement centralisé est disponible sur l'état de transfert, par exemple, à l'aide d'un réseau défini par logiciel , des techniques de routage peuvent être utilisées pour optimiser les mesures de performances globales et à l'échelle du réseau. Cela a été utilisé par de grandes sociétés Internet qui exploitent de nombreux centres de données dans différents emplacements géographiques connectés à l'aide de liens optiques privés, notamment le WAN mondial de Microsoft, l'Express Backbone de Facebook et le B4 de Google. Les mesures de performances globales à optimiser incluent la maximisation de l'utilisation du réseau, la minimisation des délais d'exécution du flux de trafic et la maximisation du trafic livré avant des échéances spécifiques. La minimisation des temps d'exécution des flux sur le WAN privé, en particulier, n'a pas reçu beaucoup d'attention de la part de la communauté des chercheurs. Cependant, avec le nombre croissant d'entreprises qui exploitent des centres de données répartis dans le monde entier connectés à l'aide de réseaux privés inter-centres de données, il est probable que les efforts de recherche dans ce domaine s'intensifient. Un travail très récent sur la réduction des temps d'achèvement des flux sur le WAN privé aborde la modélisation du routage comme un problème d'optimisation de graphe en poussant toutes les files d'attente aux points de terminaison. Les auteurs proposent également une heuristique pour résoudre le problème efficacement tout en sacrifiant des performances négligeables.

Voir également

Les références

Lectures complémentaires

Liens externes