In
computer networking
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 ...
, split-horizon route advertisement is a method of preventing
routing loop
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 destin ...
s in
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 by prohibiting a router from advertising a route back onto the interface from which it was learned.
The concept was suggested in 1974 by
Torsten Cegrell, and originally implemented in the
ARPANET
The Advanced Research Projects Agency Network (ARPANET) was the first wide-area packet-switched network with distributed control and one of the first networks to implement the TCP/IP protocol suite. Both technologies became the technical fou ...
-inspired Swedish network TIDAS.
Terminology
Here is some basic terminology:
*
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 ...
: 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 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
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. ...
. 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:
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.
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
, 1, ∞
To X: node Z advertises its distance vector, without any replacements, i.e., it sends
, 1, 3
As we see in the distance vector that is broadcast to node Y the end destination X has an infinity value.
Poised 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 poised 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, util 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:
![Network with single point of failure1](https://upload.wikimedia.org/wikipedia/commons/0/0b/Network_with_single_point_of_failure1.svg)
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.
[https://people.mpi-sws.org/~gummadi/teaching/sp07/datanets/homework/homework2solution.pdf ]
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:
*
RIP
*
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 ...
*
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 ...
*
VPLS
Virtual Private LAN Service (VPLS) is a way to provide Ethernet-based multipoint to multipoint communication over IP or MPLS networks. It allows geographically dispersed sites to share an Ethernet broadcast domain by connecting sites through ps ...
, which uses the split horizon technique to avoid loops in the forwarding plane
*
Babel, which applies split-horizon to wired links only
See also
*
Split-horizon DNS
In computer networking, split-horizon DNS (also known as split-view DNS, split-brain DNS, or split DNS) is the facility of a Domain Name System (DNS) implementation to provide different sets of DNS information, usually selected by the source addre ...
, a similar concept in
DNS
The Domain Name System (DNS) is a hierarchical and distributed naming system for computers, services, and other resources in the Internet or other Internet Protocol (IP) networks. It associates various information with domain names assigned to ...
performing selective publishing of information
*
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 ...
*
CISCO Certification
References
{{cite book
, title= Computer Networking: A top-Down Approach, Seventh Edition
, location= Harlow, England
, publisher= Pearson
, page= 418
, authors= James F. Kurose, Keith W. Ross
, year= 2017
External links
* "Split Horizon" and "Split Horizon with Poison Reverse" i
Convergence in RIP Internetworks from Microsoft TechNet.
Routing protocols
Internet Standards
Internet protocols