Randomized load balancing strategies with churn resilience in peer-to-peer networks

摘要

The objective of load balancing in peer-to-peer (P2P) networks is to balance the workload of peer nodes in proportion to their capacity so as to eliminate performance bottlenecks. It is challenging because of the dynamic nature in overlay networks, the time-varying load characteristics, and the inherent load imbalance caused by consistent hashing functions. It is known that simple randomized load balancing schemes can balance load effectively while incurring only a small overhead in general parallel and distributed computing contexts. Existing theoretical works which analyze properties of randomized load balancing schemes cannot be applied in the highly dynamic and heterogeneous P2P systems. In this paper, we characterize the behaviors of randomized load balancing schemes in a general P2P environment We extend the supermarket model by investigating the impact of node heterogeneity and churn on load distribution in P2P networks. We prove that by using d-way random choices schemes, the length of the longest queue in a P2P system with heterogeneous nodes and churn for d ≥ 2 is c * log logn/logd+O(1) with high probability, where c is a constant Our results have wide applicability and are of interest beyond the specific applications.