Overlay Network Mechanisms for Peer-to-Peer Systems

The Peer-to-Peer (P2P) paradigm provides an alternative design approach for distributed systems, which relaxes the requirement for dedicated service providers as it is the case in client-server systems. The P2P approach explores the potential to create distributed systems based on the resources and the services that can be provided by any end-point device connected to a common communication medium, i.e. the Internet. P2P-based distributed systems develop dedicated virtual networks on top of physical telecommunication networks, the so-called overlay networks. An overlay network is a mandatory abstraction from physical networks to both flexibly fulfill functional requirements such as connectivity maintenance, indexing and routing, as well as to satisfy non-functional ones, such as scalability, fault-tolerance and load-balance. A challenging aspect in designing overlay networks is the satisfaction of the posed requirements, while coping with potential conflicts among them in a customizable way. This thesis investigates a novel architecture for designing effective overlay networks for P2P systems that considers the most important characteristics of widely deployed systems. In particular, the large number of participants is considered, which introduces network scalability and expandability issues. Moreover, the thesis is concerned with their uncontrollable and difficult to predict behavior, which causes highly dynamic and fluctuating overlay network topologies. Such behavior makes it challenging to design resilient and stable systems that can operate effectively with minimum maintenance cost. Additionally, an important consideration is the intrinsic heterogeneity of their physical capabilities and user behavior that aggravates the problem of even workload distribution. A number of mechanisms have been devised to meet the aforementioned requirements. Starting with the network topology, the usage of de Bruijn graphs is proposed. Their attractive characteristic of having a logarithmically increasing diameter, even when nodes have fixed degree, is particularly useful to address the scalability requirement with minimum maintenance cost. However, the exponential expandability is an intrinsic issue for de Bruijn graphs. A graph construction algorithm based only on local information has been proposed to define de Bruijn variants with incremental expandability properties. Moreover, the fixed node degree (preferably as small as possible to keep the graph maintenance costs low) poses resiliency concerns. This matter is addressed with the introduction of peer clusters that guarantee their reliability and with a two-tier topology where the de Bruijn structure applies at the inter-cluster connections. This hybrid topology provides a tightly structured network. In parallel, it gives the freedom of selecting neighbor peers from several members of the neighbor clusters. This selection can be driven by various policies and metrics, i.e., by the efficient mapping to the underlying network or by satisfying trust-level requirements. Additional mechanisms have been proposed for the intra-cluster organization that deals with peer heterogeneity. For this issue, a role-based approach has been investigated. The common, basic operations of P2P overlay networks have been identified assigning a role to each of them. More specifically, four core roles have been identified: Routers, Cachers, Indexers and Maintainers. Peers are assigned with roles based on their capabilities and their predicted behavior so that each peer can contribute in an efficient way without hindering and degrading the overall performance. Certain rules increase the balanced contribution of each peer resulting in a fair solution. The proposed architecture has been realized within the Omicron approach. The resulting system has been evaluated both analytically and by simulation. The analytical approach is based on stochastic modeling, analysis and evaluation of the mechanisms that take into account empirically observed measurements collected from widely deployed P2P systems. Further, burn-in methods that capitalize on conditional reliability approaches are utilized in order to provide an optimal role assignment decision. The simulative approach required the usage of a tool capable of accurately capturing the dynamics of user behavior, the characteristics of the underlying networks and the detailed interaction of the involved P2P protocols. An open architecture simulation framework has been developed to augment the evaluation of our work as well as other important alternative solutions. Thereby, comparative quantitative measures of the performance in a wide range of interesting scenarios are provided. Both the analytical and the simulation results demonstrate the superior design of Omicron for large scale, dynamic and heterogeneous environments as well as its ability to effectively adapt a plethora of trade-offs in requirement constraint