The Gateway to Computer Science Excellence
+34 votes
4.4k views

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$
in Computer Networks by Boss (16.3k points)
edited by | 4.4k views
0
Just find the expectation for each level of tree

7 Answers

+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)

by Boss (15.6k points)
edited by
+2

Nicely answered.Thanks Amsar smiley

0

Ur welcome.  smiley

+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)
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?
0
Excellent!!
0
beautifully explained ...
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

by (305 points)
0
in your solution assumption is that a router can't send a message to itself. anyway, it's a self understood thing that i is not equal to j.
great explanation!
0
Nice Explanation !!
0
Great explanation ..thanks.
0
@Iceberg

Nice explanation !!
0
i also initially thought the same way but did some calculation mistake. very nice answer. thanks
0
Great Explanation!!
+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 $

by Veteran (425k points)
edited by
0
@Arjun  , Can you give me reference to more problems of this kind ?

This is very lengthy problem of averaging !
0
@Akash , check my answer..
0
how to count the number of hops ?.
0
See now..
0
Thanks Arjun Sir....
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

Answer: C

Put n = 4 in the formula given below:

by Boss (33.8k points)
0
How you decide the n=4 ?

I am not getting plz tell ..
+2
15 nodes are there in a complete binary tree. So, $n=4$ as $2^n-1$ is the no. of nodes.
0
what book or e-book is this ?
+3
+1 vote
by Loyal (7.8k points)
+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

by Active (4.9k points)
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.

by Active (4.8k 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,496 answers
195,489 comments
100,796 users