Congestion control literature:

End-to-end and Edge-to-Edge Flow Control:

  • Buffer Management
  • Rate/Credit-Based Schemes

    TCP related:

    M. Allman, V. Paxson and W. Stevens, TCP Congestion Control, RFC 2581, Proposed Standard, April 1999.

    The latest standard on TCP Congestion Control. Required reading.

    V. Jacobson, Congestion Avoidance and Control. Proceedings of SIGCOMM '88 (Palo Alto, CA, Aug. 1988) Available from: ee.lbl.gov/nrg-papers.html

    The classic TCP congestion control paper. Describes the slow start, implicit loss detection, congestion avoidance, and RTT filtering algorithms. Papers on TCP improvements. Great archive of TCP-related Papers. IETF Groups: TCPSAT , TCPIMPL , PILC (drafts and RFCs can be found here).

    Floyd, S., and Jacobson, V. "Random Early Detection gateways for Congestion Avoidance". IEEE/ACM Transactions on Networking, V.1 N.4, August 1993, p. 397-413. Available from: ee.lbl.gov/nrg-papers.html

    The paper describing the RED buffer management/packet drop algorithm. This work complements end-to-end TCP control, by using a simple, stateless, randomized packet dropping algorithm to avoid TCP synchronization effects. Latest RED page

    Mathis, M., Mahdavi, J., Floyd, S., and Romanow, A., TCP Selective Acknowledgement Options. RFC 2018, April 1996. Available from: ftp://ftp.isi.edu/in-notes/rfc2018.txt . Latest SACK Page.

    Describes the use of Selective Acknowledgements in TCP. Note that SACK refers to the capability to specify selective retransmission of blocks of data, not just one segment (as opposed to Selective Reject). This feature can improve TCP performance considerably, especially in the presence of bursty packet drops. The SACK page also describes other related enhancements including Forward Acks etc.

    Ramakrishnan, K.K., and Floyd, S., A Proposal to add Explicit Congestion Notification (ECN) to IP. RFC 2481, January 1999. Available from: ftp://ftp.isi.edu/in-notes/rfc2481.txt

    This RFC describes TCP-ECN, an experimental proposal in the Internet. This scheme uses one-bit feedback from routers in a manner similar to the Decbit scheme (see elsewhere in this page), but adapts its use for TCP. Latest ECN page .

    Janey Hoe, Improving the Start-up Behavior of a Congestion Control Scheme for TCP, in ACM SIGCOMM, August 1996. Available from: http://www.acm.org/sigcomm/sigcomm96/papers/hoe.ps.

    Floyd, S., and Henderson, T., The NewReno Modification to TCP's Fast Recovery Algorithm, RFC 2582, Experimental, April 1999. Available from: Sally Floyd's page

    These papers describe the proposed NewReno enhancements to TCP.

    Mathis, M., and Mahdavi, J., Forward Acknowledgement: Refining TCP Congestion Control, SIGCOMM 96, August 1996.

    Describes another technique to refine congestion control.

    L. Brakmo and L. Peterson. TCP Vegas: End to End Congestion Avoidance on a Global Internet. IEEE Journal on Selected Areas in Communication, Vol 13, No. 8 (October 1995) pages 1465-1480. Available from: http://www.cs.arizona.edu/protocols/

    This paper describes TCP Vegas, a new version of TCP which uses an estimate of the bandwidth-delay product of the pipe to perform better congestion avoidance. Though very popular in academic and research circles, this work has not won the favor of implementors and standards bodies. Additional Vegas Page (USC).

    J. Padhye, V. Firoiu, D. Towsley and J. Kurose, "Modeling TCP Throughput: A Simple Model and its Empirical Validation," Proccedings of SIGCOMM'98. Available from: http://www-net.cs.umass.edu/~jitu/publications.html . Tech-report is more recent than the paper.

    This paper proposes a simple, but powerful stochastic model for steady state TCP throughput and shows it to be inversely proportional to the RTT, p^0.5 and timeout intervals. It started off work in TCP-friendly congestion control protocols, which is now influencing work in UDP and multicast congestion control.

    Related work by INRIA folks: INRIA TCP modeling work

    L. Zhang, S. Shenker, and D.D. Clark. ``Observations on the Dynamics of a Congestion Control Algorithm: The Effects of Two-Way Traffic''. Proc. of ACM SIGCOMM '91, pages 133-147, Sep. 1991. Downloadable in three parts: [Part 1][Part 2][Part 3].

    Describes the ack compression problem in TCP.

    S.Floyd and V. Jacobson. ``On Traffic Phase Effects in Packet-Switched Gateways''. ACM Computer Communication Review, 21(2), Aug. 95. Available from ftp://ftp.ee.lbl.gov/papers/phase.ps.Z

    Describes TCP traffic synchronization problems. RED was later designed to tackle this issue.

    T. V. Lakshman and U. Madhow, The performance of TCP/IP for networks with high bandwidth-delay products and random loss, IEEE/ACM Trans. Networking, June 1997. Available from: http://www.comm.csl.uiuc.edu/~madhow/publications.html

    Interesting analysis of TCP performance, including effects of asymmetry.

    R. Morris, Scalable TCP Congestion Control, PhD thesis, January 1999. Available from: http://www.eecs.harvard.edu/~rtm/papers.html Describes methods for scalable buffer management for TCP flows. Includes the FRED method presented in SIGCOMM'97.


    Cardwell N., Savage S., and Anderson T., ``Modeling TCP Latency,''  INFOCOM '2000. Available from: http://ieeeinfocom.org/2000/papers


    Mo, J., La R.J., Anantharam V., and Walrand J., ``Analysis and comparison of TCP Reno and Vegas,'' Proc. of INFOCOM'99. Available from: http://berkeley.edu/~jhmo/draft4.ps


    Floyd, S., Handley, M., Padhye, J., and Widmer, J., ``Equation-Based Congestion Control for Unicast Applications,'' Proc. of SIGCOMM '00. Available from: Sally Floyd's Website

    Wireless/Asymmetry Issues:

    Hari Balakrishnan, "Challenges to Reliable Data Transport over Heterogeneous Wireless Networks," Available from: http://inat.lcs.mit.edu/papers/hari-phd/

    Congestion control issues relating to TCP over wireless and asymmetric media. Includes a discussion of the Berkeley "snoop" protocol. Won the ACM best dissertation award.

    Researchers in this area:

    Explicit Rate-based, Window-based, Credit-based Control:

    Shivkumar Kalyanaraman, Raj Jain, Sonia Fahmy, Rohit Goyal, and Bobby Vandalore, "The ERICA Switch Algorithm for ABR Traffic Management in ATM Networks," Submitted to IEEE/ACM Transactions on Networking, November 1997.

    This paper uses explicit rate-based congestion control for the ABR service in ATM. Conceptually, explicit rate-based schemes involve more participation by interior nodes (routers/switches) and involve the exchange of more information than implicit congestion indication (like TCP Reno), or bit-based feedback schemes (Decbit, TCP-ECN). The payoff is the achieving of properties such as efficiency, fairness, controlled queueing delays, and fast transient response while being robust to measurement errors. Explicit, transparent window-based control has been used by Packeteer Inc.

    Postscript (1.29 MB | Gzip Compressed Postscript (200 KB)

    Anna Charny, "An Algorithm for Rate Allocation in a Packet Switching Network With Feedback", April 1994.

    This is the classic MS thesis that introduced the explicit rate control idea upon which ABR explicit rate schemes have been based.

    (PDF) | (PS) | (html)

    Prasad Bagal, Shivkumar Kalyanaraman, Bob Packer, "Comparative study of RED, ECN and TCP Rate Control," Technical Report, March 1999

    This paper studies the use of transparent explicit window control of TCP using a rate-control scheme, followed by rate-to-window translation and acknowledgement pacing. Comparative performance analysis with RED and ECN shows improvements in fairness, efficiency etc.

    Postscript (474KB) | gzip Compressed Postscript (108KB) | PDF (254KB)

    Related paper dealing with basic explicit rate-to-window conversion techniques: Postscript (1960KB).
    Packeteer, a company that makes TCP rate-control products

    Kung, H. T. and R. Morris, Credit-Based Flow Control for ATM Networks, IEEE Network Magazine, Vol. 9, No. 2, March/April 1995, pp. 40-48. Available from: http://www.eecs.harvard.edu/~htk/

    This paper describes the credit-based approach to flow-control in ATM Networks. This is a hop-by-hop window (credit) based scheme. It lost out in the great rate-vs-credit debate in the ATM Forum, but nevertheless has very influential ideas. Can achieve tight queue bounds, fairness, efficiency etc, but required mandatory per-flow queueing support.


    Afek Y., Mansour Y., and Ostfeld Z., ``Phantom: A simple  and effective flow control scheme,''Proc. of SIGCOMM' 96. Available from:
    ftp://ftp.math.tau.ac.il/pub/afek/phantom3.ps.gz


    Kalampoukas L., Varma A., Ramakrishnan K.K., ``Explicit Window Adaptation: A Method to Enhance TCP Performance,'' Proc. of INFOCOM '98. Available from: www.cse.ucsc.edu/research/hsnlab/publications/publications_sorted_by_year.html

    DEC work (Jain, Ramakrishnan, Chiu): Bit-based (Decbit), AIMD, Timeout, Delay-based etc:

    K.K. Ramakrishnan and R. Jain, "Congestion Avoidance in Computer Networks with A Connecitonless Network Layer: Part IV: A Selective Binary Feedback Scheme for General Topologies," DEC Technical Report DEC-TR-510, August 1987, 43 pp. Available from: http://www.cis.ohio-state.edu/~jain/papers/dectr510.htm

    This paper describes the classic Decbit scheme which introduces the use of 1-bit feedback, additive-increase-multiplicative-decrease policy (AIMD), and associated filtering schemes. Later schemes such as TCP-ECN, OSI, frame-relay and ATM ABR 1-bit feedback schemes were motivated by this work.

    D. Chiu and R. Jain, "Analysis of the Increase/Decrease Algorithms for Congestion Avoidance in Computer Networks," Journal of Computer Networks and ISDN, Vol. 17, No. 1, June 1989, pp. 1-14. Available from: http://www.cis.ohio-state.edu/~jain/papers/cong_av.htm

    This paper analyzes the additive increase/multiplicative decrease policy for dynamic window adjustment, and shows it to be superior in terms of stability and fairness properties over other alternatives.

    R. Jain, "A Delay Based Approach for Congestion Avoidance in Interconnected Heterogeneous Computer Networks," Computer Communications Review, ACM SIGCOMM, October 1989, pp. 56-71. Available from: http://www.cis.ohio-state.edu/~jain/papers/delay.htm

    This paper describes the use of round-trip delay in estimating congestion epoch lengths. Delay is highly variable, and hence the scheme is a study in the use of advanced filtering techniques to obtain the required congestion information.

    R. Jain, "A Timeout Based Congestion Control Scheme for Window Flow- Controlled Networks", IEEE Journal of Selected Areas in Communications, Vol. SAC-4, No. 7, October 1986, pp. 1162-1167. Reprinted in C. Partridge, Ed., "Innovations in Internetworking," Artech House, Norwood, MA 1988. Available from: http://www.cis.ohio-state.edu/~jain/papers/control.htm

    This paper, a precursor of Jacobson's TCP congestion control paper, describes the use of timeout and packet loss as an implicit indicator of congestion. It also describes the method of starting the dynamic window from one segment.

    K. Ramakrishnan and R. Jain, "Congestion Avoidance in Computer Networks with A Connecitonless Network Layer: Part IV: A Selective Binary Feedback Scheme for General Topologies," DEC Technical Report DEC-TR-510, August 1987, 43 pp. Available from: http://www.cis.ohio-state.edu/~jain/papers/dectr510.htm

    This paper describes the classic Decbit scheme which introduces the use of 1-bit feedback, additive-increase-multiplicative-decrease policy (AIMD), and associated filtering schemes. Later schemes such as TCP-ECN, OSI, frame-relay and ATM ABR 1-bit feedback schemes were motivated by this work.

    New End-to-End Unicast Architectures

    Hari Balakrishnan, Hariharan Rahul, and Srinivasan Seshan, "An Integrated Congestion Management Architecture for Internet Hosts" Proc. ACM SIGCOMM, Cambridge, MA, September 1999. Available from:

    Proposes a new end-system architecture to aggregate congestion control actions for UDP, TCP and other unicast transports into a single "congestion manager." This proposal is being discussed for standardization in the IETF. Latest CM page. Related Work on Multiplexing TCP, UDP sessions .

    Floyd, S., and Fall, K., Promoting the Use of End-to-End Congestion Control in the Internet. Under submission, February 1998. This is a revised version of sections of Router Mechanisms to Support End-to-End Congestion Control, Technical report, February 1997. Available from: ee.lbl.gov/nrg-papers.html

    The paper describing need for end-to-end congestion control even for non-TCP applications. Related work on Global Optimization using End-to-End Congestion Control.

    Multicast:

    McCanne, S., Jacobson, V., and Vetterli, M. Receiver-driven Layered Multicast. ACM SIGCOMM '96, August 1996, Stanford, CA. Available from: ee.lbl.gov/nrg-papers.html

    Describes how the IP multicast signaling and routing mechanisms to develop a congestion control algorithm for layered video. Later papers by others have used similar techniques using layered FEC, or every layered data multicast transmission.

    Reliable Multicast Congestion Control, Available from: http://ale.east.isi.edu/RMRG/

    Latest work on congestion control for reliable multicast transport (RMT) protocols. Additional (better) RMT page.

    Researchers in this area:

    QoS: Scheduling, Buffer Management, Admission Control, Int-serv/Diff-serv and Network Calculus

    Floyd, S., and Jacobson, V., Link-sharing and Resource Management Models for Packet Networks (compressed postscript, pdf). IEEE/ACM Transactions on Networking, Vol. 3 No. 4, pp. 365-386, August 1995. Available from: ee.lbl.gov/nrg-papers.html

    This paper describes the basis for the famous CBQ (class based queueing) scheduler. Note that schedulers are open-loop components which can control the parameters of the "virtual link" offered to each contending traffic class or aggregate. Latest CBQ page .

    Differentiated Services. IETF diff-serv WG , resources .

    Diff-serv is a new IETF standard that allows simple and coarse methods of providing differentiated classes of service for Internet traffic, to support various types of applications, and specific business requirements.

    A.Demers, S.Keshav, and S.J. Shenker. ``Analysis and Simulation of a Fair Queueing Algorithm''. Proc. of ACM SIGCOMM '89, pages 1-12, Sep. 1989.

    The paper on Weighted Fair Queueing (WFQ).

    I. Stoica, S. Shenker, and H. Zhang. ``Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks'' Proc. of ACM SIGCOMM '98, pages 118-130, Sep. 1998.

    Per-flow state in packet headers rather than in routers. Follow up paper in SIGCOMM'99: "Providing Guaranteed Services Without Per Flow Management" .

    D.D. Clark, S.J. Shenker, and L. Zhang. ``Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanism''. Proc. of ACM SIGCOMM '92, pages 14-26, Aug. 1992.

    Precursor to the int-serv work.

    S. Jamin, P. B. Danzig, S. J. Shenker, and L. Zhang. ``A Measurement-based Admission Control Algorithm for Integrated Services Packet Networks (Extended Version)''. ACM/IEEE Transactions on Networking, 5(1):56-70, Feb. 1997.

    Describes a new approach to admission control - measurement based. The shorter version of this paper won the SIGCOMM best paper award in 1995.


    Agrawal R., Cruz R.L., Okino C., and Rajan R., ``A Framework for Adaptive Service Guarantees,'' 36th Allerton Conference on Communication, Control, and Computing, Sep '98. Available from: Rene Cruz's Website


    Agrawal R., Cruz R.L., Okino C. and Rajan R.,``Performance Bounds for Flow Control Protocols,'' ACM/IEEE ToN,June '99. Available from: Rene Cruz's Website


    Boudec J.Y. Le, ``Application of Network Calculus To Guaranteed Service Networks,''  IEEE ToITMay '98.  Avilable from:
    http://lrcwww.epfl.ch/PS_files/NetCal.htm


    Cruz R.L., "A Calculus for Network Delay and a Note onTopologies of Interconnection Networks," PhD Thesis. Available from: Rene Cruz's Website


    Cruz R.L. and Okino C., "Service Guarantees for Joint Scheduling and Flow Control," 36th IEEE Conference on Decision and Control, Dec '97. Available from: Rene Cruz's Website


    A Good Site on Network Calculus


    Parekh A.K., and Gallager R.G., ``A generalized processor sharing approach to flow control in integrated services networks: the multiple node case,'' IEEE/ACM ToN '94. Available from:  http://www.ccrc.wustl.edu/~ton/apr94.html


    Guerin R. and Peris V., ``Quality-of-Service in Packet Networks: Basic Mechanisms and Directions.'' Computer Networks, Feb '99, pp. 169-179. Available from: Roch Guerin's Page


    Guerin R., Ahmadi H., and Naghshineh M., ``Equivalent Bandwidth and Its Application to Bandwidth Allocation in High-Speed Networks,'' IEEE JSAC , Sep '91.  Available from: Roch Guerin's Page


    Guerin R. and Orda A..  ``QoS-based Routing in Networks with Inaccurate Information:  Theory and Algorithms,'' IEEE/ACM ToN, June '99. Available from: Roch Guerin's Page

    Researchers in this area:

    Rate-based flow control (classical work)

    S. Keshav, Packet-Pair Flow Control, Tech-report, Cornell Univ. Available from: http://www.cs.cornell.edu/skeshav/papers.html .

    This paper proposes the use of rate-based flow control, combined with a per-flow round-robin scheduler at bottlenecks and a packet-pair based bandwidth probing technique. Good discussion of filters, control-theoretic and scheduling issues. Also check out Keshav's PhD thesis and SIGCOMM'91 paper. Recent work on bandwidth measurement by Allman, Paxson (SIGCOMM'99) , Lai/Baker (Nettimer/Mosquitonet project, Infocom'99) has been based upon this.

    D. D. Clark, M. L. Lambert, and L. Zhang, "NETBLT: a bulk data transfer protocol," Request for Comments (Experimental) 998, Internet Engineering Task Force, Mar. 1987.

    This document is a description of and a specification for the NETBLT protocol. It is a revision of the specification published in RFC-969. NETBLT (NETwork BLock Transfer) is a transport level protocol intended for the rapid transfer of a large quantity of data between computers. It provides a transfer that is reliable and flow controlled, and is designed to provide maximum throughput over a wide variety of networks. Although NETBLT currently runs on top of the Internet Protocol (IP), it should be able to operate on top of any datagram protocol similar in function to IP. This document is published for discussion and comment, and does not constitute a standard. The proposal may change and certain parts of the protocol have not yet been specified; implementation of this document is therefore not advised.

    Control-theoretic work:

    Hitay Ozbay, Shivkumar Kalyanaraman, Altug Iftar, "On Rate-Based Congestion Control in High Speed Networks: Design of an H-infinity Based Flow Controller for Single Bottleneck" American Control Conference, 1998.

    Design of a robust control-theoretic flow-control scheme based upon H-infinity theory. Also contains pointers to other control-theoretic work.

    Postscript (459496 bytes) | PKzip Compressed Postscript (97220 bytes) | PDF

    Other researchers in this area:

    Pricing:

    Pricing. Links.

    Pricing as a tool for economic efficiency, as well as traffic management in the Internet.

    Ron Cocchi, Deborah Estrin, Scott Shenker, and Lixia Zhang, "A study of priority pricing in multiple service class networks," in SIGCOMM Symposium on Communications Architectures and Protocols, Sept. 1992.

    Abstract: We study the role of pricing policies in multiple service class networks. We argue that some form of graduated prices are required in order for any multiclass service discipline to have the desired effect. Moreover, we demonstrate through simulation that it is possible to set the prices so that every user is more satisfied with the combined cost and performance of a network with graduated prices. For some users the performance penalty received for requesting a less-than-optimal service class is offset by the reduced price of the service. For the other users the monetary penalty incurred by using the more expensive, higher quality service classes is offset by the improved performance they receive. Thus, prices allow us to spread the benefits of multiple service classes around to all users, rather than just having these benefits remain exclusively with users who are performance sensitive.

    Ron Cocchi, Scott Shenker, Deborah Estrin, and Lixia Zhang, "Pricing in computer networks: Motivation, formulation, and example," IEEE/ACM Transactions on Networking, vol. 1, Dec. 1993. Abstract: We study the role of pricing policies in multiple service class networks. We first argue that some form of service-class sensitive pricing is required for any multiclass service discipline to attain the desired level of performance. Borrowing heavily from the Nash implementation paradigm in economics, we then present an abstract formulation of service disciplines and pricing policies. This formulation allows us to describe more clearly the interplay between service disciplines and pricing policies in determining overall network performance. Effective multiclass service disciplines allow networks to focus resources on performance sensitive applications, while effective pricing policies allow us to spread the benefits of multiple service classes around to all users, rather than just having these benefits remain exclusively with the users of applications that are performance sensitive. Furthermore, service disciplines and pricing policies combine to form the incentive system facing a user.


    Kelly F., Maulloo A., and Tan D., ``Rate control for communication networks: shadow prices, proportional fairness and stability,'' Journal of the Operational Research Society,Mar '98. Available from: http://www.statslab.cam.ac.uk/~frank/rate.html


    La R.J. and Ananthram V., ``Charge-Sensitive TCP and Rate Control in the Internet,'' Proc. of INFOCOM '00. Available from: http://ieeeinfocom.org/2000/papers

    Researchers in this area:

    Filtering, Estimation and Measurement:

    [KP91] P. Karn and C. Partridge, Improving Round-Trip Time Estimates in Reliable Transport Protocol. ACM Transactions on Computer Systems (TOCS), Vol. 9, No. 4, pp. 364-373, November 1991.

    This paper describes a new filtering technique for estimating RTT.

    Kevin Lai and Mary Baker, "Measuring Bandwidth." Proceedings of IEEE INFOCOM '99, March 1999. Available from: http://mosquitonet.stanford.edu/publications.html

    This paper discusses techniques for measuring bandwidth of a connection. Builds upon earlier work in Vern Paxson's dissertation , Keshav's packet pair scheme . TCP Vegas (reference elsewhere) estimates bandwidth-delay product, a random variable with higher variance than each of the two random variables (RTT and bandwidth) of which it is a product.

    M. Allman and V. Paxson, On Estimating End-to-End Network Path Properties, ACM SIGCOMM '99, September 1999, Cambridge, MA.

    New paper which talks about filtering RTT, RTO and bandwidth information.

    Miscellaneous:

    Scott Shenker, "A theoretical analysis of feedback flow control," in SIGCOMM Symposium on Communications Architectures and Protocols (Deepinder P. Sidhu, ed.), (Philadelphia, Pennsylvania), pp. 156-165, ACM, Sept. 1990. also in em Computer Communication Review 20 (4), Oct. 1990.

    Abstract: Congestion is a longstanding problem in datagram networks. One congestion avoidance technique is feedback flow control, in which sources adjust their transmission rate in response to congestion signals sent (implicitly or explicitly) by network gateways. The goal is to design flow control algorithms which provide time-scale invariant, fair, stable, and robust performance. In this paper we introduce a simple model of feedback flow control, in which sources make synchronous rate adjustments based on the congestion signals and other local information, and apply it to a network of Poisson sources and exponential servers. We investigate two different styles of feedback, aggregate and individual, and two different gateway service disciplines, FIFO and Fair Share. The purpose of this paper is to identify, in the context of our simple model, which flow control design choices allow us to achieve our performance goals. Aggregate feedback flow control, in which congestion signals reflect only the aggregate congestion at the gateways, can provide time-scale invariant and stable performance, but not fair or robust performance. The properties of individual feedback flow control, in which the congestion signals reflect the congestion caused by the individual source, depend on the service discipline used in the gateways. Individual feedback with FIFO gateways can provide time-scale invariant, fair, and stable performance, but not robust performance. Individual feedback with Fair Share gateways can achieve all four performance goals. Furthermore, its stability properties are superior to those of the other two design choices. By making robust and more stable performance possible, gateway service disciplines play a crucial role in realizing effective flow control.

    Back to Shivkumar Kalyanaraman's home page