# Les réseaux informatiques/Les protocoles de routage

Le routage sur internet n'est pas effectué par une instance centralisée, vu la taille du réseau et son organisation. Difficile d'organiser autour d'un seul protocole ce qui est avant tout une interconnexion de réseaux très différents. Il est proprement impossible de décider de la table de routage de chaque routeur tant il y en a, sans même parler de propager les mises à jour des tables de routage. En réalité, Internet est organisé autour de réseaux qui sont chacun "indépendants" en terme de routage : les Autonomous systems, abréviés AS. Un AS est un ensemble de réseaux et de routeurs reliés entre eux, qui sont soumis à un même protocole de routage. Ceux-ci sont souvent soumis à une même entité commerciale ou administrative : par exemple, chaque fournisseur d'accès possède son propre AS. Chaque AS est identifié par un numéro, l'Autonomous System Number (ASN), attribué par diverses organisations internationales. Tous identifient un AS, à l'exception de quelques numéros dédiés à des usages un peu particuliers, dans les protocoles de routage par exemple.
Le routage est cohérent à l'intérieur d'un AS, alors qu'il ne l'est pas entre les AS, et cela se ressent dans les algorithmes de routage utilisés. Les AS utilisent des protocoles de type IGP (Interior Gateway Protocols) pour mettre à jour les tables de routage, alors que la communication entre AS est réalisée par des protocoles de type EGP (Exterior Gateway Protocols)/BGP (Border Gateway Protocols).

## Les différentes formes de routage

Évidemment, il existe plusieurs manières de router les paquets à destination, qui sont implémentées par divers standards. Et on peut classer les différentes méthodes de routage en plusieurs catégories. Dans ce qui va suivre, nous allons donner quelques critères qui permettent de classer les protocoles de routage.

### Routage statique et dynamique

Pour savoir où envoyer les paquets reçus, les relais du réseau contiennent une table qui associe chaque adresse avec le prochain intermédiaire. Cette table porte des noms différents selon que l'on parle de routeurs ou de commutateurs : table de routage pour les routeurs et table CAM pour les commutateurs. Nous allons ici parler de la table de routage et de sa mise à jour. Nous en reparlerons plus en détail dans le prochain chapitre. Pour le moment, nous allons simplement dire qu'elle permet de savoir où envoyer chaque paquet reçu. Nous n'avons pas besoin de plus.
Le contenu de la table de routage peut être déterminé à l'avance par les concepteurs du réseau, ou mis à jour régulièrement (pour s'adapter à des ajouts ou retraits de machines). Dans le premier cas, les tables de routage sont remplies lors de l'allumage du routeur, et ne sont jamais mises à jour. On parle alors de routage statique, dans le sens où il ne peut pas évoluer sans que le gestionnaire du réseau ne fasse les modifications adéquates. Bien que très simple, cette approche a cependant de nombreux défauts. Déjà, saisir à la main chaque ligne de la table de routage est parfois long, compliqué, chronophage. Le faire de manière automatisée, chaque routeur construisant la table de routage de lui-même, étant de loin une meilleure solution. De plus, la table de routage ne peut pas s’adapter à une panne de réseau ou au changement de celui-ci. Toute modification des connexions intra-réseau demande de modifier la table de routage, manuellement.
Un routage dynamique permet de mettre à jour les tables de routage à la volée, régulièrement, sans intervention humaine. Cette mise à jour des tables de routage est alors prise en charge par un algorithme de routage, une sorte de programme intégré aux routeurs qui leur dit quoi faire pour se mettre à jour. Une sorte d'équivalent des mises à jour Windows, mais pour la table de routage. Ces algorithmes de routage sont pris en charge par des protocoles divers comme IGP ou BGP, que nous n'aborderons pas dans le détail tellement ils sont complexes. Les algorithmes de routage dynamique peuvent repérer les chemins endommagés, qui ne fonctionnent plus (un routeur débranché ou en panne, par exemple), et trouver des routes alternatives. Le réseau se reconfigure à chaque instant pour que le service soit maintenu, et que les performances soient conservées.

### Routage centralisé ou distribué

On peut aussi distinguer les méthodes de routage selon la méthode utilisée pour mettre à jour les tables de routage. La mise à jour des tables de routage peut être gouvernée par un routeur central, qui communique aux autres routeurs les informations de mise à jour : on parle alors de routage centralisé. Dans l'autre cas, le routage est un routage décentralisé : chaque routeur met à jour sa table de routage individuellement, sans intervention d'un routeur central.

## Les algorithmes de routage

Tous les algorithmes de routage se basent sur les mêmes principes mathématiques, à savoir la théorie des graphes. Pour faire simple, ces algorithmes modélisent un réseau sous la forme d'un ensemble de points reliés par des flèches : les points représentent les routeurs et ordinateurs, alors que les flèches indiquent les liens entre ces routeurs. Un exemple de graphe est donné dans le dessin à votre droite. Le but de l'algorithme est de trouver un chemin dans ce graphe qui relie l'émetteur au destinataire. Il existe de nombreux algorithmes pour trouver le chemin le plus court entre deux points d'un graphe, et il n'est pas question d'en faire la liste ici. Cependant, sachez que ceux-ci ne sont pas utilisés tels quels par les algorithmes de routage.
Les algorithmes de routage peuvent aussi tenir compte des performances des différents chemins entre deux routeurs. La mise à jour des tables routage permet alors de trouver des chemins plus courts ou plus rapides pour acheminer une donnée à une IP précise. Il suffit pour cela de tenir compte des temps de transferts entre routeurs. Pour cela il suffit d'associer à chaque flèche, chaque chemin entre deux routeurs, un poids qui indique sa rapidité. Plus la vitesse de transfert est faible entre ces deux routeurs, plus ce nombre sera fort. Pour chaque chemin identifié, l'algorithme additionne le temps de transfert de chaque flèche. Le but de l'algorithme est de trouver le chemin qui minimise le temps de transfert, qui minimise la somme finale.

### Les deux types principaux de protocoles de routage : vecteur de distance et état de liens

Dans les grandes lignes, on peut classer les protocoles de routage en deux types principaux, eux-même subdivisés en pleins de sous-types : les protocoles de type vecteur de distance, et les protocoles à état de liens.
Avec les protocoles à vecteur de distance, les routeurs envoient régulièrement l'ensemble de leur table de routage aux routeurs voisins, auxquels il est directement connecté. Ceux-ci mettent alors à jour leur propre table de routage en tenant compte des informations envoyées. Évidemment, cela consomme beaucoup de débit réseau, ce qui est un défaut majeur. C'est la raison principale pour laquelle ils ne peuvent pas être utilisés sur des réseaux trop importants : les envois prendraient beaucoup trop de temps avec des grosses tables de routage. De plus, les tables de routage mettent beaucoup de temps avant de se stabiliser, ce qui rend le routage très inefficace au début de l'utilisation du réseau. Encore un autre défaut rédhibitoire.
Les protocoles à état de lien sont plus efficaces en terme de débit et de stabilisation des tables de routage. Au lieu d'envoyer la table de routage complète, ils envoient des messages courts, qui donnent des indications sur la connectivité du réseau. De manière générale, ces messages sont de simples tests qui vérifient que le voisin est toujours accessible, connecté. Au bout de plusieurs tentatives échouées, le routeur contacté est considéré comme inaccessible et le routeur envoie une indication aux autres voisins comme quoi il ne peut plus communiquer avec lui. En clair, chaque routeur indique quel est l'état des liens qu'il entretient avec les autres routeurs : il dit qu'il est connecté à tel ou tel routeur, que telle connexion a été déconnectée, etc. Avec ces protocoles, le volume de données transmises est plus faible. Pas besoin d'envoyer une table de routage complète, juste quelques messages courts. Outre la forte réduction de débit utilisé, la vitesse de convergence est plus rapide, pour diverses raisons techniques que omettons volontairement.

### Les algorithmes de routage par inondation (aléatoires)

Les algorithmes de routage par inondation font un routage complètement aléatoire, où chaque routeur émet les paquets reçus sur toutes ses sorties. Ce qui explique le nom de cet algorithme : le routeur inonde le réseau du paquet reçu. Et aussi bizarre que cela puisse paraitre, cet algorithme garantit que le récepteur recevra le paquet, tant qu'il existe un paquet entre l'émetteur et le récepteur. De plus, cet algorithme réagit parfaitement aux changement du réseau : on peut changer les connexions du réseau sans que cela empêche le paquet d'arriver à destination. Mais les défauts sont assez évidents : beaucoup de bande passante est gâchée pour envoyer un paquet en plusieurs exemplaires.
Pour éviter cela, on peut modifier l'algorithme précédent et n'envoyer le paquet reçu que sur une seule sortie, qui est choisie aléatoirement. Cela évite d'envoyer plusieurs copies d'un même paquet, mais celui-ci prendra parfois un chemin assez tordu et mal commode pour arriver à destination. Le paquet peut se perdre en chemin et mettre beaucoup de temps avant d'arriver. Les performances du réseau sont améliorées, du terme de bande passante, mais pas en temps de latence, qui augmente. L'algorithme en question est appelé algorithme par inondation sélective.