Rate control in communication networks
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/multiplicative 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.
(Talk based on joint work with Richard Gibbens, Aman Maulloo and
David Tan.)
Frank Kelly's home
page