A Distance Vector Routing(DVR) requires that a router informs its neighbors of topology changes periodically. This algorithm is also well known in the Competitive Programming fraternity as the Bellman-Ford algorithm. The Distance Vector Routing(DVR) protocols have a major issue of Routing Loops because the Bellman-Ford algorithm cannot prevent loops. The Count to Infinity problem arises from the routing loop in this Distance Vector Routing(DVR) network. Such Routing Loops usually occurs when 2 routers send an update together at the same time or when an interface goes down.
The Count to Infinity Problem
The crux of the Count to Infinity problem is that if node A tells node B that it has a path somewhere, there is no way for node B to know if the path has node B as a part of it.
Consider the above diagram, for this setup, the Bellman-Ford algorithm will work such that for each router, they will have entries for each other. Router A will infer that it can reach B at a cost of 2 units, and B will infer that it can reach C at a cost of 1 unit.
Consider the case in the above diagram, where the connection between B and C gets disconnected. In this case, B will know that it cannot get to C at a cost of 1 anymore and update its table accordingly. However, it can be possible that A sends some information to B that it is possible to reach C from A at a cost of 2. Then, since B can reach A at a cost of 1, B will erroneously update its table that it can reach C via A at a cost of 1 + 2 = 3 units. A will then receive updates from B and update its costs to 4, and so on. Thus, the process enters into a loop of bad feedback and the cost shoots towards infinity. This entire situation is called the Count to Infinity problem.
Solution for the Count to Infinity Problem
Route Poisoning:
Route Poisoning is a method used to prevent routers from sending packets through a route that has been deemed invalid within computer networks. Upon failure of a route, Distance Vector Protocols spread the bad news about the route failure by poisoning the route. In Route Poisoning, a special metric value called Infinity is used when advertising the route. Routers with a metric of Infinity are considered to have failed. The main disadvantage of this method is that it increases the sizes of routing announcements significantly in many common network topologies.
Split Horizon:
In our initial diagram, if the connection between B and C is down, and A sends a route to B, B could use up that route to reach A. Hereafter, A would send the same packet back to B, and the process would end up in an endless loop. However, by Split Horizon Rule, the route to C from A will not be advertised back to B.
The below diagram shows Split Horizon in effect,
FAQs
1. Is there some way through which we can obtain better efficiency than the above-mentioned methods?
A. We can use Split Horizon along with Route Poisoning, combined effectively, to achieve efficiency and reduce the rate of increase in the size of routing announcements.
2. What are Holdown Timers with respect to routing loops?
A. Holdown Timers can be used to prevent routing loops. A Holdown Timer starts immediately when the router is informed that some link it is connected to is down. During this time, the router will ignore all the updates and responses on the down route, unless it receives a response from the downed route link itself. When the timer is on, only if the downed link is reachable again, can the routing table be updated.
