Peer counting and sampling in overlay networks: random walk methods

ABSTRACT

In this article we address the problem of counting the number of peers in a peer-to-peer system, and more generally of aggregating statistics of individual peers over the whole system. This functionality is useful in many applications, but hard to achieve when each node has only a limited, local knowledge of the whole system. We propose two generic techniques to solve this problem. The Random Tour method is based on the return time of a continuous time random walk to the node originating the query. The Sample and Collide method is based on counting the number of random samples gathered until a target number of redundant samples are obtained. It is inspired by the "birthday paradox" technique of [6], upon which it improves by achieving a target variance with fewer samples. The latter method relies on a sampling sub-routine which returns randomly chosen peers. Such a sampling algorithm is of independent interest. It can be used, for instance, for neighbour selection by new nodes joining the system. We use a continuous time random walk to obtain such samples. We analyse the complexity and accuracy of the two methods. We illustrate in particular how expansion properties of the overlay affect their performance.

REFERENCES

• 1: D. Aldous and J. Fill. Reversible markov chains and random walks on graphs. monograph in preparation, available at http://stat-www.berkeley.edu/users/aldous/book.html.
• 2: N. Alon and J. Spencer. The probabilistic method. Wiley, 2002.
• 3: S. Alouf, E. Altman, and P. Nain. Optimal on-line estimation of the size of a dynamic multicast group. IEEE INFOCOM '02, 2002.
• 4: S. Asmussen. Applied probability and queues. Springer, 2003.
• 5: F. Baccelli and P. Brémaud. Elements of Queueing Theory. Springer, 2003.
• 6: M. Bawa, H. Garcia-Molina, A. Gionis, and R. Motwani. Estimating aggregates on a peer-to-peer network. Technical Report, Dept. of computer science, Stanford University.
• 7: P. Billingsley. Convergence of probability measures. Wiley, 1999.
• 8: Jean-Chrysostome Bolot , Thierry Turletti , Ian Wakeman, Scalable feedback control for multicast video distribution in the Internet, Proceedings of the conference on Communications architectures, protocols and applications, p.58-67, August 31-September 02, 1994, London, United Kingdom
• 9: S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Gossip algorithms: Design, analysis and applications. IEEE INFOCOM, 2005.
• 10: Miguel Castro , Peter Druschel , Ayalvadi Ganesh , Antony Rowstron , Dan S. Wallach, Secure routing for structured peer-to-peer overlay networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060317]
• 11: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 12: D. Dolev, O. Mokryn, and Y. Shavitt. On multicast trees: structure and size estimation. IEEE INFOCOM 2003, 2003.
• 13: P. Th. Eugster , R. Guerraoui , S. B. Handurukande , P. Kouznetsov , A.-M. Kermarrec, Lightweight probabilistic broadcast, ACM Transactions on Computer Systems (TOCS), v.21 n.4, p.341-374, November 2003 [doi>10.1145/945506.945507]
• 14: T. Friedman and D. Towsley. Multicast session membership size estimation. IEEE INFOCOM, 1999.
• 15: Ayalvadi J. Ganesh , Anne-Marie Kermarrec , Laurent Massoulié, Peer-to-Peer Membership Management for Gossip-Based Protocols, IEEE Transactions on Computers, v.52 n.2, p.139-149, February 2003 [doi>10.1109/TC.2003.1176982 ]
• 16: A.J. Ganesh, L. Massoulié, and D. Towsley. The effect of network topology on the spread of epidemics. In IEEE INFOCOM, 2005.
• 17: A.J. Ganesh and F. Xue. Expansion properties of k-out random graphs. Preprint, 2004.
• 18: Keren Horowitz , Dahlia Malkhi, Estimating network size from local information, Information Processing Letters, v.88 n.5, p.237-243, 16 December 2003 [doi>10.1016/j.ipl.2003.08.011]
• 19: Márk Jelasity , Alberto Montresor, Epidemic-Style Proactive Aggregation in Large Overlay Networks, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.102-109, March 24-26, 2004
• 20: Márk Jelasity , Mike Preuß, On Obtaining Global Information in a Peer-to-Peer Fully Distributed Environment (Research Note), Proceedings of the 8th International Euro-Par Conference on Parallel Processing, p.573-577, August 27-30, 2002
• 21: M. Jelasity, S. Voulgaris, R. Guerraoui, and A-M. Kermarrec. Gossip-based peer sampling. submitted.
• 22: A.-M. Kermarrec, L. Massoulié, and A. J. Ganesh. Efficient application-level multicast on a network-aware self-organizing overlay. IRISA internal publication, 1166--8687;1657, 2004.
• 23: Dionysios Kostoulas , Dimitrios Psaltoulis , Indranil Gupta , Ken Birman , Al Demers, Decentralized Schemes for Size Estimation in Large and Dynamic Groups, Proceedings of the Fourth IEEE International Symposium on Network Computing and Applications, p.41-48, July 27-29, 2005 [doi>10.1109/NCA.2005.15]
• 24: E. Le Merrer, A.-M. Kermarrec, and L. Massoulié Peer to peer size estimation in large and dynamic networks: A comparative study. IEEE HPDC-15, 2006.
• 25: J. Li and D.-Y. Lim. A robust aggregation tree on distributed hash tables. MIT student oxygen workshop 2004, September 2004.
• 26: T. Lindvall. Lectures on the Coupling Method. Dover, 2002.
• 27: N. Linial and A. Wigderson. Expander graphs and their applications. Lecture Notes available at http://www.cs.huji.ac.il/~nati/, 2002.
• 28: Dahlia Malkhi , Moni Naor , David Ratajczak, Viceroy: a scalable and dynamic emulation of the butterfly, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571857]
• 29: Gurmeet Singh Manku, Routing networks for distributed hash tables, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.133-142, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872054]
• 30: B. Mohar. Some applications of laplace eigenvalues of graphs, in graph symmetry: algebric methods and applications. Eds. G. Hahn and G. Sabidussi, NATO ASI Ser. C 497, Kluwer, 1997, pp. 225--275.
• 31: J. Nonnenmacher and E. W. Biersack. Optimal multicast feedback. IEEE INFOCOMM '98, 1998.
• 32: D. Psaltoulis, D. Kostoulas, I. Gupta, K. Birman, and A. Demers. Practical algorithms for size estimation in large and dynamic groups. PODC 2004, 2004.
• 33: Dimitrios Psaltoulis. Private communication. July 2005.
• 34: S. Ross. Simulation. Elsevier, 2001.
• 35: X. Zhang, J. Liu, B. Li, and T.-S. P. Yum. Donet/coolstreaming: A data-driven overlay network for live media streaming. In IEEE INFOCOM, 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Performance

Keywords:
expander graphs, peer-to-peer systems, random walks, sampling