fbpx

Distance Vector Routing in Computer Network

Distance Vector Routing in Computer Network

 · Distance Vector Routing in Computer Network algorithms operate by having each router maintain a table (i.e, a vector) giving the best-known distance to each destination and which line to use to get there.
· These tables are updated by exchanging information with the neighbors.
· The distance vector routing algorithm is sometimes called by other names, most commonly the distributed Bellman-Ford routing algorithm and the Ford-Fulkerson-algorithm, after the researchers who developed it (Bellman, 1957; and Ford and Fulkerson, 1962).
· It was the original ARPANET routing algorithm and was also used on the Internet under the name RIP. 

Distance Vector Routing in Computer Network
Distance Vector Routing in Computer Network
               (a) A subnet. (b) Input from A, I, H, K, and the new routing table for J.
·  Part (a) shows a subnet. The first four columns of part (b) show the delay vectors received from the neighbors of router J.
·  A claims to have a 12-msec delay to B, a 25-msec delay to C, a 40-msec delay to  D, etc. Suppose that J has measured or estimated its delay to its neighbors, A,  I, H, and K as 8, 10, 12, and 6 msec, respectively. Each node constructs a one-dimensional array containing the “distances”(costs) to all other nodes and distributes that vector to its immediate neighbors.
  1The starting assumption for distance-vector routing is that each node knows the cost of the link to each of its directly connected neighbors.
   2 – A link that is down is assigned an infinite cost.
Example.
 
ssssssff%2B2
Distance Vector Routing in Computer Network

Table 1. Initial distances stored at each node(global view).

 
Information
Stored at Node
Distance to Reach Node
A
B
C
D
E
F
G
A
0
1
1
1
1
B
1
0
1
C
1
1
0
1
D
1
0
1
E
1
0
F
1
0
1
G
1
1
0
We can represent each node’s knowledge about the distances to all other nodes as a table like the one given in Table 1
             Note that each node only knows the information in one row of the table.
1. Every node sends a message to its directly connected neighbors containing its personal list of distance.  (  for  example, A sends  its  information  to   its   neighbors B, C, E, and F. )
2. If any of the recipients of the information from A find that A is advertising a path shorter than the one they currently know about, they update their list to give the new path length and note that they should send packets for that destination through A. ( node B learns from A that node E can be reached at a cost of 1; B also knows it can reach A at a cost of  1,  so  it  adds  these  to  get  the  cost  of  reaching E by  means of A. B records that it can reach E at a cost of 2 by going through A.)
3. After every node has exchanged a few updates with its directly connected neighbors, all nodes will know the least-cost path to all the other nodes.
4. In addition to updating their list of distances when they receive updates, the nodes need to keep track of which node told them about the path that they used to calculate the cost so that they can create their forwarding table. ( for example, B knows that it was A who said ” I can reach E in one hop” and so B puts an entry in its table that says ” To reach E, use the link to A.


In practice, each node’s forwarding table consists of a set of triples of the form: ( Destination, Cost, NextHop).
For example, Table 3 shows the complete routing table maintained at node B for the network in figure1.

Table 2. final distances stored at each node ( global view).

Information
Stored at Node
Distance to Reach Node
A  
B        
C        
D    
E    
F     
G       
A
0  
1       
1       
2   
1    
1     
2      
B
1  
0       
1       
2  
2    
2    
3     
C
1  
1      
0       
2    
2   
2      
D
2  
2      
1      
3   
2  
1     
E
1   
2      
2     
0   
2  
3    
F
1   
2      
2     
2   
0  
1    
G
2   
3       
2     
3   
0    

Table 3. Routing table maintained at node B.
Destination
Cost
NextHop
A
1
A
C
1
C
D
2
C
E
2
A
F
2
A
G
3
A
THE COUNT-TO-INFINITY PROBLEM
ssssssff%2B3
Distance Vector Routing in Computer Network
· Consider the five-node (linear) subnet of Figure, where the delay metric is the number of hops.     Suppose A is down initially and all the other routers know this. In other words, they have all recorded the delay to A as infinity.
· Now let us consider the situation of Figure (b), in which all the lines and routers are initially up. Routers B, C, D, and E have distances to A of 1, 2, 3, and 4, respectively. Suddenly A goes down, or alternatively, the line between A and B is cut, which is effectively the same thing from B‘s point of view.

2 thoughts on “Distance Vector Routing in Computer Network”

Leave a Comment