Les protocoles s'appuient sur des algorithmes. Quels critères doivent être pris en comptes pour analyser correctement leur performance?

• Quels échanges de données sont nécessaires pour leur fonctionnement?
• Ces échanges occupent ils une part importante de la capacité des liens?
• A quelle vitesse convergent t-ils?
• etc

Ce sont ces critères qui rentreront en ligne de compte lorsqu' un gestionnaire de réseau devra choisir et régler les paramètres d'un protocole de routage.

Pour rappel le routage au sein d'un réseau consiste essentiellement à trouver pour chaque paquet un chemin vers la bonne sortie: le paquet entre par un routeur et doit ressortir par une autre routeur qui le rapproche le plus possible de sa vraie destination.

Pour trouver la bonne sortie et le bon chemin vers la sortie, on peut imaginer de nombreuses solutions/stratégies. Il faut garder à l'esprit les principes du routage à vecteur de distance et du routage a état de lien.

A également été évoqué le cas du routage statique, dans lequel un centre de contrôle acquiert la connaissance de la cartographie complète du réseau, exécute un algorithme de calcul des plus courts chemins (tel que l'algorithme de Dijkstra) et redistribue les routes ainsi calculées à tous les routeurs. Cette solution est assez semblable au routage à état de lien si ce n'est que les messages contenant la cartographie locale sont envoyés à un récepteur unique: le centre de contrôle. Cette stratégie est désignée routage statique centralisé.

Si on souhaite minimiser les échanges entre routeurs et conserver au maximum la bande passante pour les données utiles, on peut adopter une stratégie n'ayant pas besoins de communiquer les tables de routage. On peut tout à fait envoyer tout le trafic vers un point central connaissant toutes les routes et qui inclus dans l’entête du paquet la liste ordonnée des routeurs à parcourir. Chaque routeur examinera alors l'entete pour déterminer le prochain routeur, et aucun d'eux n'aura besoin de maintenir une table de routage. Cette stratégie est désignée par routage pré-calculé.

Cas extrême, on peut également adopter une stratégie de routage aléatoire. Chaque paquet reçu est envoyé aléatoirement à une destination et on espère que tôt ou tard, la bonne destination sera atteinte. Cela peut fonctionner, néanmoins un paquet pourra errer très longtemps au sein d’un réseau.

A l'inverse, un routeur envoyer un paquet à tous les routeurs auxquels ils est connecté: cette stratégie est dite par inondation. Elle offre la garantie de trouver la bonne sortie assez rapidement puisque sont explorés en parallèle tous les chemins possibles.

Toutes ces stratégies peuvent fonctionner pour acheminer un paquet vers un routeur de destination dans un réseau. Cependant elles ne sont pas toutes aussi efficaces.

Correspond à l'ensemble des messages que s'échangent les routeurs pour connaître leur voisinage, acquérir les données nécessaires à l’exécution de leurs algorithmes de calcul des routes etc. C'est tout le trafic qui n'est pas explicitement du trafic de données: on le désigne par surcoût du protocole.

Le débit disponible pour acheminer des paquets de données est égal au débit moins le surcoût du protocole. Ce surcoût ne doit donc pas être trop important.

• Le routage aléatoire et l’inondation ne nécessitent aucun trafic de contrôle.
• Pour le routage à vecteur de distance, toute la table de routage doit être transmise mais seulement aux voisins directs.
• Pour le routage à état de lien volumétrie plus faible permettant de définir le voisinage mais il devra être transmis à tous les routeurs du réseau.
• Dans le cas du routage statique centralisé, les paquets décrivant le voisinage de chaque nœuds ne sont plus envoyés qu'à une seule destination: le centre de contrôle, ce qui permet d'économiser du trafic de contrôle. Il faut cependant retransmettre toutes les tables actualisés à tous les routeurs.
• Le routage pré-calculé n'a pas à retransmettre les tables de routage. Le centre de contrôle est le seul à connaître les routes. Il reçoit que tous les paquets décrivant le voisinage et calcule les routes. En revanche il sera sur le chemin de chaque paquet et devra faire face à un volume de trafic très important.

Au delà de la seule volumétrie du trafic de contrôle, on doit s'interroger sur l'efficacité du processus de relayage.

Si chaque paquet doit parcourir un chemin beaucoup plus long que le chemin le plus court, l'économie faite sur le trafic de contrôle risque d'être rapidement compensée par l'ensemble des retransmissions inutiles.

Si l'on considère les stratégies d'inondation ou de routage aléatoire par exemple, leur fonctionnement va provoquer un nombre de réémissions du même paquet beaucoup plus important que nécessaire puisqu'on va dupliquer le paquet à l’extrême dans le cas de l'inondation ou traverser aléatoirement un grand nombre de routeurs dans le second cas.

C'est justement dans ce cas que les protocole de vecteur de distance ou à état de lien sont très efficaces. Ils sont capable de déterminer non pas un chemin valide mais le meilleur chemin au sens d'un critère sélectionné tel que la longueur des routes, la bande passante, le délai de bout en bout etc

Le routage statique centralisé, lui aussi calcule a priori les meilleurs routes possibles mais de manière centralisé. Le principal désavantage, est sa fragilité. Si le centre de contrôle tombe en panne, l'ensemble du réseau perd sa capacité à s'adapter au changement de configuration et risque de ne plus fonctionner du tout.

On voit ici se dessiner les contours d'un autre critère de performance: la robustesse du protocole de routage.

Le routage centralisé n'est pas très robuste. Le routage pré-calculé l'est encore moins puisque toute la connaissance des routes dans le réseau n'est présente qu'en un seul point.

• Dans cas du routage centralisé, une panne du centre de contrôle fera perdre au réseau sa capacité d'adaptation mais les routes calculées continueront à fonctionner.
• Dans le cas du routage pré-calculé, le centre de contrôle étant un point de passage obligé, tout le réseau sera HS.
• Au contraire, le routage aléatoire et l'inondation sont robustes face aux pannes puisque aucun élément n'est indispensable.
• Les protocoles de routage distribués sont également robustes puisque aucun point du réseau n'est privilégié.

La réactivité est également un critère de performance important. C'est le temps nécessaire entre le moment ou un événement tel qu'une panne survient et le moment où le changement est pris en compte sur l'ensemble des routeurs du réseau.

• Dans le cas du routage à vecteur de distance, le temps est fonction du point où a lieu l’événement et le point le plus éloigné dans le réseau. Il peut mettre un certain temps à converger.
• Le routage à état de lien, est à priori plus réactif, puisqu'il suffit que le ou les routeurs ayant détecté le problème transmettent l'information à tous les autres routeurs du réseau.Le temps d'inonder le réseau une fois.

La performance d'un protocole de routage peut donc être caractérisée selon plusieurs critères:

• Surcoût du protocole
• Qualité des routes calculées
• Robustesse
• Réactivité aux pannes

Aucun algorithme n'est parfait et tout est question de compromis. Un administrateur réseau aura pour tâche de sélectionner le protocole de routage qui réalisera le compromis qu' il désire dans son réseau en prenant en compte les caractéristiques de celui-ci:

• la taille du réseau
• son étendue
• la fiabilité des équipements
• la charge imposée au réseau
• les besoins en qualité de service des flux de données

Même les stratégies les plus incongrues telles le routage aléatoire ou l'inondation peuvent être le meilleur choix par exemple dans des réseaux où tous les éléments, même les routeurs sont mobiles.

• Seuls le routage aléatoire et l'inondation ne nécessitent aucun trafic de contrôle puisque, dans ces deux cas, aucune route n'est calculée. Dans toutes les autres stratégies, il est nécessaire au minimum d'échanger, avec un centre de contrôle ou un autre routeur, des paquets afin de déterminer les routes.
• Quels protocoles génèrent des routes de coût minimal? Le but des algorithmes de routage, qu'ils soient centralisés ou distribués, est de calculer la route la meilleure au sens d'un critère donné (longueur, débit…). L'inondation, du fait qu'elle explore tous les chemins en parallèle, fera forcément emprunter au paquet de données le meilleur chemin, ainsi que plusieurs autres très mauvais. Dans le cas du routage pré-calculé, les paquets passent par un intermédiaire, ce qui rallonge leur route même si celle-ci est optimale de l'entrée à l'intermédiaire et de l'intermédiaire à la sortie.
• En général quel protocole génère le moins de trafic de contrôle entre le routage à vecteur de distance et le routage à état de liens? Il n'y a pas de cas général. Tout dépend des caractéristiques du réseau : de sa taille, de son étendue, de la taille des tables de routage, etc.