Structures et Algorithmes pour la coopération pair-à-pair

Peer-to-peer overlay networks are distributed systems, without any hierarchical organization or centralized control. Peers form self-organizing overlay networks that are on top of the Internet. Both parts of this thesis deal with peer-to-peer overlay networks, the first part with unstructured ones used to build a large scale Networked Virtual Environment. The second part gives insights on how the users of a real life structured peer-to-peer network behave, and how well the proposed algorithms for publishing and retrieving data works. Moreover we analyze the security (holes) in such a system. Networked virtual environments (NVEs), also known as distributed virtual environments, are computer-generated, synthetic worlds that allow simultaneous interactions of multiple participants. Many efforts have been made to allow people to interact in realistic virtual environments, resulting in the recent boom of Massively Multiplayer Online Games (MMOG). In the first part of the thesis, we present a complete study of an augmented Delaunay-based overlay for peer-to-peer massively shared virtual worlds. We design an overlay network matching the Delaunay triangulation of the participating peers in a generalized d-dimensional space. Especially, we describe the selforganizing algorithms for peer insertion and deletion. To reduce the delay penalty of overlay routing, we propose to augment each node of the Delaunay-based overlay with a limited number of carefully selected shortcut links creating a small-world. We show that a small number of shortcuts is sufficient to significantly decrease the delay of routing in the space. We present a distributed algorithm for the clustering of peers. The algorithm is dynamic in the sense that whenever a peer joins or leaves the NVE, the clustering will be adapted if necessary by either splitting a cluster or merging clusters. The main idea of the algorithm is to classify links between adjacent peers into short intracluster and long inter-cluster links. In a structured system, the neighbor relationship between peers and data locations is strictly defined. Searching in such systems is therefore determined by the particular network architecture. Among the strictly structured systems, some implement a distributed hash table (DHT) using different data structures. DHTs have been actively studied in literature and many different proposals have been made on how to organize peers in a DHT. However, very few DHTs have been implemented in real systems and deployed on a large scale. One exception is KAD, a DHT based on Kademlia, which is part of eDonkey, a peer-to-peer file sharing system with several million simultaneous users. In the second part of this thesis we give a detailed background on KAD, the organization of the peers, the search and the publish operations, and we describe our measurement methodology. We have been crawling KAD continuously for more than a year. We obtained information about geographical distribution of peers, session times, peer availability, and peer lifetime. We found that session times are Weibull distributed and show how this information can be exploited to make the publishing Mechanism much more efficient. As we have been studying KAD over the course of the last two years we have been both, fascinated and frightened by the possibilities KAD offers. We show that mounting a Sybil attack is very easy in KAD and allows to compromise the privacy of KAD users, to compromise the correct operation of the key lookup and to mount DDOS with very little resources.Des réseaux de type pair-à-pair "overlay" sont des systèmes distribués sans aucune organisation hiérarchique ni contrôle centralisé. Les pairs forment un réseau overlay au dessus de l'Internet. Les deux parties de cette thèse traitent les réseaux pair-à-pair overlay. La première partie utilise un réseau non structuré afin de construire un environnement virtuel partagé à grande échelle. Nous présentons une étude complète d'un overlay basé sur la triangulation de Delaunay. Avant tout nous décrivons les algorithmes auto-organisant pour l'insertion et la suppression d'un pair. Afin de réduire la pénalité de latence introduite par le routage dans l'overlay, nous proposons d'augmenter chaque nœud par quelques liens raccourcis qui créent un petit monde. Nous montrons que très peu de liens sont suffisants pour réduire la latence de manière significative. La deuxième partie de cette thèse donne des aperçus du comportement des utilisateurs d'un réseau pair-à-pair structuré dans le monde réel. Nous détaillons le fonctionnement de KAD, une table de hachage distribuée basé sur Kademlia, un système de partage de fichier avec plusieurs millions d'utilisateurs simultanés. Nous avons exploré le réseau de KAD pendant plus d'une année. C'est ainsi que nous avons obtenu des informations sur la distribution géographique, les temps de sessions, la disponibilité et le temps de vie des pairs. Nous sommes fascinés et effrayés par les possibilités que KAD offre. Le montage d'une attaque Sybil est très facile et permet de récupérer des données personnelles des utilisateurs, de compromettre le fonctionnement correct de la recherche dans KAD et de conduire une attaque DDOS