Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Partage de Charge et Ing´ enierie de Traﬁc dans les R´ eseaux MPLS Ramon Casell

Partage de Charge et Ing´ enierie de Traﬁc dans les R´ eseaux MPLS Ramon Casellas To cite this version: Ramon Casellas. Partage de Charge et Ing´ enierie de Traﬁc dans les R´ eseaux MPLS. do- main other. T´ el´ ecom ParisTech, 2002. English. <pastel-00000680> HAL Id: pastel-00000680 https://pastel.archives-ouvertes.fr/pastel-00000680 Submitted on 4 Jun 2004 HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci- entiﬁc research documents, whether they are pub- lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destin´ ee au d´ epˆ ot et ` a la diﬀusion de documents scientiﬁques de niveau recherche, publi´ es ou non, ´ emanant des ´ etablissements d’enseignement et de recherche fran¸ cais ou ´ etrangers, des laboratoires publics ou priv´ es. Th` ese pr´ esent´ ee pour obtenir le grade de docteur de l’Ecole Nationale Sup´ erieure des T´ el´ ecommunications Sp´ ecialit´ e : Informatique et R´ eseaux M. Ramon CASELLAS Partage de Charge et Ing´ enierie de Traﬁc dans les R´ eseaux MPLS soutenue le 25 novembre 2002 devant le jury compos´ e de Annie Gravey Pr´ esident Ravi R. Mazumdar Rapporteurs Philippe Nain James Roberts Examinateurs Samir Tohm´ e Jean-Louis Rougier Daniel Kofman Directeur de th` ese A la m´ emoire de mon p` ere, Ramon Casellas Forn´ es, A ma m` ere, Araceli Regi i de Luque, A mon fr` ere, Toni Casellas Regi, Merci. Remerciements Cette th` ese n’aurait jamais vu le jour sans l’aide et le soutien d’un certain nombre de personnes auxquelles j’aimerais exprimer ici toute ma reconnaissance. Je voudrais tout d’abord remercier mon directeur de th` ese, M. Daniel Kofman, pour sa conﬁance renouvel´ ee et ses encouragements continus tout au long de ces trois ann´ ees. Ses commentaires et ses remarques m’ont ´ et´ e tr` es pr´ ecieux et m’ont aid´ e ` a d´ evelopper un esprit critique indispensable pour mener ` a bien un tel travail. Je suis profond´ ement redevable aux membres de mon jury : merci ` a Mme. Annie Gravey, directrice du d´ epartement Informatique de l’ENST Bretagne, dont les commentaires toujours pertinents et la jovialit´ e ont souvent relanc´ e ma motivation ; merci ` a M. Ravi R. Mazumdar, Professeur ` a l’Universit´ e de Purdue, dont les commentaires et les remarques m’ont ´ et´ e tr` es utiles pour le d´ eveloppement de la derni` ere partie de ce document, et qui a accept´ e d’ˆ etre rapporteur de mon travail, et ` a M. Philippe Nain, directeur de recherche ` a l’INRIA, qui a ´ egalement bien voulu ˆ etre rapporteur du document. M. Jim Roberts, de France T´ el´ ecom Recherche et D´ eveloppement m’a fait l’honneur de bien vouloir faire partie de ce jury ; M. Jean-Louis Rougier a ´ et´ e un excellent coll` egue et un tr` es bon ami. Je le remercie d’avoir ´ egalement accept´ e de faire partie de ce jury. Finalement, merci ` a M. Samir Tohm´ e, responsable du groupe R´ eseau Haut D´ ebit du d´ epartement INFRES de l’ENST, pour avoir accept´ e de faire partie de mon jury de th` ese. Dans le contexte de mes travaux de recherche, j’ai eu des discussions tr` es enrichissantes avec plusieurs membres du d´ epartement INFRES, notamment MM. Laurent Decreusefond et Hayri Korezlioglu ; qu’ils en soient grandement remerci´ es. MM. Fran¸ cois Baccelli, Laurent Massouli´ e et Jean Mairesse, responsables du DEA Probabilit´ es Appliqu´ ees et Processus Ponctuels ` a l’Universit´ e Paris VI, m’ont facilit´ e le premier contact avec la th´ eorie des grandes d´ eviations et son application aux r´ eseaux de ﬁles d’attente. Je leur en suis sinc` erement reconnaissant. Merci ` a M. Anthony Busson, colocataire de bureau et ami, qui a ´ et´ e parfois oblig´ e de me rappeler qu’une probabilit´ e ne peut ˆ etre sup´ erieure ` a un, et ` a M. Christian Roche qui s’est gracieusement charg´ e de la lourde tˆ ache de relire les versions pr´ eliminaires de ce document et de m’aider ` a aplanir mes diﬃcult´ es avec la langue de Moli` ere. Il se peut qu’un certain nombre de fautes de frappe soient encore pr´ esentes dans la version ﬁnale de ce document. Je fais appel ` a ce sujet ` a l’indulgence du lecteur. Lors de mon s´ ejour ` a l’ENST j’ai eu la chance de cˆ otoyer un grand nombre d’enseignants-chercheurs et de th´ esards d’horizons divers avec lesquels j’ai partag´ e de tr` es bons moments : M. Sergio Beker, M. Philippe Monnier, M. Philippe Martins, Mlle. Nadia Boukhatem, M. Gwendal Legrand et tant d’autres, trop nombreux pour ˆ etre tous cit´ es ici. Finalement, je tiens ` a remercier mes amis ` a Barcelone, Juan et Ramon San-Martin et Sergio Cor- mano, qui m’ont soutenu et encourag´ e pendant tout mon s´ ejour en France. Merci ` a Jes´ us Garc´ ıa et 5 C´ elia Cost´ eja, mes chers colocataires, qui ont support´ e mes moments de fatigue et de pessimisme. Enﬁn, un grand merci ` a ma m` ere et ` a mon fr` ere pour leur aﬀection qui m’a ´ et´ e extrˆ emement pr´ ecieuse durant ces ann´ ees loin d’eux. 6 R´ esum´ e Dans cette th` ese, nous nous sommes int´ eress´ es ` a l’optimisation du partage de charge dans un r´ eseau supportant le routage ` a la source. Une mod´ elisation g´ en´ erique en ﬁles d’attente aliment´ ees par un traﬁc caract´ eris´ e par sa bande passante eﬀective et l’utilisation de la th´ eorie des Grandes D´ eviations nous a permis de d´ eduire de r` egles d’ing´ enierie dans divers contextes en optimisant des fonctions de coˆ ut qui reﬂ` etent les besoins des r´ eseaux op´ erationnels. Des propri´ et´ es structurelles sur les poli- tiques optimales ont ´ et´ e d´ emontr´ ees pour des cas particuliers mais importants dans le domaine de l’ing´ enierie du traﬁc. La variabilit´ e de la capacit´ e des chemins d’un r´ eseau a ´ et´ e int´ egr´ ee ` a l’aide du concept de capa- cit´ e eﬀective. Nous avons mis en ´ evidence qu’un dimensionnement bas´ e sur une capacit´ e moyenne peut s’av´ erer sous optimal et nous avons quantiﬁ´ e cela. Ainsi, une approche d’ing´ enierie de traﬁc adaptative a ´ et´ e propos´ ee en faisant ´ evoluer le partage en fonction des mesures r´ ealis´ ees sur le r´ eseau. Dans la derni` ere partie de ce travail nous avons regard´ e le r´ eseau dans sa globalit´ e, mod´ elisant les interactions entre l’ensemble des couples entr´ ee-sortie, nous permettant de mieux optimiser le r´ eseau mais au coˆ ut d’une grande complexit´ e de calcul. Abstract In this dissertation, we propose and optimize load sharing mechanisms adapted to a network suppor- ting source routing. A generic model using queues fed by traﬃc which is represented by its eﬀective bandwidth is deﬁned, and the use of the large deviations theory allows us to obtain traﬃc enginee- ring rules and guidelines for several scenarios by optimizing cost functions that reﬂect the needs of operational networks. Structural properties about optimal load sharing policies have been obtained in particular but important cases with regard to traﬃc engineering. The time varying property of the end to end capacity of network paths has been taken into account by means of what we call eﬀective capacity. We have shown that a load sharing based on average values may not be optimal, and we have quantiﬁed this. In this sense, we have also proposed and adaptive measurement based load sharing mechanism. In the last part of our work, we have extended our model in order to consider the whole network, taking into account the interactions between all origin-destination couples, allowing a better opti- mization of the network but with a high computation complexity. 7 Administrativia Le pr´ esent document est le manuscrit de th` ese pour obtenir le grade de docteur de l’Ecole Natio- nale Sup´ erieure des T´ el´ ecommunications sp´ ecialit´ e Informatique et R´ eseaux. La th` ese « Partage de charge et Ing´ enierie de Traﬁc dans les r´ eseaux MPLS » a ´ et´ e r´ ealis´ ee par M. Ramon Casel- las <casellas@infres.enst.fr> et dirig´ ee par M. Daniel Kofman <kofman@infres.enst.fr> . Cette th` ese a ´ et´ e ﬁnanc´ ee ` a l’aide d’une bourse allou´ ee par France T´ el´ ecom, division Recherche et D´ eveloppement (FTRD/DAC/ISIS, responsable M. James Roberts ), contrat NUM 991B174. Les travaux de recherche de cette th` ese ont eu lieu ` a l’Ecole Nationale Sup´ erieure des T´ el´ ecommu- nications, 46, rue Barrault 75634 Paris Cedex 13. Contexte Le contexte de cette th` ese est constitu´ e par un ensemble de uploads/Science et Technologie/ partage-de-charge-et-ingienierie-de-trafic-mpls 1 .pdf