« Les réseaux informatiques/Les protocoles de routage » : différence entre les versions

Contenu supprimé Contenu ajouté
Ligne 61 :
[[File:AODV Decouverte Route.png|vignette|Exemple de réseau représenté sous la forme de graphe, avec les tables de routage qui correspondent.]]
 
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. PourIl celaexiste de nombreux algorithmes pour trouver le chemin le plus court entre deux points d'un graphe, leset tablesil den'est routagepas doiventquestion êtred'en correctementfaire initialiséesla avantliste leici. transfertCependant, sache que ceux-ci ne sont pas utilisés tels quels par les algorithmes de routage.
 
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.
Ligne 68 :
 
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.
 
===Routage aléatoire===
 
Les algorithmes de routage les plus simple font un routage complètement aléatoire. Cela peut paraitre étonnant, mais c'est une technique qui fonctionne quelque soit le réseau et ses caractéristiques. L'exemple le plus connu est le '''routage par inondation''', 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.