edited by
5,221 views
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.

  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.

GATE2005-IT_85a

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.

  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{3} \\\hline \text{E}& \text{C} & \text{3} \\\hline  \text{F}& \text{C} & \text{4} \\\hline \end{array}}$
  2. $\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}}$
  3. $\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}}$
  4. $\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}}$
edited by

4 Answers

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.

edited by
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.
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.
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
Answer:

Related questions

15 votes
15 votes
3 answers
2
Ishrat Jahan asked Nov 3, 2014
5,913 views
Count to infinity is a problem associated with:link state routing protocol.distance vector routing protocolDNS while resolving host nameTCP for congestion control
27 votes
27 votes
3 answers
4
Ishrat Jahan asked Nov 3, 2014
19,345 views
Consider the following message $M = 1010001101$. The cyclic redundancy check (CRC) for this message using the divisor polynomial $x^5+x^4+x^2+1$ is :$01110$$01011$$10101$...