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.
Continuing from the earlier problem, suppose at some time , when the costs have stabilized, node A goes down. The cost from node F to node A at time (t+100) is :
- A.
>100 but finite
- B.
∞
- C.
3
- D.
>3 and ≤100
Attempted by 9 students.
Show answer & explanation
Correct answer: B
Answer: ∞
Reasoning:
When node A goes down, each neighbour of A immediately detects that the direct link to A is inaccessible and sets the tentative cost to A to ∞ for that neighbour.
Neighbours advertise their routing information in the next synchronous update. Since A was the destination and its only connections were through those neighbours, there is no other node that can supply a valid finite route to A after the failure.
Therefore the information that A is unreachable (cost ∞) propagates outward across the network. After a number of synchronous update intervals equal to at most the network diameter, all nodes (including F) will record the cost to A as ∞.
Because t+100 is much larger than the graph diameter, by time t+100 the cost from F to A is ∞.
Key takeaway: Once a destination node fails and its immediate neighbours mark it unreachable, no alternate finite path appears in this topology, so the route cost becomes ∞ and that unreachable status propagates to all nodes.