Split horizon route advertisement

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.

"Split horizon" redirects here. For the Domain Name System feature, see Split-horizon DNS.

The concept was suggested in 1974 by Torsten Cegrell, and originally implemented in the Arpanet inspired Swedish network TIDAS.[1][2][3]

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 an implemented algorithm that is often used within distance-vector routing. The use of poison reverse is to solve the count-to-infinity problem (more about the count to infinity problem can be found in distance vector routing). Practically, poison reverse can be thought of as the reverse of 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 Z and Y increases, the count to infinity problem will occur and here we implement the use of poison reverse. As long as Z routes via node Y to get to X, Z will broadcast an infinite cost to the destination X, to the node which Z routes via (Y).

  • the numbers between nodes is the cost of the links.

Following this topology and we assume this distance vector table of Z:

DestinationZYX
Z013
Y102
X320

As Z routes via Y to get to X and because of that have the cost 3. The poison reverse kicks in when we broadcast our distance vector to our neighbors: The distance tables we broadcast is:

To Y: [0, 1, ∞]

To X: [0, 1, 3]

As we see in the distance vector that is broadcast to node Y the end destination X has an infinity value. This solves the count-to-infinity problem since if the link between Y and Z will not bounce between each other and instead directly try another path.

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 A to get to the destination. This will cause B to route through A and from there we have a loop 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:

  • RIP
  • IGRP
  • EIGRP
  • VPLS, which uses the split horizon technique to avoid loops in the forwarding plane
  • Babel, which applies split-horizon to wired links only

See also

References
  1. A Routing Procedure for the TIDAS Message-Switching Network, IEEE Transactions on communication 1975
  2. Letter from Torsten Cegrell to professor Leonard Kleinroch, 1974-08-19
  3. Torsten Cegrell - the swede who "fixed" the Internet, Internetmuseum.se, access date 2017-11-09
  4. IP routing protocols By Uyless D. Black
  5. https://people.mpi-sws.org/~gummadi/teaching/sp07/datanets/homework/homework2solution.pdf

James F. Kurose, Keith W. Ross (2017). Computer Networking: A top-Down Approach, Seventh Edition. Harlow, England: Pearson. p. 418.CS1 maint: uses authors parameter (link)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.