Question

Problem 5. Distance Vector (DV) Routing (12 pt.)

Consider the network in the LS problem. Assume all the nodes other than the source node have the optimal distance information to all other nodes. Calculate the distance from the source to the destination node, and determine the next hop node. In case of a tie, you can choose any of the best nodes (Hint: “Bellman-Ford example”)

(i) dw(s)

(ii) dw(t)

(iii) dw(y)

Answer 1

Here since all the distance metric is non-negative, therefore DIjkstra algorithm can be applied from the source node s to compute the shortest path to every other nodes.

(i) To compute dw(s) i.e. shortest distance from node w to node s, note that source node w has 3 neighbours which are x , v and u.

As mentioned in the question, apart from source node every node has shortest path computed to other node.

Here, dx(s) = weight(x,v) + weight(v,t) + weight(t,s) = 3+4+1 = 8

dv(s) = weight(v,t) + weight(t,s) = 4+1 = 5

du(s) = weight(u,t) + weight(t,s) = 2+1 = 3

Hence the next hop from for node w will be selected based on min{weight(w,x) + dx(s) , weight(w,v) + dv(s) , weight(w,u) + du(s) = min(6+8 , 4+5 , 3+3) = 6

Hence dw(s) = 6 and next hop selected for destination s from node w will be node u.

ii.  

dx(t) = weight(x,v) + weight(x,t) = 3+4 = 7

dv(t) = weight(v,t) = 4

du(t) = weight(u,t) = 2

Hence the next hop from for node w will be selected based on min{weight(w,x) + dx(t) , weight(w,v) + dv(t) , weight(w,u) + du(t) = min(6+7 , 4+4 , 3+2) = 5

Hence dw(t) = 5 and next hop selected for destination t from node w will be node u.

iii.

dx(y) = weight(x,v) + weight(v,y) = 3+1 = 4

dv(y) = weight(v,y) = 1

du(y) = weight(u,v) + weight(v,y) = 3+1 = 4

Hence the next hop from for node w will be selected based on min{weight(w,x) + dx(y) , weight(w,v) + dv(y) , weight(w,u) + du(y) = min(6+4 , 4+1 , 3+4) = 5

Hence dw(y) = 5 and next hop selected for destination y from node w will be node v.

Please comment for any clarification.