Global Optimization with EndtoEnd Congestion
Control:
Pointers to the Literature
General References.....
Modeling the Internet.....
Proportional Fairness.....
Optimization Flow Control.....
Delaybased Optimization
General References

Jaffe, Flow Control Power is Nondecentralizable,
IEEE Transactions on Communications, vol. 29, pp. 13011306, September
1981.
By showing that endhosts 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. 114.
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 ratebased AIMD algorithm
achieves convergence to a fair equilibrium
between users, given a singlebottleneck scenario
and synchronization among users.

Scott Shenker, A Theoretical Analysis of Feedback Flow Control, SIGCOMM 90,
pp. 156165.
"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
timescale 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
timescale 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, polylogarithmic time, distributed algorithms
for achieving globallyoptimal 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 EndtoEnd 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
TCPFriendly web page.
The global bandwidth allocation for TCPstyle 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 3337.
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), 237252.
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, endnodes 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.
Endtoend congestion control: utility
functions, random losses and ECN marks, Infocom 2000 and
longer technical report.
This paper considers a framework of endtoend congestion control
where users have different utility functions, and shows how
TCPstyle congestion control could be expressed in this framework.
The paper argues that, with ECN and the other assumptions
implicit in the paper, nearly lossfree 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 packetmarking probability to drive the link
utilization to one, and shows that,
under certain assumptions and with TCPstyle endtoend 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 Online Measurement,
Proceedings of the 16th International Teletraffic
Congress, Edinburgh, U.K., June 1999. See also
Optimization Flow Control with OnLine 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.
Delaybased Optimization

Jeonghoon Mo and
Jean Walrand,
Fair EndtoEnd Windowbased Congestion Control,
September 1998.
This paper shows the existence of fair windowbased endtoend
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 maxmin
and
proportional fairness.

L. Massoulie and J. Roberts,
Bandwidth Sharing: Objectives and Algorithms,
INFOCOM 99.
This paper reviews maxmin 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.
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.
Maintained by
Sally Floyd and
Jeonghoon Mo.
Last modified: February 2001