Skip to content

M4.3 Réseaux - Chap4 - Routage

Nous avons vu dans les cours précédent le routage statique et la traduction d'adresse NAT. Rappelons que le routage consiste à acheminer un paquet d'une machine source à la machine destination. Sur Internet, un ensemble de routeurs, très grand et changeant constamment, est en charge de l'acheminement des paquets. Le routage statique entre tous ces routeurs est alors inenvisageable. Dans ce dernier item, nous verrons donc ce qu'apporte le routage dynamique et comment il fonctionne.

1. Routage dynamique

diapo 3 La diapositive présente les réseaux traversés par une requête au site web de l'université de Santiago depuis la maison d'un particulier. On sépare les réseaux traversés en 4 groupe. * Le réseau vert du domicile est un réseau local privé (habituellement de classe C et d'adresse 192.168.1.0), il a une box d'accès à Internet ayant notamment la fonction de routeur. Via le protocole NAT pour les paquets IPv4 et directement pour IPv6, la box est passerelle par défaut, elle a une table de routage statique de 2 lignes et achemine ainsi tous les paquets destinés à l'extérieur vers le routeur du réseau du fournisseur d'accès à Internet (FAI). * Le réseau rouge représente le réseau du fournisseur d'accès à Internet. Il dispose de plusieurs routeurs connectés entre eux. Cela permet d'assurer une continuité de fonctionnement en cas de panne ou de maintenance d'un équipement et peut également permettre de partager le traffic sur plusieurs routes pour éviter les congestions. * Le réseau violet est celui d'un fournisseur de services (par exemple les serveurs de l'université de Santiago) à qui est destinée la requête. Ce réseau est divisé via des routeurs en plusieurs sous-réseaux, pour des raisons de sécurité et de résistance aux pannes notamment. * Enfin, le dernier réseau entrant en jeu est le réseau nommé ici coeur d'internet, en bleu qui représente tous les autres routeurs d'Internet participant à l'acheminement du paquet. Ils appartiennent à différents opérateurs, qui seront présentés un peu plus loin dans ce cours. Les groupes de routeurs de chaque opérateur sont nommés Systèmes Autonomes.

diapo 4

La commande traceroute (tracert sous Windows) nous indique les routeurs traversés par les paquets pour atteindre le serveur de l'université de Santiago. Le site web de RIPE qui gère les IPs pour l'Europe et celui de g-force donnent des indications sur les propriétaires des routeurs d'Internet, identifiés par leur adresse IP. Les étoiles indiquent qu'un routeur n'a pas répondu ou mal répondu aux requêtes liées à traceroute.

traceroute6 effectuerait la même recherche de parcours, en ipv6.

Sur le chemin indiqué par traceroute, on note le passage par la box, l'arrivée chez le fournisseur d'accès Orange. Orange est un opérateur du coeur d'Internet, il est donc connecté directement à Level3, autre opérateur du coeur d'internet. Enfin, le paquet arrive sur le site puis sur le serveur du fournisseur de service, en l'occurence l'université de Santiago.

diapo 5

Mis à part le réseau du domicile, très simple, un routage efficace (c'est-à-dire un acheminement fiable et rapide des paquets) dans les 3 autres réseaux est complexe car le nombre de routeurs de ce réseau est important. On distingue le routage interne, à l'intérieur d'un même système autonome, du routage externe, entre ces systèmes autonomes.

En interne, chaque opérateur maitrise tous les routeurs de son système autonome et choisit la méthode de routage lui convenant. Pour établir les tables de routage, il serait possible de proposer un routage statique centralisé. Ce serait complexe et fastidieux, vu le grand nombre de routeur et devrait être refait à chaque panne d'un routeur. Cela ne fonctionnerait plus si la liaison avec le centre d'élaboration du routage statique tombait en panne. C'est pourquoi il est souvent préféré un protocole de routage distribué dans les routeurs et itératifs pour plus de simplicité et pour une cicatrisation automatique du réseau.

En externe, entre les différents systèmes autonomes d'Internet, la méthode de routage, BGP, est imposée et sera l'objet de la dernière partie de ce cours.

diapo 6

Le routage interne doit être cohérent (c'est-à-dire sans boucle) et pour chaque destination, le routeur doit proposer un port de sortie.

Comme indiqué précédemment, le routage dynamique est distribué et itératif, c'est-à-dire que chaque routeur élabore régulièrement ses routes à partir des informations reçues des autres routeurs.

Le routage dynamique demande donc à ce que les routeurs échangent des informations entre eux. Le protocole est donc un compromis entre l'efficacité du routage, le temps de cicatrisation et les taille et fréquence d'envoi des messages d'informations inter-routeurs.

2 protocoles parmi les plus utilisés seront présentés ici : RIP et OSPF.

diapo 7 RIP

RIP (Routing Information Protocol) est le premier algorithme de routage dynamique à avoir été mis en oeuvre sur ARPAnet, il est aussi nommé algorithme de Bellman-Ford, en hommage à ses développeurs.

Dans les tables de routage sont indiqués également le nombre de saut pour atteindre le réseau de destination. Un saut étant le passage par un routeur.

L'échange inter-routeur est l'envoi par chaque routeur à ses voisins de sa table de routage.

il devient lourd lorsque le nombre de noeuds augmente (les tables transmises deviennent très grandes)

On reprend ici le réseau du fournisseur d'accès à internet. Il dispose de 5 routeurs, chacun ayant 2 à 4 interfaces réseaux reliés à des réseaux /24 (communément appelés de classe C). On ne s'intéresse ici qu'au routage interne. Regardons comment le protocole RIP permet l'établissement des tables de routage.

diapo 8 RIP

Au démarrage du réseau, chaque routeur connaît les adresses et sous-réseaux de ses propres interfaces. Chacun envoie alors en Multicast (via l'adresse 224.0.0.9) à ses voisins sa table de routage. * Le routeur A envoie sa table de routage, * Le routeur B met à jour sa table de routage, * Le routeur D met à jour sa table de routage, * Le routeur D envoie ensuite sa table de routage avec la métrique associée. * C mettent alors à jour leur table de routage. * Un paquet envoyé de la maison en bas à droite vers la maison en haut à gauche (d'adresse 10.01.3.3) sera ainsi envoyé par E vers C puis de C vers A qui trouvera la maison sur son interface 3.

Les échanges continuent ensuite, menant à un routage complet, et ensuite, les échanges de tables ou de changement dans les tables pour faire plus léger, permettent de prendre en compte les évolutions ou pannes du réseau. En cas de présence de 2 chemins pour atteindre un réseau, c'est celui avec la métrique (le nombre de sauts) la plus petite qui est choisi.

diapo 9 RIP

RIP est efficace pour obtenir un chemin optimal en nombre de saut. Cependant : * Les tables échangées sont vite très grandes * Tous les liens sont perçus comme équivalents, un nombre de saut plus faible n'étant pas forcément synonyme d'un chemin plus court ou plus rapide. * La prise en compte d’une panne ou d'un changement de topologie est long.

C'est pourquoi pour des réseaux de taille importante, on préfère au protocole RIP le protocole OSPF.

diapo 10 OSPF

Dès 1979, RIP est remplacé par un algorithme de routage par état de liens sur ARPAnet. OSPF, normalisé en 1990, est le descendant de ce protocole. Il continue d'évoluer (la version 3 publiée en 2008 prend en compte ipv6) et est très utilisé pour le routage dynamique internet.

OSPF signifie Open Shortest Path First

A la différence de RIP, chaque routeur va former la cartographie complète du réseau, en notant ses voisins et le coût du lien. Ce coût du lien est souvent inversement proportionnel à la bande passante de la ligne. Il peut être aussi choisi proportionnel au temps d'un aller-retour entre les deux voisins. * Chaque routeur envoie un paquet multicast "Hello" à ses voisins, toutes les 10 s habituellement, pour s'annoncer. Les destinataires répondent alors par un paquet "Hello" également. * Chaque routeur envoie ensuite, dans un message LSA à tous les routeurs du réseau local, la liste de tous ses voisins directs et le coût de ces liens .

Chaque routeur a alors la carte complète du réseau et utilise l’algorithme Djikstra de recherche de plus court chemin pour créer sa table de routage. Regardons ce qu'il se passe sur le réseau du fournisseur de service, composé de 5 routeurs.

diapo 11

Au démarrage du réseau, le routeur A envoie des messages "Hello" en multicast (adresse 224.0.0.5) via toutes ses interfaces. Il répétera ensuite ces envois toutes les 10 s pour permettre la détection de panne.

Les routeurs ne transmettent pas ces messages, qui ne sont donc reçus que par les voisins directs.

Le routeur B, voisin direct, reçoit le message et met à jour sa liste de voisins en attribuant un coût au lien, ici 1 pour une liaison 10 Gbit/s,

Le routeur D fait de même,

Il envoie ensuite un message "hello" à ses voisins.

Les routeurs A, E, C peuvent alors mettre à jour leur liste de voisins.

De cette manière, chaque routeur a rapidement la liste de ses voisins.

diapo 12

Les messages LSA Link-State Advertisements permettent de propager les informations de voisinage de chaque routeur.

  • Une fois qu'un routeur, A ici, connaît la liste de ses voisins, il diffuse l'information de son voisinage (information assez courte) à l'ensemble des routeurs du réseau, via un paquet DBD (DataBase Description) en multicast.
  • Si un routeur, ici le routeur D, ne connaît pas un des routeurs du paquet DBD envoyé par A, il va faire une requête LSR (Link-State Request) d'informations complémentaires.
  • Le routeur A envoie alors les informations de ses liens avec B via une réponse LSU (Link-State Update).
  • Le routeur D met à jour sa table LSDB Link-State DataBase avec ses nouvelles informations et envoie un acquittement.
  • De la même manière, B enverra des informations et la table LSDB arrivera à une description complète du réseau.

diapo 13

Chaque routeur dispose alors d'une cartographie complète du réseau qu'il va utiliser pour compléter sa table de routage. Il utilise pour cela l'algorithme de recherche du plus court chemin de Djikstra.

L'algorithme de Djikstra consiste à ajouter les routeurs à la table de routage, en cherchant le coût minimum.

D ajoutera ainsi d'abord E pour un coût 1 et d'éventuels réseaux accessibles par C.

En cas de défaillance de E par exemple, celui-ci n'envoie plus de messages "hello" et OSPF ajustera alors automatiquement la table de routage de D pour atteindre B via C.

OSPF est aujourd'hui très utilisé et comporte des extensions, notamment la possibilité de créer des zones pour limiter les échanges, ou de choisir quelques routeurs centralisant l'information pour limiter les messages LSA. La version 3 d'OSPF supporte le routage ipv6.

diapo 14

Les algorithmes de routage interne nécessitent que les routeurs concernés utilisent le même algorithme et ils fonctionnent, notamment pour OSPF, avec un nombre de routeurs important (une centaine), mais limité tout de même.

Ils sont donc utilisés pour le routage dynamique dans un ensemble de routeurs d'une même entreprise ou d'un même opérateur. Ces ensembles sont nommés systèmes autonomes. Ils ont quelques interfaces avec l'extérieur.

Le routage externe quant à lui concerne le routage entre la centaine de milliers de systèmes autonomes de l'Internet. En plus de la grande taille du réseau, il doit prendre en compte des aspects économiques ou politiques pour privilégier certains chemins. Pour l'ensemble de l'Internet, ce routage externe utilise le protocole BGP (Border Gateway Protocol).

diapo 15 Structure Internet

Pour comprendre certains aspects du routage externe, commençons par détailler un peu la structure de l'Internet. Chaque système autonome (SA en anglais) a un numéro attribué par l'IANA via les registres régionaux, comme pour les adresses IP. Par exemple, l'université Paris Saclay a le numéro 2269 attribué par RIPE.

Les systèmes autonomes de quelques opérateurs, classés Tier 1 (que l'on peut traduire par niveau 1), ont un large accès à Internet grâce à de grands réseaux de fibres optiques et à des accords d'échanges (dit de peering) entre eux. . Ils sont peu nombreux (une vingtaine dans le monde) et forment la colonne vertébrale d'Internet. Orange, Level 3, Deutsch Telecom sont 3 d'entre eux.

Ces opérateurs facturent cet accès à leur client, c'est un accord de transit.

Ces clients, pour diminuer leur facture et améliorer les performances,établissent des interconnexions entre eux avec des accords de peering. . Sont apparus alors des points d'échanges, interconnexions (payantes) entre de nombreux systèmes autonomes Tier2. On dénombre une vingtaine de points d'échange en France.

Les opérateurs classés Tier 2 utilisent un ou plusieurs opérateurs de niveau 1 pour accéder à l'ensemble de l'Internet mais on aussi des accords de peering, notamment via des points d'échange. Ils proposent des accords de transit à d'autres systèmes. Les systèmes classés Tier 3 sont seulement clients d'accords de transit. Ils peuvent avoir aussi des accords de peering, notamment via des points d'échange.

diapo 16 BGP

Voyons maintenant les grandes lignes du protocole de routage externe BGP.

Via ce protocole circulant sur des paquets IP, les systèmes autonomes annoncent à leurs voisins les préfixes auxquels ils ont accès par des messages eBGP (external BGP).
Les systèmes autonomes relaient les annonces de préfixes, avec les chemins de systèmes autonomes à traverser. (On parle de protocole à vecteur de chemin) Le SA A relaie ainsi à son client C les informations reçues de son autre client B.

Les principaux messages eBGP entre 2 routeurs en frontière de système autonome sont OPEN pour ouvrir la connexion, KEEP ALIVE pour garder la connexion et UPDATE pour informer d'un changement dans les préfixes annoncés.

Dans cet exemple, l'opérateur C a reçu plusieurs routes possibles pour atteindre les serveurs de l'entreprise et de l'université.

Il faut donc ajouter une stratégie de routage, stratégie décidée par l'opérateur. Pour le système autonome C, le lien de peering vers le système autonome B pourrait être privilégié car gratuit, à la différence du lien de transit vers le système autonome A. L'opérateur C va alors ajouter une préférence locale sur son routeur C vers B. Sinon, on choisit le chemin le plus court (c'est-à-dire avec le moins de systèmes autonomes à traverser, ce qui n'est pas forcément le chemin le meilleur en terme de débit, latence ou nombre de routeurs traversés)

Les critères peuvent aussi être politiques pour favoriser des routes évitant de traverser des systèmes autonomes concurrents ou ennemis.

Les routeurs BGP d'un même système autonome s'informent via des messages iBGP (Internal BGP).