useful both in understanding the performance problems of the current congestion control algorithm and
in designing better algorithms to solve these problems, while maintaining fairness in resource allocation.
Congestion control consists of two components, a source algorithm, implemented in TCP, that
adapts sending rate (or window) to congestion information in the source’s path, and a link algorithm,
implemented in routers, that updates and feeds back a measure of congestion to sources that traverse
the link. Typically, the link algorithm is implicit and the measure of congestion is either loss probability
or queueing delay. For example, the current protocol TCP Reno and its variants use loss probability
as a congestion measure, and TCP Vegas primarily uses queueing delay as a congestion measure. Both
are implicitly updated by the queueing process and implicitly fed back to sources via end-to-end loss
and delay, respectively. In contrast, ECN will allow the explicit update and feedback of other kinds of
congestion measure.
The source-link algorithm pair, referred to here as TCP/AQM (active queue management) algo-
rithms,
1
forms a distributed feedback system, the largest man-made feedback system in deployment. In
this system, hundreds of millions of TCP sources and hundreds of thousands of network devices interact
with each other, each executing a simple local algorithm, implicitly or explicitly, based on local infor-
mation. Their interactions result in a collective behavior, whose equilibrium and stability properties we
now discuss.
3.1 Equilibrium and performance
We can interpret TCP/AQM as a distributed algorithm over the Internet to solve a global optimization
problem [5]; see also [6, 7] for recent surveys. The solution of the optimization problem and that of
an associated problem determine the equilibrium and performance of the network. Different TCP and
AQM algorithms all solve the same prototypical problem. They differ in the objective function of the
underlying optimization problem and the iterative procedure to solve it.
Even though historically TCP and AQM algorithms have not been designed as an optimization
procedure, this interpretation is valid under fairly general conditions, and useful in understanding
network performance, such as throughput, utilization, delay, loss, and fairness. Moreover, the underlying
optimization problem has a simple structure, that allows us to efficiently compute these equilibrium
properties numerically, even for a large network that is hard to simulate.
Specifically, we can regard each source as having a utility function, as a function of its data rate.
Consider the problem of maximizing the sum of all source utility functions over their rates, subject to
link capacity constraints. This is a standard constrained optimization problem for which many iterative
solutions exist. The challenge in our context is to solve for the optimal source rates in a distributed
manner using only local information. A key feature we exploit is the duality theory. It says that
associated with our (primal) utility maximization problem is a dual minimization problem. Whereas
the primal variables over which utility is to be maximized are source rates, the dual variables for the
dual problem are congestion measures at the links. Moreover, solving the dual problem is equivalent to
solving the primal problem. There is a class of optimization algorithms that iteratively solve for both
the primal and the dual problems at once.
TCP/AQM can be interpreted as such a primal-dual algorithm, that is distributed and decentralized,
to solve the utility maximization problem and the associated dual problem. TCP iterates on the source
rates (a source increases or decreases its window in response to congestion in its path), and AQM iterates
on the congestion measures (e.g., loss probability at a link increases or decreases as sources traversing
that link increase or decrease their rates). They cooperate to determine iteratively the network operating
point that maximizes aggregate utility. When this iterative process converges, the equilibrium source
rates are optimal solutions of the primal problem and the equilibrium congestion measures are optimal
solutions of the dual problem. The throughput and fairness of the network are thus determined by the
1
We will henceforth refer it as a “TCP algorithm” even though we really mean the congestion control algorithm in
TCP.
3