Wormhole switching

From Wikipedia, the free encyclopedia

Wormhole switching or Wormhole routing is a system of simple flow control in computer networking based on known fixed links. Large network packets are broken into small pieces called flits (flow units). The first flit (i.e. address) sets up the routing behavior for all subsequent flits associated with the packet. The name plays on the way packets are sent over the links: the address is so short that it can be translated before the message itself arrives. This allows the router to quickly set up the routing of the actual message and then "bow out" of the rest of the conversation. The transmission from the source node to the destination node is done through a sequence of routers. Flits of a single packet may occupy multiple consecutive routers and links, like a worm.

Actually, switching is the more appropriate term than routing [1]. "Routing" defines the route or path taken to reach the destination. Wormhole technique does not dictate the route (to where) but selects when the packet moves forward from a router (when). Cut-through switching forwards packets in similar manner, but ensures that packet fits into single buffer. Consequently, cut-through does not occupy multiple links/routers.

In most respects, wormhole is very similar to ATM or MPLS forwarding, with the exception that the cell does not have to be queued.


Wormhole technique is primarily used in multiprocessor systems, notably hypercubes. In a hypercube computer each CPU is attached to several neighbours in a fixed pattern, which reduces the number of hops from one CPU to another. Each CPU is given a number (typically only 8-bit to 16-bit), which is its network address, and packets to CPUs are sent with this number in the header. When the packet arrives at an intermediate router for forwarding, the router examines the header (very quickly), sets up a circuit to the next router, and then bows out of the conversation. This reduces latency (delay) notably compared to store-and-forward switching that waits for the whole packet before forwarding.

[edit] See also

[edit] References

  1. ^ John L. Hennessy and David A. Patterson (2006). "Appendix E.5", Computer Architecture: A Quantitative Approach, Fourth Edition, Morgan Kaufmann Publishers, Inc. ISBN 9780123704900.