Routage multichemins par interface d'entrée
Langue Français
Ce document est protégé en vertu du Code de la Propriété Intellectuelle.
Auteur : Mérindol, Pascal
Date de soutenance : 01-01-2008
Directeur(s) de thèse : Pansiot, Jean-Jacques - Cateloin, Stéphane
Établissement de soutenance : Université Louis Pasteur (Strasbourg)
École doctorale : École doctorale Mathématiques, sciences de l'information et de l'ingénieur (Strasbourg ; 1997-....)
Discipline : Informatique
Classification : Informatique
Mots-clés libres : Réseaux d'ordinateurs
Mots-clés :
- Réseaux d'ordinateurs
- Thèses et écrits académiques
- Routeurs (réseaux d'ordinateurs)
- Thèses et écrits académiques
- Interfaces (informatique)
- Thèses et écrits académiques
Résumé : La fiabilité d'un réseau IP face aux pannes et aux congestions dépend du temps de réaction associé au protocole de routage sous-jacent. Actuellement, les protocoles de routage à états des liens tels que OSPF ou IS-IS n utilisent que les meilleures routes de coût égal pour commuter les paquets IP à l'échelle d'un domaine. La propriété de sous-optimalité des meilleures routes garantit la cohérence du routage au saut par saut bien que les chemins calculés via l'algorithme de Dijkstra soient composés de proche en proche. Selon la métrique employée, la diversité des chemins existant peut être largement sous exploitée avec une condition telle que la sous-optimalité. Or la diversité des alternatives de routage est l'un des éléments clés pour assurer un temps de réaction limité. La difficulté inhérente aux protocoles de routage multichemins saut par saut est la vérification de l'absence de boucles de routage. Chaque noeud doit garantir que le trafic qu il achemine ne soit pas commuté sur un circuit dont il fait partie. Dans ce rapport de thèse, après avoir mis en avant l'état de l'art existant dans la littérature, nous exposons deux contributions dont la combinaison assure cette propriété. La première proposition est basée sur l'algorithme de Dijkstra, il s'agit d'un algorithme de recherche opératoire nommé Dijkstra-Transverse qui calcule un ensemble de chemins transverses entre un noeud racine et chaque autre noeud du graphe modélisant le réseau. La seconde contribution est une procédure de validation distribuée dont le but est d'élaguer les circuits potentiellement générés par le routage saut par saut. Pour accroître la diversité des chemins validés, la procédure de commutation est spécifique à chaque interface entrante. Par ailleurs, nous avons évalué l'impact de la diversité des chemins pour mettre en oeuvre une couverture efficace en cas de panne de liens. La notion de couverture se décline en deux versions, locale ou globale, selon le type de protection envisagé, en d'autres termes, s'il est possible ou non de notifier les routeurs en amont de l'occurence d'une panne. Nous nous sommes également intéressés aux aspects ingénierie de trafic liés à l'équilibrage de la charge en cas de congestion. Afin d'estimer l'importance de la diversité des chemins pour mettre en oeuvre un routage proportionnel efficace, notre travail s'est focalisé sur la définition d'un module réactif de partage de charge. Celui-ci est simplement basé sur une analyse locale de la bande passante résiduelle et permet de mettre en relief les performances de nos propositions de routage par comparaison avec l'existant. De manière générale, dans un souci de crédibilité, nos évaluations par simulation sont basés sur des topologies et une génération de trafic réalistes. Les résultats obtenus mettent en avant l'efficacité de nos algorithmes pour déployer un routage multichemins générant une diversité accrue par rapport à l'existant. Celle-ci est en effet nécessaire pour obtenir une capacité de commutation suffisante pour contourner les pannes et les congestions comme l'indiquent nos résultats liés aux deux types d'applications évalués.
Entrepôt d'origine : 
Identifiant : ecrin-ori-297029
Type de ressource : Thèse
