Is the Internet Fractal? The Multicast Power Law Revisited

Cédric Adjih 1 Leonidas Georgiadis 1 Philippe Jacquet 1 Wojciech Szpankowski 1
1 HIPERCOM - High performance communication
Inria Paris-Rocquencourt, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : 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.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00072466
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 10:02:06 AM
Last modification on : Thursday, February 7, 2019 - 4:45:49 PM
Long-term archiving on : Sunday, April 4, 2010 - 11:08:59 PM

Identifiers

  • HAL Id : inria-00072466, version 1

Collections

Citation

Cédric Adjih, Leonidas Georgiadis, Philippe Jacquet, Wojciech Szpankowski. Is the Internet Fractal? The Multicast Power Law Revisited. [Research Report] RR-4157, INRIA. 2001. ⟨inria-00072466⟩

Share

Metrics

Record views

291

Files downloads

243