Le routage.

 Le routage des paquets dans un réseau maillé consiste à fixer par quelle ligne de sortie chaque commutateur réexpédie les paquets qu'il reçoit. Ceci se fait en fonction de la destination finale du paquet et selon une table de routage qui indique pour chaque destination finale quelles sont les voies de sortie possible.

Pour l'exemple de la figure 1.17 on pourrait avoir la table de routage suivante :

 

destination finale voie de sortie

D1 A1, A2

D2 A2

D3 A2, A3

D4 A3

  

Figure 1.17: Routage de paquets.

D'une manière générale le routage est un ensemble de processus algorithmiques devant prendre des décisions dispersés dans le temps et dans l'espace. Les différents algorithmes sont répartis sur chaque nud du réseau et l'ensemble peut fonctionner de manière centralisée ou répartie.

• Le routage centralisé est géré par un nud particulier du réseau qui reçoit des informations de chacun des nuds du réseau et leur envoie leur table de routage. Pour fixer ces tables on prend en compte notamment le coût des liaisons, le coût de passage dans un nud, le débit demandé, le nombre de nuds à traverser, la sécurité de transport de certains paquets, l'occupation des mémoires des nuds de commutation,... Le plus souvent un algorithme de plus court chemin donne de bons résultats en fixant à 1 le coût de franchissement d'un nud (on peut également pondérer plus fortement les nuds qui sont les plus occupés). La mise à jour des tables de routage peut se faire de manière
  • fixe : en fait il n'y a pas de mise à jour, la table de routage est fixée une fois pour toute en fonction de la topologie du réseau.
  • synchrone : toutes les tables sont mises à jour au même moment par le centre de contrôle qui reçoit des informations de la part de tous les nuds à intervalles réguliers (toutes les 10 sec par exemple).
  • asynchrone : les tables sont mises à jour indépendamment les unes des autres dans certaines parties du réseau, chaque nud envoyant un compte-rendu de son état au centre de contrôle lorsqu'il observe des changements significatifs.
  Mais le routage centralisé dans un réseau à grande échelle est peu performant, car un routage est d'autant meilleur qu'il réagit rapidement aux informations qui lui parviennent. De plus, si une panne survient dans l'ordinateur qui assure ce contrôle, c'est tout le réseau qui tombe en panne.
• Le routage décentralisé ne possède pas de centre de contrôle et les rêgles de passage d'un paquet (paquet d'appel pour établissement d'un circuit virtuel) sont :
  • l'inondation : à la réception d'un paquet celui-ci est renvoyé sur toutes les lignes de sortie. Cette technique simpliste et rapide est efficace dans les réseaux à trafic faible et où le temps réél est nécessaire mais elle est pénalisante en flux de données, inadaptée aux réseaux complexe et au circuit virtuel.
  • la technique <<hot patatoes >> : un paquet reçu est renvoyé le plus tôt possible par la première ligne de sortie vide. On améliore ce principe en affectant des coefficients à chaque ligne de sortie en fonction de la destination voulue. On tient compte de l'état des nuds voisins, sans utiliser de paquet de contrôle, mais simplement en comptabilisant le nombre de paquets reçus de chacun d'eux. Ils peuvent également envoyer de manière synchrone ou asynchrone un compte-rendu de leur état, permettant ainsi de choisir la <<meilleure>> ligne à un instant donné. Mais ceci reste local et une panne du réseau localisée au-delà du premier nud voisin ne pourra pas être prise en compte.
  • le routage adaptatif à la fois dans l'espace et dans le temps demande, de la part de chaque nud, une connaissance complète du réseau. Les différents nuds s'échangent donc des messages, mais si chacun envoie des messages à tous les autres le trafic va augmenter de manière baucoup trop grande. C'est pourquoi un nud ne transmet un compte-rendu qu'à ses voisins immédiats qui doivent en tenir compte dans leur propre compte-rendu. (voir exemple)

D'une manière générale, le routage doit éviter l'usage d'algorithmes adaptatifs trop complexes et limiter les dialogues de services entre les nuds sinon l'effet obtenu sera à l'opposé de celui recherché.