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.