Load management in peer-to-peer systems: structures and algorithms

Dans cette thèse, nous présentons plusieurs techniques inédites pour la gestion de charge dans les systèmes pair-à-pair. Nous abordons deux types de systèmes pair-à-pair: les systèmes de recherche d’information (en particulier DHTs), où nous définissons de nouvelles solutions pour l’équilibrage de charge, et les systèmes de diffusion d’information, où nous définissons de nouvelles méthodes de réduction de charge. Tout d’abord, nous présentons le contexte des systèmes pair-à-pair et nous élaborons sur les solutions existantes en matière de gestion de charge. Nous les classifions en trois différentes catégories: le placement des objets, le trafic de routage et la sous-couche (underlay). Bien que les deux premières catégories visent avant tout les systèmes de recherche d’information, portant sur l’affectation objet-à-nœud et sur les stratégies de routage appliquées pour la recherche d’objet, la dernière catégorie est plus générale. Tout recouvrement (overlay), quel que soit son applicabilité, doit avoir une certaine connaissance de son sous-couche afin de pouvoir gérer sa charge de trafic. Nous apportons trois solutions à la gestion de charge dans les systèmes pair-à-pair. Nous proposons HyPeer, un recouvrement de type DHT avec équilibrage dans l’espace de noms qui offre un choix flexible entre plusieurs stratégies de routage. à cette fin, nous avons construit la structure de HyPeer uniforme et régulière, où les nœuds sont consciencieusement placés. Le but est de fournir une redondance des chemins (path redundancy), où les chemins ont des longueurs similaires. Avec plusieurs chemins entre deux nœuds, de nombreuses différentes stratégies de routage peuvent être appliquées. Nous proposons quatre stratégies visant les plus communs objectifs: chemin court, délai faible, tolérance de panne et, le plus important dans notre contexte, équilibrage de charge de routage. Nos stratégies atteignent toutes de très bons résultats au coût de juste quelques calculs locaux pour déterminer le saut suivant dans le chemin. En outre, le recouvrement soutient la définition de nouvelles stratégies de routage ou le raffinage des stratégies de routage existantes avec de nouvelles métriques. Pour les autres DHTs existants, nous proposons une solution d’équilibrage de charge de routage qui peut ˆêtre appliquée à tout recouvrement qui permet une flexibilité dans le choix des voisins. Notre solution est adaptative et elle est basée sur la réorganisation des liens (link reorganization): en fonction de la fluctuation de charge dans le système, les voisins les plus chargés sont écartés, le trafic étant dirigé vers des pairs moins chargés. Cette solution a peu de frais, ne génère pas de messages supplémentaires et la réorganisation des liens est déclenché que lorsque la charge atteint des valeurs trop élevées. Dans les systèmes de diffusion d’information, nous proposons une nouvelle stratégie pour réduire la charge au niveau sous-couche. Nous n’utilisons pas le hasard comme les stratégies classiques le font, ce qui génère une charge de trafic très grande dans la sous-couche. Nous considérons plutôt la conscience de proximité. Après une dispersion limitée de l’information dans le réseau, nous donnons la préférence aux routes courtes pour la livraison du message de diffusion. Notre solution permet de réduire considérablement la charge de trafic dans la sous-couche, tout en n’affectant pas le temps de diffusion.In this thesis, we present several novel techniques for load management in peer-to-peer systems. We tackle two types of peer-to-peer systems: information lookup systems (in particular DHTs), where we define new load balancing solutions, and information dissemination systems, where we define new methods for load reduction First, we introduce the context of peer-to-peer systems and we elaborate on the existing solutions on load management. We classify them into three different categories: object placement, traffic routing and underlay. While the first two categories are aimed mostly at information lookup systems, dealing with object-to-node assignment and the routing strategies to be applied for object lookup, the latter category is more general. Any overlay, regardless its applicability, needs to have some knowledge about its underlay in order to manage its traffic load. Our contributions to load management solutions are threefold. We propose HyPeer, a novel DHT overlay with namespace balancing that offers flexible-choice among several routing strategies. For this purpose, we have built the uniform and regular HyPeer structure, where the nodes are conscientiously placed in order to offer path redundancy at similar path lengths. Having multiple paths between any two nodes, many different routing strategies can be applied. We propose four routing strategies aiming the most common goals: short path length, low path delay, fault tolerance and, most important in our context, routing load balancing. They all achieve very good results at the cost of only few local computations to determine the next hop in the request path. Moreover, the overlay offers support for defining new routing strategies or for refining the existing routing strategies with new metrics. For other existing DHTs, we propose a routing balancing solution that can be applied to any overlay that allows flexibility in the choice of the neighbors. Our solution is adaptive and it is based on link reorganization: according to the load fluctuation in the system, the most loaded neighbors are discarded, the forwarding traffic being redirected to less loaded peers instead. This solution comes at low costs, no extra messages being involved and moreover triggering link reorganization only when the load reaches too high values. In information dissemination systems, we propose a novel strategy in order to reduce the load at the underlay level. We do not use complete randomness as classical strategies do, this generating too much traffic load at the underlay, instead we consider proximity awareness. After a limited seeding of the network, we give preference to the usage of short routes for delivering the dissemination message. Our solution significantly reduces the traffic load at the underlay, while not affecting the dissemination time