Resource pricing and the evolution of congestion control
This talk will discuss the stability and fairness of rate control
algorithms for
communication networks. Algorithms that provide natural generalizations to
large-scale networks of simple additive increase/multi-plicative decrease
schemes
are shown to be stable about a system optimum characterized by a
proportional
fairness criterion. Stability is established by showing that, with an
appropriate
formulation of an overall optimization problem, the network's implicit
objective
function provides a Lyapunov function for the dynamical system defined by
the rate
control algorithm. The network's optimization problem may be cast in primal
or dual
form: this leads to two classes of algorithm, which may be interpreted in
terms of
either congestion indication feedback signals or explicit rates based on
shadow prices.
Both classes of algorithm provide natural implementations of proportionally
fair
pricing, and can be viewed as "charge-aware" developments of, respectively,
Jacobson's TCP algorithm and ATM available bit rate algorithms.
As an application of the theory, the talk will conclude with a discussion
of ways in
which the transmission control protocol of the Internet may evolve to
support
heterogeneous applications. The claim will be made 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.
This talk is based on joint work with Richard Gibbens, Aman Maulloo and
David Tan.
slides.
References:
Frank Kelly's home
page
f.p.kelly@statslab.cam.ac.uk