Is the Internet Fractal? The Multicast Power Law Revisited
Résumé
One of the main benefits of multicast communication is the overall reduction of network load. To quantify this reduction, when compared to traditional unicast, experimental studies by Chuang and Sirbu indicated the so called power law which asserts that the number of links in a multicast delivery tree connecting a source to m (distinct) sites is in m^0.8. In order to explain theoretically this behavior, Phillips, Shenker, and Tangmunarunkit examined approximately the link number for a V-ary complete tree topology, and concluded that this number grows nearly linearly with m, thus not obeying the power law. We first re-examine the analysis by Phillips et.al. and provide precise asymptotic expansion for the link number that confirms the nearly linear (with some wobbling) growth. Claiming that the essence of the problem lies in the modeling assumptions, we replace the V-ary complete tree topology by a V-ary self-similar tree with similarity factor 0\leq\theta<1. In such a tree a node at level k is replicated CV^(D-k)\theta times, where D is the depth of the tree and C is a constant. Under this assumption, we analyze again L(m) and prove that L(m)\sim cm^1-\theta where c is an explicitly computable constant. Hence self-similar trees provide a plausible explanation of the multicast power law. Next, we examine more general conditions for general trees, under which the power law still holds. We also discuss some experimental results in real networks that reaffirm the power law and show that in these networks the general conditions hold.