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 updating interval, three tasks are performed.
(i) A node determines whether its neighbors in the graph are accessible. If so, it sets the tentative cost to each accessible neighbor as 1. Otherwise, the cost is set to ∞
(ii) From each accessible neighbor, it gets the costs to relay to other nodes via that neighbor (as the next hop).
(iii) Each node updates it 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.
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 updating interval, three tasks are performed.
(i) A node determines whether its neighbors in the graph are accessible. If so, it sets the tentative cost to each accessible neighbor as 1. Otherwise, the cost is set to ∞
(ii) From each accessible neighbor, it gets the costs to relay to other nodes via that neighbor (as the next hop).
(iii) Each node updates it 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.
The correct option is A
For node A routing table will be:
Bold edges showing the path:
For node B routing table will be:
Bold edges showing the path:
For node C routing table will be:
Bold edges showing the path:
For node D routing table will be:
Bold edges showing the path:
For node A routing table will be:
Bold edges showing the path:
For node B routing table will be:
Bold edges showing the path:
For node C routing table will be:
Bold edges showing the path:
For node D routing table will be:
Bold edges showing the path:
