iCON2 : Internet Congestion Control, in Retrospect.
Aditya Akella, Richard Karp, Christos Papadimitriou, Srini Seshan, Scott Shenker and Ion Stoica.
Over a decade ago, the Internet suffered a series of congestion
collapses leading to the development of TCP's congestion control
algorithms. Since then, there has been
wide-spread belief that the congestion control algorithms have been a
major reason behind the stability and effecient operation of the
Internet. In this work, we revisit this basic conventional wisdom from
two angles each corresponding to one of the two components of this
work. Each of the two components is described hereunder.
Related Publications and Talks
- The pioneering theoretical analysis of Chiu and Jain has resulted in
the widespread belief that linear
additive-increase-multiplicative-decrease (AIMD) control algorithms
should be used in the Internet. However, these early congestion control design
decisions were made in a context where loss recovery was fairly
primitive (e.g. TCP Reno) and often timed-out when more than a
few losses occurred. Moreover, routers were almost always FIFO
In subsequent years, there has been significant improvement in TCP
loss recovery algorithms. For instance, TCP SACK can absorb many
losses without timing out. In addition, there have been many
proposals for improved router behavior: RED active queue management,
Explicit Congestion Notification (ECN), and per-flow packet scheduling
(DRR and fair queueing).
In this Work, we evaluate the four linear congestion control styles
-- AIMD, AIAD, MIMD, MIAD -- in the context of these various loss
recovery and router algorithms. We find that in the traditional
context of TCP Reno loss recovery and FIFO drop-tail routers, AIMD is
clearly the superior design choice. However, when we include the
more modern developments of better loss recovery and queue management
schemes, we find quite a different story. In particular, AIAD seems
to be a reasonable alternative choice. We also show that with minor
modifications, AIAD can also be made fair, a problem that AIAD faces
with FIFO drop-tail buffers.
The "socially responsible" congestion control behavior, that is
implemented by the bulk of Internet
end-points, has been given credit for the continued stability of the
network. This paper is an attempt to understand if these social
congestion control algorithms were aptly credited. We answer whether
greedy behavior by network end-points actually results in unstable
network conditions such as congestion collapse or does socially
responsible congestion control behavior actually match the best
interests of greedy end-users performing reliable data transfer. The
answer to this question has important implications to network
operation. If the answer is that greedy behavior results in
instability, then the reason that the Internet is functioning
correctly is either that end-users are consciously socially
responsible or that it is too difficult to modify end-hosts to behave
greedily. Clearly, network operators cannot rely
on either of these conditions persisting and they must deploy new
network mechanisms to ensure that network end-points do not behave
greedily in the future. On the other hand, if selfishness does not
result in poor network behavior, then we need no such mechanisms
deployed and there are reasons beyond just the social congestion
control algorithms of TCP that perhaps contribute to stability in the
face of greedy network end-point behavior.
In this part of our analysis of congestion control algorithms, we
adopt a game-theoretic analysis of TCP to show the following
- In certain situations, greedy end-point behavior is
identical to the socially optimal behavior. In particular, these
behaviors overlap in the historically significant setting of TCP-Reno
end-points in a network of drop-tail routers.
- Unfortunately, our analysis also shows
that most situations that are typical of
current conditions, e.g., TCP-SACK end-points with either drop-tail or RED
routers, encourage greedy flows to exhibit undesirable behavior. This
results in Nash Equilibria with poor overall network efficiency.
- It is possible, as we have shown, to
design simple, scalable queue management algorithms to ensure that the
advantage gained by greedy flows is more than offset by a high packet
loss rate. Another valuable upshot of our analysis of the TCP Game has
been the development of simple schemes to evaluate the effectiveness
of active queue management techniques in containing aggressive
Selfish Behavior and Stability of the
Internet: A Game-Theoretic Analysis of TCP [ps] [pdf]
Aditya Akella, Richard Karp, Christos Papadimitriou, Srinivasan Seshan
and Scott Shenker.
ACM SIGCOMM 2002, Pittsburgh PA.
Slides from the talk [ppt] [pdf].
- Exploring Congestion Control [ps] [pdf]
Aditya Akella, Srinivasan
Seshan, Scott Shenker and
CMU SCS Technical Report Number CMU-CS-02-139.
- Exploring Congestion Control [ppt]
At CMU Systems Seminar, Nov 2001.