UCL >> Computer Science dept >> Networks research group >> Damon Wischik >> Talks >>

The teleology of switched networks

Stochastic Networks Workshop, Cambridge, 9 June 2009 [slides jnt] [slides pdf] [demo nb]
Submitted paper

Abstract.

A switched network is a queueing system in which there are constraints on which queues may be served simultaneously. It runs a scheduling algorithm, that specifies which queues to serve at any instant in time. I will summarize the behaviour of switched networks light load (large deviations), in critical load (state space collapse), and in overload (fluid models). There is a rich structure of optimization problems that ties together these three types of performance analysis.
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.