Protocoles & algorithmes de routage

- Dernière mise à jour le 26 Juillet 2000 -

Pour constituer sa table de routage,
un routeur doit être informé, ou s'informer, de la topologie du réseau.

Pour ce faire, il exite de nombreuses techniques concurrentes ou coopérantes
dont nous allons tenter de donner un aperçu aussi shématique que possible :

(Flèches actives)


Routage CENTRALISE
Routage DISTRIBUÉ
Routage STATIQUE
Routage DYNAMIQUE
Algorithmes à VECTEUR DE DISTANCE
Algorithmes à ETAT DE LIENS
Routage par la SOURCE
Diverses catégories de routage.

Description shématique des protocoles particuliers en usage actuellement, en :
Protocoles de routage actuellement en usage-

autre lien :
Retour à la première partie du document "Routage"
(généralités)

 

 



Routage centralisé :

Mis en oeuvre grâce à un superviseur (éventuellement secondé par des serveurs secondaires),
qui se tient informé des caractéristiques de l'ensemble des liaisons entre routeurs.

Il peut donc juger de la meilleure route d'un accès à un autre d'un réseau.

Il en informe chacun des routeurs qui met à profit ces informations pour mettre à jour sa table de routage.

Dans les réseaux de grande envergure - réseaux opérateurs - la supervision des voies de communication est indispensable pour gérer les demandes connexion qui peuvent varier en qualité de service (QoS) : vitesse, bande passante, sécurité, prix etc. A ce niveau, le routage centralisé s'intègre dans l'environnement su superviseur.


Routage distribué :

Mis en oeuvre par chacun des routeurs du réseau grâce à la diffusion de trames de questionnement des ses voisins.

Ce grâce à des logiciels résidant dans chaque routeur et mettant en oeuvre des algorithmes lui permettant de découvrir les chemins les plus avantageux au regard de la métrique.


Routage statique :

Le "routage statique" consiste à remplir manuellement les tables de routage internes des routeurs du réseau.

L'inconvénient est que toute modification du réseau nécessitera la remise à jour des tables de la plupart des routeurs, ce qui peut être long et complexe dans de grands réseaux.

L'avantage, pour les petits réseaux, est qu'il ne nécessite aucun protocole de routage, pénalisant pour le trafic du fait d'incessants échanges de trames d'information entre routeurs. De plus, il est mois chèr.


Algorithmes de routage - routage dynamique -

On a proposé un nombre considérable d'algorithmes de routage concurrents.
Les performances recherchées étant :

La rapidité de convergence : c.a.d. le temps que mettront l'ensemble des routeurs du réseau à faire l'apprentissage de leur environnement (ou à réagir à un changement du réseau) pour le consigner sur leurs tables de routage.

Leur aptitude à ne pas inonder le réseau :
de messages de service
de trames dupliquées
etc.

L'éfficacité du routage en termes de :
rapidité d'acheminement des trames ou paquets
aptitude à ne pas perdre des paquets
prise en compte des paramètres de qualité de service (QoS) dans le choix des itinéraires

Il existe plusieurs types d'algorithmes adaptatifs de routage :

Les algorithmes globaux utilisent des informations provenant d'un superviseur d'ensemble du réseau pour prendre les meilleures informations de routage. On parle de " routage centralisé ".
C'est à cette catégorie qu'appartient l'algorithme dit "à état des liens" dont nous parlerons dans la suite.

Les algorithmes distribués utilisent à la fois des données locales et des données globales du réseau. Notons : Un routeur ne peut pas toujours connaître l'itinéraire complet pour atteindre un hôte ou un sous-réseau sur un réseau distant, mais il connaît parfaitement les chemins proches les meilleurs pour aller dans la bonne direction. Dans la suite, nous examinons quelques protocoles de routage parmi les plus utilisés afin de se faire une idée du fonctionnement interne et relationnel de ces systèmes.
C'est à cette catégorie qu'appartient l'algorithme dit "à vecteur de distance" dont nous parlerons dans la suite.

Les algorithmes locaux n'utilisent que des valeurs locales de chaque routeur. On parle de "routage isolé ". En fait, dans cette perspective, la direction de distribution des paquets compte moins que de choisir le moyen le plus rapide de s'en débarrasser (technique dite du 'hot potatoe').
Le routeur choisit ses files d'attente les plus courtes, ce qui est un moyen comme un autre d'optimiser la rapidité de transmission, mais aussi d'innonder le réseau de trames identiques qui gènent le trafic et qu'il faudra éliminer.


Principales catégories d'algorithmes de routage


Algorithmes à vecteur de distance : (Document en cours de construction)

 


 


Algorithmes à état des liens : (Document en cours de construction)

 


 


Routage par la source : (Document en cours de construction)

 


GLOSSAIRE


Topologie

Du grec : "Connaissance des lieux"

C'est une branche des mathématiques qui étudie les rapports spaciaux entre objets, la manière de passer de l'un à l'autre, la notion de frontière, d'ensemble fermé, ouvert, continu, etc.

Retour au texte


Noeud, Station, ETTD, Hôte...

On désigne ainsi tout équipement informatique susceptible d'échanger des données sur le réseau.
Ce peut être l'un des ordinateurs d'un réseau local, deux ordinateurs reliés à un réseau étendu WAN, un routeur, un commutateur.
Un répéteur n'est pas à proprement dit un noeud : il n'a pas d'adresse ni des moyens de traiter l'information autrement que physiquement.

ETTD (Equipement Terminal de Traitement des Données) est le nom d'un noeud dans la dénomination ISO.
Hôte est une dénomination appartenant à la communauté Internet.







Notes


Adaptatif

Les routeurs modifient automatiquement des informations de routage lorsqu'un changement se produit dans la topologie du réseau : apparition ou disparition d'un sous-réseau, d'un routeur. Les informations de routage sont mises à jour dans le table de routage interne. Même si la construction de cette table demande un certain temps de dialogue avec l'environnement, une fois établie, elle permettra au routeur de choisir sans délai la meilleure route pour les paquets traités. Bien entendu, les entrées des tables de routage sont systématiquement effacées au bout d'un temps d'inactivité fixé en paramètre. Sinon l'élimination des configurations obsolètes serait difficile à implémenter. Comme généralement la modification apportée est minime - disparition ou apparition d'un nouvel hôte - le dialogue de reconstitution partielle de la table ne dure ni n'encombre notablement le reste du réseau.

Retour au texte afférent