Vous êtes ici : UVSQ RechercheDoctoratSoutenances de thèse

Introduction de la qualité de service dans le réseau inter-domaine Internet : algorithmes et modélisation

Par Monsieur Marc-Antoine WEISSER Discipline : INFORMATIQUE

Résumé : Internet est un réseau composé de plusieurs milliers de réseaux indépendants. Ils sont inter-connectés et forment le réseau inter-domaine. Les paquets traversant le réseau suivent une route, déterminée par BGP, qui peut emprunter plusieurs de ces domaines. Aucune information concernant la qualité des routes n'est diffusée dans le réseau. Dans cette thèse, nous étudions deux approches pour introduire la qualité de service dans le réseau inter-domaine. Chacune s'appuie sur les informations rassemblées par BGP, sans modification du protocole. Malgré la faible quantité d'information demandée par les algorithmes que nous proposons, nous montrons qu'ils sont performants. La première approche est un mécanisme d'alertes pour permettre aux domaines clients d'être avertis lorsqu'un de leur fournisseur est congestionné afin qu'ils puissent choisir des routes ne traversant pas de domaines saturés. La seconde approche est un mécanisme de sélection de routes multi-contraintes. Ce mécanisme respecte les limitations du réseau inter-domaine comme l'opacité des domaines. Pour ces deux approches nous avons produit un ensemble de résultats théoriques pour prouver la complexité des problèmes rencontrés et fait des simulations pour montrer les performances de nos solutions. Pour ces simulations, nous avons besoin de topologies représentatives du réseau inter-domaine et de sa structure hiérarchique. Un tel générateur n'existant pas, nous en avons créé un (logiciel SHIIP). Nous proposons donc dans cette thèse plusieurs mécanismes pour l'introduction de la qualité de service dans Internet et un modèle de topologies aléatoires représentatives de la hiérarchie du réseau inter-domaine.

Abstract : The Internet is a network composed of more than 20,000 independent networks. They are inter-connected and built the inter-domain network. Packets passing through the network follow a path selected by BGP which can be composed of many domains. No information concerning the quality of the path is spread into the network. In this thesis, we study two approaches to introduce the quality of service into the inter-domain network. Each approach is built on the information collected by BGP, without modification of the protocol. The proposed algorithms use a small quantity of information and we show that they are efficient. The first approach is a mechanism based on alert messages diffusion. It allows client domains to be aware when some of there provider domains are congested and to adapt their paths to avoid the congestion. The second approach is a multi-constraint path selection mechanism. It respects the limitations of the inter-domain network such as the opacity of domains. For both approaches we produce theoretical results on the complexity of the studied problems and simulations showing the efficient behaviour of our solutions. To build simulation models, we need topologies which are representative of the inter-domain network and of its hierarchical structure. Because a such generator did not exist, we write it (SHIIP software). We propose in this thesis two mechanisms to introduce the quality of service in the Internet and a model of random topology representative of the hierarchical structure of the inter-domain network.

Informations complémentaires

Tadeusz CZACHORSKI, Professeur des Universités, à « IITIS » Gliwice Pologne - Rapporteur Sébastien TIXEUIL, Professeur des Universités, à l'Université Pierre et Marie Curie Paris 6 - Rapporteur Jean-Claude KONIG, Professeur des Universités, à LIRMM, Montpellier - Examinateur Dominique GOUYOU-BEAUCHAMPS, Professeur des Universités, à LRI, Orsay - Examinateur Joanna TOMASIK, Professeur, à Supélec, Gif-sur-Yvette - Encadrante Olivier MARCE, Ingénieur de recherche, à Alcatel-Lucent R&D, Marcoussis - Invité Dominique BARTH, Professeur à l'Université de Versailles Saint-Quentin-en-Yvelines - Directeur de Thèse