The task of designing an efficient packet routing algorithm is central to the design of most large-scale general-purpose parallel computers. In fact, even the basic unit of time in some parallel machines is measured in terms of how fast the packet router operates. For example, the speed of an algorithm in the Connection Machine CM-2 is often measured in terms of routing cycles (roughly the time to route a random permutation) or petit cycles (the time to perform an atomic step of the routing algorithm). Similarly, the performance of a machine like the BBN Butterfly [5] is substantially influenced by the speed and rate of successful delivery of its router.
Packet routing also provides an important bridge between theoretical computer science and applied computer science; it is through packet routing that a real machine such as the Connection Machine is able to simulate an idealized machine such as the CRCW PRAM. More generally, getting the right data to the right place at the right time is an important, interesting, and challenging problem. Not surprisingly, it has also been the subject of a great deal of research.