Logo de l'E.N.T. Alsace
Thèses électroniques Service Commun de la documentation
Logo de l'Université de Strasbourg
Thèses et Mémoire de l'Université de Strasbourg

Routage multichemins par interface d’entrée

MERINDOL, Pascal (2008) Routage multichemins par interface d’entrée. Thèses de doctorat, Université Louis Pasteur.

Plein texte disponible en tant que :

PDF - Un observateur de PDF est nécessaire, comme par exemple GSview, Xpdf or Adobe Acrobat Reader
5321 Kb

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´es `a 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.

Type d'EPrint:Thèse de doctorat
Discipline de la thèse / mémoire / rapport :Informatique
Sujets:CL Classification > DDC Dewey Decimal Classification > 000 Informatique, information, généralités > 004 Informatique > 004.6 Interfaçage et communication
Classification Thèses Unistra > Sciences, technologies > Informatique, information, généralités > 004 Informatique > 004.6 Interfaçage et communication

UNERA Classification UNERA > ACT Domaine d'activité UNERA > ACT-11 Technologies de l’information, télécommunications, réseaux
UNERA Classification UNERA > DISC Discipline UNERA > DISC-19 Mathématiques et informatique
Code ID:1552
Déposé le :15 Janvier 2009

Administrateurs de l'archive uniquement : éditer cet enregistrement