Dynamic load balancing in RCAN content addressable network

ABSTRACT

RCAN [1] is a novel multi-ring content addressable peer-to-peer system. RCAN was proposed in the aim of improving the routing performance of CAN [4] overlays while minimizing the maintenance overhead during nodes churn in large networks. The key idea of RCAN is to equip each node with a few long-links towards some distant nodes. Long-links are clockwise directed and wrap around to form small rings along each dimension. The number of rings and their sizes self-adjust as nodes join and leave the system. RCAN is a pure P2P design, where all nodes assume the same responsibility. Unlike some existing P2P overlays, RCAN is self-organizing and does not assume any a-priori fixed limits for the network size or the routing state per node. Each node auto-adapts its routing state to cope with network changes.

In this work, we address the problem of load balancing in RCAN system. We propose fully decentralized mechanisms to cope with large scale data imbalance. Our methods extend the random join process [7,12] to enable a newly joining node to locate an existing node with a heavy load to share the load with. A new joining node selects one or more existing nodes at random, and then it chooses the heaviest node among them to share the load with. The heaviest node may also be located through a random walk starting from a randomly selected node. In opposition to [7], the proposed methods do not rely on any external index nor assume any global knowledge. All routing and load information is disseminated in the network through links established between immediate and distant neighbors, incurring thus no extra overhead. On another side, the number of probed nodes is logarithmic [1] which enables to achieve constant load imbalance less than or equal to 8 [12, 13, 16]. A combination of the two methods would achieve much smaller load imbalance that is less than or equal to 4 [12]. We also studied the impact of number of entry points to the systems on the load imbalance factor. To the best of our knowledge we are the first to address this problem. We have also conducted an extensive experimental study using uniform and non-uniform data distributions to demonstrate the effectiveness and the scalability of our proposals.

REFERENCES

• 1: Djelloul Boukhelef , Hiroyuki Kitagawa, Multi-ring Infrastructure for Content Addressable Networks, Proceedings of the OTM 2008 Confederated International Conferences, CoopIS, DOA, GADA, IS, and ODBASE 2008. Part I on On the Move to Meaningful Internet Systems:, November 09-14, 2008, Monterrey, Mexico [doi>10.1007/978-3-540-88871-0_15]
• 2: David R. Karger , Matthias Ruhl, Simple efficient load balancing algorithms for peer-to-peer systems, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007919]
• 3: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 4: Gurmeet Singh Manku , Mayank Bawa , Prabhakar Raghavan, Symphony: distributed hashing in a small world, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.10-10, March 26-28, 2003, Seattle, WA
• 5: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 6: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 7: Ozgur D. Sahin , Divyakant Agrawal , Amr El Abbadi, Techniques for Efficient Routing and Load Balancing in Content-Addressable Networks, Proceedings of the Fifth IEEE International Conference on Peer-to-Peer Computing, p.67-74, August 31-September 02, 2005 [doi>10.1109/P2P.2005.37]
• 8: Ion Stoica , Robert Morris , David Liben-Nowell , David R. Karger , M. Frans Kaashoek , Frank Dabek , Hari Balakrishnan, Chord: a scalable peer-to-peer lookup protocol for internet applications, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.17-32, February 2003 [doi>10.1109/TNET.2002.808407]
• 9: Xiaoping Sun, SCAN: a small-world structured p2p overlay for multi-dimensional queries, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242760]
• 10: Xu, Z. and Zhang, Z.2002. Building low-maintenance expressways for P2P systems. Technical Report HPL-2002-41 41, HP Laboratories, Palo Alto.
• 11: Sonesh Surana , Brighten Godfrey , Karthik Lakshminarayanan , Richard Karp , Ion Stoica, Load balancing in dynamic structured peer-to-peer systems, Performance Evaluation, v.63 n.3, p.217-240, March 2006 [doi>10.1016/j.peva.2005.01.003]
• 12: Krishnaram Kenthapadi , Gurmeet Singh Manku, Decentralized algorithms using both local and random probes for P2P load balancing, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073990]
• 13: Moni Naor , Udi Wieder, Novel architectures for P2P applications: The continuous-discrete approach, ACM Transactions on Algorithms (TALG), v.3 n.3, p.34-es, August 2007 [doi>10.1145/1273340.1273350]
• 14: George Giakkoupis , Vassos Hadzilacos, A scheme for load balancing in heterogenous distributed hash tables, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073872]
• 15: Ittai Abraham , Baruch Awerbuch , Yossi Azar , Yair Bartal , Dahlia Malkhi , Elan Pavlov, A Generic Scheme for Building Overlay Networks in Adversarial Scenarios, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.40.2, April 22-26, 2003
• 16: Gurmeet Singh Manku, Balanced binary trees for ID management and load balance in distributed hash tables, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011797]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Distributed data structures

General Terms:
Algorithms, Performance

Keywords:
P2P, load balancing, multi-ring content-addressable network