The concept was suggested in 1974 by Torsten Cegrell, and originally implemented in the ARPANET-inspired Swedish network TIDAS.[1][2][3]
Terminology
Here is some basic terminology:
Route poisoning: if a node N learns that its route to a destination D is unreachable, inform that to all nodes in the network by sending them a message stating that the distance from N to D, as perceived by N, is infinite.
Split horizon rule: if a node N uses interface I to transmit to a given destination D, N should not send through I new information about D.
Poison reverse rule: if a node N uses interface I to transmit to a given destination D, N sends through I the information that its cost-to-go to D is infinite.
Whereas under split horizon N does not send any information through I, under poison reverse node N tells a white-lie.
Example
In this example, network node A routes packets to node B in order to reach node C. The links between the nodes are distinct point-to-point links.
According to the split-horizon rule, node A does not advertise its route for C (namely A to B to C) back to B. On the surface, this seems redundant since B will never route via node A because the route costs more than the direct route from B to C. However, if the link between B and C goes down, and B had received a route from A to C, B could end up using that route via A. A would send the packet right back to B, creating a loop. This is the Count to Infinity Problem. With the split-horizon rule in place, this particular loop scenario cannot happen, improving convergence time in complex, highly-redundant environments.
Split-horizon routing with poison reverse[4] is a variant of split-horizon route advertising in which a router actively advertises routes as unreachable over the interface over which they were learned by setting the route metric to infinite (16 for RIP). The effect of such an announcement is to immediately remove most looping routes before they can propagate through the network.
The main disadvantage of poison reverse is that it can significantly increase the size of routing announcements in certain fairly common network topologies, but it allows for the improvement of the overall efficiency of the network in case of faults. Split horizon states that if a neighboring router sends a route to a router, the receiving router will not propagate this route back to the advertising router on the same interface.
With route poisoning, when a router detects that one of its connected routes has failed, the router will poison the route by assigning an infinite metric to it and advertising it to neighbors. When a router advertises a poisoned route to its neighbors, its neighbors break the rule of split horizon and send back to the originator the same poisoned route, called a poison reverse. In order to give the router enough time to propagate the poisoned route and to ensure that no routing loops occur while propagation occurs, the routers implement a hold-down mechanism.
Poison Reverse
Poison Reverse is often used within distance-vector routing to solve the count-to-infinity problem. Practically, poison reverse can be thought of as an alternative to split horizon. With poison reverse, route advertisements that would be suppressed by split horizon are instead advertised with a distance of infinity.
The basic idea of poison reverse is to make sure that a path does not turn back into the same node if a cost has changed within the network. An example of this would be: Node Z routes via node Y to destination X. If the cost between Y and X increases, the count to infinity problem will occur. To avoid it, we implement poison reverse. As long as Z routes via node Y to get to X, Z will tell a white lie to Y: Z will announce to Y an infinite cost to the destination X.
The numbers on the edges are the costs of the links.
Following this topology, we build the distance vectors of all nodes in the network:
Destination
to Z
to Y
to X
from Z
0
1
3
from Y
1
0
2
from X
3
2
0
The first, second and third lines correspond to node Z, node Y and node X distance vectors, respectively.
The following matrix contains the estimates of the distances from Z to all the other nodes in the network through each of its neighbors.
Destination
via Z
via Y
via X
to Z
0
X
X
to Y
X
1
32
to X
X
3
30
As Z routes via Y to get to X, the cost-to-go from Z to X is 3. The poison reverse kicks in when a node broadcasts its distance vector to its neighbors. The distance vectors broadcast by Z are:
To Y: node Z advertises its distance vector, replacing the last element by ∞, i.e., it sends [0, 1, ∞]
To X: node Z advertises its distance vector, without any replacements, i.e., it sends [0, 1, 3]
As we see in the distance vector that is broadcast to node Y the end destination X has an infinity value.
Poison reverse solves the count-to-infinity problem since if the link between Y and X has its cost increased to, say, 70, then Y and Z will not bounce between each other and instead directly try another path. Alternatively, if poison reverse is not used, when the link between Y and X has its cost increased, Y will announce the news to Z. However, before announcing, Y may leverage the fact that Z can reach X with a cost of 3 to decide that Y can reach X with a cost of 4. Then, Z updates its cost-to-go to X, through Y, as 5. Following that, Y updates its cost-to-go to X, through Z, as 6, and so on, until cost-to-go from Z to X reaches 30. At this point, after 30 iterations, the algorithm converges.
Poison reverse doesn't always work. For example:
If the link between C and D would fail node C can still try to go through B to get to the destination. B was already routing through A, and will continue doing so. Now, A cannot route through B, due to poison reverse, but at this point A will eventually receive a message from C announcing that C has a route with cost 7 to D, where c(C,B)+distance(B,D)=3+(3+1)=7. Then, A will rely on C to route to D. In summary, after failure of CD, C will update, followed by A, B, C, A, B, C and so on. From there we have a loop that we can not solve with poison reverse.[5]
This can though be completed with an implementation of a distance vector protocol called RIP.
Implementations
The split-horizon method is effective and simple to implement, and is therefore used by most distance-vector protocols. It is notably used by:
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.
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 source to destination. The largest number of hops allowed for RIP is 15, which limits the size of networks that RIP can support.
Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.
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 protocol, available only on Cisco routers. In 2013, Cisco permitted other vendors to freely implement a limited version of EIGRP with some of its associated features such as High Availability (HA), while withholding other EIGRP features such as EIGRP stub, needed for DMVPN and large-scale campus deployment. Information needed for implementation was published with informational status as RFC 7868 in 2016, which did not advance to Internet Standards Track level, and allowed Cisco to retain control of the EIGRP protocol.
A* is a graph traversal and path search algorithm, which is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. One major practical drawback is its space complexity, as it stores all generated nodes in memory. Thus, in practical travel-routing systems, it is generally outperformed by algorithms that can pre-process the graph to attain better performance, as well as memory-bounded approaches; however, A* is still the best solution in many cases.
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).
The Optimized Link State Routing Protocol (OLSR) is an IP routing protocol optimized for mobile ad hoc networks, which can also be used on other wireless ad hoc networks. OLSR is a proactive link-state routing protocol, which uses hello and topology control (TC) messages to discover and then disseminate link state information throughout the mobile ad hoc network. Individual nodes use this topology information to compute next hop destinations for all nodes in the network using shortest hop forwarding paths.
In mathematics, a norm is a function from a real or complex vector space to the non-negative real numbers that behaves in certain ways like the distance from the origin: it commutes with scaling, obeys a form of the triangle inequality, and is zero only at the origin. In particular, the Euclidean distance in a Euclidean space is defined by a norm on the associated Euclidean vector space, called the Euclidean norm, the 2-norm, or, sometimes, the magnitude of the vector. This norm can be defined as the square root of the inner product of a vector with itself.
The diffusing update algorithm (DUAL) is the algorithm used by Cisco's EIGRP routing protocol to ensure that a given route is recalculated globally whenever it might cause a routing loop. It was developed by J.J. Garcia-Luna-Aceves at SRI International. The full name of the algorithm is DUAL finite-state machine. EIGRP is responsible for the routing within an autonomous system, and DUAL responds to changes in the routing topology and dynamically adjusts the routing tables of the router automatically.
The Neighbor Discovery Protocol (NDP), or simply Neighbor Discovery (ND), is a protocol of the Internet protocol suite used with Internet Protocol Version 6 (IPv6). It operates at the link layer of the Internet model, and is responsible for gathering various information required for network communication, including the configuration of local connections and the domain name servers and gateways.
A path-vector routing protocol is a network routing protocol which maintains the path information that gets updated dynamically. Updates that have looped through the network and returned to the same node are easily detected and discarded. This algorithm is sometimes used in Bellman–Ford routing algorithms to avoid "Count to Infinity" problems.
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 considered from their routing tables. Unlike the split horizon with poison reverse, route poisoning provides for sending updates with unreachable hop counts immediately to all the nodes in the network.
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.
Geographic routing is a routing principle that relies on geographic position information. It is mainly proposed for wireless networks and based on the idea that the source sends a message to the geographic location of the destination instead of using the network address. In the area of packet radio networks, the idea of using position information for routing was first proposed in the 1980s for interconnection networks. Geographic routing requires that each node can determine its own location and that the source is aware of the location of the destination. With this information, a message can be routed to the destination without knowledge of the network topology or a prior route discovery.
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, and as a result, in a group of nodes, the path to a particular destination forms a loop.
The Wireless Routing Protocol (WRP) is a proactive unicast routing protocol for mobile ad hoc networks (MANETs).
IEEE 802.1aq is an amendment to the IEEE 802.1Q networking standard which adds support for Shortest Path Bridging (SPB). This technology is intended to simplify the creation and configuration of Ethernet networks while enabling multipath routing.
An Internet Protocol Version 6 address is a numeric label that is used to identify and locate a network interface of a computer or a network node participating in a computer network using IPv6. IP addresses are included in the packet header to indicate the source and the destination of each packet. The IP address of the destination is used to make decisions about routing IP packets to other networks.
In a router, route redistribution allows a network that uses one routing protocol to route traffic dynamically based on information learned from another routing protocol.
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.
