A routing loop is a common problem with various types of
networks, particularly
computer networks. They are formed when an error occurs in the operation of the
routing algorithm
Routing is the process of selecting a path for traffic in a Network theory, network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit switching, circuit-switched networks, such as ...
, and as a result, in a group of nodes, the path to a particular destination forms a loop.
In the simplest version, a routing loop of size two,
node A thinks that the path to some destination (call it C) is through its neighbouring node, node B. At the same time, node B thinks that the path to C starts at node A.
Thus, whenever traffic for C arrives at either A or B, it will loop endlessly between A and B, unless some mechanism exists to prevent that behaviour.
How a routing loop can form
For example, in this illustration, node A is transmitting data to node C via node B. If the link between nodes B and C goes down and B has not yet informed node A about the breakage, node A transmits the data to node B assuming that the link A-B-C is operational and of lowest cost. Node B knows of the broken link and tries to reach node C via node A, thus sending the original data back to node A. Furthermore, node A receives the data that it originated back from node B and consults its routing table. Node A's routing table will say that it can reach node C via node B (because it still has not been informed of the break) thus sending its data back to node B creating an infinite loop. This routing loop problem is also called a ''two-node loop''.
How a routing loop can persist
Consider now what happens if both the link from A to C and the link from B to C vanish at the same time (this can happen if node C has crashed). A believes that C is still reachable through B, and B believes that C is reachable through A. In a simple reachability protocol, such as
EGP, the routing loop will persist forever.
In a naive distance-vector protocol, such as the
routing information protocol, the loop will persist until the metrics for C reach ''infinity'' (the maximum number of routers that a packet can traverse in
RIP
Rest in peace (RIP), a phrase from the Latin (), is sometimes used in traditional Christian services and prayers, such as in the Catholic, Lutheran, Anglican, and Methodist denominations, to wish the soul of a decedent eternal rest and peace.
...
is 15. The value 16 is considered infinity and the packet is discarded).
Prevention and mitigations
In a
link-state routing protocol
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 ...
, such as
OSPF or
IS-IS, a routing loop disappears as soon as the new network topology is flooded to all the routers within the routing area. Assuming a sufficiently reliable network, this happens within a few seconds.
Newer
distance-vector routing protocol
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. ...
s like
EIGRP
Enhanced Interior Gateway Routing Protocol (EIGRP) is an advanced distance-vector routing protocol that is used on a computer network for automating routing decisions and configuration. The protocol was designed by Cisco Systems as a proprietary pr ...
,
DSDV
Destination-Sequenced Distance-Vector Routing (DSDV) is a table-driven routing scheme for ad hoc mobile networks based on the Bellman–Ford algorithm. It was developed by C. Perkins and P. Bhagwat in 1994. The main contribution of the algorithm w ...
, and
Babel
Babel is a name used in the Hebrew Bible for the city of Babylon and may refer to:
Arts and media Written works Books
*Babel (book), ''Babel'' (book), by Patti Smith
* Babel (2012 manga), ''Babel'' (2012 manga), by Narumi Shigematsu
* Babel (20 ...
have built-in loop prevention: they use algorithms that assure that routing loops can never happen, not even transiently. Older routing protocols like
RIP
Rest in peace (RIP), a phrase from the Latin (), is sometimes used in traditional Christian services and prayers, such as in the Catholic, Lutheran, Anglican, and Methodist denominations, to wish the soul of a decedent eternal rest and peace.
...
and
IGRP do not implement the newest forms of loop prevention and only implement mitigations such as
split horizon
In computer networking, split-horizon route advertisement is a method of preventing routing loops in distance-vector routing protocols by prohibiting a router from advertising a route back onto the interface from which it was learned.
The concep ...
,
route poisoning Route poisoning is a method to prevent a router from sending packets through a route that has become invalid within computer networks. Distance-vector routing protocols in computer networks use route poisoning to indicate to other routers that a ro ...
, and
holddown
Holddown works by having each router start a timer when they first receive information about a network that is unreachable. Until the timer expires, the router will discard any subsequent route messages that indicate the route is in fact reachable ...
timers.
See also
*
Switching loop
References
{{reflist
Routing