ROUTAGE
Protocoles & algorithmes de routage

Accueil
du Site

Précédent -Suivant

Sommaire

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

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

 
Lien direct
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.

Routage centralisé


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

Il peut donc calculer à tout instant la meilleure route d'un point à un autre d'un réseau.

Il en informe automatiquement chacun des routeurs du réseau, lesquels mettent à profit ces informations pour tenir à jour leur 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) : à savoir : vitesse, bande passante, immunité vis-à-vis des perturbateurs, sécurité, prix etc.


Routage distribué


Mis en oeuvre par chacun des routeurs du réseau grâce à des protocoles conversationnels :

  • chaque routeur questionne ses voisins pour s'enquérir de leurs connaissances sur la localisation d'une destination.
    Et ce, par diffusion de trames de questionnement auxquelles ces voisins répondent dans la mesure où ils détiennent cette information.
  • Sinon, ils lancent eux-mêmes des trames de questionnement à leurs voisins.
  • De proche en proche, l'information cherchée, si elle existe, est inmanquablement trouvée et retournée au demandeur initial qui la note dans sa table de routage.

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 .

  • L'avantage du routage distribué est sa souplesse (adaptatif ) : en effet, les algorithmes de routage sont attentifs à tout changement de topologie dans la répartition à tout instant des noeuds du réseau et remettent à jour spontanément les tables de routage.

  • L'inconvénient est que cet incessant échange d'informations entre routeurs encombre le réseau et pénalise le trafic en diminuant la bande passante.

Note : Pour se faire une idée de ce que peut être un protocole conversationnel, il est bon de revoir, pour l'exemple, le protocole ARP.
Je précise que ARP n'est pas un protocole de routage !
Seul est à considérer l'aspect conversationnnel du mécanisme.

Routage statique


Le "routage statique" consiste pour le personnel gestionnaire du réseau à remplir manuellement les tables de routage internes de chacun des routeurs.

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

L'avantage, pour les petits réseaux, est qu'il ne nécessite aucun protocole de routage, toujours peu ou prou pénalisant pour le trafic du fait des incessants échanges de trames d'information qu'il implique entre routeurs. Et c'est mois cher !


Exemple :
Si votre ordinateur est relié à un réseau local, il vous suffira :

  • de passer en mode commande [Démarrer] [Exécuter]
  • de taper la commande :" cmd " : l'écran des commandes apparaît (gén. à fond noir)
  • taper : "route print", pour voir apparaître la table de routage statique associée à votre machine.

En tapant seulement la commande "route" vous obtiendrez un mode d'emploi qui vous permettra, entre autre, d'ajouter manuellement des entrées à cette table.
N.B. Faites bien attention à ce que vous faites alors, si vous voulez continuer à lire ces pages ...


Algorithmes de routage - routage dynamique -


Le qualificatif "routage dynamique" signifie que le réseau réagit spontanément à toute modification : disparition d'un hôte, apparition de nouveaux hôtes, mises hors service de certains parcours du fait d'encombrement ou, tout simplement, d'une coupure franche.

On peut redire ici que cette dynamique est la rasion d'être des réseaux territoriaux.
Le cahier des charges initial de l'ancêtre d'Internet comportait la faculté de se reconfigurer automatiquement dans le cas où une attaque de missiles détériorerait une partie du réseau matériel.



On a proposé à travers les temps 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 mettre à jour dans leurs tables de routage.

Leur aptitude à ne pas inonder le réseau :
de messages de service
de trames dupliquées
etc. ce qui pénalise les performances de transfert par l'encombrement qu'ils provoquent.

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 distribués.
  • Les algorithmes globaux.
  • Les algorithmes locaux.

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 de quelques principes 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 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 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' - la 'patate chaude' ).
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

Ce type de routage est utilisé dans des réseaux maillés moyennement étendus.
.
Le fonctionnement est de type " distribué" donc contributif c.a.d. que chaque routeur du réseau
est muni du même algorithme de fonctionnement autonome pour la recherche des informations auprès de ses voisins :
sans qu'aucun de ces voisins ni lui-même n'ait au départ, la moindre information à fournir !
Tout est dans le dialogue.
C'est paradoxal, mais très naturel en somme : voyez le monde des fourmis ou des blattes...

Principes

  1. Initialisation.
    Chaque routeur est paramétré avec sa propre identité (Adresse ip et Nom)

    Chaque routeur ouvre dans son espace mémoire une table de routage
    , initialement vide, établissant une correspondance entre :
    1. des adresses IP de destination
    2. la distance (nombre de sauts ou tout autre métrique ) pour atteindre cette destination.
    3. le numéro de port du routeur par lequel la destination est atteignable au moindre coût
      (ce qui est équivalent à désigner par un nom en clair le routeur voisin le mieux placé).

      AU sens strict, l'ensemble des deux premières entrées
      s'appelle "vecteur de distance"


  2. Les distances de chaque entrée de la table sont initialement fixées à un nombre (dit inifini) c.a.d. plus grand que toute distance raisonnable. (l'algorithme les ajustera à la baisse).

    Le routeur réserve dans cette table une entrée pour lui-même où il inscrit la distance zéro.

    Dans le cas où la métrique choisie n'est pas simplement le nombre de sauts, il évalue la distance (ou coût) qui le sépare de ses voisins immédiats et la note en mémoire.

  3. Lorsqu'il est saisi d'un routage à effectuer (réception d'un paquet pour retransmission), le routeur consulte d'abord sa table de routage pour connaître le port correspondant à cette destination (généralement l'adresse IP de destination). S'il trouve, le tour est joué.

    Si, comme c'est la cas au début, il n'a aucune entrée correspondant à cette destination, l'algorithme de recherche de la meilleure route est déclenché.
    Le routeur :
    1. Envoie des paquets d'exploration dans toutes les directions et attend des paquets-réponses des routeurs environnants interrogés, qui lui renverront les meilleures offres de vecteurs pour la destination recherchée.
    2. Choisit, parmi ces réponses, celle qui correspond au meilleur coût (il ajoutera le coût de la liaison avec le routeur répondant).
    3. Achemine le paquet.
    4. Met à jour sa table avec le nouvel élément.
    5. Informe ses voisins du changement. Envoi du nouveau vecteur de distance.
      Ceci afin que ces derniers reconsidèrent éventuellement les valeurs leur table.

  4. Chaque routeur communique à ses voisins les informations de sa table :
    • Lorsqu'il note qu'une liaison avec une destination connnue disparaît.
    • Lorsqu'une nouvelle liaison apparaît.
    • Lors de son initialisation.
    • A des intervalles réguliers.

  5. Lorsqu'il reçoit un nouveau vecteur de distance provenant d'un voisin, chaque routeur vérifie sa table et en modifie le contenu si la nouvelle proposition est meilleure que celle qu'il détenait.

Ce n'est qu'un principe, l'étude détaillée de l'algorithme le mettant en pratique est beaucoup plus complexe
et ne trouve pas sa place dans ce cours purement descriptif des concepts.

Ce type d'algorithme comporte un défaut : sa lenteur de convergence.
La convergence étant la rapidité avec laquelle le réseau tout entier réagit, soit à son initialisation
soit et surtout à une modification de topologie (disparition ou apparition d'un nouvel hôte).
On imagine bien que le dialogue d'échanges de nouveaux vecteurs entre voisins
peut se propager et prendre du temps pour se stabiliser..


Algorithmes à état des liens

(Document en cours de construction)


Routage par la source

(Document en cours de construction)

Orientation

Précédent -Suivant
Routage (définitions)
Interconnexion des réseaux.
Sommaire "Réseaux"
Sommaire

du Site