Turn restriction routing

Last updated August 21, 2024

A routing algorithm decides the path followed by a packet from the source to destination routers in a network. An important aspect to be considered while designing a routing algorithm is avoiding a deadlock. 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.

Reason for deadlock

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. The main reason for a deadlock is the cyclic acquisition of channels in the network.^[2] 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.

Solution to deadlock

Deadlocks can either be detected, broken or avoided from happening altogether. Detecting and breaking deadlocks in the network is expensive in terms of latency and resources. So an easy and inexpensive solution is to avoid deadlocks by choosing routing techniques that prevent cyclic acquisition of channels.^[3]

Logic behind turn restriction routing

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. All the clockwise and anti-clockwise turns that are possible in a non restricted routing algorithm are shown in fig 2.

Fig 3: Dimension-ordered (X-Y) routing XY Turns.jpg — Fig 3: Dimension-ordered (X-Y) routing

Examples of turn restriction routing

A turn restriction routing can be obtained by prohibiting at least one of the four possible clockwise turns and at least one of the four possible anti-clockwise turns in the routing algorithm. This means there are at least 16 (4x4) 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.

Fig 4: West first routing West First Turns.jpg — Fig 4: West first routing

Fig 5: North last routing North Last Turns.jpg — Fig 5: North last routing

Fig 6: Negative first routing Negative First Turns.jpg — Fig 6: Negative first routing

Dimension-ordered (X-Y) routing

Dimension ordered (X-Y) routing^[1] (shown in fig 3) 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

West first routing^[1] (shown in fig 4) restricts all turns to the west direction. This means west direction should be taken first if needed in the proposed route.

North last routing

North last routing^[1] (shown in fig 5) 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

Negative first routing^[1] (shown in fig 6) 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.

Advantages of turn restriction routing

Avoiding deadlocks is less expensive to implement than deadlock detecting and breaking techniques.
Turn restrictions provide alternate minimum length paths as well as non minimum length paths from one node to another, which allows routing around congested or failed links.

For example, consider figure 7 below. Say there are multiple routers, F1, F2 etc., that feed packets to a congested, but low-cost link from source router S to destination router D. Implementing Turn restriction routing means that some of the turns from any of the feeder routers to the congested router S may now be restricted. 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.

Related Research Articles

Routing is the process of selecting a path for traffic in a network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit-switched networks, such as the public switched telephone network (PSTN), and computer networks, such as the Internet.

In computer networking, a routing table, or routing information base (RIB), is a data table stored in a router or a network host that lists the routes to particular network destinations, and in some cases, metrics (distances) associated with those routes. The routing table contains information about the topology of the network immediately around it.

Wormhole flow control, also called wormhole switching or wormhole routing, is a system of simple flow control in computer networking based on known fixed links. It is a subset of flow control methods called Flit-Buffer Flow Control.

In computer networking, the transport layer is a conceptual division of methods in the layered architecture of protocols in the network stack in the Internet protocol suite and the OSI model. The protocols of this layer provide end-to-end communication services for applications. It provides services such as connection-oriented communication, reliability, flow control, and multiplexing.

A distance-vector routing protocol in data networks determines the best route for data packets based on distance. Distance-vector routing protocols measure the distance by the number of routers a packet has to pass; one router counts as one hop. Some distance-vector protocols also take into account network latency and other factors that influence traffic on a given route. To determine the best route across a network, routers using a distance-vector protocol exchange information with one another, usually routing tables plus hop counts for destination networks and possibly other traffic information. Distance-vector routing protocols also require that a router inform its neighbours of network topology changes periodically.

Link-state routing protocols are one of the two main classes of routing protocols used in packet switching networks for computer communications, the others being distance-vector routing protocols. Examples of link-state routing protocols include Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS).

Network congestion in data networking and queueing theory is the reduced quality of service that occurs when a network node or link is carrying more data than it can handle. Typical effects include queueing delay, packet loss or the blocking of new connections. A consequence of congestion is that an incremental increase in offered load leads either only to a small increase or even a decrease in network throughput.

A load-balanced switch is a switch architecture which guarantees 100% throughput with no central arbitration at all, at the cost of sending each packet across the crossbar twice. Load-balanced switches are a subject of research for large routers scaled past the point of practical central arbitration.

Pathfinding or pathing is the search, by a computer application, for the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra's algorithm for finding the shortest path on a weighted graph.

Packet loss occurs when one or more packets of data travelling across a computer network fail to reach their destination. Packet loss is either caused by errors in data transmission, typically across wireless networks, or network congestion. Packet loss is measured as a percentage of packets lost with respect to packets sent.

Flooding is used in computer network routing algorithms in which every incoming packet is sent through every outgoing link except the one it arrived on.

A wireless ad hoc network (WANET) or mobile ad hoc network (MANET) is a decentralized type of wireless network. The network is ad hoc because it does not rely on a pre-existing infrastructure, such as routers or wireless access points. Instead, each node participates in routing by forwarding data for other nodes. The determination of which nodes forward data is made dynamically on the basis of network connectivity and the routing algorithm in use.

The Better Approach to Mobile Ad-hoc Networking (B.A.T.M.A.N.) is a routing protocol for multi-hop mobile ad hoc networks which is under development by the German "Freifunk" community and intended to replace the Optimized Link State Routing Protocol (OLSR) as OLSR did not meet the performance requirements of large-scale mesh deployments.

Routing in delay-tolerant networking concerns itself with the ability to transport, or route, data from a source to a destination, which is a fundamental ability all communication networks must have. Delay- and disruption-tolerant networks (DTNs) are characterized by their lack of connectivity, resulting in a lack of instantaneous end-to-end paths. In these challenging environments, popular ad hoc routing protocols such as AODV and DSR fail to establish routes. This is due to these protocols trying to first establish a complete route and then, after the route has been established, forward the actual data. However, when instantaneous end-to-end paths are difficult or impossible to establish, routing protocols must take to a "store and forward" approach, where data is incrementally moved and stored throughout the network in hopes that it will eventually reach its destination. A common technique used to maximize the probability of a message being successfully transferred is to replicate many copies of the message in hopes that one will succeed in reaching its destination.

Bufferbloat is a cause of high latency and jitter in packet-switched networks caused by excess buffering of packets. Bufferbloat can also cause packet delay variation, as well as reduce the overall network throughput. When a router or switch is configured to use excessively large buffers, even very high-speed networks can become practically unusable for many interactive applications like voice over IP (VoIP), audio streaming, online gaming, and even ordinary web browsing.

In queueing theory, a discipline within the mathematical theory of probability, the backpressure routing algorithm is a method for directing traffic around a queueing network that achieves maximum network throughput, which is established using concepts of Lyapunov drift. Backpressure routing considers the situation where each job can visit multiple service nodes in the network. It is an extension of max-weight scheduling where each job visits only a single service node.

In computer networking, a flit is a link-level atomic piece that forms a network packet or stream. The first flit, called the header flit holds information about this packet's route and sets up the routing behavior for all subsequent flits associated with the packet. The header flit is followed by zero or more body flits, containing the actual payload of data. The final flit, called the tail flit, performs some book keeping to close the connection between the two nodes.

The STC104 switch, also known as the C104 switch in its early phases, is an asynchronous packet-routing chip that was designed for building high-performance point-to-point computer communication networks. It was developed by INMOS in the 1990s and was the first example of a general-purpose production packet routing chip. It was also the first routing chip to implement wormhole routing, to decouple packet size from the flow-control protocol, and to implement interval and two-phase randomized routing.

A butterfly network is a technique to link multiple computers into a high-speed network. This form of multistage interconnection network topology can be used to connect different nodes in a multiprocessor system. The interconnect network for a shared memory multiprocessor system must have low latency and high bandwidth unlike other network systems, like local area networks (LANs) or internet for three reasons:

Deterministic Networking (DetNet) is an effort by the IETF DetNet Working Group to study implementation of deterministic data paths for real-time applications with extremely low data loss rates, packet delay variation (jitter), and bounded latency, such as audio and video streaming, industrial automation, and vehicle control.

References

1 2 3 4 5 CHRISTOPHER J. GLASS AND LIONEL M. NI. "The Turn Model for Adaptive Routing" (PDF). Michigan State University. Archived from the original (PDF) on 2016-12-03. Retrieved 2016-12-02.
↑ Coulouris, George (2012). Distributed Systems Concepts and Design. Pearson. ISBN 978-0-273-76059-7.
↑ Havender, James W (1968). "Avoiding deadlock in multitasking systems". IBM Systems Journal. 7 (2): 74–84. doi:10.1147/sj.72.0074. Archived from the original on 2012-02-24. Retrieved 2016-11-28.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:3-1] 1 2 3 4 5 CHRISTOPHER J. GLASS AND LIONEL M. NI. "The Turn Model for Adaptive Routing" (PDF). Michigan State University. Archived from the original (PDF) on 2016-12-03. Retrieved 2016-12-02.

[2] Coulouris, George (2012). Distributed Systems Concepts and Design. Pearson. ISBN 978-0-273-76059-7.

[3] Havender, James W (1968). "Avoiding deadlock in multitasking systems". IBM Systems Journal. 7 (2): 74–84. doi:10.1147/sj.72.0074. Archived from the original on 2012-02-24. Retrieved 2016-11-28.

[1]

[2]

[3]