Load balancing in dynamic structured P2P systems Export

@inproceedings{Godfrey2004, abstract = {Most P2P systems that provide a DHT abstraction distribute objects randomly among "peer nodes" in a way that results in some nodes having /spl theta/(log N) times as many objects as the average node. Further imbalance may result due to non-uniform distribution of objects in the identifier space and a high degree of heterogeneity in object loads and node capacities. Additionally, a node's load may vary greatly over time since the system can be expected to experience continuous insertions and deletions of objects, skewed object arrival patterns, and continuous arrival and departure of nodes. We propose an algorithm for load balancing in such heterogeneous, dynamic P2P systems. Our simulation results show that in the face of rapid arrivals and departures of objects of widely varying load, our algorithm achieves load balancing for system utilizations as high as 90\% while moving only about 8\% of the load that arrives into the system. Similarly, in a dynamic system where nodes arrive and depart, our algorithm moves less than 60\% of the load the underlying DHT moves due to node arrivals and departures. Finally, we show that our distributed algorithm performs only negligibly worse than a similar centralized algorithm, and that node heterogeneity helps, not hurts, the scalability of our algorithm.}, author = {Godfrey, B. and Lakshminarayanan, K. and Surana, S. and Karp, R. and Stoica, I.}, booktitle = {INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies}, citeulike-article-id = {1641433}, citeulike-linkout-0 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1354648}, journal = {INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies}, keywords = {balan, balancing, ecs256, load, p2p}, pages = {2253--2262 vol.4}, posted-at = {2007-10-09 03:17:04}, priority = {4}, title = {Load balancing in dynamic structured P2P systems}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1354648}, volume = {4}, year = {2004} }

TY - CONF ID - Godfrey2004 L3 - citeulike-article-id:1641433 N2 - Most P2P systems that provide a DHT abstraction distribute objects randomly among "peer nodes" in a way that results in some nodes having /spl theta/(log N) times as many objects as the average node. Further imbalance may result due to non-uniform distribution of objects in the identifier space and a high degree of heterogeneity in object loads and node capacities. Additionally, a node's load may vary greatly over time since the system can be expected to experience continuous insertions and deletions of objects, skewed object arrival patterns, and continuous arrival and departure of nodes. We propose an algorithm for load balancing in such heterogeneous, dynamic P2P systems. Our simulation results show that in the face of rapid arrivals and departures of objects of widely varying load, our algorithm achieves load balancing for system utilizations as high as 90% while moving only about 8% of the load that arrives into the system. Similarly, in a dynamic system where nodes arrive and depart, our algorithm moves less than 60% of the load the underlying DHT moves due to node arrivals and departures. Finally, we show that our distributed algorithm performs only negligibly worse than a similar centralized algorithm, and that node heterogeneity helps, not hurts, the scalability of our algorithm. JF - INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies EP - 2262 vol.4 TI - Load balancing in dynamic structured P2P systems VL - 4 T2 - INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies SP - 2253 KW - balan KW - balancing KW - ecs256 KW - load KW - p2p AU - Godfrey, B AU - Lakshminarayanan, K AU - Surana, S AU - Karp, R AU - Stoica, I PY - 2004/// UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1354648 ER -