In this installment, we’ll look at some techniques for improving the performance of Distance-Vector (D-V) routing protocols.
As previously discussed, if a routing loop occurs between two routers, the routing updates will bounce between those routers. This is sometimes referred to as “routing feedback”. The metric for the prefix will count up to the maximum (as determined by the number of bits used to track the metric), roll over to zero, and then start counting upwards again (the “count to infinity”). This process, and thus the loop, will continue forever, and any data packet caught in the loop will ricochet between the routers until its IP TTL reaches zero, at which time it is discarded. This is a waste of bandwidth in the routers’ backplanes, and on the link connecting them.
Defining a Maximum
One thing we can do to break the loop is to enforce a rule that if a metric exceeds a specified maximum, that route is considered unreachable and removed from the routing table. Once the metric exceeds the max, the route will be removed from the routing table, and it will no longer be advertised to any neighbors. Eventually the route times out of the neighbors’ routing tables as well, and the network is converged. For IP RIP, for example, a metric of 16 or more hops is considered “infinity”. With an update timer of 30 seconds and a flush timer of 4 minutes, convergence for RIP should occur within 12 minutes.
As we have seen, defining a maximum stops a routing loop from existing forever, but it could still last quite a while. What we’d like to do is prevent the loop from forming between the two routers in the first place. This can be accomplished by enforcing what is known as the “split horizon” rule. The split horizon rule says that
“It is never useful to advertise information back in the direction from which it came”
What this means is, if a router learns a route on one interface, and decides that’s the best way to reach that destination, it won’t advertise that route back out on that same interface. It will, however, advertise the route on the other interfaces. Thus, instead of just simple-mindedly sending its routing table out on every interface, the router actually filters the table in accordance with the split horizon rule, on a per-interface basis. This process of sending information out on all interfaces other than the one on which it is received is called “flooding”.
The split horizon rule has two effects. First, since a router can no longer advertise a “best” route back to the router from which it learned it, no loop can form between two routers. Second, the routers are not wasting each others’ time and bandwidth with redundant advertisements (why tell them what they told just you?). Note that it’s not a violation of split horizon for a router to advertise a better route to a prefix from neighbors from which it has learned an inferior route. In fact, it’s required! For IP RIP, which has a 4 minute flush timer and a 30 second update timer, the split horizon rule should reduce the convergence interval to less than 5 minutes.
Another refinement is what’s called “route poisoning”. The idea is that when a router learns that a route is unreachable, instead of just removing it from the routing table and no longer advertising it, it advertises the route with the maximum metric (which the routers treat as “infinity”), and then removes it. The effect of this is that routers are now able to explicitly inform their neighbors that they can no longer get packets to a prefix. Thus, instead of waiting for the flush timer to remove the route from the routing tables, it would be removed at the next update. For IP RIP, this would be within 30 seconds.
An enhancement to route poisoning goes by the name “poison reverse”. What this means is that when a router poisons a route (advertises it as unreachable), a neighbor that now has no route to that destination will echo the poisoning back. This makes sure that both routers know that the route is unreachable, and there is no way that a loop between those two routers could form. Note that poison reverse overrides the split horizon rule, but because the routers are advertising “bad news”, it’s allowed.
Continuing on in the spirit of shortening the convergence time, we could also have the routers advertise changes that occur when they occur. In other words, rather than waiting until the next update interval to inform their neighbors that the status of a route has changed, tell them right now using what is referred to as a “triggered” update (also known as a “triggered incremental” or “flash” update). A triggered update contains information only about the route for which the status has changed. This change could be that the route has become unreachable (route poisoning), that it has become reachable, or that its metric has changed. Flash updates occur in addition to the periodic flooding of the routing tables, and can reduce the convergence time to nearly zero.
Next time, we’ll continue our discussion of enhancements to Distance-Vector protocols.
Author: Al Friebe