Turn restriction routing

A routing algorithm decides the path followed by a packet from the source to destination routers in a network.

Turn restriction routing[1] is a routing algorithm for mesh-family of topologies which avoids deadlocks by restricting the types of turns that are allowed in the algorithm while determining the route from source node to destination node in a network.A deadlock (shown in fig 1) is a situation in which no further transportation of packets can take place due to the saturation of network resources like buffers or links.

So an easy and inexpensive solution is to avoid deadlocks by choosing routing techniques that prevent cyclic acquisition of channels.

A cyclic acquisition of channels can take place only if all the four possible clockwise (or anti-clockwise) turns have occurred.

Some of these techniques have been listed below.Dimension ordered (X-Y) routing[1] (shown in fig 3) restricts all turns from y-dimension to x-dimension.

Those feeder routers may have to use a longer path to get to destination D, thereby decongesting the link from S to D to an extent.

Fig 1: Figure shows four channels with both input and output buffers full. All packets in output buffers are to be forwarded to next channel. But since their input buffers are full, this forwarding cannot take place. As a result, no packet can be moved any further. This results in a deadlock.
Fig 2: All possible turns in a network route- clockwise and anti-clockwise.
Fig 3: Dimension-ordered (X-Y) routing
Fig 4: West first routing
Fig 5: North last routing
Fig 6: Negative first routing
Fig 7: Topology of four routers F1, F2, S and D connected to each other. Turn restrictions could ease congestion on link S-D to an extent.