Home » Computer Network » Explain the count to infinity problem. How it can be solved using split horizon algorithm? What are its limitation?

Explain the count to infinity problem. How it can be solved using split horizon algorithm? What are its limitation?

Support this post with a reaction:

6,436 views

Distance Vector Routing

Distance Vector Routing is a dynamic routing technique used in computer networks to determine the best path for sending data from one router to another.

In this technique, each router maintains a routing table that contains information about the destination networks, distance (cost), and next-hop router.

Routers exchange their routing information with their directly connected neighboring routers at regular intervals. Based on the information received from neighboring routers, each router updates its routing table and selects the best available path to reach a destination.

Distance Vector Routing generally uses the Bellman-Ford algorithm to calculate the shortest path.

However, this routing technique has some problems. One of the major problems is the Count to Infinity Problem.

This problem occurs when routers incorrectly believe that a failed destination is still reachable through another router. As a result, they continuously increase the distance or metric to that destination.

The Split Horizon Algorithm is one of the techniques used to reduce this problem.

What is the Count to Infinity Problem?

The Count to Infinity Problem is a routing problem that occurs in Distance Vector Routing when routers continuously increase the metric (distance) to a destination that has become unreachable.

It happens because routers exchange outdated routing information and mistakenly believe that another router still has a valid path to the failed destination.

When a network link or destination fails, the routers may not immediately know about the failure. They continue using old routing information and advertise incorrect routes to their neighboring routers.

As a result, the distance to the unreachable destination increases gradually. This process continues until the routing protocol reaches its defined infinity value.

In simple words: Count to Infinity is a problem in which routers continuously increase the distance to an unreachable destination because they receive incorrect or outdated routing information from neighboring routers.

Important Characteristics of Count to Infinity

  1. It mainly occurs in Distance Vector Routing.
  2. It happens due to outdated routing information.
  3. Routers may create routing loops.
  4. The routing metric increases continuously.
  5. It takes time for routers to identify that a destination is unreachable.
  6. It increases network traffic because routers repeatedly exchange routing updates.

Causes of the Count to Infinity Problem

The major causes of the Count to Infinity Problem are explained below.

1. Outdated Routing Information

Routers may continue using old routing information even after a network link or destination has failed.

2. Slow Convergence

Distance Vector Routing requires time to update routing tables across all routers. During this period, routers may use incorrect routes.

3. Routing Loops

Two or more routers may incorrectly believe that another router has a valid path to the same destination. This can create a routing loop.

4. Periodic Routing Updates

Routers exchange routing information periodically. If a failure occurs between updates, neighboring routers may continue advertising outdated information.

5. Incorrect Distance Calculation

When routers receive incorrect information, they may continuously increase the metric to an unreachable destination instead of immediately marking it as unreachable.

Example of the Count to Infinity Problem

Consider three routers A, B, and C connected in a network. Suppose a destination network X is directly connected to Router A.

Initially, Router B learns about network X through Router A, and Router C learns about network X through Router B.

The routing information is as follows:

  • Router A can reach network X directly with a cost of 1.
  • Router B reaches network X through Router A with a cost of 2.
  • Router C reaches network X through Router B with a cost of 3.

Now, suppose the connection between Router A and network X fails.

Router A identifies that network X is unreachable and advertises an infinite metric. However, Router B and Router C may still have outdated routing information.

They may incorrectly believe that the other router can reach network X.

As a result, the distance to network X keeps increasing through repeated routing updates.

This is called the Count to Infinity Problem.

Count to Infinity Problem

Figure: Count to Infinity Problem

How Does the Distance Increase?

For example, assume that routers use a simplified distance metric and increase the cost by 1 when learning a route from a neighbor.

Routing updateRouter ARouter B
Initial route12
After failure and stale update32
Next update34
Next update54
Further updates56

The values keep increasing because each router believes that the other router has a valid route to network X.

In protocols such as RIP, the metric value 16 represents infinity. Therefore, the counting process stops when the metric reaches 16.

Result: The routers take time to recognize that the destination is unreachable. This delay is known as the Count to Infinity Problem.

What is the Split Horizon Algorithm?

Split Horizon is a routing technique used in Distance Vector Routing to prevent routing loops and reduce the Count to Infinity Problem.

According to this technique, a router does not advertise a route back through the same interface from which it originally learned that route.

In simple words, if a router learns a route from a neighboring router, it will not advertise that same route back to that neighbor.

This prevents neighboring routers from receiving incorrect routing information about routes that they originally advertised.

Working Principle of Split Horizon

  1. A router receives routing information from one of its neighboring routers.
  2. It stores the received information in its routing table.
  3. When sending routing updates to other neighboring routers, it checks where each route was learned.
  4. It does not advertise a route back through the interface from which that route was learned.
  5. This prevents the neighboring router from receiving its own routing information again.

Purpose: Split Horizon prevents routers from advertising a route back to the router from which they originally learned it, thereby reducing routing loops.

How Does Split Horizon Solve the Count to Infinity Problem?

Split Horizon helps solve the Count to Infinity Problem by preventing a router from sending routing information back to the neighbor from which it learned that route.

Consider two routers, A and B, connected to each other. Suppose network X is directly connected to Router A.

Initially:

  • Router A knows network X directly.
  • Router B learns about network X from Router A.
  • Router B stores the route to X through Router A.

Now, suppose the connection between Router A and network X fails.

Without Split Horizon, Router B may continue advertising its old route to Router A. Router A may mistakenly believe that network X is still reachable through Router B. This can create a routing loop.

With Split Horizon, the following process takes place:

1. Route Learning: Router B learns about network X from Router A and stores it in its routing table.

2. Route Advertisement: When Router B sends routing updates to Router A, it does not advertise the route to network X back to Router A.

3. Link Failure: When network X becomes unreachable, Router A identifies the failure and marks the route as unreachable.

4. Prevention of Incorrect Information: Router B does not send its previously learned route back to Router A.

5. Routing Table Update: Router B receives the unreachable route information from Router A and updates its routing table accordingly.

6. Problem Prevention: Since Router A does not receive an incorrect route from Router B, a two-router routing loop is prevented.

Therefore, Split Horizon reduces the possibility of routing loops and helps prevent the Count to Infinity Problem.

 Split Horizon Algorithm

Figure: Split Horizon Algorithm

Limitations of Split Horizon Algorithm

Although Split Horizon helps prevent routing loops, it has some limitations.

1. Does Not Prevent All Routing Loops

Split Horizon mainly prevents routing loops between two directly connected routers. It cannot completely prevent loops involving three or more routers.

2. Limited Protection in Complex Networks

In large networks with multiple routers and alternative paths, incorrect routing information may still circulate through different routes.

3. Slow Convergence

Split Horizon does not guarantee immediate routing table updates. Routers may still take time to identify network failures and update their routing information.

4. Does Not Eliminate the Count to Infinity Problem Completely

It reduces the possibility of the Count to Infinity Problem but does not completely eliminate it in every network topology.

5. Limited Effect on Multiple Router Loops

When three or more routers are involved, one router may learn a route through another router and advertise it to a third router, which may create a routing loop.

6. Additional Techniques May Be Required

In complex networks, Split Horizon is often combined with other routing techniques such as Route Poisoning, Poisoned Reverse, and Hold-Down Timers to improve routing stability.

Difference Between Split Horizon and Split Horizon with Poisoned Reverse

Split Horizon and Split Horizon with Poisoned Reverse are related techniques used to prevent routing loops.

Split HorizonSplit Horizon with Poisoned Reverse
Does not advertise a route back to the router from which it was learned.Advertises the route back with an infinite metric.
The route advertisement is suppressed.The route is explicitly marked as unreachable.
Reduces routing loops between neighboring routers.Provides stronger protection against two-router routing loops.
Sends no route information for that destination on the reverse interface.Sends route information with an infinite cost.

Example:

  • In Split Horizon, Router B does not advertise the route learned from Router A back to Router A.
  • In Poisoned Reverse, Router B advertises the same route back to Router A with an infinite metric.

Both techniques help prevent routing loops in Distance Vector Routing.