Random walk based node sampling in self-organizing networks

ABSTRACT

Random walk is a means of network node sampling that requires little index maintenance and can function on almost all connected network topologies. With careful guidance, node samples following a desired probability distribution can be generated with the only requirement that the sampling probabilities of each visited node and its direct neighbors are known at each walk step. This paper describes a broad range of network applications that can benefit from such guided random walks in dynamic and decentralized settings. This paper also examines several key issues for implementing random walks in self-organizing networks, including the convergence time of random walks, impact of dynamic network changes and particularly resulted walker losses, and the difficulty of pacing walk steps without synchronized clocks between network nodes. Our result suggests that with proper management, these issues do not cause significant problems under many realistic network environments.

REFERENCES

• 1: L. Adamic, B. Huberman, R. Lukose, and A. Puniyani. Search in Power Law Networks. Physical Review, (64):46135--46143, 2001.
• 2: A. Barabási and R. Albert. Emergence of Scaling in Random Networks. Science, 286:509--512, 1999.
• 3: Ashwin R. Bharambe , Mukesh Agrawal , Srinivasan Seshan, Mercury: supporting scalable multi-attribute range queries, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 4: B. Bollobás. Random Graphs. Academic Press, London, UK, 1985.
• 5: Bélaa Bollobás , Oliver Riordan, The Diameter of a Scale-Free Random Graph, Combinatorica, v.24 n.1, p.5-34, January 2004 [doi>10.1007/s00493-004-0002-2]
• 6: Béla Bollobás , Oliver Riordan , Joel Spencer , Gábor Tusnády, The degree sequence of a scale-free random graph process, Random Structures & Algorithms, v.18 n.3, p.279-290, May 2001 [doi>10.1002/rsa.1009 ]
• 7: Edith Cohen , Scott Shenker, Replication strategies in unstructured peer-to-peer networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 8: B. F. Cooper. Quickly Routing Searches Without Having to Move Content. In Proc. of the 4th International Workshop on Peer-to-Peer Systems (IPTPS), Ithaca, NY, February 2005.
• 9: W. Doeblin. Exposé de la théorie des chaînes simples constantes de Markov á un nombre fini d'états. Mathématique de l'Union Interbalkanique, 2:77--105, 1938.
• 10: C. Gkantsidis, M. Mihail, and A. Saberi. Random Walks in Peer-to-peer Networks. In Proc. of the IEEE INFOCOM, pages 120--130, Hong Kong, China, March 2004.
• 11: C. Gkantsidis, M. Mihail, and A. Saberi. Hybrid Search Schemes for Unstructured Peer-to-peer Networks. In Proc. of the IEEE INFOCOM, pages 1526--1537, Miami, FL, March 2005.
• 12: W. K. Hastings. Monte Carlo Sampling Methods Using Markov Chains and Their Applications. Biometrika, 57:97--109, 1970.
• 13: 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]
• 14: R. Karp , C. Schindelhauer , S. Shenker , B. Vocking, Randomized rumor spreading, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.565, November 12-14, 2000
• 15: David Kempe , Jon Kleinberg , Alan Demers, Spatial gossip and resource location protocols, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.163-172, July 2001, Hersonissos, Greece [doi>10.1145/380752.380796]
• 16: 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]
• 17: D. Kostić, A. Rodriguez, J. Albrecht, A. Bhirud, and A. Vahdat. Using Random Subsets to Build Scalable Network Services. In Proc. of the 4th USENIX Symp. on Internet Technologies and Systems (USITS), Seattle, WA, March 2003.
• 18: C. Law and K. Siu. Distributed Construction of Random Expander Networks. In Proc. of the IEEE INFOCOM, pages 2133--2143, San Francisco, CA, March 2003.
• 19: Dmitri Loguinov , Anuj Kumar , Vivek Rai , Sai Ganesh, Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863999]
• 20: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514206]
• 21: N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller. Equation of State Calculations by Fast Computing Machines. Journal of Chemical Physics, 21:1087--1092, 1953.
• 22: Milena Mihail , Christos Papadimitriou , Amin Saberi, On Certain Connectivity Properties of the Internet Topology, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.28, October 11-14, 2003
• 23: Boris Pittel, On spreading a rumor, SIAM Journal on Applied Mathematics, v.47 n.1, p.213-223, Feb. 1987 [doi>10.1137/0147013]
• 24: Dana Randall, Mixing, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.4, October 11-14, 2003
• 25: 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
• 26: 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
• 27: K. Shen. Structure Management for Scalable Overlay Service Construction. In Proc. of the First USENIX/ACM Symp. on Networked Systems Design and Implementation (NSDI), pages 281--294, San Francisco, CA, March 2004.
• 28: 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
• 29: M. Zhong and K. Shen. Popularity-Biased Random Walks for Peer-to-Peer Search Under the Square-Root Principle. In Proc. of the 5th International Workshop on Peer-to-Peer Systems (IPTPS), Santa Barbara, CA, February 2006.
• 30: M. Zhong, K. Shen, and J. Seiferas. Non-uniform Random Membership Management in Peer-to-Peer Networks. In Proc. of the IEEE INFOCOM, pages 1151--1161, Miami, FL, March 2005.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques