A peer-to-peer overlay network is a logical network, built on top of a physical network. In contrast to classical client-server distributed architectures, peer-to-peer overlay networks allow location of resources without centralized control. Existing overlay networks can be roughly classified as unstructured and structured. In the former, the distribution of resources and the network structure are independent. They are easily constructed, however resource location requires exhaustive search over the network. In the later, the distribution of resources and the network structure are correlated and as a result there are more efficient methods for resource location. However, the construction and the maintenance methods are more complex for structured overlay networks. The first part of this thesis focuses on the self-organizing construction of structured overlay network. The existing approaches rely on sequential processes for structured overlay network construction. The construction starts from a single node and nodes join the network sequentially. The possibility of using parallel processes for structured overlay network construction has not been widely considered in the literature. We study this approach for a specific structured overlay network, namely P-Grid, whose topology is based on a binary tree structure. We propose a randomized parallel algorithm that successfully constructs a P-Grid structured overlay network. We experimentally evaluate our algorithm and compare it to one of the few other parallel construction algorithms that has been used for FreeNet, a loosely structured overlay network. We show that the performance of FreeNet construction heavily depends on the specific parameter settings while our P-Grid construction process remains unaffected by the settings of the system parameters. Next we propose an optimized randomized algorithm for the parallel construction of P-Grid, which achieves the expected lower bounds for communication cost. The correctness of the algorithm is based on graph-theoretic properties of random regular graphs. A frequent assumption in the design of peer-to-peer overlay networks is that all peers have equal properties. Existing designs usually do not explicitly take into account the wide range of possible behaviors and capabilities of peers that include processing power, storage and link capacities, propensity of peers to stay available for longer periods, and also the diversity of application requirements. The second part of the thesis deals with the issue of non-uniform peer capacities and varying application requirements. As a first approach we propose a generalization of P-Grid, namely k-ary P-Grid. By introducing a system parameter for controlling the outdegree of peers, the k-ary P-Grid allows obtaining a tradeoff between peer resources dedicated to the network, and the network performance. The second approach, named SP-Grid, is a hierarchical peer-to-peer overlay network that allows a subset of powerful peers (superpeers) to construct an additional overlay on top of P-Grid, in which each superpeer becomes responsible for a set of peers. The SP-Grid provides better performance guarantees for resource location than P-Grid and k-ary P-Grid. We provide the construction, maintenance, resources location and load-balancing algorithms for SP-Grid. P-Grid, k-ary P-Grid and SP-Grid can be constructed on top of each other, can possibly coexist together and serve as fall-back solutions for each other. Our unique approach offers an easy implementation that allows transitions from unstructured to more structured overlay networks. Thus, it supports a framework for flexible support of resource location satisfying the performance requirements of a wide range of applications.
EPFL2006
