A four-node ring network carries packets clockwise. Each node has a buffer for packets arriving from its neighbour. Under heavy traffic, every node's buffer fills with a packet that needs to move on to the next node, whose buffer is also full. Every packet waits for space that only the next packet can free by moving. The ring has no faulty part, and it has stopped.
How do networks deadlock through their buffers, and how is it prevented?
The obvious defence is bigger buffers: if packets have more room, they will not get stuck. Bigger buffers make the deadlock rarer, not impossible: a burst big enough still fills every buffer around the cycle. The problem is the shape of the dependencies, not their size. As long as a packet holding a buffer can wait for a buffer that, through a chain, waits for it, deadlock is possible.
Draw a channel dependency graph: one node per buffer (or virtual channel), an arrow from buffer X to buffer Y if a packet in X can wait for Y. Routing deadlock is possible exactly when this graph has a cycle. A ring's graph is a cycle by construction; a mesh's has cycles if packets can turn in every direction.
Fix | How it breaks the cycle | Where used |
|---|---|---|
Turn restrictions | Forbid enough turns that no cycle can form; XY routing forbids all turns from Y back to X (lesson 8.9) | Meshes |
Dateline (extra virtual channel) | Packets start on VC 0 and move to VC 1 when they cross a chosen point (the dateline); no packet goes from VC 1 back to VC 0, so the cycle is cut into a line | Rings and tori |
Escape channel | Packets may route adaptively on some VCs, but can always fall back to an escape VC that follows a deadlock-free route; a stuck packet always has a way out | Adaptive routing |
The dateline is the classic ring fix: on a 4-node ring with the dateline between node 3 and node 0, a packet travelling from node 2 to node 1 uses VC 0 for 2→3, then VC 1 for 3→0 and 0→1. The dependency graph is VC 0 links → VC 1 links, which ends; nothing points back from VC 1 to VC 0.
Network | Routing-deadlock fix |
|---|---|
On-chip meshes | XY (dimension-order) routing: turn restrictions, no extra VCs needed. |
Rings and tori | A dateline with two virtual channels per direction. |
Adaptive networks | Escape virtual channels with a deadlock-free routing function underneath. |
These fixes cover routing deadlock only. Message-dependent deadlock (lesson 9.4) needs separate classes in addition: a ring with a dateline and requests and responses on the same VCs can still deadlock through the protocol.
A ring network (illustrative) was designed with large buffers and no dateline, on the reasoning that with 16 entries per node "it would never fill". It passed months of simulation with realistic traffic and deadlocked in the lab under a stress test that sent every node's traffic two hops clockwise at once. Adding a dateline VC fixed it; the buffers could then be made smaller.
The dependency cycle is still there; a large enough burst can still fill every buffer around it, so deadlock becomes rarer, not impossible.
VC 0 throughout: it never crosses the dateline.
Routing deadlock is a cycle of packets holding buffers while waiting for the next one.
It is possible exactly when the channel dependency graph has a cycle; buffer size does not change that.
Fix it with turn restrictions, a dateline VC, or escape channels, and handle message classes separately on top.