The Gateway to Computer Science Excellence

+34 votes

A group of $15$ routers is interconnected in a centralized complete binary tree with a router at each tree node. Router $i$ communicates with router $j$ by sending a message to the root of the tree. The root then sends the message back down to router $j$. The mean number of hops per message, assuming all possible router pairs are equally likely is

- $3$
- $4.26$
- $4.53$
- $5.26$

+119 votes

Best answer

**OPTION is C.**

Here, we have to count average hops per message.

**Steps**:

1) Message goes up from sender to root

2) Message comes down from root to destination

1) Average hops message goes to root - $\dfrac{(3\times 8)+(2\times 4)+(1\times 2)+(0\times 1) }{15}=2.267$

Here $3\times 8$ represents $3$ hops & $8$ routers for Bottommost level & So on..

2) Similarly average hops when message comes down - $\dfrac{(3\times 8)+(2\times 4)+(1\times 2)+(0\times 1)}{15}$ {Same as above}

So, Total Hops $= 2\times 2.267 =4.53$ **(Answer)**

+4

It seems that Source and Destination can be same, by your answer. Isn't it? That results in a very small offset in your answer, from Arjun's. :p

0

@arjun sir @ manoj,@shresta,@kapil why it cant be like this:

1 leaf node can send message to other 7 leafnode and another leaf node can send to other 7 and so on

so it will be 8*8*3(considering leaf to root)

1 leaf node can send message to other 7 leafnode and another leaf node can send to other 7 and so on

so it will be 8*8*3(considering leaf to root)

0

yes that is

you r counting how a leaf can send a message.rt?

And he is calculating how many ways a message can be send.

See the last solution , it is what u r telling rt?

you r counting how a leaf can send a message.rt?

And he is calculating how many ways a message can be send.

See the last solution , it is what u r telling rt?

0

Are source and destination nodes too calculated as hops? For a leaf node, source to root will have 3 hops and root to the destination will have **2 hops. **But you are calculating root to the destination as 3 hops. Why are you counting destination as hop in the second step viz., root node to destination calculation?

+42 votes

Explanation: Consider Complete tree in Figure

If H wants to communicate with router at level 3 then it first sends packet to node A, then A forward packet to the router at Level 3; total 6 hops are required if A wants to communicate with any level 3 node.

Similarly, 5 hops are required if H wants to communicate with any level 2 node , 4 hops are required if H wants to communicate with any level 1 node and 3 hops are required if H wants to communicate with any level 0 node . Hops required if H wants to communicates with all other nodes = (8-1)*6 + 4*5+2*4 +1*3 = 73 If all 8 level 3 nodes communicates with all other nodes then hops required=73*8=584

Similarly, Hops required if D wants to communicates with all other nodes = 8*5 + (4-1)*4+2*3 +1*2 = 60 If all 4 level 2 nodes communicates with all other nodes then hops required=60*4=240 Hops required

if B wants to communicates with all other nodes = 8*4 + 4*3+(2-1)*2 +1*1 = 47 If all 4 level 2 nodes communicates with all other nodes then hops required=47*2=94 Hops required

if A wants to communicates with all other nodes = 8*3 + 4*2+2*1 = 34 Total hops required

when all nodes communicate with all other nodes=584+240+94+34= 952

Total number of message is 2 * 15C2 =2 * (15*14/2)=2*105=210 Here 2 is multiplied with 15C2 because in communication between A and B, A sends message to B and B sends message to A. The mean number of hops per message= 952/210= 4.53

+29 votes

The path length differs for nodes from each level. For a node in level $4,$

we have maximum no. of hops as follows,

Level | Max. no. of hops |
---|---|

1 | 3 (3-2-1) |

2 | 3+1 = 4 (3-2-1-2) |

3 | 3 + 2 = 5 (3-2-1-2-3) |

4 | 3 + 3 = 6 (3-2-1-2-3-4) |

So, mean no. of hops for a node in level $4$

$= \dfrac{1.3 + 2.4 + 4.5 + 7.6}{14} =\dfrac{73}{14}$, as we have $1, 2, 4$ and $8$ nodes

respectively in levels $1, 2, 3$ and $4$ and we discard the source one in level $4.$

Similarly, from a level $3$ node we get mean no. of hops,

$= \dfrac{1.2 + 2.3 + 3.4+ 8.5}{14} = \dfrac{60}{14}$

From level $2,$ we get mean no. of hops

$= \dfrac{1.1 +1.2 + 4.3 + 8.4}{14} = \dfrac{47}{14}$

And from level $1,$ we get, mean no. of hops

$= \dfrac {0 + 2.1 + 4.2 + 8.3}{14} = \dfrac{34}{14}$.

So, now we need to find the overall mean no. of hops which will be

$= \dfrac{\text{Sum of mean no. of hops for each node}}{\text{No. of nodes}}$

$= \dfrac{ \dfrac{73}{14} \times 8 + \dfrac{60}{14} \times 4 + \dfrac{47}{14} \times 2 + \dfrac{34}{14} \times 1}{15}$

$= \dfrac{68}{15}$

$= 4.53 $

0

@Arjun , Can you give me reference to more problems of this kind ?

This is very lengthy problem of averaging !

This is very lengthy problem of averaging !

0

not able to understand. plss sm 1 help me with representation of tree, how everything is being calculated?

+1

@Arjun Why did you taken destination in hop count?

https://en.wikipedia.org/wiki/Hop_(networking) diagram here says you shouldn't

+5 votes

+1 vote

And Now comes my answer , hope atleast someone will find it helpful

I am still so not know why to include destination in hop count. as wiki says we should not

https://en.wikipedia.org/wiki/Hop_(networking) but solving this question by including destination

Level | No of node |

1 | 1 |

2 | 2 |

3 | 4 |

4 | 8 |

path from level | path to level | no of such path | length of path | calculation |
---|---|---|---|---|

4 | 4 |
8C2 = 28 (path from any of level 4 node to level 4 node) |
6 | |

4 | 3 | 8*4 | 5 | |

4 | 2 | 8*2 | 4 | |

4 | 1 | 8*1 | 3 | |

3 | 3 | 4C2=6 | 4 | |

3 | 2 | 4*2=8 | 3 | |

3 | 1 | 4 | 2 | |

2 | 2 | 1 | 2 | |

2 | 1 | 2 | 1 | |

1 | 1 | 1 | 0 | |

Now multiply 'no of such path' with respective 'length of path' and divide by total of 'length of path' ANS is C

0 votes

**explanation by Amitabh Tiwari:-**

You have 8 leaves.

If a leaf wants to communicate to other 7 leaves ...each such communication would need 7 hops. So 7*7 hops for leaf to leaf communication.

Now each of these leaves can communicate with the 4 nodes in the level above them in 5 hops. So 4*5.

Each of these leaves can communicate with 2 nodes who are the children of root in 4 hops. So 2*4.

Each of these leaves could also communicate with root in 3 hops.

So on total for a single leaf average number of hops to communicate with all other nodes in tree is : (7*7 + 4*5 +2*4 + 3)/14

There are 8 such leaves:

So multiply the above expression by 8 to get average number of hops for communication of leaves with all other nodes in tree.

Now the way we did it for leaves.

Repeat the same procedure for nodes at level 2,level 1 and root.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,496 answers

195,489 comments

100,796 users