edited by
18,706 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

Best answer
199 votes
199 votes

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)

edited by
79 votes
79 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

38 votes
38 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 $

edited by
16 votes
16 votes

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$

Answer:

Related questions