Q6(b) · Distance-vector link change

Q6(b). x has only neighbors w and y. Links x–w=2, x–y=5, w–y=2. Minimum cost from w to destination u is 5 and from y to u is 6. All link costs are positive integers. Find x’s distance vector for w,y,u. Give a change to x–w or x–y that does not change x’s minimum cost to u. [5 marks]

Answer

Given

x–w2,x–y5,w–y2; Dw(u)=5,Dy(u)=6.

To find

Dx(w),Dx(y),Dx(u) and a link change leaving Dx(u) unchanged.

Formula and why

LaTeX: D_x(u)=\min(2+5,5+6)

Compare complete candidate route costs, not the last advertised value alone.

Solution

Step 1. Neighbor destinations

Dx(w)=2 direct. Dx(y)=min(5,2+2)=4 viaw.

Step 2. Destination u

Dx(u)=min(7,11)=7 viaw. Vector for(w,y,u) is (2,4,7).

Step 3. Choose a harmless change

Increase c(x,y) from5 to6. Route viaw remains2+5=7; route viay becomes6+6=12. The minimum cost to u is unchanged, so x has no changed u-distance to advertise. Other destination entries must be considered separately.