Count to infinity

[life24]

Hello my friends,
Why any increase cost propagation is quickly but any decrease cost propagation is slowly in distance vector routing?

Thanks :wub:

 

[Gryz]

Distance vector is not a protocol. Distance vector is a mathematical algorithm to compute shortest paths in a network. It's also called the Bellman-Ford algorithm. And to make it even more complex: routers use a distributed version of Bellman-Ford, because the routers in a network form a kind of distributed system.

There are routing protocols that use the Bellman-Ford Distance Vector algorithm as the mathematical core of their protocol. RIP is the best known example of a routing protocol that uses Bellman-Ford. However, there are more. IGRP and EIGRP use Distance Vector too. One could argue BGP is kind of a distance-vector protocol too. (BGP is a path-vector protocol. It uses path-vector to prevent routing loops. But it uses distance-vector to compute the best paths (where path-length is the main metric)).

Routing protocols do not only do computations. There are more things they do. E.g. very important is how they exchange routing information.

RIP (and IGRP) do periodic updates. That means they will send 1 or more packets, every 30 seconds, out of every interface they have. And hope that other routes receive these packets. You could improve this, if you wanted. E.g. the EIGRP protocol has acknowledgements for these packets. If it doesn't get an ack, it retransmits the packet. EIGRP also send hello packets separately, to try to figure out who its neighbors are.



Your question is related to something RIP does to try and improve its performance. RIP has so-called "flash updates". When a router receives a RIP-packet, it compares the new routes with the old ones in its routing table. If there is no change, RIP does nothing special. It just keeps sending its periodic updates every 30 seconds. But if there was a change, RIP will send new updates out to its neighbors immediately. It doesn't wait 30 seconds, it sends out immediately. This is called a flash-update.

The second thing that RIP might do, is the rule "bad news travels fast, good news travels slow". Some RIP implementations might send a flash update only when a route gets a worse metric, or gets deleted (hopcount = 15). The news will travel fast. But when a new route appears, or a metric improves, RIP does nothing. And the new metric or new route will be advertised at the next periodic update-packet. In that case, news travels slow.

I'm not sure this is in the RFCs that describe RIP. It might depend on the implementation.

And in any case, details like this are not part of the distance vector algorithm. They are part of the protocol. E.g. EIGRP does these things completely different than RIP does.


I hope this answers your question. The question seems simple, but to understand the answer, you need to understand a bit more about routing than what the usual text-books teach people.

 

[Gryz]

Oh, the book says: "Any decrease in cost travels fast, but increase travels slow"

That's actually nonsense. Both increase and decrease travel at exactly the same speed.

If an implementation does not do flash-updates, then there will be 30 seconds between updates. New routes will be advertised within 30 seconds (per hop) through the network. If routes need to be removed, then it can take 3 * 30 seconds per hop for that information to get everywhere. However, if a router uses "poison metric, it will advertise the deleted route with metric 15 for a while. And in that case, bad news travels exactly as fast as good news.


What the writer of the book probably means is: if a new route is added to the network, it will be advertised everywhere (almost) immediatelly. Especially when the routers do flash-updates. But if a route is removed from the network, there will be counting-to-infinity. And counting-to-infinity goes slow. It will take a while before an old route is completely removed from the network. (Several times 30 seconds. Worst case = 14 * 3 * 30 seconds = 21 minutes). It doesn't matter much that it takes that long, because the destination isn't reachable anyway. The only problem is that if someone keeps sending packets to that destination, traffic will loop for up to 21 minutes. Which can cause a burden on the network.


Suppose a network as many routers. And they are connected with many links. Suppose router X advertises prefix P. Suppose it advertises P to two other routers, Y and Z, both with cost 1. Y and Z advertise P to their neighbors, with cost 2.

Now suppose router X crashes. Y and Z don't receive their periodic updates. After 3x30=90 seconds, they declare that P is not reachable anymore. Suppose they don't make that decision at exactly the same time. Suppose router Y is a bit quicker. It will note P in its routing table as down. It will then advertise P with metric 15 to all its neighbors. Now if Z was a bit slow, it might advertise P one more time, with cost 2. If Y hears that advertisement, it will think: "my old route to P via X, metric 1 is not valid anymore. But here is a new route to P, via Z, with metric 2. I'll use that one". A few seconds later Z decides that its route to P via X is not valid anymore. But in the mean time, other routers have picked up the old route that was supposed to be deleted. This "old information" keeps being advertised around. And every 90 seconds, the router that started advertising that old information will stop doing that. But another router repeats the same mistake. The good thing is: every time that happens, the metric increases (depending on number of hops over which the old/outdate info traveled). After a while, the metric has been increased to 15. And 15 is unreachable. At that point, routers will start removing the route to prefix P from their routing table.

This is counting to infinity. (Infinity is 15, in RIP). It goes slow. It takes several times, times 90 seconds. Google it, I'm sure there are better explanations than mine.


As I tried to explain in my first post: all this behaviour depends on how the protocol has been implemented. A few smart trick can be done, to make the counting-to-infinity less bad.
Example tricks:
flash updates
poison reverse
split horizon

Google what those are, and you might get a better understanding for distance vector protocols, like RIP.


For completeness sake: the expression in routing is usually: "bad news travels fast, good news travels slow". What this means is: if new paths become available, routers become available, links are back working, etc, you can wait a little (a few seconds or more) before you announce the new paths. Because traffic was flowing over another path anyway. If it changes to the better path 1 second later, or 10 seconds later, doesn't matter much.
But if a router crashes, or a link goes down, then traffic will be lost. And that's bad. So when that happens, routers will *immediately* try to notify all the other routers of the problem, and try to find an alternate path. Just so that as little traffic as possible is lost.

The writer of your book mixes things up. It might not be a very good book, sorry.

 

[VirtualLarry]

Very interesting, thanks Gryz!