The Server Reassignment Problem for Load Balancing in Structured P2P Systems

摘要

Application layer peer to peer (P2P) networks are considered to be the most important development for next generation Internet infra-structure. For these systems to be effective, load balancing among the peers is critical. Most structured P2P systems rely on ID-space partitioning schemes to solve the load imbalance problem, and has been known to result in an imbalance factor of u00026;#x0398;(log N) in the zone sizes. This paper makes two contributions. First, we propose to address the virtual server-based load balancing problem systematically using an optimization based approach, and derived an effective algorithm to re-arrange loads among the peers. We demonstrate the superior performance of our proposal in general, and its advantages over previous strategies in particular. We also explore other important issues vital to the performance in the virtual server framework, such as the effect of the number of directories employed in the system, and the performance ramification of user registration strategies. Secondly, and perhaps more significantly, we characterize systematically the effect of heterogeneity on load balancing algorithm performance, and the conditions in which heterogeneity may be easy or hard to deal with based on extensive study of a wide spectrum of load and capacity scenarios.