Routage dans les réseaux de communication
boule

Routage avec faible trafic de contrôle

La problématique du routage

Le problème est d'établir les tables de routage à travers plusieurs liens de communication, alors que bien sûr, au départ, on ne connait rien de la topologie du réseau.

Concrêtement, un mécanisme distribué doit construire et maintenir la table de routage de chaque routeur — par exemple en S :

DestinationProchain saut
II
JJ
KJ
MJ
DJ
Si le lien entre S et J ou J à L venait à disparaître, il faut alors recalculer des tables de routage, en évitant à tout prix les boucles de routage, où un routeur se retrouve à recevoir du trafic qui est déjà passé par lui (qu'il re-transmet au même endroit etc.)

Le routage dans Internet

Le premier protocole de routage est aussi le plus simple : c'est RIP (Routing Information Protocol). RIP est un protocole à vecteur de distance, pouvant générer beaucoup de trafic et des boucles de routage transitoires. On parle également d'algorithme de Bellman-Ford distribué.
(le protocole actuel est RIPv2)
EIGRP, développé par Cisco, est également basé sur le principe du vecteur de distance mais utilise la Diffusing computation en cas d'augmentation du coût d'une arête (la disparition d'une arête équivaut à un coup infini). Ce mécanisme corrige les problème de RIP, et donc il n'y a pas de boucle transitoire. Ce protocole présente beaucoup de bonne caractéristiques : il est relativement léger, rapide…

Plus communs aujourd'hui, OSPF (la solution par défaut, complexe) ou IS-IS (principes similaires à OSPF, un peu moins bavard ?) utilisent des algorithmes "à état des liens" (link states). En un mot, chaque routeur construit une représentation de la topologie du réseau et calcule les tables de routage dessus. Toute la difficulté est d'avoir des bases de données topologiques cohérentes.

En fait, dans Internet, il y a deux niveaux de hiérarchie : pour le routage entre les réseaux (aussi appelés AS — Autonomous Systems), le protocole est BGP.

BGP est à protocole à vecteur de chemin : on connait les chemins vers toutes les destinations, ce qui évite l'apparition des boucles transitoires typiques de RIP, mais pas toutes ! (Mais on ne l'a compris qu'en 2003 !)

Autres protocoles de routage

Réseaux Ad hoc

AODV, OLSR sont des protocoles dédiés au routage dans des réseaux fortement dynamiques. AODV est un protocole à vecteur de distance (comme RIP), OLSR est de la famille des protocoles à état des liens, avec l'idée de diminuer le trafic d'inondation dans le réseau (concept de MultiPoint Relay — MPR).

Réseaux mesh

Babel (RFC 8966) utilise un principe proche de celui d'EIGRP. Il se destine aux réseaux sans fil multisaut d'accès à Internet.

Réseaux de capteur

Les réseaux de capteur ont été l'objet de beaucoup d'attention depuis 2010. Il s'agit de router entre des équipement contraints en énergie (et par conséquent portée de communication, capacité). Les protocoles utilisent des variations des algorithmes à vecteur de distance.
  • RPL est la solution promue à l'IETF. Ce protocole est complexe et polymophe, avec de nombreux défauts.
  • Un variante de RPL serait utilisée pour les réseaux Wi-SUN.
  • Les compteurs Linky d'Enedis utilisent LOADng pour transmettre et relayer les informations vers et depuis le transformateur BT.

Le routage au LIG

Partant de travaux plus anciens et de la constatation des défauts des protocoles existants , l'objectif de LRP (Lightweight Routing Protocol) développé dans l'équipe Drakkar est de se focaliser sur un arbre (en fait un DODAG) pour lequel un nœud particulier (le puit) joue un rôle central. On ne maintient la connectivité qu'avec lui, le reste du trafic monte et descend sur l'ossature (l'idée est la même que dans RPL, inévitable pour certaines structures de réseau). Cette présentation en synthétise les grandes principes (voir également la thèse de doctorat d'Henry-Joseph Audéoud).

Quelques caractéristiques de LRP :

Contributeurs principaux : Martin Heusse, Chi-Anh La, Liviu Varga, Henry-Joseph Audéoud.
Laboratoire LIG UMR 5217 - 700 Avenue centrale 38 400 Saint Martin d'Hères - France