up A. Fabrikant, E. Koutsoupias, and C. Papadimitriou. Heuristically Optimized Trade-offs: A New Paradigm for Power Laws in the Internet. In Proceedings of the 29th International Colloquium on Automata, Languages, and Programming (ICALP), pages 110--122, Malaga, Spain, July 2002.

Abstract:

We propose a plausible explanation of the power law distributions of degrees observed in the graphs arising in the Internet topology [Faloutsos, Faloutsos, and Faloutsos, SIGCOMM 1999] based on a toy model of Internet growth in which two objectives are optimized simultaneously: ``last mile'' connection costs, and transmission delays measured in hops. We also point out a similar phenomenon, anticipated in [Carlson and Doyle, Physics Review E 1999], in the distribution of file sizes. Our results seem to suggest that power laws tend to arise as a result of complex, multi-objective optimization.

 Postscript    Pdf    BibTeX  
 


Elias Koutsoupias / elias_at_di.uoa.gr