Wave and equation based rate control using multicast round trip time

ABSTRACT

This paper introduces Wave and Equation Based Rate Control (WEBRC), the first multiple rate multicast congestion control protocol to be equation based. The equation-based approach enforces fairness to TCP with the benefit that fluctuations in the flow rate are small in comparison to TCP.This paper also introduces the multicast round trip time (MRTT), a multicast analogue of the unicast round trip time (RTT). The MRTT is fundamental to the equation-based protocol that each receiver uses to adjust its reception rate. Each receiver independently measures its own MRTT without placing any added messaging burden on the receiver, the sender or the intermediate network elements. Benefits provided by the MRTT include those that the RTT provides to TCP, e.g., reduced reception rates in reaction to buffer filling and fair sharing of bottleneck links. In addition, the use of MRTT is shown to synchronize and equalize the reception rates of proximate receivers and to cause reception rates to increase as the density of receivers increases.Another innovation of WEBRC is the idea of transmitting data with waves: the transmission rate on a channel is periodic, with an exponentially decreasing form during an active period followed by a quiescent period. Benefits of using waves include insensitivity to large IGMP leave latency; a frequency of joins and leaves by each receiver that is small and independent of the receiver reception rate; the use of a small number of multicast channels; fine-grained control over the receiver reception rate; and minimal, at times nonexistent, losses due to buffer overflow.

REFERENCES

• 1: John Byers , Michael Frumin , Gavin Horn , Michael Luby , Michael Mitzenmacher , Alex Roetter , William Shaver, FLID-DL: congestion control for layered multicast, Proceedings of NGC 2000 on Networked group communication, p.71-81, November 08-10, 2000, Palo Alto, California, United States [doi>10.1145/354644.354654]
• 2: John W. Byers , Michael Luby , Michael Mitzenmacher , Ashutosh Rege, A digital fountain approach to reliable distribution of bulk data, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.56-67, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 3: Paul Dagum , Richard Karp , Michael Luby , Sheldon Ross, An Optimal Algorithm for Monte Carlo Estimation, SIAM Journal on Computing, v.29 n.5, p.1484-1496, March 2000 [doi>10.1137/S0097539797315306]
• 4: 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]
• 5: S. Floyd et al. Equation-based congestion control for unicast applications: the extended version. Technical Report TR-00-003, Int. Comp. Sci. Instit., Berkeley, CA, Mar. 2000.
• 6: M. Handley et al. TCP friendly rate control (TFRC): Protocol specification. IETF Transport Area Working Group Internet-Draft, Apr. 2002. http://www.ietf.org/ internet-drafts/draft-ietf-tsvwg-tfrc-04.txt. Work in progress. Expires Oct. 2002.
• 7: T. V. Lakshman , Upamanyu Madhow, The performance of TCP/IP for networks with high bandwidth-delay products and random loss, IEEE/ACM Transactions on Networking (TON), v.5 n.3, p.336-350, June 1997 [doi>10.1109/90.611099]
• 8: M. Luby phet al. Asynchronous layered coding protocol instantiation. IETF Reliable Multicast Transport Working Group Internet-Draft, Apr. 2002. http://www.ietf.org/internet-drafts/draft-ietf-rmt- pi-alc-08.txt. Work in progress. Expires Oct. 2002.
• 9: M. Luby et al. Layered coding transport building block. IETF Reliable Multicast Transport Working Group Internet-Draft, Feb. 2002. http://www.ietf.org/ internet-drafts/draft-ietf-rmt-bb-lct-04.txt. Work in progress. Expires Aug. 2002.
• 10: M. Luby and V. K. Goyal. Wave and equation based rate control building block. IETF Reliable Multicast Transport Working Group Internet-Draft, June 2002. http://www.ietf.org/internet-drafts/draft-ietf-rmt- bb-webrc-02.txt. Work in progress. Expires Dec. 2002.
• 11: M. Luby and V. K. Goyal. Wave and equation based rate control using multicast round trip time: Extended report. Technical Report DF2002-07-001, Digital Fountain, July 2002. Available on-line at http://www.digitalfountain.com/technology/.
• 12: M. Luby phet al. Forward error correction building block. IETF Reliable Multicast Transport Working Group Internet-Draft, Feb. 2002. http://www.ietf.org/ internet-drafts/draft-ietf-rmt-bb-fec-06.txt. Work in progress. Expires Aug. 2002.
• 13: M. Luby et al. The use of forward error correction in reliable multicast. IETF Reliable Multicast Transport Working Group Internet-Draft, Feb. 2002. http://www.ietf.org/internet-drafts/draft-ietf-rmt- info-fec-02.txt. Work in progress. Expires Aug. 2002.
• 14: Matthew Mathis , Jeffrey Semke , Jamshid Mahdavi, The macroscopic behavior of the TCP congestion avoidance algorithm, ACM SIGCOMM Computer Communication Review, v.27 n.3, p.67-82, July 1997 [doi>10.1145/263932.264023]
• 15: The network simulator -- ns-2. Available at http://www.isi.edu/nsnam/ns.
• 16: 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
• 17: L. Vicisano, L. Rizzo, and J. Crowcroft. TCP-like congestion control for layered multicast data transfer. In Proc. IEEE INFOCOM, volume 3, pages 996--1003, San Francisco, CA, Mar.--Apr. 1998.
• 18: J. Widmer, R. Denda, and M. Mauve. A survey on TCP-friendly congestion control. IEEE Network, 15(3):28--37, May--June 2001.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
TCP-friendliness, congestion control, multicast, multiple-rate