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

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: Fabian E. Bustamante , Yi Qiao, Friendships that last: peer lifespan and its role in P2P protocols, Web content caching and distribution: proceedings of the 8th international workshop, Kluwer Academic Publishers, Norwell, MA, 2004
• 2: Miguel Castro , Manuel Costa , Antony Rowstron, Performance and Dependability of Structured Peer-to-Peer Overlays, Proceedings of the 2004 International Conference on Dependable Systems and Networks, p.9, June 28-July 01, 2004
• 3: Yatin Chawathe , Sylvia Ratnasamy , Lee Breslau , Nick Lanham , Scott Shenker, Making gnutella-like P2P systems scalable, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.864000]
• 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: Anja Feldmann , Ward Whitt, Fitting mixtures of exponentials to long-tail distributions to analyze network performance models, Performance Evaluation, v.31 n.3-4, p.245-279, Jan. 1998 [doi>10.1016/S0166-5316(97)00003-5]
• 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. Brighten Godfrey , Scott Shenker , Ion Stoica, Minimizing churn in distributed systems, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 11: K. Gummadi , R. Gummadi , S. Gribble , S. Ratnasamy , S. Shenker , I. Stoica, The impact of DHT routing geometry on resilience and proximity, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863998]
• 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: Simon S. Lam , Huaiyu Liu, Failure recovery for structured P2P networks: protocol design and performance evaluation, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 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: Derek Leonard , Vivek Rai , Dmitri Loguinov, On lifetime-based node failure and stochastic resilience of decentralized peer-to-peer networks, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 19: Derek Leonard , Zhongmei Yao , Xiaoming Wang , Dmitri Loguinov, On Static and Dynamic Partitioning Behavior of Large-Scale Networks, Proceedings of the 13TH IEEE International Conference on Network Protocols, p.345-357, November 06-09, 2005 [doi>10.1109/ICNP.2005.27]
• 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: Jinyang Li , Jeremy Stribling , Robert Morris , M. Frans Kaashoek, Bandwidth-efficient management of DHT routing tables, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.99-114, May 02-04, 2005
• 22: David Liben-Nowell , Hari Balakrishnan , David Karger, Analysis of the evolution of peer-to-peer systems, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571863]
• 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: Petar Maymounkov , David Mazières, Kademlia: A Peer-to-Peer Information System Based on the XOR Metric, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.53-65, March 07-08, 2002
• 26: Carl D. Meyer, Matrix analysis and applied linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 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. Greg Plaxton , Rajmohan Rajaraman , Andréa W. Richa, Accessing nearby copies of replicated objects in a distributed environment, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.311-320, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258523]
• 29: 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
• 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: Sidney I. Resnick, Adventures in stochastic processes, Birkhauser Verlag, Basel, Switzerland, 1992
• 32: Sean Rhea , Dennis Geels , Timothy Roscoe , John Kubiatowicz, Handling churn in a DHT, Proceedings of the annual conference on USENIX Annual Technical Conference, p.10-10, June 27-July 02, 2004, Boston, MA
• 33: 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
• 34: Dan Rubenstein , Sambit Sahu, Can unstructured P2P protocols survive flash crowds?, IEEE/ACM Transactions on Networking (TON), v.13 n.3, p.501-512, June 2005 [doi>10.1109/TNET.2005.845530]
• 35: Kunwadee Sripanidkulchai , Aditya Ganjam , Bruce Maggs , Hui Zhang, The feasibility of supporting large-scale live streaming applications with dynamic application end-points, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 36: Mudhakar Srivatsa , Bugra Gedik , Ling Liu, Large Scaling Unstructured Peer-to-Peer Networks with Heterogeneity-Aware Topology and Routing, IEEE Transactions on Parallel and Distributed Systems, v.17 n.11, p.1277-1293, November 2006 [doi>10.1109/TPDS.2006.158]
• 37: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 38: Murad S. Taqqu , Walter Willinger , Robert Sherman, Proof of a fundamental result in self-similar traffic modeling, ACM SIGCOMM Computer Communication Review, v.27 n.2, p.5-23, Apr. 1997 [doi>10.1145/263876.263879]
• 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: Zhongmei Yao , Derek Leonard , Xiaoming Wang , Dmitri Loguinov, Modeling Heterogeneous User Churn and Local Resilience of Unstructured P2P Networks, Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, p.32-41, November 12-15, 2006 [doi>10.1109/ICNP.2006.320196]
• 44: Hui Zhang , Ashish Goel , Ramesh Govindan, Incrementally improving lookup latency in distributed hash table systems, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 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: Dengyong Zhou , Jiayuan Huang , Bernhard Schölkopf, Learning from labeled and unlabeled data on a directed graph, Proceedings of the 22nd international conference on Machine learning, p.1036-1043, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102482]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms; Network problems
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Management, Performance

Keywords:
age-based selection, heavy-tailed lifetimes, node isolation, peer-to-peer networks, user churn