Editing Wormhole switching (section)

== Mechanism principle ==
In the wormhole flow control, each packet is broken into small pieces called [[flits (computer networking)|flits]] (flow control units or flow control digits).

Commonly, the first flits, called the header flits, holds information about this packet's route (for example, the destination address) and sets up the routing behavior for all subsequent flits associated with the packet. The header flits are followed by zero or more body flits which contain the actual payload of data. Some final flits, called the tail flits, perform some bookkeeping to close the connection between the two nodes.

In wormhole switching, each buffer is either idle, or allocated to one packet. A header flit can be forwarded to a buffer if this buffer is idle. This allocates the buffer to the packet. A body or trailer flit can be forwarded to a buffer if this buffer is allocated to its packet and is not full. The last flit frees the buffer. If the header flit is blocked in the network, the buffer fills up, and once full, no more flits can be sent: this effect is called "back-pressure" and can be propagated back to the source.

The name "wormhole" 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. Since a packet is transmitted flit by flit, it may occupy several flit buffers along its path, creating a worm-like image.

This behaviour is quite similar to [[cut-through switching]],<ref>Stefan Haas. [http://inspirehep.net/record/887357/files/cer-002474543.pdf "The IEEE 1355 Standard: Developments, Performance and Application in High Energy Physics"]. 1998. p. 59.</ref> commonly called "virtual cut-through," the major difference being that cut-through flow control allocates buffers and channel bandwidth on a packet level, while wormhole flow control does this on the flit level.

In case of circular dependency, this back-pressure can lead to deadlock.

In most respects, wormhole is very similar to [[Asynchronous Transfer Mode|ATM]] or [[Multiprotocol Label Switching|MPLS]] forwarding, with the exception that the ''cell'' does not have to be [[queue (data structure)|queue]]d.

One thing special about wormhole flow control is the implementation of virtual channels:
<blockquote>
A virtual channel holds the state needed to coordinate the handling of the flits of a packet over a channel.  At a minimum, this state identifies the output channel of the current node for the next hop of the route and the state of the virtual channel (idle, waiting for resources, or active).  The virtual channel may also include pointers to the flits of the packet that are buffered on the current node and the number of flit buffers available on the next node.<ref name="Dally and Towles"/>{{rp|237}}
</blockquote>