Tutorial on queueing theory for switched networks
ICMS workshop for young researchers, on stochastic processes in communication networks. Edinburgh, 7–11 June 2010.
(programme)
[slides pdf]
Abstract.
A switched network consists of a collection of
queues, with constraints on which queues may be served simultaneously,
plus a policy for choosing which set of queues to serve at a given
instant. Switched networks can be used to model diverse communications
systems such as Internet routers, bandwidth sharing by TCP, and
wireless networks. I will describe these modelling applications. I
will also describe several approaches to performance analysis:
stability analysis via Lyapunov functions, heavy traffic analysis,
overload analysis, and underload analysis using large deviations
theory.
A four-way road roundabout is an example of a switched network.
For example, if there is a steady flow of cars travelling from south to north,
then no cars from the west entrance can enter. These two diagrams show
two possible sets of traffic flows. If each lane can carry at most
x cars per minute, then in the left-hand diagram the roundabout
can carry up to 3x cars per minute, whereas in the right-hand diagram
the roundabout is only carrying up to 2x cars per minute.
An input-queued switch is the piece of silicon in the heart of
high-end Internet routers. It is an example of a switched network.
This diagram shows an input-queued switch with three inputs and three outputs.
At each clock tick, the switch chooses which inputs to connect to which
outputs, and it sends packets along the connections. The two diagrams here
show two different sets of connections.
The switch chooses the connections based on how much work there is
at each input for each output. In the left-hand diagram the switch has
chosen badly, since it connects the bottom input to the middle output—but there are no packets waiting here to be sent.