Computer Networks · TEE · papers

Q6(c) · Recovering unknown routing weights

2024-12-06 · AI-only Sem V variant

Exact historical variant. Current-syllabus questions solved; excluded topics and source limitations stated.

Q6(c). Undirected graph: U–V has unknown link cost X, U–nodeX has unknown link cost Y, U–W=8, V–W=1, V–nodeX=4, nodeX–W=7, nodeX–nodeY=4, W–nodeY=1, W–Z=4, nodeY–Z=6. The shortest-path table from V is V:0/none, W:1/V, nodeY:2/W, nodeX:4/V, Z:5/W, U:6/V. Find unknown edge costs X and Y; write n/a if undetermined. [5 marks]

Answer

Given

dV(U)=6 with predecessorV; dV(nodeX)=4 with predecessorV. Unknown linkX is U–V; linkY is U–nodeX.

To find

Unknown edge costs or n/a.

Formula and why

d(U)=d(\operatorname{pred}(U))+c(\operatorname{pred}(U),U)LaTeX: d(U)=d(\operatorname{pred}(U))+c(\operatorname{pred}(U),U)

A predecessor edge lies on the reported shortest path, so its cost is fixed by the distance difference. An unused edge is usually constrained, not uniquely determined.

Solution

Step 1. Recover link X

U’s predecessor isV:6=0+X, therefore X=6.

Step 2. Test what is known about link Y

The alternate routeV→nodeX→U costs4+Y. It must not be shorter than6, henceY≥2 (assuming nonnegative costs). Many values satisfy this; ifY=2 there is a tie and predecessorV remains valid. Therefore Y=n/a (not uniquely determined).