skip to main content
article

Node isolation model and age-based neighbor selection in unstructured P2P networks

Published: 01 February 2009 Publication History

Abstract

Previous analytical studies of unstructured P2P resilience have assumed exponential user lifetimes and only con-sidered age-independent neighbor replacement. In this paper, we overcome these limitations by introducing a general node-isolation model for heavy-tailed user lifetimes and arbitrary neighbor-se-lection algorithms. Using this model, we analyze two age-biased neighbor-selection strategies and show that they significantly improve the residual lifetimes of chosen users, which dramatically reduces the probability of user isolation and graph partitioning compared with uniform selection of neighbors. In fact, the second strategy based on random walks on age-proportional graphs demonstrates that, for lifetimes with infinite variance, the system monotonically increases its resilience as its age and size grow. Specifically, we show that the probability of isolation converges to zero as these two metrics tend to infinity. We finish the paper with simulations in finite-size graphs that demonstrate the effect of this result in practice.

References

[1]
F. E. Bustamante and Y. Qiao, "Friendships that last: Peer lifespan and its role in P2P protocols," in Proc. Int. Workshop Web Content Caching Distribution, Sep. 2003, pp. 233-246.
[2]
M. Castro, M. Costa, and A. Rowstron, "Performance and depend-ability of structured peer-to-peer overlays," in Proc. DSN, Jun. 2004, pp. 9-18.
[3]
Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S. Shenker, "Making Gnutella-like P2P systems scalable," in Proc. ACM SIG-COMM, Aug. 2003, pp. 407-418.
[4]
B.-G. Chun, B. Zhao, and J. Kubiatowicz, "Impact of neighbor se-lection on performance and resilience of structured P2P networks," in Proc. IPTPS, Feb. 2005, pp. 264-274.
[5]
E. B. Dynkin, "Some limit theorems for sums of independent random variables with infinite mathematical expectations," Sel. Transl. Math. Statist. Probabil., vol. 1, pp. 171-189, 1961.
[6]
H. Exton, Handbook of Hypergeometric Integrals: Theory, Applica-tions, Tables, Computer Programs. Chichester, U.K.: Ellis Horwood, 1978.
[7]
A. Feldmann and W. Whitt, "Fitting mixtures of exponentials to long-tailed distributions to analyze network performance models," Perform. Eval., vol. 31, no. 3-4, pp. 245-279, Jan. 1998.
[8]
W. Feller, An Introduction to Probability Theory and Its Applications, Volume 2. New York: Wiley, 1966.
[9]
C. Gkantsidis, M. Mihail, and A. Saberi, "Random walks in peer-to-peer networks," in Proc. IEEE INFOCOM, Mar. 2004, pp. 120-130.
[10]
P. B. Godfrey, S. Shenker, and I. Stoica, "Minimizing churn in dis-tributed systems," in Proc. ACM SIGCOMM, Sep. 2006, pp. 147-158.
[11]
K. Gummadi, R. Gummadi, S. Gribble, S. Ratnasamy, S. Shenker, and I. Stoica, "The impact of DHT routing geometry on resilience and prox-imity," in Proc. ACM SIGCOMM, Aug. 2003, pp. 381-394.
[12]
T. Hettmansperger and M. Keenan, "Tailweight, statistical inference, and families of distributions--A brief survey," in Statist. Distrib. Sci-entif. Work, G. P. Patil, S. Kotz, and J. K. Ord, Eds.: Kluwer, 1980, vol. 1, pp. 161-172.
[13]
M. F. Kaashoek and D. Karger, "Koorde: A simple degree-optimal dis-tributed hash table," in Proc. IPTPS, Feb. 2003, pp. 98-107.
[14]
M. Kijima, Markov Processes for Stochastic Modeling. London, U.K.: Chapman & Hall, 1997.
[15]
S. Krishnamurthy, S. El-Ansary, E. Aurell, and S. Haridi, "A statistical theory of chord under churn," in Proc. IPTPS, Feb. 2005, pp. 93-103.
[16]
S. S. Lam and H. Liu, "Failure recovery for structured P2P networks: Protocol design and performance evaluation," in Proc. ACM SIGMET-RICS, Jun. 2004, pp. 199-210.
[17]
J. Ledlie, J. Shneidman, M. Amis, and M. Seltzer, Reliability-and Capacity-Based Selection in Distributed Hash Tables Harvard Univ., Dept. Comput. Sci., Sep. 2003, Tech. Rep.
[18]
D. Leonard, V. Rai, and D. Loguinov, "On lifetime-based node failure and stochastic resilience of decentralized peer-to-peer networks," in Proc. ACM SIGMETRICS, Jun. 2005, pp. 26-37.
[19]
D. Leonard, Z. Yao, X. Wang, and D. Loguinov, "On static and dynamic partitioning behavior of large-scale networks," in Proc. IEEE ICNP, Nov. 2005, pp. 345-357.
[20]
J. Li, J. Stribling, T. M. Gil, R. Morris, and M. F. Kaashoek, "Com-paring the performance of distributed hash tables under churn," in Proc. IPTPS, Feb. 2004, pp. 87-99.
[21]
J. Li, J. Stribling, R. Morris, and M. F. Kaashoek, "Bandwidth-effi-cient management of DHT routing tables," in Proc. USENIX NSDI, May 2005, pp. 1-11.
[22]
D. Liben-Nowell, H. Balakrishnan, and D. Karger, "Analysis of the evolution of the peer-to-peer systems," in Proc. ACM PODC, Jul. 2002, pp. 233-242.
[23]
L. Lovász, "Random Walks on graphs: A survey," in Combinatorics, Paul Erdös is Eighty, D. Miklós, V. T. Sós, and T. Szönyi, Eds. Bu-dapest, Hungary: János Bolyai Math. Soc., 1996, vol. 2, pp. 353-398.
[24]
L. Massoulié, A.-M. Kermarrec, and A. Ganesh, "Network awareness and failure resilience in self-organising overlay networks," in Proc. IEEE SRDS, Oct. 2003, pp. 47-55.
[25]
P. Maymounkov and D. Mazieres, "Kademlia: A peer-to-peer informa-tion system based on the XOR metric," in Proc. IPTPS, Mar. 2002, pp. 53-65.
[26]
C. D. Meyer, Matrix Analysis and Applied Linear Algebra. Philadel-phia, PA: SIAM, 2000.
[27]
G. Pandurangan, P. Raghavan, and E. Upfal, "Building low-diameter peer-to-peer networks," IEEE J. Sel. Areas Commun., vol. 21, no. 6, pp. 995-1002, Aug. 2003.
[28]
C. G. Plaxton, R. Rajaraman, and A. W. Richa, "Accessing nearby copies of replicated objects in a distributed environment," in Proc. ACM SPAA, 1997, pp. 311-320.
[29]
S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, "A scalable content-addressable network," in Proc. ACM SIGCOMM, Aug. 2001, pp. 161-172.
[30]
S. Ratnasamy, M. Handley, R. Karp, and S. Shenker, "Topologically-aware overlay construction and server selection," in Proc. IEEE IN-FOCOM, Jun. 2002, pp. 1190-1199.
[31]
S. Resnick, Adventures in Stochastic Processes.: Birkhäuser, 2002.
[32]
S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz, "Handling churn in a DHT," in Proc. USENIX Ann. Tech. Conf., Jun. 2004, pp. 127-140.
[33]
A. Rowstron and P. Druschel, "Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems," in Proc. IFIP/ACM Int. Conf. Distrib. Syst. Platforms (Middleware), Nov. 2001, pp. 329-350.
[34]
D. Rubenstein and S. Sahu, "Can unstructured P2P protocols survive flash crowds," IEEE/ACM Trans. Netw., vol. 13, no. 3, pp. 501-512, Apr. 2005.
[35]
K. Sripanidkulchai, A. Ganjam, B. Maggs, and H. Zhang, "The fea-sibility of supporting large-scale live streaming applications with dy-namic application end-points," in Proc. ACM SIGCOMM, Aug. 2004, pp. 107-120.
[36]
M. Srivatsa, B. Gedik, and L. Liu, "Large scaling unstructured peer-to-peer networks with heterogeneity-aware topology and routing," IEEE Trans. Parallel Distrib. Syst., vol. 17, no. 11, pp. 1277-1293, Nov. 2006.
[37]
I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, "Chord: A scalable peer-to-peer lookup service for internet applica-tions," in Proc. ACM SIGCOMM, Aug. 2001, pp. 149-160.
[38]
M. S. Taqqu, W. Willinger, and R. Sherman, "Proof of a fundamental result in self-similar traffic modeling," ACM Comput. Commun. Rev., vol. 27, no. 2, pp. 5-23, Apr. 1997.
[39]
V. Venkataraman, P. Francisy, and J. Calandrino, "Chunkyspread: Multitree unstructured peer-to-peer multicast," in Proc. IPTPS, Feb. 2006.
[40]
V. Vishnumurthy and P. Francis, "On Heterogeneous overlay construc-tion and random node selection in unstructured P2P networks," in Proc. IEEE INFOCOM, Apr. 2006.
[41]
X. Wang, Z. Yao, and D. Loguinov, "Residual-based measurement of peer and link lifetimes in Gnutella networks," in Proc. IEEE INFOCOM, May 2007, pp. 391-399.
[42]
R. W. Wolff, Stochastic Modeling and the Theory of Queues. Engle-wood Cliffs, NJ: Prentice-Hall, 1989.
[43]
Z. Yao, D. Leonard, X. Wang, and D. Loguinov, "Modeling heteroge-neous user churn and local resilience of unstructured P2P networks," in Proc. IEEE ICNP, Nov. 2006, pp. 32-41.
[44]
H. Zhang, A. Goal, and R. Govindan, "Incrementally improving lookup latency in distributed hash table systems," in Proc. ACM SIGMETRICS, Jun. 2003, pp. 114-125.
[45]
B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. Kubiatowicz, "Tapestry: A resilient global-scale overlay for service de-ployment," IEEE J. Sel. Areas Commun., vol. 22, no. 1, pp. 41-53, Jan. 2004.
[46]
M. Zhong, K. Shen, and J. Seiferas, "Non-uniform random member-ship management in peer-to-peer networks," in Proc. IEEE INFOCOM, Mar. 2005, pp. 1151-1161.
[47]
D. Zhou, J. Huang, and B. Schölkopf, "Learning from labeled and un-labeled data on a directed graph," in Proc. ICML 2005, Aug. 2005, pp. 1036-1043.

Cited By

View all
  • (2017)A Survey on Network Methodologies for Real-Time Analytics of Massive IoT Data and Open Research IssuesIEEE Communications Surveys & Tutorials10.1109/COMST.2017.269446919:3(1457-1477)Online publication date: 21-Aug-2017
  • (2015)Unstructured P2P link lifetimes reduxIEEE/ACM Transactions on Networking10.1109/TNET.2014.230615323:3(755-767)Online publication date: 1-Jun-2015
  • (2013)P2P group management systemsACM Computing Surveys10.1145/2431211.243121945:2(1-25)Online publication date: 12-Mar-2013

Recommendations

Reviews

Ruay-Shiung Chang

A peer-to-peer (P2P) network allows users to share files anonymously and easily. It does not need a central server, nor does it need any governance. Users-nodes in a P2P network-join or leave the network randomly. A node searches for a file by querying other peers. Depending on how the connections of peers are built and maintained, a P2P network can be either unstructured or structured. In an unstructured P2P network, links between peers are formed arbitrarily. If the links you choose connect to nodes that disappear suddenly, you can get disconnected easily. Therefore, it is reasonable to choose neighbors that are assumed to have a long lifetime. This paper furthers the research by introducing a general node-isolation model for heavy-tailed user lifetimes and arbitrary neighbor-selection algorithms. Using this model, [the authors] analyze two age-biased neighbor-selection strategies and show that they significantly improve the residual lifetimes of chosen users. This will lead to better-connected peers. This paper mostly contains mathematical analysis. It would have been better if the authors had provided a step-by-step procedure to increase the applicability of this research. Apart from that, the paper is generally well written and shows the good quality of the journal in which it was published. 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 IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 17, Issue 1
February 2009
346 pages

Publisher

IEEE Press

Publication History

Published: 01 February 2009
Revised: 11 September 2007
Received: 01 February 2007
Published in TON Volume 17, Issue 1

Author Tags

  1. age-based selection
  2. heavy-tailed lifetimes
  3. node isolation
  4. peer-to-peer networks
  5. user churn

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 12 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2017)A Survey on Network Methodologies for Real-Time Analytics of Massive IoT Data and Open Research IssuesIEEE Communications Surveys & Tutorials10.1109/COMST.2017.269446919:3(1457-1477)Online publication date: 21-Aug-2017
  • (2015)Unstructured P2P link lifetimes reduxIEEE/ACM Transactions on Networking10.1109/TNET.2014.230615323:3(755-767)Online publication date: 1-Jun-2015
  • (2013)P2P group management systemsACM Computing Surveys10.1145/2431211.243121945:2(1-25)Online publication date: 12-Mar-2013

View Options

Login options

Full Access

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