More Web Proxy on the site http://driver.im/

article

On zone-balancing of peer-to-peer networks: analysis of random node join

Authors:

Dmitri LoguinovAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 32, Issue 1

Pages 211 - 222

https://doi.org/10.1145/1012888.1005713

Published: 01 June 2004 Publication History

Abstract

Balancing peer-to-peer graphs, including zone-size distributions, has recently become an important topic of peer-to-peer (P2P) research [1], [2], [6], [19], [31], [36]. To bring analytical understanding into the various peer-join mechanisms, we study how zone-balancing decisions made during the initial sampling of the peer space affect the resulting zone sizes and derive several asymptotic results for the maximum and minimum zone sizes that hold with high probability.

References

[1]

K. Aberer, A. Datta, and M. Hauswirth, "The Quest for Balancing Peer Load in Structured Peer-to-Peer Systems," EPFL Technical Report, 2003.

[2]

M. Adler, E. Halperin, R.M. Karp, and V.V. Vazirani, "A Stochastic Process on the Hypercube with Applications to Peer-to-Peer Networks," ACM STOC, June 2003.

Digital Library

[3]

J. Aspnes, Z. Diamadi, and G. Shah, "Fault-Tolerant Routing in Peer-to-Peer Systems," ACM PODC, July 2002.

Digital Library

[4]

Y. Azar, A. Broder, A. Karlin, and E. Upfal, "Balanced Allocations," SIAM Journal on Computing, vol. 29, July 1999.

Digital Library

[5]

A. Barabasi, R. Albert, and H. Jeong, "Mean-Field Theory for Scale-Free Random Networks," Physica A 272, 1999.

[6]

J. Byers, J. Considine, and M. Mitzenmacher, "Geometric Generalizations of the Power of Two Choices," BU Technical Report, February 2003.

[7]

J. Byers, J. Considine, and M. Mitzenmacher, "Simple Load Balancing for Distributed Hash Tables," IPTPS, February 2003.

[8]

Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S. Shenker, "Making Gnutella-like P2P Systems Scalable," ACM SIGCOMM, August 2003.

Digital Library

[9]

R.M. Corless, G.H. Gonnet, D.E.G. Hare, D.J. Jeffrey, and D.E. Knuth, "On the Lambert W Function," Advances in Computational Mathematics, vol. 5, 1996.

[10]

D.A. Darling, "On a Class of Problems Related to the Random Division of an Interval," Annals of Math. Statistics, vol. 24, June 1953.

[11]

M.H. DeGroot, Probability and Statistics. Addison-Wesley, 2001.

[12]

L. Devroye, "Law of the Iterated Logarithm for Order Statistics of Uniform Spacings," Annals of Probability, vol. 9, no. 5, 1981.

[13]

L. Devroye, "A Log-Log Law for Maximal Uniform Spacings," Annals of Probability, vol. 10, no. 35, 1982.

[14]

S.N. Dorogotsev and J. Mendes, Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford University Press, 2003.

Digital Library

[15]

P. Fraigniaud and P. Gauron, "The Content-Addressable Network D2B," Technical Report 1349, 2003.

[16]

P. Gupta and P.R. Kumar, "The Capacity of Wireless Networks," IEEE Transactions on Information Theory, March 2000.

[17]

F. Kaashoek and D. Karger, "Koorde: A Simple Degree-optimal Hash Table," IPTPS, February 2003.

[18]

D. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin, and R. Panigrahy, "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web," ACM STOC, May 1997.

Digital Library

[19]

D. Karger and M. Ruhl, "New Algorithms for Load Balancing in Peer-to-Peer Systems," IRIS Student Workshop, August 2003.

[20]

R.M. Karp, M. Luby, and F. Meyer auf~der Heide, "Efficient PRAM Simulation on a Distributed Memory Machine," ACM STOC, May 1992.

Digital Library

[21]

C. Knessl and W. Szpankowski, "Limit Laws for Heights in Generalized Tries and Patricia Tries," LATIN, 2000.

Digital Library

[22]

T.G. Kurtz, "Solutions of Ordinary Differential Equations as Limits of Pure Jump Markov Processes," Journal of Applied Probability, vol. 7, 1970.

[23]

C. Law and K.-Y. Siu, "Distributed Construction of Random Expander Graphs," IEEE INFOCOM, March 2003.

[24]

D. Liben-Nowell, H. Balakrishnan, and D. Karger, "Analysis of the Evolution of Peer-to-Peer Networks," ACM PODC, July 2002.

Digital Library

[25]

D. Loguinov, A. Kumar, V. Rai, and S. Ganesh, "Graph-Theoretic Analysis of Structured Peer-to-Peer Systems: Routing Distances and Fault Resilience," ACM SIGCOMM, August 2003.

Digital Library

[26]

W. Magnus, F. Oberhettinger, and R.P. Soni, Formulas and Theorems for the Special Functions of Mathematical Physics. Springer-Verlag, 1966.

[27]

D. Malkhi, M. Naor, and D. Ratajczak, "Viceroy: A Scalable and Dynamic Emulation of the Butterfly," ACM PODC, July 2002.

Digital Library

[28]

M. Mitzenmacher, "Load Balancing and Density Dependent Jump Markov Processes," IEEE FOCS, October 1996.

Digital Library

[29]

M. Mitzenmacher, "Studying Balanced Allocations with Differential Equations," Combinatorics, Probability, and Computing, vol. 8, 1999.

Digital Library

[30]

M. Mitzenmacher, "The Power of Two Choices in Randomized Load Balancing," Ph.D. thesis, 1996.

Digital Library

[31]

A. Mondal, K. Goda, and M. Kitsuregawa, "Effective Load-Balancing of Peer-to-peer systems," Data Engineering Workshop, March 2003.

[32]

A. Montresor, H. Meling, and O. Babaoglu, "Messor: Load-Balancing through a Swarm of Autonomous Agents," International Workshop on Agents and Peer-to-Peer Computing, 2002.

Digital Library

[33]

M. Naor and U. Wieder, "Novel Architectures for P2P Applications: the Continuous-Discrete Approach," ACM SPAA, June 2003.

Digital Library

[34]

A. Rao, K. Lakshminarayanan, S. Surana, R. Karp, and I. Stoica, "Load Balancing in Structured P2P Systems," IPTPS, February 2003.

[35]

S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, "A Scalable Content-Addressable Network," ACM SIGCOMM, August 2001.

Digital Library

[36]

M. Roussopoulos and M. Baker, "Practical Load Balancing for Content Requests in Peer-to-Peer Networks," Stanford University Technical Report, January 2003.

[37]

A. Rowstron and P. Druschel, "Pastry: Scalable, Decentralized Object Location and Routing for Large-Scale Peer-to-Peer Systems," IFIP/ACM International Conference on Distributed Systems Platforms, November 2001.

Digital Library

[38]

I. Stoica, R. Morris, D. Karger, M.F. Kaashoek, and H. Balarkishnan, "Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications," ACM SIGCOMM, August 2001.

Digital Library

[39]

W. Szpankowski, "Patricia Trees Revisited Again," Journal of the ACM, vol. 37, 1990.

Digital Library

[40]

B. Vocking, "How Asymmetry Helps Load Balancing," IEEE Symposium on Foundations of Computer Science, 1999.

Digital Library

[41]

X. Wang, Y. Zhang, X. Li, and D. Loguinov, "On Zone-Balancing of Peer-to-Peer Networks: Analysis of Random Node Join (extended version)," Texas A&M Technical Report, June 2004.

Digital Library

[42]

J. Xu, A. Kumar, and X. Yu, "On the Fundamental Tradeoffs between Routing Table Size and Network Diameter in Peer-to-Peer Networks," IEEE JSAC, vol. 22, no. 1, January 2004.

Digital Library

[43]

B.Y. Zhao, J.D. Kubiatowicz, and A. Joseph, "Tapestry: An Infrastructure for Fault-Tolerant Wide-Area Location and Routing," UC Berkeley Technical Report, April 2001.

Digital Library

[44]

Y. Zhu and Y. Hu, "Efficient, Proximity-Aware Load Balancing for Structured Peer-to-Peer Systems," International Conference on Peer-to-Peer Computing, September 2003.

Digital Library

[45]

S.Q. Zhuang, B.Y. Zhao, and A.D. Joseph, "Bayeux: An Architecture for Scalable and Fault-Tolerant Wide-Area Data Dissemination," ACM NOSSDAV, June 2001.

Digital Library

Cited By

Rosas EHidalgo NMarin MGil-Costa V(2014)Web search results caching service for structured P2P networksFuture Generation Computer Systems10.5555/2747903.274817630:C(254-264)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.5555/2747903.2748176
Rosas EHidalgo NMarin MGil-Costa V(2014)Web search results caching service for structured P2P networksFuture Generation Computer Systems10.1016/j.future.2013.06.01830(254-264)Online publication date: Jan-2014
https://doi.org/10.1016/j.future.2013.06.018
Wang XLoguinov D(2007)Load-balancing performance of consistent hashingIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2007.89388115:4(892-905)Online publication date: 1-Aug-2007
https://dl.acm.org/doi/10.1109/TNET.2007.893881
Show More Cited By

Index Terms

On zone-balancing of peer-to-peer networks: analysis of random node join
1. Networks
  1. Network protocols

Recommendations

On zone-balancing of peer-to-peer networks: analysis of random node join
SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systems

Balancing peer-to-peer graphs, including zone-size distributions, has recently become an important topic of peer-to-peer (P2P) research [1], [2], [6], [19], [31], [36]. To bring analytical understanding into the various peer-join mechanisms, we study ...
Locality-Aware and Churn-Resilient Load-Balancing Algorithms in Structured Peer-to-Peer Networks

Structured peer-to-peer overlay networks, like distributed hash tables (DHTs), map data items to the network based on a consistent hashing function. Such mapping for data distribution has an inherent load balance problem. Data redistribution algorithms ...
Understanding churn in peer-to-peer networks
IMC '06: Proceedings of the 6th ACM SIGCOMM conference on Internet measurement

The dynamics of peer participation, or churn, are an inherent property of Peer-to-Peer (P2P) systems and critical for design and evaluation. Accurately characterizing churn requires precise and unbiased information about the arrival and departure of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 32, Issue 1

June 2004

432 pages

ISSN:0163-5999

DOI:10.1145/1012888

Issue’s Table of Contents

SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systems
June 2004
450 pages
ISBN:1581138733
DOI:10.1145/1005686
General Chair:
E. G. Coffman
Columbia University
,
Program Chairs:
Zhen Liu
IBM Research
,
Arif Merchant
HP Labs

Copyright © 2004 ACM.

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2004

Published in SIGMETRICS Volume 32, Issue 1

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
830
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rosas EHidalgo NMarin MGil-Costa V(2014)Web search results caching service for structured P2P networksFuture Generation Computer Systems10.5555/2747903.274817630:C(254-264)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.5555/2747903.2748176
Rosas EHidalgo NMarin MGil-Costa V(2014)Web search results caching service for structured P2P networksFuture Generation Computer Systems10.1016/j.future.2013.06.01830(254-264)Online publication date: Jan-2014
https://doi.org/10.1016/j.future.2013.06.018
Wang XLoguinov D(2007)Load-balancing performance of consistent hashingIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2007.89388115:4(892-905)Online publication date: 1-Aug-2007
https://dl.acm.org/doi/10.1109/TNET.2007.893881
Le VBabin GKropf P(2006)BALLS: A structured peer-to-peer system with integrated load balancingBALLS : Un Système Pair-à-Pair Structuré Avec L’Équilibrage de Charge Intégréannals of telecommunications - annales des télécommunications10.1007/BF0321989661:11-12(1229-1281)Online publication date: Dec-2006
https://doi.org/10.1007/BF03219896
Loguinov DCasas JWang X(2005)Graph-theoretic analysis of structured peer-to-peer systemsIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2005.85707213:5(1107-1120)Online publication date: 1-Oct-2005
https://dl.acm.org/doi/10.1109/TNET.2005.857072
Ferretti S(2013)Shaping opportunistic networksComputer Communications10.1016/j.comcom.2012.12.00636:5(481-503)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1016/j.comcom.2012.12.006
Yao ZLoguinov D(2011)Analysis of Link Lifetimes and Neighbor Selection in Switching DHTsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2011.10122:11(1834-1841)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1109/TPDS.2011.101
Pitoura TTriantafillou P(2009)Distribution fairness in Internet-scale networksACM Transactions on Internet Technology10.1145/1592446.15924509:4(1-36)Online publication date: 14-Oct-2009
https://dl.acm.org/doi/10.1145/1592446.1592450
Cichon JCichon KKobylanski P(2009)Node Evaluation in the Chord P2P SystemsProceedings of the 2009 Fourth International Conference on Dependability of Computer Systems10.1109/DepCoS-RELCOMEX.2009.32(168-175)Online publication date: 30-Jun-2009
https://dl.acm.org/doi/10.1109/DepCoS-RELCOMEX.2009.32
Chen CTsai K(2008)The Server Reassignment Problem for Load Balancing in Structured P2P SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2007.7073519:2(234-246)Online publication date: 1-Feb-2008
https://dl.acm.org/doi/10.1109/TPDS.2007.70735
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents