23 votes 23 votes 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 updated 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. $\overset{\text{Table for node A}}{\begin{array}{|c|c|c|} \hline \text {A} & \text{-} &\text{-} \\\hline \text{B}& \text{B} & \text{1} \\\hline \text{C}& \text{C} & \text{1} \\\hline \text{D}& \text{B} & \text{3} \\\hline \text{E}& \text{C} & \text{3} \\\hline \text{F}& \text{C} & \text{4} \\\hline \end{array}}$ $\overset{\text{Table for node C}}{\begin{array}{|c|c|c|} \hline \text {A} & \text{A} &\text{1} \\\hline \text{B}& \text{B} & \text{1} \\\hline \text{C}& \text{-} & \text{-} \\\hline \text{D}& \text{D} & \text{1} \\\hline \text{E}& \text{E} & \text{1} \\\hline \text{F}& \text{E} & \text{3} \\\hline \end{array}}$ $\overset{\text{Table for node B}}{\begin{array}{|c|c|c|} \hline \text {A} & \text{A} &\text{1} \\\hline \text{B}& \text{-} & \text{-} \\\hline \text{C}& \text{C} & \text{1} \\\hline \text{D}& \text{D} & \text{1} \\\hline \text{E}& \text{C} & \text{2} \\\hline \text{F}& \text{D} & \text{2} \\\hline \end{array}}$ $\overset{\text{Table for node D}}{\begin{array}{|c|c|c|} \hline \text {A} & \text{B} &\text{3} \\\hline \text{B}& \text{B} & \text{1} \\\hline \text{C}& \text{C} & \text{1} \\\hline \text{D}& \text{-} & \text{-} \\\hline \text{E}& \text{E} & \text{1} \\\hline \text{F}& \text{F} & \text{1} \\\hline \end{array}}$ Computer Networks gateit-2005 computer-networks routing normal + – Ishrat Jahan asked Nov 3, 2014 • edited Apr 13, 2019 by ajaysoni1924 Ishrat Jahan 5.3k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments set2018 commented Dec 10, 2017 reply Follow Share Manu Thakur yes got it ,correct ans is c 0 votes 0 votes Mk Utkarsh commented Jan 6, 2018 reply Follow Share is this RIP? 0 votes 0 votes Sonu Kumar 1 commented Jan 25, 2018 i moved by Puja Mishra Jan 30, 2018 reply Follow Share No need to make table for each router. Just use your intuition and see what is the length of shortest path possible between each pair of routers and try to match with the given options. 2 votes 2 votes Please log in or register to add a comment.
Best answer 21 votes 21 votes $$\overset{\text{Table for Node A}}{\begin{array}{|c|c|c|} \hline \text {A} & \text{-} &\text{-} \\\hline \text{B}& \text{B} & \text{1} \\\hline \text{C}& \text{C} & \text{1} \\\hline \text{D}& \text{B} & \text{2} \\\hline \text{E}& \text{C} & \text{2} \\\hline \text{F}& \text{C} & \text{3} \\\hline \end{array}} \quad \overset{\text{Table for Node D}}{\begin{array}{|c|c|c|} \hline \text {A} & \text{B} &\text{2} \\\hline \text{B}& \text{B} & \text{1} \\\hline \text{C}& \text{C} & \text{1} \\\hline \text{D}& \text{-} & \text{-} \\\hline \text{E}& \text{E} & \text{1} \\\hline \text{F}& \text{F} & \text{1} \\\hline \end{array}} \quad \overset{\text{Table for Node C}}{\begin{array}{|c|c|c|} \hline \text {A} & \text{A} &\text{1} \\\hline \text{B}& \text{B} & \text{1} \\\hline \text{C}& \text{-} & \text{-} \\\hline \text{D}& \text{D} & \text{1} \\\hline \text{E}& \text{E} & \text{1} \\\hline \text{F}& \text{D} & \text{2} \\\hline \end{array}} \quad \overset{\text{Table for Node B}}{\begin{array}{|c|c|c|} \hline \text {A} & \text{A} &\text{1} \\\hline \text{B}& \text{-} & \text{-} \\\hline \text{C}& \text{C} & \text{1} \\\hline \text{D}& \text{D} & \text{1} \\\hline \text{E}& \text{C} & \text{2} \\\hline \text{F}& \text{D} & \text{2} \\\hline \end{array}}$$ Correct tables are as above. Only option C is matching. Prashant. answered Aug 8, 2016 • edited Apr 13, 2019 by ajaysoni1924 Prashant. comment Share Follow See all 3 Comments See all 3 3 Comments reply ankyAS commented Jan 15, 2017 reply Follow Share i u have made a mistake in table for node c where path to F costs only 2. 0 votes 0 votes Kapil commented Apr 7, 2017 reply Follow Share @Prashant. Your table for node C is also matching along with node B. In node C table, last row needs correction !! 2 votes 2 votes vishalshrm539 commented Jan 18, 2018 reply Follow Share @Pavan Although distances are right but next HOP in the C's table may be different rt...? 0 votes 0 votes Please log in or register to add a comment.
11 votes 11 votes Answer: C A, B, D do not give the shortest distance. After stabilizing, distance of all nodes from a specific node should be minimum. Rajarshi Sarkar answered Apr 8, 2015 Rajarshi Sarkar comment Share Follow See all 2 Comments See all 2 2 Comments reply Gate Mm commented Dec 4, 2015 reply Follow Share After stabilizing can it happen that there exists a better path but the node is not aware of.e.g here in table for c a better path to F exists using D.is it ok? @Arjun Sir 1 votes 1 votes Nit9 commented Jan 4, 2017 reply Follow Share stablizing means the algo will run for n-1 steps, and there no possible way that a beeter path is left. its similar to bellman ford algo 2 votes 2 votes Please log in or register to add a comment.
7 votes 7 votes after stabilizing ,the shortest path is given by option (C) but here some people might think option (B) as answer but they are mistaken as in the last row of option (b) although the distance from C to F via E is 3 units but its not the best path or shortest path since we have an alternate path from C to F via D with a distance of 2 units. so option (C) is right. dhruvkc123 answered Sep 1, 2017 dhruvkc123 comment Share Follow See all 0 reply Please log in or register to add a comment.
4 votes 4 votes Correct option - 3) Table for node B A A 1 B - - C C 1 D D 1 E C 2 F D 2 Paras Nath answered Sep 14, 2016 Paras Nath comment Share Follow See all 0 reply Please log in or register to add a comment.