Figure 1 is a diagrammatical depiction of a network of routers with link costs. Copy the table given in the figure and complete the distance table using the Distance Vector routing algorithm executed at node B. Assume that routing loops are prevented. Finally indicate in a table the resulting routing table.
Figure required: Figure 1 (Distance Vector Routing): routers A, B, C, D, E with link costs A–B 6, A–E 2, B–C 1, B–E 3, C–D 2, E–D 3, and an empty distance table D^B() with columns “via” A, E, C and destination rows A, E, D, C.
Try an answer before revealing the guidance below.
Key Concepts
- Bellman-Ford equation
- Distance table D^B(dest, via)
- Neighbour distance vectors
- Loop prevention
- Routing table
Answer Approach
- List B’s neighbours and the direct link costs to each.
- For each neighbour, find its least-cost distance to every destination without routing back through B.
- Fill each cell as c(B, neighbour) + neighbour’s distance to the destination.
- For each destination row, pick the minimum to build the routing table.
Full Answer
Answer status: Draft answer (unofficial). Revision notes, not an official marking scheme.
Assumption (the usual classroom reading of “routing loops are prevented”): each cell D^B(dest, via v) = c(B, v) + the neighbour’s least cost to dest along a path that does not return through B. Links (Figure 1): A–B 6, A–E 2, B–C 1, B–E 3, C–D 2, D–E 3. D^B(A): via A = 6, via E = 3 + 2 = 5, via C = 1 + 7 = 8. D^B(E): via A = 6 + 2 = 8, via E = 3, via C = 1 + 5 = 6. D^B(D): via A = 6 + 5 = 11, via E = 3 + 3 = 6, via C = 1 + 2 = 3. D^B(C): via A = 6 + 7 = 13, via E = 3 + 5 = 8, via C = 1. Routing table at B (minimum of each row): A → next hop E, cost 5; E → E, cost 3; D → C, cost 3; C → C, cost 1.
D_B(y) = min over neighbours v { c(B, v) + D_v(y) }Shortcuts: K concepts · A approach · F answer · R reviewed · B bookmark · ← / → previous / next