Queueing in switched networks
Abstract.
A switched network is a system with several traffic flows,
constraints on which flows can be served simultaneously, and a
scheduling algorithm which decides which flows should be served. For
example, a crossroads has 12 traffic flows (incoming traffic on each
road can turn left or right or go straight); you are only allowed to
turn when there is no oncoming traffic; and traffic lights regulate
which lanes can move. Switched networks have been used to model the
silicon core of an Internet router, the bandwidth sharing mechanism of
TCP, and the dynamics of an wavelength-routed optical network. In this
talk, I will describe the mathematics for modelling and designing
scheduling algorithms.
Bibliographic references are given in the notes section of each Powerpoint slide.
See also a draft paper, Heavy traffic analysis of optimal scheduling algorithms for switched networks.
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.