next up previous
Next: Results Up: Realisation and Performance of Previous: Network topologies

Network Routing

The STC104 contains a non-blocking crossbar switch, which uses wormhole routing [6]. The routing decision is made as soon as the packet header arrives, the header is then sent to the chosen output link and the rest of the packet follows without being internally buffered. This implies that packets can be passing through several switches at the same time. The packet header creates a temporary circuit (`worm hole') through which the data flows. As the end of the packet passes through each device the circuit closes. Worm-hole routing minimises latency and buffering requirements compared to switches using store and forward techniques. It also has the advantage that it allows arbitrary length packets. The packet latency across the STC104 has been measured to be .

Under random traffic the performance of a network is limited by head-of-line blocking. When several packets are contending for the same output link and a packet is stalled because the required output link is busy, all packets in the input queue behind it are also blocked, even if their selected output link is free. Each STC104 switch can buffer 43 bytes in the input port, and 23 bytes in the output port. This effect limits the theoretical performance of a cross-bar switch under random traffic to about 60% of the maximum cross-sectional bandwith [7].

The STC104 supports a locally adaptive routing scheme which allows packets to be sent down any free output link in a programmed set of consecutive links. This improves performance by ensuring that there are no packets waiting to use one link when an equivalent link is idle. A set of links used to access a common destination can therefore be logically grouped together, increasing the aggregate throughput to the destination. This grouped adaptive routing allows efficient load-balancing in multi-stage networks [8] and also enables a degree of automatic fault-tolerance [9]. On the grid topology grouped adaptive routing is used on parallel links between adjacent routers. For Clos networks, all the links from the terminal stage switches to the centre stage can be grouped, because all the centre stage switches are equivalent. Parallel links from the centre stage to the terminal stage are also grouped.


next up previous
Next: Results Up: Realisation and Performance of Previous: Network topologies

Roger Heeley
Fri Sep 26 17:00:08 MET DST 1997