The Gateway to Computer Science Excellence
+20 votes
1.8k views

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}}$
in Computer Networks by Boss (16.3k points)
edited by | 1.8k views
0
correct me if wrong plz?

initially for this graph all distances are 1 .I am calculating routing table on every node.After that for A ,its neighbour are B and C .At A i am calculating its distance vextor but i am stuck at that point when B-F=infinity,C-F infinity .

So for A how to calculate distance vector in F using B and C routing table .In given answer it is 3?pls someone help
0
Yes, (C) is the correct option.
0

 Manu Thakur

yes got it ,correct ans is c 

0
is this RIP?
+1
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.

5 Answers

+18 votes
Best answer

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

by Veteran (62.7k points)
edited by
0
i u have made a  mistake in table for node c where path to F costs only 2.
+2
@Prashant.

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

In node C table, last row needs correction !!
0
@Pavan

Although distances are right but next HOP in the C's table may be different rt...?
+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.
by Boss (33.8k points)
+1
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
+2
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
+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.
by Junior (887 points)
+6 votes
Answer-->C
by Junior (939 points)
+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
by Boss (10k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,508 answers
195,527 comments
100,961 users