Hash-based proximity clustering for efficient load balancing in heterogeneous DHT networks

M. Adler, E. Halperin, R.M. Karp, V. Vazirani, A stochastic process on the hypercube with applications to peer-peer networks, in: Proceedings of STOC, 2003. Ahmad, 1991, Semi-distributed load balancing for massively parallel multicomputer systems, IEEE Trans. Software Eng., 17, 10.1109/32.99188 K. Albrecht, R. Arnold, M. Gähwiler, R. Wattenhofer, Aggregating information in peer-to-peer systems for improved join and leave, in: Proceedings of the 4th International Conference on P2P Computing, 2004. Asano, 1997, Space filling curves and their use in geometric data structure, Theoret. Comput. Sci., 181, 3, 10.1016/S0304-3975(96)00259-9 Y. Azar, A. Broder, et al., Balanced allocations, in: Proceedings of STOC, 1994, pp. 593–602. A.R. Bharambe, M. Agrawal, S. Seshan, Mercury: supporting scalable multi-attribute range queries, in: Proceedings of ACM SIGCOMM, 2004. M. Bienkowski, M. Korzeniowski, F.M. auf der Heide, Dynamic load balancing in distributed hash tables, in: Proceedings of IPTPS, 2005. J. Byers, J. Considine, M. Mitzenmacher, Geometric generalizations of the power of two choices, in: Proceedings of ACM SPAA, 2004. M. Castro, P. Druschel, Y.C. Hu, A. Rowstron, Topology-aware routing in structured peer-to-peer overlay networks, in: Future Directions in Distributed Computing, 2002. A. Chervenak, M. Cai, M. Frank, A peer-to-peer replica location service based on a distributed hash table, in: ACM/IEEE Conference on Supercomputing (SC), 2004. S. Fu, H. Shen, C. Xu, Power of two for randomized selections in generalized supermarket models, Technical Report, ECE Department, Wayne State University, 2006. P. Ganesan, M. Bawa, H. Garcia-Molina, Online balancing of range-partitioned data with applications to peer to peer systems, in: Proceedings of the 30th VLDB Conference, 2004. L. Garces-Erice, E.W. Biersack, K.W. Ross, P.A. Felber, G. Urvoy-Keller, Hierarchical p2p systems, in: Proceedings of ACM/IFIP International Conference on Parallel and Distributed Computing (Europar), 2003. Godfrey, 2006, Load balancing in dynamic structured P2P systems, Performance Evaluation, 63 B. Godfrey, I. Stoica, Heterogeneity and load balance in distributed hash tables, in: Proceedings of INFOCOM, 2005. D. Karger, E. Lehman, T. Leighton, M. Levine, et al., Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, in: Proceedings of STOC, 1997, pp. 654–663. D.R. Karger, M. Ruhl, Simple efficient load balancing algorithms for peer-to-peer systems, in: Proceedings of IPTPS, 2004. G. Manku, Balanced binary trees for ID management and load balance in distributed hash tables, in: Proceedings of PODC, 2004. M. Mitzenmacher, On the analysis of randomized load balancing schemes, in: Proceedings of SPAA, 1997. M. Nar, U. Wieder, Novel architectures for p2p applications: the continuous–discrete approach, in: Proceedings of ACM SPAA, 2003. A. Rao, K. Lakshminarayanan, et al., Load balancing in structured P2P systems, in: Proceedings of IPTPS, 2003. S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Shenker, A scalable content-addressable network, in: Proceedings of ACM SIGCOMM, 2001, pp. 329–350. S. Ratnasamy, M. Handley, R. Karp, S. Shenker, Topologically-aware overlay construction and server selection, in: Proceedings of INFOCOM, 2002. A. Rowstron, P. Druschel, Pastry: scalable, decentralized object location and routing for large-scale peer-to-peer systems, in: Proceedings of Middleware, 2001. H. Shen, C. Xu, Hash-based proximity clustering for load bancing in heterogeneous DHT networks, in: Proceedings of IPDPS, 2006. Shen, 2007, Locality-aware and churn-resilient load balancing algorithms in structured peer-to-peer networks, IEEE Trans. Parallel and Distributed Systems, 18, 849, 10.1109/TPDS.2007.1040 Shen, 2006, Cycloid: a scalable constant-degree p2p overlay network, Performance Evaluation, 63, 195, 10.1016/j.peva.2005.01.004 Stoica, 2003, Chord: a scalable peer-to-peer lookup protocol for Internet applications, IEEE/ACM Trans. Networking, 11, 17, 10.1109/TNET.2002.808407 M. Waldvogel, R. Rinaldi, Efficient topology-aware overlay network, in: Proceedings of HotNets-I, 2002. Z. Xu, M. Mahalingam, M. Karlsson, Turning heterogeneity into an advantage in overlay routing, in: Proceedings of INFOCOM, 2003. Z. Xu, C. Tang, Z. Zhang, Building topology-aware overlays using global soft-state, in: Proceedings of ICDCS, 2003. E. Zegura, K. Calvert, et al., How to model an Internetwork, in: Proceedings of INFOCOM, 1996. C. Zhang, A. Krishnamurthy, R.Y. Wang, Brushwood: distributed trees in peer-to-peer systems, in: Proceedings of IPTPS, 2005. B. Zhao, Y. Duan, L. Huang, A. Joseph, J. Kubiatowicz, Brocade: landmark routing on overlay networks, in: Proceedings of IPTPS, 2002. Zhao, 2004, Tapestry: an infrastructure for fault-tolerant wide-area location and routing, IEEE J. Select. Areas in Commun., 12, 41, 10.1109/JSAC.2003.818784 Zhu, 2005, Efficient proximity-aware load balancing for dht-based p2p systems, IEEE Trans. Parallel and Distributed Systems, 16, 10.1109/TPDS.2005.46