DATA LINK LAYER

Question

A group of $2^n -1$ routers are interconnected in a centralized binary tree with a router at each tree node . Router 1 communicates with Router j by sending a message to the root of the tree. The root then sends a message back down to j  Derive an approximate expression for the minimum number of hops per message for large N , assuming that all the router pairs are equally likely

1). $2N-4$

2). $N-4/2$

3). $N-4/2$

4). $N-4$

Answer 1

Answer is 2N-4

 binary tre having 2ⁿ-1 routers

In Nth level of tree each node(router) will take n-1 hops to tranfer to root and half of the total routers are on this level. (n-1)*1/2 hops

N-1 level 's nodes will take n-2 hops to tranfer to root and half of the remaining routers are on this level. (n-2)*1/4 hops

N-2 level 's nodes will take n-3 hops to tranfer to root and half of the remaining routers are on this level. (n-3)*1/8 hops

N-3 level 's nodes will take n-4 hops to tranfer to root and half of the remaining routers are on this level. (n-4)*1/16 hops

So in total i router to root 

=  (n-1)*1/2+ (n-2)*1/4+ (n-3)*1/8+ (n-4)*1/16+......

= n-2 

Similarly root to router j again n-2

Mminimum no. Hops = 2(n-2)= 2n-4

Comments

How have you solved the generated series?