edited by
18,709 views
62 votes
62 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

  1. $3$
  2. $4.26$
  3. $4.53$
  4. $5.26$
edited by

8 Answers

5 votes
5 votes

Answer: C

Put n = 4 in the formula given below:

3 votes
3 votes

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

Answer:

Related questions