Equilibrage de charge et diffusion multicast dans les systèmes pair-à-pair
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
Within a Peer-to-Peer (P2P) Systems a large number of users interact ail together in order to gather ressources in a dynamic environnement. Several decentralized P2P Systems construct an overlay network based on a de Bruijn graph, and offer a good tradeoff between network diameter and node average degree, with a simple routing algorithm. However, they do not efficiently balance the network's load and do not support some more and more popular kinds of communications in the internet such as multicast. This thesis work proposes significant improvements to these Systems, and an efficient multicast algorithm. A first contribution is the improvement of the d-dimensional D2B protocol. First, we describe the protdcol in detail, and then we propose solutions to problems of network coherence (related to its dynamîcity) and to fault tolerance. A second contribution relates to load balancing in such Systems. After the description of the main existing load balancing methods, we present our solutions for balancing the nodes1 degrees. A third and final contribution is dedicated to multicast in a P2P System, at the application level. After a short state of the art of existing methods, we present our concept of "tree-farm". This solution allows for building families of sets of interior-noeud-disjoint trees for efficient multicast communications in P2P Systems based on de Bruijn graphs. The three contributions are evaluated by means of simulations and compared with existing methods of the state of the art.
Abstract FR:
Les systèmes pair-à-pair (P2P: Peer-to-Peer) mettent en relation des utilisateurs afin de mutualiser des ressources dans un environnement dynamique. Plusieurs types de systèmes P2P décentralisés construisent un réseau logique basé sur un graphe de de Bruijn, et offrent un bon compromis entre la taille du réseau et le degré moyen d'un nœud, avec un algorithme de routage simple, ils ne permettent cependant pas d'équilibrer efficacement la charge du réseau et ne supportent pas certains types de flux qui prennent de plus en plus d'importance dans l'Internet, telle la diffusion multicast. Cette thèse propose des améliorations à ces systèmes, et un support efficace de la diffusion multicast. Une première contribution consiste à améliorer le protocole D2B d-dimensionnel. Il est d'abord décrit en détails, puis des solutions aux problèmes de cohérence du réseau (liées à sa dynamicité) et de tolérance de pannes sont proposées. Une deuxième contribution concerne l'équilibrage de charge dans de tels systèmes. Les principales méthodes d'équilibrage de charge existantes sont d'abord décrites, avant de présenter nos solutions d'équilibrage du degré des nœuds. Une troisième et dernière contribution est consacrée à la diffusion multicast dans un système P2P, au niveau application. Après une introduction aux principales méthodes existantes, notre concept de "tree-farm" est présenté. Il permet de construire des familles d'ensembles d'arbres intérieur-disjoints pour la diffusion multicast dans un système P2P basé sur un graphe de de Bruijn. Les trois contributions sont évaluées à l'aide de simulations et comparées avec les méthodes de référence de l'état de l'art.