Global Optimization with End-to-End Congestion Control: Pointers to the Literature

General References

• Jaffe, Flow Control Power is Nondecentralizable, IEEE Transactions on Communications, vol. 29, pp. 1301-1306, September 1981.
  By showing that end-hosts cannot distinguish different networks, this paper demonstrates that any objective criteria depending on average delay of networks cannot be optimized in a distributed manner.

• Chiu and Jain, Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks, Journal of Computer Networks and ISDN, Vol. 17, No. 1, June 1989, pp. 1-14.
  The Additive Increase and Multiplicative Decrease (AIMD) congestion avoidance algorithms of TCP are based in part on this theoretical work. This paper shows that a rate-based AIMD algorithm achieves convergence to a fair equilibrium between users, given a single-bottleneck scenario and synchronization among users.

• Scott Shenker, A Theoretical Analysis of Feedback Flow Control, SIGCOMM 90, pp. 156-165.
  "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. ... Aggregate feedback flow control ... can provide time-scale invariant and stable performance, but not fair or robust performance. The properties of individual feedback flow control ... 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."

• Awerbuch and Azar, Local Optimization of Global Objectives: Competitive Distributed Deadlock Resolution and Resource Allocation, FOCS, 1994.
  This paper presents local, poly-logarithmic time, distributed algorithms for achieving globally-optimal solutions for resource allocation problems. The paper outlines applications of these algorithms for distributed bandwidth management in communication networks.

• Yair Bartal, J. Byers and D. Raz, Global Optimization using Local Information with Applications to Flow Control, STOC, October 1997.
  This theoretical paper gives a distributed algorithm for maximizing revenue or total flow, given repeated rounds. Each connection has a price it is willing to pay per unit of bandwidth. In each round, each connection sends a message, receiving feedback from the routers along the path. The algorithm converges to a (1 + epsilon) approximation to the global optimum solution in a polylogarithmic number of rounds.

• Jamal Golestani, A Class of End-to-End Congestion Control Algorithms for the Internet , Proceedings of ICNP, 1998.

Modeling the Internet

• Papers discussing global bandwidth allocation in the current Internet, where routers can be modeled as marking or dropping packets with a probability that is a function of the average queue size, and sources can be modeled (to a first approximation) as adjusting their sending rate as an inverse linear function of the roundtrip time and the square root of the packet drop or mark rate, can be found at the TCP-Friendly web page. The global bandwidth allocation for TCP-style transports could be explored for a range of scheduling (FIFO, round robin) and drop preference algorithms at the routers.

Proportional Fairness

• Frank Kelly and others, papers on Proportional Fairness.

• Frank Kelly, Charging and rate control for elastic traffic, European Transactions on Telecommunications, volume 8 (1997) pages 33-37.
  This work shows that if users' utility functions are concave functions of their attained throughput, then their aggregate utility is maximized by the network allocating scarce network resources according to a weighted proportional fairness criteris, where the network shares resources in proportion to how much the users choose to pay.

• Frank Kelly, A.K. Maulloo and D.K.H. Tan, Rate control in communication networks: shadow prices, proportional fairness and stability, Journal of the Operational Research Society 49 (1998), 237-252.
  This paper shows that a weighted proportionally fair allocation can be achieved by simple rate control algorithms similar to those in TCP. ``The optimization problem may be cast in primal or dual form: this leads naturally to two classes of algorithm, which may be interpreted in terms of either congestion indication feedback signals or explicit rates based on shadow prices.''

• R.J. Gibbens and F.P. Kelly, Resource pricing and the evolution of congestion control.
  Building on [K97] and [KMT98], this paper argues that ``by appropriately marking packets at overloaded resources and by charging a fixed small amount for each mark received, end-nodes are provided with the necessary information and the correct incentive to use the network efficiently.''

Adaptive ECN Marking

These papers build upon the framework of Kelly and others above.
• S. Kunniyur and R. Srikant. End-to-end congestion control: utility functions, random losses and ECN marks, Infocom 2000 and longer technical report.
  This paper considers a framework of end-to-end congestion control where users have different utility functions, and shows how TCP-style congestion control could be expressed in this framework. The paper argues that, with ECN and the other assumptions implicit in the paper, nearly loss-free operation can be achieved.

• S. Kunniyur and R. Srikant, A Decentralized Adaptive ECN Marking Algorithm, Globecom 2000, Nov. 2000.
  This paper presents an adaptive active queue management mechanism that adjusts the packet-marking probability to drive the link utilization to one, and shows that, under certain assumptions and with TCP-style end-to-end congestion control, the scheme is globally exponentially stable.

Optimization Flow Control

• David Lapsley and Steven Low, An Optimiation Approach to ABR Control, IEEE ICC'98, Atlanta, GA, June 1998. See also Steven Low and David Lapsley, Optimization Flow Control, I: Basic Algorithm and Convergence, September 1998, or the later version in IEEE/ACM Transactions on Networking, December 1999.
  This paper presents a framework designed for ABR service in ATM networks, where each link advertises a bandwidth price, and each source adjusts its rate according to the sum of the bandwidth prices on all of the links in the path. The links then adjust their prices in response to the new source rates, and the cycle repeats.

• Steven Low, Optimization Flow Control with On-line Measurement, Proceedings of the 16th International Teletraffic Congress, Edinburgh, U.K., June 1999. See also Optimization Flow Control with On-Line Measurement or Multiple Paths, February 1999.
  This paper modifies [LL98] above by showing that the links do not require explicit knowledge of the aggregate of the source transmission rates, but can set the link price proportional to the buffer occupancy.

• Steven Low and others, Optimization Flow Control.
  This page outlines a modified version of Optimization Flow Control that uses packet marking to convey to a source the information it needs to optimally adjust its rate.

Delay-based Optimization

• Jeonghoon Mo and Jean Walrand, Fair End-to-End Window-based Congestion Control, September 1998.
  This paper shows the existence of fair window-based end-to-end congestion control. Their protocols use only implicit feedback available to end hosts and does not communicate with routers or switches inside networks. They propose (p,a)-proportional fairness which generalizes max-min and proportional fairness.

• L. Massoulie and J. Roberts, Bandwidth Sharing: Objectives and Algorithms, INFOCOM 99.
  This paper reviews max-min fairness and proportional fairness, and proposes a potential delay minimization criteria as an alternative. They also show that fixed window size control can achieve such objectives.