What exactly can cause counting-to-infinity in the bellman-ford algorithm

Question

From what I can understand, counting-to-infinity occurs when one router feeds another old information, which continues to propagate through the network toward infinity. From what I read, this can definitely occur when a link is removed.

So in this example, the Bellman-Ford algorithm will converge for each router, they will have entries for each other. R2 will know that it can get to R3 at a cost of 1, and R1 will know that it can get to R3 via R2 at a cost of 2.

If the link between R2 and R3 is disconnected, then R2 will know that it can no longer get to R3 via that link and will remove it from it's table. Before it can send any updates it's possible that it will receive an update from R1 which will be advertising that it can get to R3 at a cost of 2. R2 can get to R1 at a cost of 1, so it will update a route to R3 via R1 at a cost of 3. R1 will then receive updates from R2 later and update its cost to 4. They will then go on feeding each other bad information toward infinity.

One thing I have seen mentioned a few places is that there can be other causes of counting to infinity other than just a link going offline such as changing the cost of a link. I got to thinking about this and from what I can tell, it seems to me that perhaps the cost of a link being increased could cause the problem. However, I do not see that it's possible for a lowering cost to cause the problem.

For instance, in the example above, when the algorithm converges and R2 has a route to R3 at a cost of 1, and R1 has a route to R3 via R2 at a cost of 2. If the cost between R2 and R3 is increased to 5. Then this would cause the same problem, R2 could get an update from R1 advertising a cost of 2, and change its cost to 3 via R1, R1 then changing its route via R2 to a cost of 4 and so on. However, if the cost decreases on a converged route then it wouldn't cause a change. Is this correct? It is an increasing cost between links that may cause the problem, not decreasing cost? Are there any other possible causes? Would taking a router offline be the same as a link going out?

Answer 1

Have a look on this example:

The routing table will be:

    R1   R2    R3
R1  0    1     2
R2  1    0     1
R3  2    1     0

Now, assume the connection between R2 and R3 is lost (You can the line broke or a middle router between them fell).

After one iteration of sending the information, you wil get the following routing table:

    R1   R2    R3
R1  0    1     2
R2  1    0     3
R3  2    3     0

It happens because R2,R3 is no longer connected, so R2 "thinks" it can redirect packages to R3 through R1, which has a path of 2 - so it will get a path of weight 3.

After an extra iteration, R1 "sees" R2 is more expensive than it used to be, so it modifies its routing table:

    R1   R2    R3
R1  0    1     4
R2  1    0     3
R3  4    3     0

and so on, until they converge on the correct value - but that could take a long time, especially if (R1,R3) is expensive.
This is called "count to infinity" (if w(R1,R3)=infinity and is the only path - it will continue counting forever).

---

Note that when a cost between two routers goes up you will encounter the same issue (assume w(R2,R3) goes up to 50 in the above example). The same thing will happen - R2 will try to route to R3 via R1 without "realizing" it depends on (R2,R3) as well, and you will get the same first steps and converge once you find the correct cost.
However, if the cost goes down - it will not happen since the new cost is better then the current - and the router R2 will stick with the same routing with decreased cost, and will not try to route through R1.

Answer 2

According to Wikipedia:

RIP uses the split horizon with poison reverse technique to reduce the chance of forming loops and uses a maximum number of hops to counter the 'count-to-infinity' problem. These measures avoid the formation of routing loops in some, but not all, cases. The addition of a hold time (refusing route updates for a few minutes after a route retraction) avoids loop formation in virtually all cases, but causes a significant increase in convergence times.

More recently, a number of loop-free distance vector protocols have been developed — notable examples are EIGRP, DSDV and Babel. These avoid loop formation in all cases, but suffer from increased complexity, and their deployment has been slowed down by the success of link-state routing protocols such as OSPF.

http://en.wikipedia.org/wiki/Distance-vector_routing_protocol#Workarounds_and_solutions

Answer 3

This doesn't acknowledge the Bellman-Ford Algorithm part of the question, but this is a simplified answer. Here goes.

Notice the image by the original poster. There is R1, R2, and R3; representing Routers 1, 2, and 3 respectively.

Each link costs 1, and each hop costs 1. To hop two routers (example: R1 to R3) rerquires a cost of 2.

Each router keeps track of the costs and updates the information. If there is a missing value however (for example, a missing link between routers), the hop count is removed, and is filled by another Router when there is an update to routing tables.

Example:

If Router 3's link to Router 2 goes down, Router 2 will remove the route from it's table. Router 1 still thinks it takes two hops to get to Router 3. This gets replicated to Router 2, and now both Routers think it takes two hops to get to Router 3.

Router 1 does some simple math, "If it takes me one hop to get to Router 2, and Router 2 takes two hops to get to Router 3, it should take me three hops to get to Router 3. Brilliant!" Router 2 does similar math and adds one hop to it's route, and so on.

This is how the loop works.

Answer 4

Hold downs:

• As metric increases, delay propagating information

Limitations:

• Delays convergence Loop avoidance
• Full path information in route advertisement
• Explicit queries for loops (e.g. DUAL) Split horizon
• Never advertise a destination through its next hop
  • A doesnʼt advertise C to B
• Poison reverse: Send negative information when advertising a destination through its next hop
• A advertises C to B with a metric of ∞
  • Limitation: Only works for “loop”s of size 2