Count to Infin, Split Horizon, Rt Poison, Hold Down Timers

FIGURE-1: Distance Vector Loop Avoidance

For example: in figure-1, R3 has just sent out an update to R1 and R4, and suddenly the link between R3 and R5 goes down. R3 must wait, till the periodic update timer expires, to notify R1. During this time R1, R2 and R4 will continue to use the old route to R5 and routing black-hole is already created. In a larger network this routing information inconsistency could lead to a routing loop.

Split Horizon

Split Horizon rules dictate that routing information should never be sent out an interface it was learnt from. In figure-1, R3 is providing update about 192.168.35.0 to R1 and R4. Up to this point, R1 and R4 should advertise this information to R2 and back to R3. This process of advertising back the route to originator is called “reverse route”.

Common sense dictates that R1 and R4 should not advertise back to R3 since it already knows about 192.168.35.0 and off-course it waste resources. Split horizon prevents this reverse route phenomenon to evade routing loops. For example: let us assume that split horizon is not in effect and network 192.168.35.0 is unreachable. Even if the route invalidation timer is in effect, R3 must wait for next periodic update. But unexpectedly, R4 update arrives early. Now R3 has 192.168.35.0 reachable via R4 in two hops and a routing loop has occurred.

Count to Infinity

The primary purpose of split horizon is to avoid loop between neighbors. But split horizon alone can not avoid loop in a network such as in figure-1. For sake of simplicity, we are not considering multiple path to the destination.

Now assuming that the network is stable, we have the following routing table entries for 192.168.35.0:

Let us take a closer look how routing information is propagated. The network 192.168.35.0 has failed. R3 sends an update to R1 and R4 that 192.168.35.0 is unreachable. R3, R4 and R1 now have the following route entries.

Since R2 hasn’t yet informed of the update that 192.168.35.0 is now not available (and unfortunately) it sends an update to R1. How did the hop count increased? Actually R2 learned 192.168.35.0 from R1 and R4; therefore, information learned from R4 is a different entity than that of R1. R1 will advertise 192.168.35.0 via R4 to R1 and vice versa and split horizon rule is not void in this condition. In a stable network, R1 and R4 will not install these advertisements from R2, since they already have best path through R3 in one hop.

The routing snapshot looks as under:

R1 send this update to R3. R3 now can reach 192.168.35.0 via R1 in four hops. The routing table will be:

R3 installs this route and advertise to R4. R4 now think that the metric toward 192.168.35.0 from R3 has increased; nonetheless, it is the only route and must be installed. The routing table of R4 looks like:

R4 advertises to R2, R2 to R1 to R3 and goes on. For each update, the hop count keeps on increasing. This phenomenon is called to count to infinity. To elevate this problem distance vector protocols define “infinity”. For example: RIP defines infinity as hop count reaches 16 and such routing information is discarded immediately. Although routing loop will be eliminated, but the convergence will be slow as each router must wait for hop count to reach infinity.

Split Horizon with Poison Reverse (route poisoning)

Uses the “infinity” value and advertise the route back to originator on the interface through which it was learned from as “unreachable”. The analogy is simple: “bad information is better than no information”. The count to infinity problem can be avoided since each neighbor is advertising routes leaned on same interface as unreachable. There is no need to wait for hop count to reach infinity.

Hold Down Timer

Flash (or triggered) updates allowed fast convergence but hold down timers introduces uncertainty to reduce the acceptance of bad routing information. If an advertisement is received with increased metric (or hop count), the router set a hold down timer before accepting the new routing information. Until the hold down timer expires, router will not accept any route for the specified destination with equal or worst metric. The trade off is the convergence time vs. containing bad routing information. In figure-1, R3 must set a hold down timer before accepting any update from R1 and R4.

This brings us to the end of this article in which we covered various techniques used by Distance Vector Routing protocols to prevent routing loops.