User:Ashishjoseph1991/sandbox
 | This is a user sandbox of Ashishjoseph1991. You can use it for testing or practicing edits. This is not the sandbox where you should draft your assigned article for a dashboard.wikiedu.org course. To find the right sandbox for your assignment, visit your Dashboard course page and follow the Sandbox Draft link for your assigned article in the My Articles section. |
A routing algorithm decides the path followed by a packet from the source to destination in a network. An important aspect to be considered while designing a routing algorithm is avoiding a deadlock. Turn restriction routing is one such algorithm for mesh-family of topologies which avoids deadlocks by restricting the types of turns that are allowed in the algorithm.
A deadlock is a situation in which no further transport of packets can take place due to the saturation of network resources like buffers or links. The main reason for a deadlock is the cyclic acquisition of channels in the network[3]. For example, consider there are four channels in a network. Four packets have filled up the input buffers of these four channels and needs to be forwarded to the next channel. Now assume that the output buffers of all these channels are also filled with packets that need to be transmitted to the next channel. If these four channels form a cycle, it is impossible to transmit packets any further because the output buffers and input buffers of all channels are already full. This is known as cyclic acquisition of channels and this results in a deadlock.
Deadlocks can be detected, broken[4] or avoided. Detecting and breaking deadlocks is expensive in terms of latency and resources[4]. So an easy and inexpensive way is to avoid deadlocks from happening in the network by avoiding routing techniques that could result in a cyclic acquisition of channels.[5]
Logic behind turn restriction routing derives from a key observation. A cyclic acquisition of channels can take place only if all the four possible clockwise (or anti-clockwise) turns have occurred. This means deadlocks can be avoided by prohibiting at least one of the clockwise turns and one of the anti-clockwise turns.
A turn restriction routing can be obtained by prohibiting at least one of the 4 possible clockwise turns and at least one of the four possible anti-clockwise turns in the routing algorithm. This means there are 16 (4x4)[7] possible turn restriction routing techniques as you have 4 clockwise turns and 4 anti-clockwise turns to choose from. Some of these techniques have been listed below.
X-Y routing restricts all turns from y-dimension to x-dimension. This prohibits two anti-clockwise and two clockwise turns which is more than what is actually required. Even then since it restricts the number of turns that are allowed we can tell that this is an example for turn restriction routing.
West first routing restricts all turns to the west direction. This means west direction should be taken first if needed in the proposed route.
North last routing restricts turning to any other direction if the current direction is north. This means north direction should be taken last if needed in the proposed route.
Negative first routing restricts turning to a negative direction while the current direction is positive. West is considered as the negative direction in X-dimension and south is considered as the negative direction in Y-dimension. This means any hop in one of the negative directions should be taken before taking any other turn.
- Provides alternate minimum length paths from one node to another.
- Provides non-minimum length path which allows routing around congested or failed links.
References
[edit]- ^ Solihin, Yan (2009). fundamentals of parallel computer architecture. solihin books. pp. 375–377. ISBN 9780984163007.
- ^ Solihin, Yan (2009). fundamentals of parallel computer architecture. solihin books. pp. 374–375. ISBN 9780984163007.
- ^ Coulouris, George (2012). Distributed Systems Concepts and Design. Pearson. p. 716. ISBN 978-0-273-76059-7.
- ^ a b c Solihin, Yan (2009). fundamentals of parallel computer architecture. solihin books. p. 375. ISBN 9780984163007.
- ^ Havender, James W (1968). "Avoiding deadlock in multitasking systems". IBM Systems Journal. 7.
- ^ a b c d e f Solihin, Yan (2009). Fundamentals of parallel computer architecture. Solihin books. p. 376. ISBN 9780984163007.
- ^ a b Solihin, Yan (2009). Fundamentals of parallel computer architecture. solihin books. pp. 376–377. ISBN 9780984163007.