Processus et protocoles de routage
Le routage est une composante fondamentale de la gestion des réseaux. C'est le principe qui permet à des paquets de quitter le brin local pour atteindre une machine qui se trouve au-delà d'un routeur ou d'une passerelle.
On distingue les techniques d'acheminement de paquets qui fonctionnent par routage de celles qui fonctionnent par commutation (X. 25 par exemple). Les techniques de commutation maintiennent des états associés à un circuit virtuel qui réalise une ouverture de communication de bout en bout. Les éléments d'interconnexion de routage, eux, ne doivent fournir qu'un service minimum : router du mieux qu'ils peuvent (best effort).
Avec le temps, il s'avère que le mode routé et plus robuste que le mode point à point connecté : en effet, si un relais tombe en panne, les voisins du relais IP recalculent les tables de routage est acheminent les paquets suivants par une nouvelle route. Dans la technologie point à point, si le circuit est rompu, la connexion est avortée.
Le routage IP est donc dynamiquement adaptatif : il est effectué de saut en saut (next hop) depuis la source jusqu'à destination, et à chaque saut il y a prise de décision autonome afin de sélectionner la route qui acheminera le datagramme. À chaque étape, un relais n'a qu'une connaissance partielle du routage.
Un protocole de routage constitue donc le système par lequel un routeur va pouvoir acheminer un paquet vers un autre réseau.
Un protocole routé, lui, désigne un protocole qui possède une spécification équivalente à celle de la couche trois du modèle OSI et qui définit un adressage logique permettant le routage. C'est le cas par exemple du protocole IP ; ce n'est pas le cas du protocole NetBIOS.
L'objectif de protocole de routage peut se résumer en cinq points :
découvrir dynamiquement les routes vers les sous réseaux d'un réseau et les inscrire dans une table de routage ;
s'il existe plusieurs routes vers un sous réseau, inscrire la route la meilleure (la plus courte) ;
détecter les routes qui ne sont plus valides et les supprimer de la table ; si le réseau dont le chemin est supprimé peut-être accédé par le biais d'un autre routeur, inscrire ce nouveau chemin dans la table en remplacement du chemin supprimé ;
ajouter le plus rapidement possible de nouvelles routes, ou mettre à jour le plus vite possible les routes considérées comme meilleures : le temps qui s'écoule entre la perte d'une route et la découverte d'une autre route s'appelle le temps de convergence ;
empêcher les boucles de routage.
La longue histoire des réseaux fait qu'il existe de nombreux protocole de routage. Nous n’étudierons que ceux qui sont applicables à TCP/IP.
Notez que l'on distingue les protocoles de routage externe, qui sont conçus pour assurer la communication entre deux réseaux différents contrôlés par deux organisations différentes, et les protocoles de routage interne, destinés à assurer la communication entre les différentes parties d'un réseau contrôlé par la même organisation.
Le protocole de routage par état de liens (link state) entre dans la catégorie des protocoles de routage interne. Le plus connu d'entre eux est OSPF (Open Shortest Path First). Il a été créé au milieu des années 80 en raison de l’incapacité de plus en plus flagrante d'un autre protocole, nommé RIP (voir plus bas) de répondre aux besoins des intérêts ou de grandes dimensions et hétérogènes. Il a pour caractéristique d'être dans le domaine public (open), et de se baser sur un algorithme de calcul de route nommée SPF ou parfois algorithme de Dijkstra, du nom de son fondateur.
Lorsqu'un routeur qui supporte la technologie OSPF démarre, il commence par s'assurer que ses interfaces fonctionnent. Puis, il envoie des messages hello sur ces interfaces qui lui servent à découvrir la topologie du réseau local. Ces paquets seront renvoyés régulièrement (et les autres routeurs feront de même vers ce routeur-ci) de façon à s'assurer de l'état du lien entre les routeurs (d'où le nom protocole de routage par état de liens).
Un des routeurs adjacents sera considéré comme routeur par défaut vers un autre sous réseau, et un autre comme routeur de secours. À partir de ces informations, chaque routeur dessine un arbre de communication vers les autres sous réseaux en se prenant comme racine. L'algorithme SPF sert à construire cet arbre en calculant les routes les plus courtes.
Ce protocole supporte des options complémentaires, comme par exemple la possibilité de signaler que certaines données sont urgentes (elles seront donc prioritaires dans la distribution).
Ce type de routage n'est cependant pas celui qui est le plus utilisé. En effet, il reste fragile si le routeur par défaut et le routeur de secours tombent en panne. Il a cependant d'autres avantages : il permet la transmission des paquets sécurisés (il n'existe qu'une route entre deux routeurs), les métriques sont précises, les débits meilleurs, la convergence rapide, le traitement des routes externes séparé, le debug facile. Par ailleurs, tous les routeurs ont la topologie du réseau dans leur table, et les tables sont donc cohérentes.
Il s'agit là du protocole plus utilisé dans TCP/IP. C'est un protocole moins complexe que OSPF. Il est basé sur un protocole nommé RIP. Tous les protocoles de routage par vecteur de distance actuels sont plus ou moins dérivés de RIP. Son succès ne vient pas de ses performances, mais du fait qu'il a été développé par l'université de Berkeley et livré avec Unix 4. Son objectif initial était simplement d'interconnecter quelques machines sur un réseau local. Se répandant avec Unix, il a été implémenté sur des réseaux de plus en plus grands, souvent sans tenir compte de ses limitations. Du coup, il a été re-développé et amélioré pour compenser ses faiblesses. Aujourd'hui on utilise notamment RIP IP, et RIP 2.
Voici les tâches que doit réaliser ce protocole :
découvrir les informations de routage ;
détecter les routes défaillantes ;
prendre en compte la meilleure route disponible après défaillance d'une autre route ;
prévenir les boucles de routage.
Pour réaliser ces tâches, un routeur basé sur RIP ou sur un protocole voisin (par exemple IGRP) doit adopter un certain nombre de comportements :
ajouter dans sa table de routage interne les sous réseaux directement connectés ;
envoyer des mises à jour Broadcast ou multicast pour communiquer les informations de routage aux routeurs adjacents ;
écouter les mises à jour envoyées par les routeurs voisins ; il découvre ainsi de nouvelles routes et apprend les routes défaillantes ;
évaluer l'efficacité d'une route par rapport à une autre (à l'aide d'une métrique).
La table de routage d'un routeur comprend : d'abord le groupe de machines desservies (du type 162.11.7.0), puis l'interface de sortie qui mène à ce groupe (S0, E0, etc), puis le prochain saut (soit un champ vide si le routeur est directement connecté au groupe, soit l'adresse IP du routeur qui mène au groupe, directement ou indirectement).
Le terme vecteur de distance prend ici son sens : un routeur A qui enregistre un groupe 162.1.7.0 connecté par l'intermédiaire d'un routeur B ne sait rien de la topologie au-delà de B. Il sait simplement que le routeur B. mène à ce groupe avec une métrique communiquée par B.
Périodiquement, chaque routeur envoie à ses voisins des mises à jour de sa table. En l'absence de mises à jour au-delà d'un certain intervalle, les routes communiquées par un routeur sont supprimées de la table des routeurs voisins, qui supposent que le routeur A est défaillant.
Un routeur peut connaître une route vers un sous réseau, et découvrir lors d'une mise à jour l'existence d'une autre route qui y mène aussi. Dans ce cas, la route qui possède la meilleure métrique est choisie, et l'autre effacée de la table de routage. Si la métrique est la même, la première route est conservée. En fonction des versions, la table comporte alors soit les deux routes soit seulement la première.
Quand un routeur prend connaissance d'une indisponibilité d'un sous réseau, il pourrait simplement cesser de l'annoncer. Mais ce silence est difficile de distinguer d'une interruption involontaire du signal liée à un parasitage sur la ligne. C'est pour cette raison qu'il est préférable de continuer à annoncer la route, mais avec une métrique infinie. C'est la règle suivante : lorsqu'un routeur prend connaissance d'une route en panne, il doit l'annoncer avec une métrique infinie sur les mêmes interfaces que celles par lesquelles elle a pu être annoncée.
C'est un problème qui se produit quand plusieurs routes mènent au même réseau. Quand tout fonctionne correctement, le paragraphe ci-dessus s'applique. Mais quand un routeur vient à être défaillant, les choses se compliquent.
Supposons trois routeurs A, B et C connectés en triangle. Le routeur C annonce une route vers un sous réseau 162.7.1.0 qu'il dessert. Régulièrement, chaque routeur envoie aux autres une mise à jour de ses tables. Mais cet envoi n'est pas forcément simultané pour les trois routeurs. Quand un réseau devient inaccessible, le routeur qui le dessert envoie une mise à jour avec une métrique infinie.
Si le routeur C envoie cette information aux routeurs B au moment même où le routeur B envoie au routeur C une mise à jour avec une route vers le sous réseau 162.7.1.0 et une métrique de deux : en temps normal, le routeur C qui a dans sa table une route vers ce sous réseau avec une métrique de 0 ignorera la mise à jour. Mais la route vers ce réseau étant défaillante, la métrique 0 n'est plus valable. Le routeur C enregistrera donc la nouvelle métrique communiquée par B, alors qu'elle n'est pas valable !
À la mise à jour d'après, B. communiquera une métrique infinie (il a pris en compte l'information transmise par C), mais C communiquera à B une route avec une métriques trois ! La boucle est infinie.
Pour éviter ce problème, on met en place une fonction appelée Split horizon : elle se résume par la règle suivante : toutes les routes accessibles via une certaine interface ne doivent pas être incluses dans une mise à jour sortant par cette même interface.
Dans notre exemple, si C communique à B une route par son interface S0, B ne communiquera pas à C à partir de l'interface S0 les routes qu'il a apprises par cette même interface.
Hold down :
Mais d'autres problèmes peuvent encore se produire. Dans l'exemple cité ici, on parle d'un troisième routeur A. Même avec la fonction Split horizon, le routeur B peut recevoir du routeur A une route vers le sous réseau 162.7.1.0 avec une métrique de deux. À la prochaine mise à jour, il communiquera sur S0 cette route, puisqu'il ne l'a pas apprise par cette interface. Le problème recommence, et il se multiplie d'autant plus qu'il y a plus de routeurs interconnectés.
Pour le résoudre, on utilise une fonction qui s'appelle le temporisateur de retenue (Hold down), qui se définit par la règle suivante : lorsqu'un routeur prend connaissance de l'indisponibilité d'une route vers un sous réseau, il doit ignorer toute information concernant un chemin vers ce sous réseau pendant une durée égale au temporisateur hold down.
Avec cette fonction, le temps est laissé à l'information d'indisponibilité de la route à se communiquer à tous les routeurs.
Lorsqu'un routeur détecte un changement d'état dans sa table, il attend la fin de son temporisateur pour annoncer les variations. Il serait tout aussi bien d'envoyer immédiatement une mise à jour dans le cas d'une route interrompue. C'est ce qu'accomplit la fonction de mise à jour déclenchée : le routeur envoie les informations sur les routes défectueuses avant d'attendre la fin du temporisateur, dès qu'il a connaissance de cette défection.
En conclusion, on voit qu'il existe de nombreux problèmes liés au routage. Le nombre plus ou moins grand d'interfaces disponibles, mais aussi l'implémentation logicielle qui permet de traiter les problèmes évoqués ici, fait qu'il existe un grand nombre de routeurs différents, aux caractéristiques différentes. Le terme routeur est donc bien générique, et il est important lors de son acquisition de vérifier, en fonction de la topologie du réseau local (éventuellement de son interconnexion avec d'autres réseaux), qu'il est capable d'accomplir les taches requises, et en particulier qu'on n'aura pas de communication parasite lié au bouclage.