A group of 2n - 1 routers are interconnected in a centralised 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 j. The mean number of hops per message for large n, assuming that all router pairs are equally likely will be
| A. | n - 4 |
| B. | 2n - 1 |
| C. | n - 2 |
| D. | 2n - 4 |
Answer : D Explanation : Mean router-router path is twice the mean router-root path.
Number levels of the tree with the root as 1 and the deepest level as n.
Path from the root to level n requires n - 1 hops, and 0.50 of the routers are at this level. Path from root to level n - 1 has 0.25 of the routers, and a length of n – 2 hops. therefore, Mean path length l = 0.5 x (n-1) + 0.25 x (n-2) + 0.125 x (n-3) +....
The expression reduces to l = n – 2
Mean router-router path = 2n – 4.  |
|
|
Option: A Explanation : Explanation will come here. Explanation will come here. Explanation will come here. Explanation will come here. Explanation will come here. |
