The Gateway to Computer Science Excellence

+41 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$

0

Ref: http://ledr.luon.net/documents/2IC10/bas_mark/week1.pdf

http://cseweb.ucsd.edu/~pblair/hwsoln/hwsoln.html

# of levels | # of routers |

1 | $2^1-1=1$ |

2 | $2^2-1=3$ |

3 | $2^3-1=7$ |

1000 (large value) | $2^{1000}-1\approx 2^{1000}$ |

At $n^{th}$ level, # of routers = $\dfrac{1}{2}\times 2^n$

At $(n-1)^{th}$ level, # of routers = $\dfrac{1}{4}\times 2^n$

.

.

At $n^{th}$ level, # of hops = $n-1$ hops

At $(n-1)^{th}$ level, # of hops = $n-2$ hops

.

.

Total # of hops from router to root router:

$\dfrac{1}{2}\times 2^n\times (n-1)+\dfrac{1}{4}\times 2^n\times (n-2)+$$\dfrac{1}{8}\times 2^n\times (n-3)+.....$

Putting values from the question:

$\dfrac{1}{2}\times 2^4\times 3+\dfrac{1}{4}\times 2^4\times 2+$$\dfrac{1}{8}\times 2^4\times 1=34$

Now when I am dividing $34$ with $16$ which has to be done will we get $2.125$ and in-order to find mean # of hops from router to another router you will multiply $2.125\times 2$ which will give you $4.25$ which close to option $B$.

But if I divide $34$ with $15(2^n-1),$ you will get asnwer as $4.53$ which is leading to option $C$

Where I am going wrong please do tell me sir.

0

I think your method is absolutely right.

But I didn't understand why you are dividing by 16, should it not be 15? We have only 15 routers right?

+2

# of levels | # of routers |

1 | $2^1-1=1$ |

2 | $2^2-1=3$ |

3 | $2^3-1=7$ |

4 | $2^{4}-1=15$ |

At $n^{th}$ level, # of routers = $\left \lceil \dfrac{1}{2}\times(2^n-1) \right \rceil$

At $(n-1)^{th}$ level, # of routers = $\left \lceil \dfrac{1}{4}\times(2^n-1) \right \rceil$

.

.

At $n^{th}$ level, # of hops = $n-1$ hops

At $(n-1)^{th}$ level, # of hops = $n-2$ hops

.

.

Total # of hops from router to root router:

$\left \lceil \dfrac{1}{2}\times (2^n-1) \right \rceil \times (n-1)+$ $\left \lceil \dfrac{1}{4}\times (2^n-1) \right \rceil \times (n-2)+$ $\left \lceil \dfrac{1}{8}\times (2^n-1)\right \rceil \times (n-3)+.....$

Putting values from the question:

$\left \lceil \dfrac{1}{2}\times (2^4-1)\right \rceil \times 3+\left \lceil \dfrac{1}{4}\times (2^4-1)\right \rceil \times 2+$ $\left \lceil \dfrac{1}{8}\times (2^4-1)\right \rceil \times 1=34$

$\dfrac{34}{15}=2.26$

mean # of hops from router to another router you will multiply $2.26\times 2$ which will give you $4.53$.

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

+5

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?

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

+1

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!

great explanation!

0

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.

for level 3 to level 3 then total 5 intermediate node then total 5 hop count .

how it conclude 6 hop count? why we take destination as hop

+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

+1 vote

Although steps maybe lengthy, this may seem more* intuitive* to some.

Given in the question:

assuming all possible router pairs

Meaning selection of any two routers is independent (same routers can be selected). Total possible selections = $15^{2} = 225$

Therefore,

- Maximum hops = $6$ (Leaf node to another leaf node)
- Minimum hops = $0$ (Root to root)

$Hop$ $Count$ | $Possibilities$ |

$6$ | $8*8 = 64$ |

$5$ | $8*4*2 = 64$ |

$4$ | $(2*8*2) + (4*4) = 48$ |

$3$ | $(8*1*2) + (4*2*2) = 32$ |

$2$ | $(4*1*2) + (2*2) = 12$ |

$1$ | $2*1*2 = 4$ |

$0$ | $1*1 = 1$ |

__ Explanation__ (assuming Root node is at level $1$):

- $6$ hops are only possible when you pick any 2 leaf nodes (3+3 hops), so pick any 2 leaf nodes independently, which is $8*8$.
- $5$ hops are only possible when one node is a leaf and another node is in level $3$, hence $8*4$. Pick the source node (the node which will send the message) in 2 ways, giving a total of $2*8*4$ possibilities.
- $4$ hops are possible in 2 cases:

- One node is a leaf and another node in level $2$, giving $8*2*2$ possibilities (2 ways to pick the source node).

- Both nodes are in level $3$, giving $4*4$ possibilities.

Apply similar reasoning to the remaining possible hop counts.

Let $X$ be a discrete random variable denoting possible hops, i.e. $P(X=k)$ gives the probability of having $k$ hops.

Hence, expected number of hops:

$E[X] = 6*P(X=6) + 5*P(X=5) + 4*P(X=4) + 3*P(X=3) + 2*P(X=2) + 1*P(X=1) + 0*P(X=0)$

$= \frac{1}{225}* [(64*6) + (64*5) + (48*4) + (32*3) + (12*2) + (4*1) + (1*0)] = \frac{1020}{225} = 4.533333 \approx 4.53$

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.

52,345 questions

60,503 answers

201,881 comments

95,331 users