Distance-Vector Routing Algorithm
Distance-Vector Routing Algorithm
Distance-Vector Routing is a routing algorithm used to find the least-cost path from a router to every other router in a network.
The basic idea is:
Each router maintains a list of the minimum costs to reach every other router and shares this information with its immediate neighbors.
The neighbors use this information to improve their own routing information. This process continues until the routing information becomes stable.
1. What is a Distance Vector?
A distance vector is a one-dimensional array that contains the least cost from one router to all other routers.
For example, suppose router A has the following information:
| Destination | A | B | C | D |
|---|---|---|---|---|
| Cost from A | 0 | 2 | 7 | 6 |
The vector maintained by A is:
A = [0, 2, 7, 6]
Here:
-
0→ cost from A to itself -
2→ least cost from A to B -
7→ least cost from A to C -
6→ least cost from A to D
Importantly, a distance vector tells us the cost, not the complete path.
2. Initial Distance Vector
When a router starts, it initially knows only:
- The cost to itself → 0
- The cost to its immediate neighbors
- The cost to all other routers → ∞ (infinity)
For example:
2 A ------- B | | 5 | C
Initially, router A knows:
| Destination | Cost |
|---|---|
| A | 0 |
| B | 2 |
| C | 5 |
| D | ∞ |
A router discovers its immediate neighbors and their distances and creates this initial vector.
3. Exchange of Distance Vectors
Each router sends its distance vector to its immediate neighbors.
For example:
Vector A ─────────► A B ◄───────── Vector B
When B receives A's vector, B checks:
"Can I reach some destination more cheaply by going through A?"
If yes, B updates its distance vector.
After updating, B sends its new vector to its neighbors.
This process continues until no further improvements are possible.
4. Bellman-Ford Equation
The main equation used by Distance-Vector Routing is the Bellman-Ford equation.
Where:
- = current least cost from router x to destination y
- = cost from router x to neighbor z
- = neighbor z's known cost to destination y
In simple words:
New cost through a neighbor = Cost to reach the neighbor + Neighbor's cost to reach the destination.
If this new cost is smaller than the existing cost, the router updates its table.
The following shows the general case in which Dij is the shortest distance and cij is the cost between node i and j.
In distance-vector routing, normally we want to update an existing least cost with a least cost through an intermediary node, such as z, if the latter is shorter. In this case, the equation becomes simpler, as shown below:
Figure 4.58 shows the idea graphically for both cases.We can say that the Bellman-Ford equation enables us to build a new least-cost path from previously-established least-cost paths. In Figure 4.58, we can think of (a→y),
Dxy = min {(c xa + Day), (c xb + Dby), (c xc + Dcy), …}
Dxy = min {Dxy, (c xz + Dzy)
5. Simple Example
Consider the following network:
2 A ------- B \ / 5 \ / 4 \ / C
Suppose B wants to find the least-cost path to C.
Initially, B knows:
B → C = 4
Suppose B receives A's vector and learns:
A → C = 5
The cost from B to A is 2.
So B calculates:
Cost through A = Cost(B,A) + Cost(A,C) = 2 + 5 = 7
B already knows a direct route to C with cost 4.
Therefore:
min(4, 7) = 4
So B does not change its route to C.
Another Example: Finding an Improved Route
Suppose instead:
B → C = 10 B → A = 2 A → C = 5
B initially thinks:
Cost B → C = 10
After receiving A's vector:
Cost through A = 2 + 5 = 7
Since:
7 < 10
B changes its route:
B → C = 7
and the next hop is A.
So the route becomes:
B → A → C
6. How the Algorithm Works
The algorithm can be understood in five simple steps:
Step 1: Initialize
Each router creates its distance vector.
Cost to itself = 0 Cost to neighbor = link cost Cost to others = ∞
Step 2: Exchange
Each router sends its vector to all immediate neighbors.
Step 3: Calculate
When a router receives a neighbor's vector, it calculates possible new routes using:
New cost = Cost to neighbor + Neighbor's cost to destination
Step 4: Update
If the new cost is smaller:
New cost < Existing cost
the router updates its distance vector.
Step 5: Repeat
The updated vector is sent to the neighbors.
This continues until the network converges, meaning the routers have reached stable least-cost information. The algorithm describes as operating independently and asynchronously at each node.
7. Important Characteristics
| Feature | Distance-Vector Routing |
|---|---|
| Information maintained | Distance/cost to destinations |
| Information exchanged with | Immediate neighbors |
| Main equation | Bellman-Ford |
| Initial knowledge | Own node and immediate neighbors |
| Other destinations initially | ∞ |
| Operation | Iterative and asynchronous |
| Goal | Find least-cost paths |
| After update | Updated vector is sent to neighbors |
8. Main Problem: Count to Infinity
A major problem with Distance-Vector Routing is the count-to-infinity problem.
When a link fails, the information about the failure may spread slowly through the network. Routers can temporarily believe that another router has a route to the failed destination, causing the cost to increase step by step.
For example:
A ─── B ─── X
If the link A–X fails:
A cannot reach X
But if B has not yet learned this and tells A:
"I can reach X."
A may believe:
A → B → X
B may then believe that A can reach X:
B → A → X
This creates a routing loop:
A → B → A → B → A → ...
The cost keeps increasing until it eventually reaches infinity. This is called count to infinity.
Summary
Distance-Vector Routing is a routing algorithm in which each router maintains the least-cost distance to every destination and periodically exchanges its distance vector with its immediate neighbors, using the Bellman-Ford equation to update the routes.
Comments
Post a Comment