Analysis and optimization of peer-to-peer systems under churn.

摘要

In peer-to-peer (P2P) systems, the phenomenon of churn (i.e., peer dynamics) will destroy the overlay structure, cause the loss of data objects, deteriorate the lookup performance, increase the bandwidth cost, and thus impact the performance of distributed applications greatly. Due to the prevalence of churn in real environments, it is essential to get a better understanding on how peer-to-peer systems evolve under churn and how to optimize the system performance under churn. In this thesis, we focus our research on the analysis and optimization of peer-to-peer systems under churn. Our research work falls into three main aspects: object storage under churn, object lookup under churn, and object (or load) balancing under churn.We firstly develop a stochastic model to shed light on the evolution of stored objects in peer-to-peer systems under different types of churn, and analytically study the interplay between object maintenance and churn. To avoid the complexity of Markovian modeling, our model is based on stochastic differential equations, and thus we can provide closed-form terms to capture the system time-evolution, and formally derive asymptotic performance metrics of P2P storage systems under different maintenance strategies and various kinds of churn. Our analytical results provide some important insights in object maintenance under churn, which are useful in the optimization of P2P storage systems, e.g., reducing bandwidth usage, provisioning for bandwidth spike, improving system capacity, etc. Besides analytical study, our analysis is also validated by extensive simulation.Next, we consider the problem of optimizing lookup performance in DHT-based P2P systems under churn. We analytically study three important aspects on the optimization of DHT lookup performance, i.e., lookup strategy, lookup parallelism and lookup key replication. Our objective is to build a theoretical basis for the designers to make better choices in their future design. We first compare the performance of two representative lookup strategies - recursive routing and iterative routing, and explore the existence of better alternatives. Then we study the effectiveness of lookup parallelism in systems with different churn rates and show how to select the optimal degree of parallelism. Due to the importance of key replication on lookup performance, we also analyze the reliability of replicated keys under two different replication policies, and show how to perform proper configuration. Later, our results are also validated by simulation, and Kad is taken as a case to show the meaningfulness of our analysis.Lastly, we study the effectiveness of two representative load balancing strategies in DHT-based P2P systems, (1) Rendezvous Directory Strategy (RDS) and (2) Independent Searching Strategy (ISS), under system churn. It enables us to have a clear understanding about their efficiency, scalability and robustness. Based on the analysis results, we also propose a Group Multicast Strategy (GMS) for load balancing in DHT systems, which attempts to achieve the benefits of both RDS and ISS. In order to have a better understanding of GMS, we also perform analytical studies on GMS in terms of its scalability and efficiency under churn. Finally, the effectiveness of GMS is evaluated by extensive simulation under different workload and churn levels.