Self-organizing topology adaptation in peer-to-peer networks

Abstract

The peers in a Peer-to-Peer (P2P) system arrange themselves in a virtual network called the overlay network. The overlay network sits above the underlying physical network and is used to search for resources and peers, and to route messages between peers. The topology of the overlay network is the graph whose vertices are the peers and whose edges are the connections between the peers. The choice of topology affects application performance and the correct choice depends on the application. The literature contains examples of topologies that can be used to implement various types of applications. Topology adaptation algorithms are used to maintain an overlay network’s topology as per application requirements. Early P2P applications either did not use topology adaptation algorithms or used simple solutions based on a centralized component that results in poor fault-tolerance and scalability. Since 2002, decentralized algorithms have been proposed that may be used to create and maintain specific topologies. Although this is certainly an improvement, these algorithms are typically designed to create a specific topology for a specific application and are therefore not generally applicable or easily reusable. As a result, topology adaptation algorithms have to be designed from scratch and an application that has been developed using an existing algorithm cannot be altered easily to create and maintain a new topology. This thesis presents a general approach to decentralized topology adaptation in unstructured P2P overlay networks. The approach is based on a single abstract algo- rithm called the PEer-to-peer Self-organizing TOpology (PESTO), which can be used ii to develop a family of self-organizing topology adaptation algorithms for unstructured decentralized P2P overlay networks. PESTO is inspired by an idea from sociology, proposed by economist Thomas Schelling, to explain the existence of segregated neigh- borhoods in urban areas. An instantiation of PESTO requires formulation of rules that use a peer’s local awareness of the overlay network topology and result in overall emergent behavior of the network. To validate PESTO, we present and evaluate three concrete realizations. Two of these can be used to cluster peers with a given property, such as geographical location. The third realization can be used to create a backbone network of powerful computers called hubs, which can be used for search and for routing of messages between peers. Simulations are used to demonstrate that the concrete realizations can create self- organizing overlay network topologies with desirable properties. The three concrete realizations show that PESTO is sufficiently general to be applicable across a range of applications. The topology adaptation algorithms are placed in the context of a general-purpose P2P reference architecture, called the P2P reference Architecture that Supports Topol- ogy Adaptation (PASTA). A distinguishing feature of PASTA is that it contains a component that allows topology adaptation using the novel approach presented in the thesis. In addition, PASTA serves as a template, which can be used as a starting point for designing new P2P applications and middlewares. PASTA is sufficiently general to allow the description and comparison of the structure of existing P2P applications which is shown through structural description of a number of existing P2P applications. PASTA’s ability to describe and compare P2P applications can be used to enhance the understanding of the P2P domain and the research done on it