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.Bib
@string{ICALP02 = {Proceedings of the 29th International Colloquium on
Automata, Languages, and Programming (ICALP)}}
@InProceedings{FKP02,
author = {A.Fabrikant and E. Koutsoupias and C. Papadimitriou},
title = {Heuristically Optimized Trade-offs: A New Paradigm for Power Laws in the Internet},
booktitle = ICALP02,
year = 2002,
address = {Malaga, Spain},
pages = {110--122},
}