Global Optimization with End-to-End Congestion
Pointers to the Literature
Modeling the Internet.....
Optimization Flow Control.....
Jaffe, Flow Control Power is Nondecentralizable,
IEEE Transactions on Communications, vol. 29, pp. 1301-1306, September
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
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,
"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,
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.
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
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.
Frank Kelly and others, papers on
Charging and rate control for elastic traffic,
European Transactions on Telecommunications, volume 8 (1997)
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
``The optimization problem may be cast in primal or dual
form: this leads naturally to two classes of algorithm, which may be
in terms of either congestion indication feedback signals or explicit
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
appropriately marking packets at overloaded resources and by charging a
small amount for each mark received, end-nodes are provided with the
necessary information and the correct incentive to use the network
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
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
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.
Jeonghoon Mo and
Fair End-to-End Window-based Congestion Control,
This paper shows the existence of fair window-based end-to-end
control. Their protocols use only implicit feedback available to
hosts and does not communicate with routers or switches inside
They propose (p,a)-proportional fairness which generalizes max-min
L. Massoulie and J. Roberts,
Bandwidth Sharing: Objectives and Algorithms,
This paper reviews max-min fairness and proportional fairness, and proposes
a potential delay minimization criteria as an alternative. They also
that fixed window size control can achieve such objectives.
Notes: [BBR97], [KMT98], and [LL98] all discuss global optimization
in both a primal and dual form. In [BBR97] the primal maximizes
the aggregate flow or revenue, and the dual minimizes the aggregate
weights on the routers. In [LL98] and [KMT98], the primal maximizes
the aggregate utility as a function of source rates.
Sally Floyd and
Last modified: February 2001