INTRODUCTION AU ROUTAGE

FONCTIONNEMENT D’UN ROUTEUR

La figure 2–2 illustre comment fonctionne un routeur. Un routeur exécute en parallèle 3 processes distincts :
• la commutation de paquets • le routage • la gestion
Ces processes sont en compétition permanente pour les ressources mémoire et CPU du routeur.
La commutation de paquets représente la finalité du routeur. Les paquets à commuter contiennent des données à destination de hosts distants. Ces paquets sont reçus sur un port d’entrée i, forwardés vers un port de sortie j et enfin émis sur ce port j. Le forwarding nécessite la consultation d’une table de routage qui indique le port de sortie correspondant à l’adresse de destination du paquet. La table de routage est aussi appelée Forwarding database.
La table de routage peut être mise à jour de 2 manières :
• manuellement La mise à jour manuelle est effectuée par l’ingénieur réseau à travers le process de gestion (Telnet, SNMP…). On parle alors de routage statique. • dynamiquement La mise à jour dynamique est effectuée par un protocole de routage à travers le process de routage. On parle alors de routage dynamique.
Le routage statique permet l’élimination du process de routage ce qui libère certaines ressources mémoire et CPU. Cependant, toute modification de la topologie du réseau (ajout, supression ou panne d’éléments du réseau) doit être immédiatement prise en compte par l’ingénieur réseau; celui-ci doit alors modifier la table de routage en conséquence sous peine de dysfonctionnements plus ou moins graves (trous noirs).
Le routage dynamique détecte toute modification de la topologie du réseau et la répercute en recalculant la table de routage. La détection de la modification de la topologie de réseau et le recalcul de la table de routage qui en découle sont d’autant plus rapides que le protocole de routage est efficace. On parle alors de vitesse de convergence.
Le process de commutation de paquets se limite aux seules couches les plus basses de l’architecture mais ce n’est pas forcément le cas des processes de routage et de gestion (figure 2–3).

ROUTAGE HIERARCHIQUE

Certains très grands réseaux tels que l’Internet nécessitent un routage hierarchique à la fois pour des raisons de performance et de politique industrielle. Pour ce faire, le réseau est découpé en domaines de routage et chaque domaine de routage est lui-même découpé en areas. Chaque domaine de routage est géré par une autorité administrative et une seule.
Les routeurs à la frontière entre domaines de routage utilisent un protocole de routage inter-domaine pour router entre ces domaines. De nombreux travaux à l’OSI et l’IETF sont consacrés actuellement au routage inter-domaine, les protocoles existants étant considérés comme perfectibles.Les routeurs à l’intérieur d’un domaine de routage utilisent un protocole de routage intradomaine pour router à l’intérieur de ce domaine. Les routeurs à la frontière entre areas assurent le routage inter-area appelé routage de niveau 2. Les routeurs à l’intérieur d’une area assurent le routage intra-area appelé routage de niveau 1.Dans la terminologie de l’IETF, domaine de routage, protocoles de routage inter- et intradomaine s’appellent respectivement AS, EGP et IGP.

ALGORITHMES DE PLUS COURT CHEMIN

MODELISATION DU RESEAU

Un graphe est un ensemble constitué de noeuds et d’arcs reliant ces noeuds. Un réseau peut être modélisé par un graphe; il suffit de considérer les routeurs comme des noeuds et les liaisons de données comme des arcs. Cette modèlisation est particulièrement fructueuse car elle permet aux concepteurs de protocoles de routage de s’appuyer sur un ensemble théorique très riche.
Quelques définitions sont nécessaires pour aller plus avant :
• Trajet Un trajet est une séquence de noeuds N1, N2,…Nl telle que (N1, N2), (N2, N3),… (Nj-1, Nj) sont des arcs. • Chemin (path) Un chemin est un trajet sans noeuds qui se répètent. • Cycle Un cycle est un trajet sans noeuds qui se répètent sauf N1=Nj avec j>3. • Graphe connecté Un graphe connecté est un graphe tel qu’il existe toujours un chemin entre le noeud Ni et tous les autre noeuds. • Graphe pondéré Un graphe pondéré est un graphe dont les arcs ont un coût. • Graphe orienté Un graphe orienté est un graphe dont les arcs ont un sens. • Arbre Un arbre est un graphe connecté sans cycle. • Arbre recouvrant (spanning tree) Un arbre recouvrant est un arbre passant par tous les noeuds d’un graphe connecté.• Arbre recouvrant de poids minimal Un arbre recouvrant de poids minimal est un arbre recouvrant dont les chemins reliant le noeud racine aux autres noeuds ont un coût minimal. Grâce à ces définitions, nous pouvons affirmer que tout réseau peut être modèlisé comme un graphe connecté, orienté et pondéré. En choisissant un routeur comme noeud racine, on peut alors calculer l’arbre recouvrant de poids minimal pour le réseau. On obtient ainsi l’ensemble des plus courts chemins reliant ce routeur à l’ensemble des destinations. C’est la démarche suivie par les protocoles de routage. Les algorithmes de calcul de plus courts chemins les plus utilisés par les protocoles de routage sont ceux de BELLMAN-FORD (voir paragraphe 3.2) et de DIJKSTRA (voir paragraphe 3.3). Les protocoles de routage utilisant l’algorithme de BELLMAN-FORD sont dits de type Distance-Vector. Les protocoles de routage utilisant l’algorithme de DIJKSTRA sont dits de type Link-State. Le livre de BERTSEKAS et GALLAGER (1992) peut être consulté pour étudier les fondements mathématiques de ces algorithmes.

ALGORITHME DE BELLMAN-FORD

L’algorithme de BELLMAN-FORD existe en 2 versions :
• centralisée • distribuée
Seule la version distribuée appelée également algorithme de FORD-FULKERSON est utilisée par les protocoles de routage de type Distance-Vector. Dans la version centralisée, chaque noeud connait la topologie du réseau et calcule l’arbre recouvrant de poids minimal dont il est la racine selon la méthode illustrée par la figure 3–1.N et M étant respectivement le nombre de noeuds et le nombre d’arcs, on démontre que l’algorithme converge au plus en N-1 étapes et que sa fonction de complexité est O(MxN).Dans la version distribuée, les noeuds n’ont pas connaissance de la topologie du réseau. Chaque noeud calcule ses distances minimales à l’ensemble des noeuds du réseau grâce aux messages que lui envoient ses noeuds voisins. Ces messages sont appelés vecteurs de distance (routing vectors) et contiennent un ou plusieurs couples (noeud, distance). De fait, le noeud racine ne supporte pas l’intégralité du calcul puisque les noeuds voisins lui fournissent des résultats intermédiaires.