The DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
A first-principles approach to understanding the internet's router-level topology
Open accessAbstract
A detailed understanding of the many facets of the Internet's topological structure is critical for evaluating the performance of networking protocols, for assessing the effectiveness of proposed techniques to protect the network from nefarious intrusions and attacks, or for developing improved designs for resource provisioning. Previous studies of topology have focused on interpreting measurements or on phenomenological descriptions and evaluation of graph-theoretic properties of topology generators. We propose a complementary approach of combining a more subtle use of statistics and graph theory with a first-principles theory of router-level topology that reflects practical constraints and tradeoffs. While there is an inevitable tradeoff between model complexity and fidelity, a challenge is to distill from the seemingly endless list of potentially relevant technological and economic issues the features that are most essential to a solid understanding of the intrinsic fundamentals of network topology. We claim that very simple models that incorporate hard technological constraints on router and link bandwidth and connectivity, together with abstract models of user demand and network performance, can successfully address this challenge and further resolve much of the confusion and controversy that has surrounded topology generation and evaluation.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135
Statistical mechanics of complex networks
Albert, R., & Barabási, A.-L. (2002) · Reviews of Modern Physics · doi:10.1103/revmodphys.74.47 · Cited by 20,471
The Structure and Function of Complex Networks
Newman, M. E. J. (2003) · SIAM Review · doi:10.1137/s003614450342480 · Cited by 18,719
Error and attack tolerance of complex networks
Albert, R., Jeong, H., & Barabási, A.-L. (2000) · Nature · doi:10.1038/35019019 · Cited by 7,534
Error and attack tolerance of complex networks
Albert, R., Jeong, H., & Barabási, A.-Ĺ. (2000) · RePEc: Research Papers in Economics · Cited by 6,469
Epidemic Spreading in Scale-Free Networks
Pastor-Satorras, R., & Vespignani, A. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.3200 · Cited by 5,731
Assortative Mixing in Networks
Newman, M. E. J. (2002) · Physical Review Letters · doi:10.1103/physrevlett.89.208701 · Cited by 4,988
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication · doi:10.1145/316188.316229 · Cited by 4,196
Routing of multipoint connections
Waxman, B. M. (1988) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.12889 · Cited by 2,885
Measuring ISP topologies with rocketfuel
Spring, N., Mahajan, R., & Wetherall, D. (2002) · Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/633025.633039 · Cited by 1,256
BRITE: an approach to universal topology generation
Medina, A., Lakhina, A., Matta, I., & Byers, J. (2002) · MASCOTS 2001, Proceedings Ninth International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems · doi:10.1109/mascot.2001.948886 · Cited by 1,226
A Brief History of Generative Models for Power Law and Lognormal Distributions
Mitzenmacher, M. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129088 · Cited by 1,188
On inferring autonomous system relationships in the Internet
Gao, L. (2001) · IEEE/ACM Transactions on Networking · doi:10.1109/90.974527 · Cited by 1,070
A random graph model for massive graphs
Aiello, W., Chung, F., & Lu, L. (2000) · Proceedings of the thirty-second annual ACM symposium on Theory of computing · doi:10.1145/335305.335326 · Cited by 917
Carlson, J. M., & Doyle, J. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.012582499 · Cited by 814
Self-citationHeuristics for Internet map discovery
Govindan, R., & Tangmunarunkit, H. (2002) · Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064) · doi:10.1109/infcom.2000.832534 · Cited by 687
Modeling the Internet's large-scale topology
Yook, S.-H., Jeong, H., & Barabási, A.-L. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.172501399 · Cited by 665
On distinguishing between Internet power law topology generators
Bu, T., & Towsley, D. (2003) · Proceedings.Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies · doi:10.1109/infcom.2002.1019309 · Cited by 516
A quantitative comparison of graph-based models for Internet topology
Zegura, E. W., Calvert, K. L., & Donahoo, M. J. (1997) · IEEE/ACM Transactions on Networking · doi:10.1109/90.650138 · Cited by 482
The origin of power laws in Internet topologies revisited
Chen, Q., Chang, H., Govindan, R., & Jamin, S. (2003) · Proceedings.Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies · doi:10.1109/infcom.2002.1019306 · Cited by 430
On the origin of power laws in Internet topologies
Medina, A., Matta, I., & Byers, J. (2000) · ACM SIGCOMM Computer Communication Review · doi:10.1145/505680.505683 · Cited by 406
Network topology generators: degree-based vs. structural
Tangmunarunkit, H., Govindan, R., Jamin, S., Shenker, S., & Willinger, W. (2002) · Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/633025.633040 · Cited by 375
Self-citationHeuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet
Fabrikant, A., Koutsoupias, E., & Papadimitriou, C. H. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45465-9_11 · Cited by 325
A better model for generating test networks
Doar, M. B. (2002) · Proceedings of GLOBECOM'96. 1996 IEEE Global Telecommunications Conference · doi:10.1109/glocom.1996.586131 · Cited by 319
The Average Distance in a Random Graph with Given Expected Degrees
Chung, F., & Lu, L. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129081 · Cited by 307
Robustness and Vulnerability of Scale-Free Random Graphs
Bollobás, B., & Riordan, O. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129080 · Cited by 273
Scaling phenomena in the Internet: Critically examining criticality
Willinger, W., Govindan, R., Jamin, S., Paxson, V., & Shenker, S. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.012583099 · Cited by 213
Self-citationGenerating network topologies that obey power laws
Palmer, C. R., & Steffan, J. G. (2002) · IEEE Global Telecommunications Conference (GLOBECOM) · doi:10.1109/glocom.2000.892042 · Cited by 209
Internet topology: connectivity of IP graphs:
Broido, A., & claffy, K. (2001) · SPIE Proceedings · doi:10.1117/12.434393 · Cited by 163
Conductance and congestion in power law graphs
Gkantsidis, C., Mihail, M., & Saberi, A. (2003) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/781027.781046 · Cited by 122
Epidemic profiles and defense of scale-free networks
Briesemeister, L., Lincoln, P. D., & Porras, P. A. (2003) · Workshop on Rapid Malcode · doi:10.1145/948187.948200 · Cited by 88
Internet connectivity at the AS-level: an optimization-driven modeling approach
Chang, H., Jamin, S., & Willinger, W. (2003) · ACM SIGCOMM Workshop on Models, Methods and Tools for Reproducible Network Research (MoMeTools) · doi:10.1145/944773.944780 · Cited by 74
Self-citation
Cited by
Resisting structural re-identification in anonymized social networks
Hay, M., Miklau, G., Jensen, D., Towsley, D., & Weis, P. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1453856.1453873 · Cited by 549
Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications
Li, L., Alderson, D., Doyle, J. C., & Willinger, W. (2005) · Internet Mathematics · doi:10.1080/15427951.2005.10129111 · Cited by 519
Self-citationCan ISPS and P2P users cooperate for improved performance?
Aggarwal, V., Feldmann, A., & Scheideler, C. (2007) · ACM SIGCOMM Computer Communication Review · doi:10.1145/1273445.1273449 · Cited by 393
The internet AS-level topology: three data sources and one definitive metric
Mahadevan, P., Krioukov, D., Fomenkov, M., Dimitropoulos, X., claffy, K. C., & Vahdat, A. (2006) · ACM SIGCOMM Computer Communication Review · doi:10.1145/1111322.1111328 · Cited by 338
Assortativity in complex networks
Noldus, R., & Van Mieghem, P. (2015) · Journal of Complex Networks · doi:10.1093/comnet/cnv005 · Cited by 266
Metadata
- Authors
- Li, L., Alderson, D., Willinger, W., & Doyle, J.
- Venue
- Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications
- Publisher
- ACM
- Published
- 2004-08-30
- Pages
- 3-14
- OpenAlex
- W2167677198
- Cited by
- 354
- References
- 32
- FWCI
- 16.18
- Type
- conference paper
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.