Routing loop problem
Encyclopedia
A routing loop is a common problem with various types of networks
, particularly computer network
s. They are formed when an error occurs in the operation of the routing algorithm, 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.
, the routing loop will persist forever.
In a naive distance vector protocol, such as RIP, the loop will persist until the metrics for C reach infinity (the maximum no. of routers that a packet can traverse in RIP is 15. The value 16 is considered infinity and the packet is discarded).
, 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 protocols (BGP, EIGRP, DSDV, Babel
) have built-in loop prevention: they use algorithms that assure that routing loops can never happen, not even transiently. Older routing protocols (RIP
) do not implement the newest forms of loop prevention and only implement mitigations such as split horizon
, route poisoning
and holddown timers.
Network theory
Network theory is an area of computer science and network science and part of graph theory. It has application in many disciplines including statistical physics, particle physics, computer science, biology, economics, operations research, and sociology...
, particularly computer network
Computer network
A computer network, often simply referred to as a network, is a collection of hardware components and computers interconnected by communication channels that allow sharing of resources and information....
s. They are formed when an error occurs in the operation of the routing algorithm, 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
Node (computer science)
A node is a record consisting of one or more fields that are links to other nodes, and a data field. The link and data fields are often implemented by pointers or references although it is also quite common for the data to be embedded directly in the node. Nodes are used to build linked, often...
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 the network given below, 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.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 EGPExterior Gateway Protocol
The Exterior Gateway Protocol is a now obsolete routing protocol for the Internet originally specified in 1982 by Eric C. Rosen of Bolt, Beranek and Newman, and David L. Mills. It was first described in RFC 827 and formally specified in RFC 904...
, the routing loop will persist forever.
In a naive distance vector protocol, such as RIP, the loop will persist until the metrics for C reach infinity (the maximum no. of routers that a packet can traverse in RIP is 15. The value 16 is considered infinity and the packet is discarded).
Prevention and mitigations
In a link-state routing protocol, such as OSPF or IS-ISIS-IS
Intermediate System To Intermediate System , is a routing protocol designed to move information efficiently within a computer network, a group of physically connected computers or similar devices....
, 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 protocols (BGP, EIGRP, DSDV, Babel
Babel (protocol)
The Babel routing protocol is a distance-vector routing protocol for Internet Protocol packet-switched networks that is designed to be robust and efficient on both wireless mesh networks and wired networks....
) have built-in loop prevention: they use algorithms that assure that routing loops can never happen, not even transiently. Older routing protocols (RIP
Routing Information Protocol
The Routing Information Protocol is a distance-vector routing protocol, which employs the hop count as a routing metric. RIP prevents routing loops by implementing a limit on the number of hops allowed in a path from the source to a destination. The maximum number of hops allowed for RIP is 15....
) do not implement the newest forms of loop prevention and only implement mitigations such as split horizon
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.-Example:...
, route poisoning
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 route is no longer reachable and should not be...
and holddown timers.