GATE IT 2007 | Question: 63

Question

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

• A. $3$
• B. $4.26$
• C. $4.53$
• D. $5.26$

Comments

@Kushagra गुप्ता

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?

---

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

---

Similar question: GATE2019-46

Answer 1

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)

Comments

What if the destination is in a different level than that of the source. Will this still be valid?

---

There seems to be an overcount. Source can be equal to destination ?

---

Please mention which one of the source or destination has been considered as hop in your solution, it is very ambiguous from your solution.

Answer 2

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

Comments

awesome

---

Lovely explanation:)

---

Best explanation !!

Answer 3

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 $

Comments

@Arjun Why did you taken destination in hop count?

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

---

same doubt, Why we are considering a destination router as a "hop" in the path?

---

Most easy and Best approach 

@Arjun Sir

Answer 4

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$

Comments

conceptually correct answer

---

should be the best answer.

---

This must be the best answer without any doubt, it is more correct

This question is actually repeated from this question

It was leaf to leaf distance and here we have all possible distances