Universite Louis Pasteur de Strasbourg Laboratoire des sciences de l'image de l'informatique et de la teledetection

Thomas Noel Universite

Description

Niveau: Supérieur, Doctorat, Bac+8
Universite Louis Pasteur de Strasbourg Laboratoire des sciences de l'image, de l'informatique et de la teledetection Routage multichemins par interface d'entree par Pascal Merindol These realisee dans le Laboratoire des sciences de l'image, de l'informatique et de la teledetection en vue de l'obtention du grade de Docteur en Informatique

• bouabdallah universite de technologie de compiegne


• strasbourg laboratoire des sciences de l'image, de l'informatique et de la teledetection


• routage multichemins par interface d'entree

Sujets

• Université
• Mérindol
• Pasteur

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 68
• Langue: Français
• Poids de l'ouvrage: 5 Mo

Extrait

´Universite Louis Pasteur de Strasbourg
´ ´ ´Laboratoire des sciences de l’image, de l’informatique et de la teledetection
Routage multichemins par interface d’entr´ee
par
Pascal M´erindol
Th`ese r´ealis´ee dans le Laboratoire des sciences de l’image, de l’informatique et de la t´el´ed´etection
en vue de l’obtention du grade de Docteur
en Informatique´Universite Louis Pasteur de Strasbourg
´ ´ ´Laboratoire des sciences de l’image, de l’informatique et de la teledetection
Cette th`ese intitul´ee
Routage multichemins par interface d’entr´ee
pr´esent´ee par
Pascal M´erindol
a ´et´e ´evalu´ee par un jury compos´e des personnes suivantes :
Directeur de th`ese Jean-Jacques Pansiot
Universit´e Louis Pasteur - Strasbourg
Co-encadrant St´ephane Cateloin
Universit´e Louis Pasteur - Strasbourg
Rapporteur Interne Thomas Noel¨
Universit´e Louis Pasteur - Strasbourg
Rapporteurs Externes Olivier Bonaventure
Universit´e catholique de Louvain
Abdelmadjid Bouabdallah
Universit´e de Technologie de Compi`egne
Examinateur Annie Gravey
TELECOM Bretagne - BrestRemerciements
Jetiensavanttout`aremerciertoutepersonnequilitceslignes,etpourceuxquiontplusdecourage,
l’int´egralit´edecemanuscrit.Parmisleslecteurslesplusm´eritants,jesouhaiteenpremierlieuremercier
mon directeur de th`ese, Jean-Jacques Pansiot, et mon co-encadrant de th`ese St´ephane Cateloin, dont
les remarques et nombreuses contributions ont transform´e ce modeste ouvrage depuis l’´etat de larve
`a celui de papillon. Leur implication dans mon travail de recherche ne se limite ´evidemment pas `a la
correction ortographique de mes publications mais s’est av´er´e tr`es pr´ecieuse en bien des domaines.
Lapatience,ladisponibilit´eetlafacult´einn´eedeJean-JacquesPansiot`asupportermesall´eesetvenues
inopin´ees dans son bureau ne seraient rien sans son ´ecoute attentive et ses r´eponses avis´ees. De son
cot´e, St´ephane Cateloin n’a pas non plus d´em´erit´e, en tant qu’investigateur du projet multi-chemins,
sa pers´ev´erance, sa motivation et ses qualit´es humaines m’ont ´et´e d’un grand secours au cours de ces
quatres ann´ees de labeur. Un troisi`eme relecteur d’un genre particulier, Julie Boc´er´ean, m’a ´egalement
apport´e moulte r´econfort et su me guider sur la piste d’une orthographe plus saine...merci pour ton
soutien au quotidien.
Bien entendu, je remercie mes parents, ma soeur et ma famille en g´en´eral pour avoir cru en moi depuis
l’´epoque b´enie de la marche `a quatre pattes.
Je profite de cet espace pour t´emoigner le plus grand respect `a l’ensemble de mon´equipe de recherche :
Alex, Antoine, Benoit, Dominique, Guillaume, Julien, Romain, Sebastien, Vincent, Yana, et aussi `a
ceux, aujourd’hui disparus, qui m’ont permis d’appr´ecier l’informatique a` sa juste valeur : Mickael
Hoerdt et Emil Ivov.
Pour finir sur une note plus formelle, je remercie les membres de mon jury de th`ese pour l’int´erˆet
qu’ils ont port´e `a mon travail et simplement pour avoir accept´e d’ˆetre rapporteurs, Messieurs Olivier
Bonaventure, Abdelmadjid Bouabdallah et Thomas Noel, ou examinatrice, Madame Annie Gravey.¨R´esum´e
La fiabilit´e d’un r´eseau IP face aux pannes et aux congestions d´epend du temps de r´eaction associ´e
au protocole de routage sous-jacent. Actuellement, les protocoles de routage a` ´etats des liens tels que
OSPFouIS-ISn’utilisentquelesmeilleuresroutesdecouˆt´egalpourcommuterlespaquetsIP`al’´echelle
d’un domaine. La propri´et´e de sous-optimalit´e des meilleures routes garantit la coh´erence du routage
ausautparsautbienquelescheminscalcul´esvial’algorithmedeDijkstrasoientcompos´esdeprocheen
proche.Selonlam´etriqueemploy´ee,ladiversit´edescheminsexistantpeutˆetrelargementsousexploit´ee
avec une condition telle que la sous-optimalit´e. Or la diversit´e des alternatives de routage est l’un des
´el´ementscl´espourassureruntempsder´eactionlimit´e.Ladifficult´einh´erenteauxprotocolesderoutage
multichemins saut par saut est la v´erification de l’absence de boucles de routage. Chaque nœud doit
garantir que le trafic qu’il achemine ne soit pas commut´e sur un circuit dont il fait partie.
Dans ce rapport de th`ese, apr`es avoir mis en avant l’´etat de l’art existant dans la litt´erature, nous
exposons deux contributions dont la combinaison assure cette propri´et´e. La premi`ere proposition est
bas´ee sur l’algorithme de Dijkstra, il s’agit d’un algorithme de recherche op´eratoire nomm´e
DijkstraTransverse qui calcule un ensemble de chemins transverses entre un nœud racine et chaque autre nœud
dugraphemod´elisantler´eseau.Lasecondecontributionestuneproc´eduredevalidationdistribu´eedont
le but est d’´elaguer les circuits potentiellement g´en´er´es par le routage saut par saut. Pour accroˆıtre la
diversit´e des chemins valid´es, la proc´edure de commutation est sp´ecifique `a chaque interface entrante.
Par ailleurs, nous avons ´evalu´e l’impact de la diversit´e des chemins pour mettre en œuvre une
couverture efficace en cas de panne de liens. La notion de couverture se d´ecline en deux versions, locale ou
globale, selon le type de protection envisag´e, 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´egalement int´eress´es aux aspects ing´enierie de trafic li´es `a l’´equilibrage de la charge
en cas de congestion. Afin d’estimer l’importance de la diversit´e des chemins pour mettre en œuvre
un routage proportionnel efficace, notre travail s’est focalis´e sur la d´efinition d’un module r´eactif de
partage de charge. Celui-ci est simplement bas´e sur une analyse locale de la bande passante r´esiduelle
et permet de mettre en relief les performances de nos propositions de routage par comparaison avec
l’existant.
De mani`ere g´en´erale, dans un souci de cr´edibilit´e, nos ´evaluations par simulation sont bas´es sur des
topologiesetuneg´en´erationdetraficr´ealistes.Lesr´esultatsobtenusmettentenavantl’efficacit´edenos
algorithmes pour d´eployer un routage multichemins g´en´erant une diversit´e accrue par rapport `a
l’existant.Celle-ciesteneffetn´ecessairepourobtenirunecapacit´edecommutationsuffisantepourcontourner
lespannesetlescongestionscommel’indiquentnosr´esultatsli´esauxdeuxtypesd’applications´evalu´es.Abstract
The reliability of IP networks in terms of failures and congestions depends on the reaction time
associatedwiththeunderlyingroutingprotocol.Currently,linkstateroutingprotocolssuchasOSPFor
IS-IS use only the best paths to forward the IP packets at a domain scale. The sub-optimality property
of best paths ensures consistency of hop by hop routing although the paths calculated using Dijkstra’s
algorithm are composed of close in close. According to the metric, the diversity of existing paths may
be largely under estimated with a condition such as sub-optimality. Yet the diversity of alternatives
paths is one of the key elements to ensure a limited reaction time. The main difficulty related to hop
by hop multipath routing protocols is to ensure the absence of routing loops. Each node must verify
that the traffic it carries is not switched on circuit where they belong.
InthisPhDreport,wepresenttwocontributionswhosethecombinationensuresthatproperty.Thefirst
proposition, based on Dijkstra’s algorithm, is a multipath search algorithm called Dijkstra-Transverse
(DT) which calculates a set of multiple paths between a root node and each other node in the graph
modeling the network. The second contribution is a distributed validation procedure DT(p) whose the
aim is to prune circuits potentially generated by hop by hop routing composition. To increase the
diversity of validated paths, the forwarding mechanism is specific to each incoming interface.
Furthermore,wehaveevaluatedtheimpactofthepathdiversitytoproduceaneffectivecoverageiflink
failureoccurs.The coveragecan be definedin two versions,localor global,dependingon the possibility
to notify upstream routers of the detected failure.
We are also interested in traffic engineering issues related to load balancing in case of congestion. To
estimatetheimportanceofpathsdiversitytoimplementaefficientproportionalrouting,wehavedefined
a reactive load balancing module. This module is based on a local analysis of residual bandwidth and
highlight the performance of our proposed routing scheme. For the sake of credibility, our simulations
are based on realistic topologies and traffic generation. The results underline the effectiveness of our
algorithms to generate a greater diversity of paths compared to existing propositions. Paths diversity
is necessary in order to obtain a sufficient forwarding capacity to circumvent outages and congestion
as indicated by our results related to these two