skip to main content
10.1145/1516241.1516259acmconferencesArticle/Chapter ViewAbstractPublication PagesicuimcConference Proceedingsconference-collections
research-article

Dynamic load balancing in RCAN content addressable network

Published: 15 February 2009 Publication History

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]
Boukhelef, D. and Kitagawa, H. 2008. Multi-ring Infrastructure for Content Addressable Networks, Proceedings of the 16th International Conference on Cooperative Information Systems (Monterrey, Mexico, November 12 - 14, 2008). CoopIS'08. Lecture Notes in Computer Science, vol. 5331. Springer Berlin, Heidelberg, 193--211.
[2]
Karger, D. R. and Ruhl, M. 2004. Simple efficient load balancing algorithms for peer-to-peer systems. In Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures (Barcelona, Spain, June 27 - 30, 2004). SPAA'04. ACM, New York, NY, 36--43.
[3]
Kleinberg, J. 2000. The small-world phenomenon: an algorithm perspective. In Proceedings of the Thirty-Second Annual ACM Symposium on theory of Computing (Portland, Oregon, United States, May 21 - 23, 2000). STOC '00. ACM, New York, NY, 163--170.
[4]
Manku, G. S., Bawa, M. and Raghavan, P. 2003. Symphony: distributed hashing in a small world. Proceedings of the 4th Conference on USENIX Symposium on Internet Technologies and Systems (USITS'03), pp.127--140.
[5]
Ratnasamy, S., Francis, P., Handley, M., Karp, R., and Schenker, S. 2001. A scalable content-addressable network. In Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (San Diego, California, United States). SIGCOMM '01. ACM, New York, NY, 161--172.
[6]
Rowstron, A. I. and Druschel, P. 2001. Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems. In Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg (Nov. 12 - 16, 2001). Lecture Notes in Computer Science, vol. 2218. Springer-Verlag, London, 329--350.
[7]
Sahin, O. D., Agrawal, D., and El Abbadi, A. 2005. Techniques for Efficient Routing and Load Balancing in Content-Addressable Networks. In Proceedings of the Fifth IEEE international Conference on Peer-To-Peer Computing (Aug. 31 -- Sep. 02, 2005). P2P. IEEE Computer Society, Washington, DC, 67--74.
[8]
Stoica, I., Morris, R., Liben-Nowell, D., Karger, D. R., Kaashoek, M. F., Dabek, F., and Balakrishnan, H. 2003. Chord: a scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Transactions on Networks 11, 1 (Feb. 2003), 17--32.
[9]
Sun, X. 2007. SCAN: a small-world structured p2p overlay for multi-dimensional queries. In Proceedings of the 16th international Conference on World Wide Web (Banff, Alberta, Canada, May 08 - 12, 2007). WWW '07. ACM, New York, NY, 1191--1192.
[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]
Surana, S., Godfrey, B., Lakshminarayanan, K., Karp, R., and Stoica, I. 2006. Load balancing in dynamic structured peer-to-peer systems. Performance Evaluation. 63, 3 (Mar. 2006), 217--240.
[12]
Kenthapadi, K. and Manku, G. S. 2005. Decentralized algorithms using both local and random probes for P2P load balancing. In Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures (Las Vegas, Nevada, USA, July 18-20, 2005). SPAA '05. ACM, New York, NY, 135--144.
[13]
Naor, M. and Wieder, U. 2007. Novel architectures for P2P applications: The continuous-discrete approach. ACM Transactions on Algorithms 3, 3 (Aug. 2007), 34.
[14]
Giakkoupis, G. and Hadzilacos, V. 2005. A scheme for load balancing in heterogenous distributed hash tables. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing (Las Vegas, NV, USA, July 17 - 20, 2005). PODC '05. ACM, New York, NY, 302--311.
[15]
Abraham, I., Awerbuch, B., Azar, Y., Bartal, Y., Malkhi, D., and Pavlov, E. 2003. A Generic Scheme for Building Overlay Networks in Adversarial Scenarios. In Proceedings of the 17th international Symposium on Parallel and Distributed Processing (April 22 - 26, 2003). IPDPS. IEEE Computer Society, Washington, DC, 40.2.
[16]
Manku, G. S. 2004. Balanced binary trees for ID management and load balance in distributed hash tables. In Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing (St. John's, Newfoundland, Canada, July 25 - 28, 2004). PODC '04. ACM, New York, NY, 197--205.

Recommendations

Reviews

Jingping Long

The peer-to-peer (P2P) diagram is gaining popularity in data sharing among large numbers of nodes. It can be viewed as a decentralized overlay network over the Internet. The basic idea is that every node in the network takes the same responsibility in locating, transferring, and storing shared data. There is no central authority-the nodes only keep information for a limited number of other nodes, typically their direct neighbors (logically, not necessarily physically). An obvious and important issue of the P2P diagram is how, in the absence of a central authority, to ensure the same responsibility ideal (at least roughly). In computer science language, this is how to ensure the load balance. Based on other researchers' efforts, Boukhelef and Kitagawa present some new ideas. Their study focuses on dynamically balancing the load in their previously proposed multi-ring content addressable network (RCAN). The basic idea of RCAN is to establish connections between distant nodes, besides the connections between neighbors. Like other P2P networks, RCAN has load balancing issues that need to be addressed. The main contribution of this paper is the proposal of three load sharing schemes that do not require a node to know any load information other than that of its neighbors. The authors provide simulation data to back their schemes. The simulations show that good load balancing is achievable. One drawback of the paper is that it doesn't clarify how long it might take, when using the proposed protocol, for heavily loaded nodes to unload their burden to lightly loaded nodes. Since the authors' protocol prohibits the use of any global load information, it is reasonable to argue that the protocol may take a longer time to cool imbalanced hot spots on the network. Another drawback is that the paper contains some spelling and grammatical errors. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ICUIMC '09: Proceedings of the 3rd International Conference on Ubiquitous Information Management and Communication
February 2009
704 pages
ISBN:9781605584058
DOI:10.1145/1516241
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 February 2009

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. P2P
  2. load balancing
  3. multi-ring content-addressable network

Qualifiers

  • Research-article

Conference

ICUIMC '09
Sponsor:

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 317
    Total Downloads
  • Downloads (Last 12 months)6
  • Downloads (Last 6 weeks)2
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media