Queueing Analysis of a Feedback-Controlled (TCP/IP) Network
Damon Wischik
Computer Science Department
University College London
Wednesday, April 6, 2005
4:30 - 5:45 PM
Terman Engineering Center, Room 453
Abstract:
Most traffic in the Internet is controlled by TCP, an algorithm which
adjusts the transmission rate of a traffic flow in response to the
congestion it perceives in the network. In core Internet routers, which
have many TCP flows, the aggregate traffic flow behaves predictably,
both at a stochastic level (Cao, Cleveland, Lin, Sun [1]) and a fluid
level (Misra, Gong and Towsley [2], Baccelli, McDonald and Reynier
[3]). This is the basis for a growing literature on Internet congestion
control [4].
This predictability can be used to address the question: how big do
buffers need to be in Internet routers? I will describe three different
buffer sizing rules, the analysis of which draws on tools from
optimization, queueing theory, statistical physics, and dynamical
systems theory:
I. buffer is proportional to number of flows (the current
standard),
II. buffer is proportional to the square root of the
number of flows
(Appenzeller, Keslassy, McKeown
[5]),
III. buffer does not depend on the number of flows.
It turns out that buffers can be made far smaller (the buffer in a
terabit router could be reduced from 30 Gbytes to 30 kbytes). This
reduction gives a slight improvement in performance. It opens the way
to all-optical routers.
This is joint work with Gaurav Raina (Cambridge). For more details, http://www.cs.ucl.ac.uk/staff/D.Wischik/Research/tcptheory.html
References:
[1] Internet traffic tends toward Poisson and independent as the load
increases (2002).
http://citeseer.ist.psu.edu/cao02internet.html
[2] Fluid-based analysis of a network of AQM routers supporting TCP
flows with an application to RED (2000).
http://portal.acm.org/citation.cfm?id=347421
[3] A mean-field model for multiple TCP connections through a buffer
implementing RED (2002).
http://www.inria.fr/rrrt/rr-4449.html
[4] For a selection of references see
http://www.cs.ucl.ac.uk/staff/D.Wischik/Interests/Topics/tcpqueue.html
[5] Sizing router buffers (2004).
http://tiny-tera.stanford.edu/~nickm/papers/sigcomm2004.pdf
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html