Fine-grained layered multicast with STAIR

ABSTRACT

Traditional approaches to receiver-driven layered multicast have advocated the benefits of cumulative layering, which can enable coarse-grained congestion control that complies with TCP-friendliness equations over large time scales. In this paper, we quantify the costs and benefits of using noncumulative layering and present a new, scalable multicast congestion control scheme called STAIR that embodies this approach. Our first main contribution is a set of performance criteria on which we base a comparative evaluation of layered multicast schemes. In contrast to the conventional wisdom, we demonstrate that fine-grained rate adjustment can be achieved with only modest increases in the number of layers, aggregate bandwidth consumption and control traffic. The STAIR protocol that we subsequently define and evaluate is a multiple rate congestion control scheme that provides a fine-grained approximation to the behavior of TCP additive increase/multiplicative decrease (AIMD) on a per-receiver basis.

REFERENCES

• 1: [1] D. Bansal and H. Balakrishnan, "Binomial congestion control algorithms," in Proc. IEEE INFOCOM, Anchorage, AK, Apr. 2001, pp. 631-640.
• 2: [2] J. Byers, M. Handley, G. Horn, M. Luby, and L. Vicisano. (2000, Aug.) More thoughts on reference simulations for reliable multicast congestion control schemes. [Online]. Available: http://www.cs.bu.edu/fac/byers/pubs/mrefsims.ps
• 3: John W. Byers , Gu-In Kwon, STAIR: Practical AIMD Multirate Multicast Congestion Control, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.100-112, November 07-09, 2001
• 4: [4] J. Byers, M. Luby, and M. Mitzenmacher, "Fine-grained layered multicast," in Proc. IEEE INFOCOM, Apr. 2001, pp. 1143-1151.
• 5: [5] J. W. Byers, G. Horn, M. Luby, M. Mitzenmacher, and W. Shaver, "FLID-DL: congestion control for layered multicast," IEEE J. Sel. Areas Commun., vol. 20, no. 8, pp. 1558-1570, Oct. 2002.
• 6: [6] J. W. Byers, M. Luby, and M. Mitzenmacher, "A digital fountain approach to asynchronous reliable multicast," IEEE J. Sel. Areas Commun., vol. 20, no. 8, pp. 1528-1540, Oct. 2002.
• 7: Sally Floyd , Kevin Fall, Promoting the use of end-to-end congestion control in the Internet, IEEE/ACM Transactions on Networking (TON), v.7 n.4, p.458-472, Aug. 1999 [doi>10.1109/90.793002]
• 8: Sally Floyd , Mark Handley , Jitendra Padhye , Jörg Widmer, Equation-based congestion control for unicast applications, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.43-56, August 28-September 01, 2000, Stockholm, Sweden
• 9: [9] S. Golestani, "Fundamental observations on multicast congestion control in the Internet," in Proc. IEEE INFOCOM, New York, Mar. 1999, pp. 990-1000.
• 10: Gu-In Kwon , John W. Byers, Scalable architectures for multicast content distribution, 2005
• 11: Michael Luby, LT Codes, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.271, November 16-19, 2002
• 12: Michael Luby , Vivek K. Goyal , Simon Skaria , Gavin B. Horn, Wave and equation based rate control using multicast round trip time, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 13: [13] M. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman, "Efficient erasure correcting codes," IEEE Trans. Information Theory, vol. 47, no. 2, pp. 569-584, Feb. 2001.
• 14: Steven McCanne , Van Jacobson , Martin Vetterli, Receiver-driven layered multicast, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.117-130, August 28-30, 1996, Palo Alto, California, United States
• 15: Jörg Nonnenmacher , Ernst W. Biersack , Don Towsley, Parity-based loss recovery for reliable multicast transmission, IEEE/ACM Transactions on Networking (TON), v.6 n.4, p.349-361, Aug. 1998 [doi>10.1109/90.720869]
• 16: [16] The network simulator - ns-2. [Online]. Available: http://www.isi.edu/ nsnam/ns
• 17: Jitendra Padhye , Victor Firoiu , Don Towsley , Jim Kurose, Modeling TCP throughput: a simple model and its empirical validation, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.303-314, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 18: Reza Rejaie , Mark Handley , Deborah Estrin, Quality adaptation for congestion controlled video playback over the Internet, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.189-200, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 19: Luigi Rizzo, Effective erasure codes for reliable computer communication protocols, ACM SIGCOMM Computer Communication Review, v.27 n.2, p.24-36, Apr. 1997 [doi>10.1145/263876.263881]
• 20: Nishanth R. Sastry , Simon S. Lam, A Theory of Window-Based Unicast Congestion Control, Proceedings of the 10th IEEE International Conference on Network Protocols, p.144-154, November 12-15, 2002
• 21: [21] L. Vicisano, L. Rizzo, and J. Crowcroft, "TCP-like congestion control for layered multicast data transfer," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 1998, pp. 996-1003.
• 22: [22] J. Widmer, R. Denda, and M. Mauve, "A survey on TCP-friendly congestion control," IEEE Network, vol. 15, no. 3, pp. 28-37, May 2001.
• 23: Jörg Widmer , Mark Handley, Extending equation-based congestion control to multicast applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.275-285, August 2001, San Diego, California, United States
• 24: Y. R. Yang , S. S. Lam, General AIMD congestion control, Proceedings of the 2000 International Conference on Network Protocols, p.187, November 14-17, 2000

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
      C.2.6 Internetworking
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Design, Management, Performance, Theory

Keywords:
Fibonacci sequence, TCP-friendliness, congestion control, noncumulative layering, reliable multicast