Consider a simple graph with unit edge costs. Each node in the graph…
2005
Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to relay a packet to its destination and the cost of the path to the destination through that router. Initially, the routing table is empty. The routing table is synchronously updated as follows. In each updation interval, three tasks are performed.
A node determines whether its neighbours in the graph are accessible. If so, it sets the tentative cost to each accessible neighbour as 1. Otherwise, the cost is set to ∞.
From each accessible neighbour, it gets the costs to relay to other nodes via that neighbour (as the next hop).
Each node updates its routing table based on the information received in the previous two steps by choosing the minimum cost.
For the graph given above, possible routing tables for various nodes after they have stabilized, are shown in the following options. Identify the correct table.
Attempted by 88 students.
Show answer & explanation
Answer:
The correct set of routing tables uses shortest-path distances (each edge has cost 1). The next hop for a destination is the neighbouring node that lies on a shortest path to that destination. The tables below list, for each source node, the next hop and the cost to every destination.
Node A: A (—), B -> next hop B cost 1, C -> next hop C cost 1, D -> next hop C cost 2, E -> next hop C cost 2, F -> next hop C cost 3
Node B: B (—), A -> next hop A cost 1, C -> next hop C cost 1, D -> next hop C cost 2, E -> next hop C cost 2, F -> next hop C cost 3
Node C: C (—), A -> next hop A cost 1, B -> next hop B cost 1, D -> next hop D cost 1, E -> next hop E cost 1, F -> next hop D cost 2
Node D: D (—), C -> next hop C cost 1, E -> next hop E cost 1, F -> next hop F cost 1, A -> next hop C cost 2, B -> next hop C cost 2
Node E: E (—), C -> next hop C cost 1, D -> next hop D cost 1, A -> next hop C cost 2, B -> next hop C cost 2, F -> next hop D cost 2
Node F: F (—), D -> next hop D cost 1, C -> next hop D cost 2, E -> next hop D cost 2, A -> next hop D cost 3, B -> next hop D cost 3
Brief justification:
Every direct neighbour appears with cost 1 and the neighbour itself as next hop (e.g., A's neighbours B and C).
Non-neighbour destinations follow the shortest path. For example, C to F is C–D–F (2 hops), so next hop is D and cost 2; A to F is A–C–D–F (3 hops), so next hop is C and cost 3.
Using these rules for every node yields the tables listed above; the option that matches these tables is the correct one.