La qualité de service dans le réseau inter-domaine Internet : algorithmes et modélisation
Institution:
Versailles-St Quentin en YvelinesDisciplines:
Directors:
Abstract EN:
The Internet is a network composed of more than 20,000 independant networks. The are inter-connectrd and built the inter-domain network. Packets passing through the network follow a path selected by BGP wich can be composed of many domains. No information concerning the qualité 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 lodification 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 sedoncd 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 produice theoretical results on the complexity of the studied problems and simulations showing the efficient behaviour of our solutions. To built simulation models, we need topologies wich are representative ot hr inter-domain network and its hierarchical structure. Because a such generator did not exist, we write it (SHIIP software). We propose in this thesis two mechanisms to introducs the quality of service in the internet and a model of random topology representative of the hierarchical structure of the inter-domain network.
Abstract FR:
Internet est un réseau constitué 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é 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 puisent 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 approche 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-domaines et de sa strucure hiérarchique. Un tel générateur n'existant pas, nous en avons crée 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.