Estimating membership in a multicast session

ABSTRACT

We propose two novel on-line estimation algorithms to determine the size of a dynamic multicast group. We first use a Wiener filter to derive an optimal estimator for the membership size of the session in case the join process is Poisson and the lifetime of participants is distributed exponentially. We next develop the best first-order linear filter from which we derive an estimator that holds for any lifetime distribution. We apply this approach to the case where the lifetime distribution is hyperexponential. Both estimators hold under any traffic regime. Applying both estimators on real traces corresponding to video sessions, we find that both schemes behave well, one of which performs slightly better than the other in some cases. We further provide guidelines on how to tune the parameters involved in both schemes in order to achieve high quality estimation while simultaneously avoiding feedback implosion.

REFERENCES

• 1: K. C. Almeroth and M. H. Ammar. MListen, 1995. http://www.cc.gatech.edu/computing/Telecomm/mbone/.
• 2: S. Alouf. Parameter Estimation and Performance Analysis of Several Networking Applications. PhD thesis, University of Nice-Sophia Antipolis, November 2002. Available at http://www.inria.fr/mistral/personnel/Sara.Alouf/.
• 3: S. Alouf, E. Altman, and P. Nain. Optimal on-line estimation of the size of a dynamic multicast group. In Proc. of IEEE INFOCOM '02, New York, New York, volume 2, pages 1109--1118, June 2002.
• 4: 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
• 5: Yang-hua Chu , Sanjay G. Rao , Hui Zhang, A case for end system multicast (keynote address), Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.1-12, June 18-21, 2000, Santa Clara, California, United States
• 6: D. R. Cox and V. Isham. Point Processes. Chapman and Hall, New York, 1980.
• 7: C. Diot, B. N. Levine, B. Lyles, H. Kassem, and D. Balensiefen. Deployment issues for the IP multicast service and architecture. IEEE Network magazine, Special Issue on Multicasting, 14(1):78--88, January/February 2000.
• 8: A. Dutta, H. Schulzrinne, and Y. Yemini. MarconiNet - an architecture for Internet radio and TV networks. In Proc. of NOSSDAV '99, Basking Ridge, New Jersey, June 1999.
• 9: Sally Floyd , Van Jacobson , Steve McCanne , Ching-Gung Liu , Lixia Zhang, A reliable multicast framework for light-weight sessions and application level framing, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.342-356, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 10: P. Francis. Yoid: Extending the internet multicast architecture. Unrefereed report, April 2000. Available at http://www.icir.org/yoid/docs/index.html.
• 11: T. Friedman and D. Towsley. Multicast session membership size estimation. In Proc. of IEEE INFOCOM '99, New York, New York, volume 2, pages 965--972, March 1999.
• 12: S. Haykin. Modern Filters. Macmillan, New York, 1989.
• 13: Simon Haykin, Adaptive filter theory (3rd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 14: Hugh W. Holbrook , David R. Cheriton, IP multicast channels: EXPRESS support for large-scale single-source applications, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.65-78, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 15: J. Jannotti, D. Gifford, K. Johnson, M. Kaashoek, and J. O'Toole. Overcast: Reliable multicasting with an overlay network. In Proc. of USENIX OSDI '00, San Diego, California, pages 197--212, October 2000.
• 16: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 17: C. Liu and J. Nonnenmacher. Broadcast audience estimation. In Proc. of IEEE INFOCOM '00, Tel Aviv, Israel, volume 2, pages 952--960, March 2000.
• 18: J. Nonnenmacher. Reliable multicast transport to large groups. PhD thesis, Ecole Polytechnique Federale de Lausanne, Switzerland, July 1998.
• 19: Jörg Nonnenmacher , Ernst W. Biersack, Scalable feedback for large groups, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.375-386, June 1999 [doi>10.1109/90.779206]
• 20: D. Pendarakis, S. Shi, D. Verma, and M. Waldvogel. ALMI: An application level multicast infrastructure. In Proc. of USENIX USITS '01, San Francisco, California, pages 49--60, March 2001.
• 21: J. Rosenberg and H. Schulzrinne. Timer reconsideration for enhanced RTP scalability. In Proc. of IEEE INFOCOM '98, San Francisco, California, volume 1, pages 233--241, March/April 1998.
• 22: H. Schulzrinne, S. Casner, R. Frederick, and V. Jacobson. RTP: a transport protocol for real-time applications. RFC 1889, Network Working Group, January 1996.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.3 Communications Applications
          Subjects: Computer conferencing, teleconferencing, and videoconferencing

General Terms:
Algorithms, Measurement, Performance

Keywords:
M/G/8 queue, Wiener filter, first-order linear filter, membership size, multicast applications, on-line estimation