Conception des algorithmes pour le routage à multiples contraintes

Conception des algorithmes pour le routage à multiples contraintes

L’objectif d’un calcul de la table routage est de déterminer une route (i.e., un ensemble de liens à parcourir) respectant certaines contraintes, pour établir une connexion d’un nœud source vers un nœud destinataire. Ce calcul est inclu dans le protocole de routage qui permet la diffusion des informations nécessaires à ce calcul.La qualité de service que l’on est en mesure d’offrir à une connexion est directement liée au choix du chemin. Le calcul de route doit prendre en compte les différentes contraintes imposées par la connexion (débit, délai, taux de perte, etc), ces paramètres peuvent en effet varier en fonction des liens empruntés. Il faut donc mettre en œuvre un algorithme de rou- tage qui a pour rôle de trouver le meilleur chemin possible entre la source et le destinataire pour satisfaire les différents critères de qualité imposés.Un algorithme de calcul d’une route avec QoS (Qualité de Service) consiste à trouver un chemin entre une source et une destination qui satisfait les exigences de QoS (bande passante, délai, etc) tout en utilisant d’une manière efficace les ressources du réseau (coût, équilibrer la charge, etc). Les algorithmes de calcul de la table de routage proposés dans cette thèse visent une application dans le domaine du routage point-à-point sous multiples contraintes pour assurer la gestion de la qualité de service dans les réseaux dynamiques sans aucune entité centrale.

Donc le routage doit être adaptatif (dynamique) et distribué entre les nœuds du réseau. Les calculs sont faits sur un graphe topologique qui représente l’état du réseau. Ce graphe est construit par l’algorithmeNous présentons l’interconnexion de réseau par un graphe simple, dont les arêtes sont les liaisons, et dont les nœuds sont les équipements, stations ou routeurs. Les liaisons sont affectées d’une ou plusieurs fonctions de poids positives. Ces poids pourront représenter la distance entre les nœuds d’extrémités, le délai de transmission des données sur la liaison, le débit, le coût, etc. Nous ne prenons pas en compte le cas des liaisons redondantes ou de secours entre deux équipe- ments de réseau ; ces liaisons seront toujours représentées par une seule arête entre deux nœuds du graphe. Nous supposons que le réseau est connexe. Toutefois, de manière transitoire, des compo- santes de réseau peuvent devenir momentanément isolées suite à une mobilité, panne ou autre. Le routage point-à-point dynamique réagie immédiatement en procédant à des mises à jours dans les informations de routage afin de trouver des chemins vers ces composantes. On ne considère pas l’état de réseau au moment d’une déconnexion temporaire de certains éléments mais uniquement après la réaction de protocole de routage ce qui renforce l’hypothèse que le graphe est toujours supposé connexe.Le graphe est supposé orienté.

En effet, nous considérons uniquement le cas de liaisons point à point bidirectionnelles entre deux équipements du réseau mais les valeurs des poids sur les deux arcs peuvent être différentes ; l’existence des liaisons unidirectionnelles affecte le routages point à point [45] et leur prise en compte nécessite des aménagements des protocoles de routage. Les algorithmes de construction de la table de routage que nous présentons dans ce mémoire, ex- ploitent tout simplement les informations issues du routage point-à-point et ne nécessitent aucune hypothèse sur le type des liaisons parcourues.Dans cette section nous présentons un aperçu des différents algorithmes de routage proposés dans la littérature. Les travaux de Wang et Crowcroft [5] ont montré que le problème de trouver un chemin optimal sous la présence de deux ou plusieurs métriques additives et/ou multiplicatives est un problème NP-complet. Un problème est dit NP si, étant donné une réponse au problème, il existe un algorithme polynomial permettant de vérifier la validité de cette réponse. Un exemple classique d’un tel problème est la recherche d’un cycle hamiltonien dans un graphe (c’est-à-dire, un cycle passant par tous les sommets du graphe), il est clair qu’étant donné une solution, il est facile en O(n) de vérifier que c’est un cycle et qu’il passe par tous les sommets du graphe. Un problème (P) est dit NP-complet s’il est dans NP, et si tout problème de type NP peut se ramener au problème (P) à l’aide d’une transformation polynomiale. Il est conjecturé qu’il n’existe pas d’algorithme polynomial permettant de résoudre un problème NP-complet. D’autre part, seuls les algorithmes polynomiaux sont utilisables en pratique. À notre connaissance, il n’y a aucun algorithme largement admis qui peut donner la solution optimale au problème consistant à trouver un chemin sous deux contraintes additives en un temps polynomial.