A routing loop is a common problem with various types of
networks
Network, networking and networked may refer to:
Science and technology
* Network theory, the study of graphs as a representation of relations between discrete objects
* Network science, an academic field that studies complex networks
Mathematics
...
, particularly
computer network
A computer network is a set of computers sharing resources located on or provided by network nodes. The computers use common communication protocols over digital interconnections to communicate with each other. These interconnections are ...
s. 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 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 net ...
, 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
In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex).
Node may refer to:
In mathematics
*Vertex (graph theory), a vertex in a mathematical graph
*Vertex (geometry), a point where two or more curves, lines, ...
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 Routing Information Protocol (RIP) is one of the oldest distance-vector routing protocols 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 sourc ...
, 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 includ ...
, such as
OSPF
Open Shortest Path First (OSPF) is a routing protocol for Internet Protocol (IP) networks. It uses a link state routing (LSR) algorithm and falls into the group of interior gateway protocols (IGPs), operating within a single autonomous syst ...
or
IS-IS
Intermediate System to Intermediate System (IS-IS, also written ISIS) is a routing protocol designed to move information efficiently within a computer network, a group of physically connected computers or similar devices. It accomplishes this b ...
, 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 ...
,
DSDV
Destination-Sequenced Distance-Vector Routing (DSDV) is a table-driven routing scheme for ad hoc mobile networks based on the Bellman–Ford algorithm
The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single sou ...
, 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
Interior Gateway Routing Protocol (IGRP) is a distance vector interior gateway protocol (IGP) developed by Cisco. It is used by routers to exchange routing data within an autonomous system.
IGRP is a proprietary protocol. IGRP was created in ...
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
A switching loop or bridge loop occurs in computer networks when there is more than one layer 2 path between two endpoints (e.g. multiple connections between two network switches or two ports on the same switch connected to each other). The loop ...
References
{{reflist
Routing