GATE IT 2005 | Question: 85a

Question

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.

1. 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 $∞$.
2. From each accessible neighbour, it gets the costs to relay to other nodes via that neighbour (as the next hop).
3. 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.

• A. $\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}}$
• B. $\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}}$
• C. $\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}}$
• D. $\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}}$

Comments

 Manu Thakur

yes got it ,correct ans is c 

---

is this RIP?

---

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.

Answer 1

$$\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.

Comments

i u have made a  mistake in table for node c where path to F costs only 2.

---

@Prashant.

Your table for node C is also matching along with node B.

In node C table, last row needs correction !!

---

@Pavan

Although distances are right but next HOP in the C's table may be different rt...?

Answer 2

Answer: C

A, B, D do not give the shortest distance. After stabilizing, distance of all nodes from a specific node should be minimum.

Comments

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

---

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

Answer 3

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.

Answer 4

Correct option -

3)	Table for node B  A  A  1  B  -  -  C  C  1  D  D  1  E  C  2  F  D  2