FPGA and Traffic Network Analysis

1.5 UAlgorithmes et métriques de routage [1]

Un algorithme est une solution détaillée d'un problème. Les algorithmes utilisés pour définir le port auquel envoyer un paquet diffèrent selon les protocoles de routage. Ils reposent sur l'utilisation de métriques pour prendre ce type de décision.

Les protocoles de routage sont conçus pour répondre à un ou plusieurs des objectifs suivants :

· Optimisation : capacité d'un algorithme de routage à sélectionner le meilleur chemin. Ce dernier sera choisi en fonction des métriques et de la pondération utilisées dans le calcul. Par exemple, un algorithme peut utiliser à la fois le nombre de sauts et le délai comme métriques, mais considérer que le délai doit prévaloir dans le calcul.

· Simplicité et réduction du temps système : plus l'algorithme est simple et plus il sera traité efficacement par le processeur et la mémoire du routeur. Ce paramètre est important si le réseau veut pouvoir évoluer vers des proportions plus conséquentes, comme Internet.

· Efficacité et stabilité : un algorithme de routage doit pouvoir fonctionner correctement dans des circonstances inhabituelles ou imprévues, comme les défaillances de matériels, les surcharges et les erreurs de mise en oeuvre.

· Flexibilité : un algorithme de routage doit pouvoir s'adapter rapidement à toutes sortes de modifications du réseau, touchant par exemple la disponibilité et la mémoire du routeur, la bande passante ou le délai réseau.

· Rapidité de convergence : la convergence est le processus par lequel tous les routeurs s'entendent sur les routes disponibles. Lorsqu'un événement sur le réseau entraîne des modifications au niveau de la disponibilité d'un routeur, des mises à jour sont nécessaires afin de rétablir la connectivité du réseau. Une convergence lente des algorithmes de routage peut empêcher la livraison des données.

Les algorithmes de routage utilisent différentes métriques pour déterminer la meilleure route (voire tableau1.5a).

Protocole	Métrique	Nombre maxi de routeur	Origine
Protocole RIP	Nombre de sauts	15	Xerox
Protocole IGRP	· Bande passante · Charge · Délai · Fiabilité	255	Cisco

UTableau1.2U : UAlgorithmes et métriques de routageU

Chacun d'eux interprète à sa façon ce qui est le mieux. L'algorithme génère un nombre, appelé valeur métrique, pour chaque chemin traversant le réseau. Les algorithmes de routage perfectionnés effectuent la sélection du chemin en fonction de plusieurs métriques combinées en une valeur composite. Généralement, les valeurs métriques faibles indiquent le meilleur chemin.

Les métriques peuvent être calculées sur la base d'une seule caractéristique de chemin, comme elles peuvent l'être sur la base de plusieurs. Les métriques les plus communément utilisées par les protocoles de routage sont les suivantes:

· Bande passante : la bande passante représente la capacité de débit d'une liaison. Une liaison Ethernet de 10 Mbits/s est généralement préférable à une ligne louée de 64 Kbits/s.

· Délai : le délai est le temps nécessaire à l'acheminement d'un paquet, pour chaque liaison, de la source à la destination. Il dépend de la bande passante des liaisons intermédiaires, de la quantité de données pouvant être temporairement stockées sur chaque routeur, de la congestion du réseau et de la distance physique.

· Charge : la charge est la quantité de trafic sur une ressource réseau telle qu'un routeur ou une liaison.

· Fiabilité : la fiabilité se rapporte habituellement au taux d'erreurs de chaque liaison du réseau.

· Nombre de sauts : le nombre de sauts est le nombre de routeurs par lesquels un paquet doit passer avant d'arriver à destination. Chaque routeur équivaut à un saut. Un nombre de sauts égal à 4 signifie que les données doivent passer par quatre routeurs pour atteindre leur destination. Lorsque plusieurs chemins sont possibles, c'est le chemin comportant le moins de sauts qui est privilégié.

· Tops : délai d'une liaison de données utilisant les tops d'horloge d'un PC IBM, un top d'horloge correspondant environ à 1/18 seconde.

· Coût : le coût est une valeur arbitraire, généralement basée sur la bande passante, une dépense monétaire ou une autre mesure, attribuée par un administrateur réseau.