Routing in interconnection networks

Summary form only given, as follows. Packet-switched interconnection networks, such as the one connecting 65,000 processors in the Connection Machine, offer the possibility of programmable connections between processors. Processors that are not directly connected communicate by means of multiple-hop routes so that the processors appear to be connected at a higher logical level. Special-purpose hardware design and a variety of dynamic control devices are used to gain speed. A similar style of packet switching has also been proposed for wide-area networks. Traffic congestion must be made to diffuse quickly through the use of fast, local mechanisms. The author discusses mathematical and information-theoretic tools for analysis and modeling, with the goal of both understanding the general design problem and of suggesting new architectures for its solution. He focuses on deflection routing, originally termed 'hot-potato' routing, which is a technique for maintaining bounded buffers in a packet-switched communication network. If, owing to congestion at a switch, not all packets can be sent out along shortest paths to their destinations, some packets are sent out on other links. The penalty is an increase in the distance traveled by packets, and the reward is the simplicity of switch design resulting from the absence of large buffers and routing tables. Traditional store-and forward networks use extensive computation at the nodes to determine packet routes in order to use transmission bandwidth sparingly. In contrast, deflection leads to simple switches by making liberal use of transmission bandwidth. Both the worst-case and average-case performance of deflection routing are discussed. Approximate analysis of the transient and steady-state behavior of deflection routing in hypercube and shufflelike networks leads to a model in which the progress of a typical packet is described by a random walk on the network graph.