Article

Free access

A first-principles approach to understanding the internet's router-level topology

Authors:

David Alderson,

Walter Willinger,

John DoyleAuthors Info & Claims

SIGCOMM '04: Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications

Pages 3 - 14

https://doi.org/10.1145/1015467.1015470

Published: 30 August 2004 Publication History

Abstract

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.

References

[1]

Abilene Network. Detailed information about the objectives, organization, and development of the Abilene network are available from http://www.internet2.edu/abilene.

[2]

W. Aiello, F. Chung, and L. Lu. A Random Graph Model for Massive Graphs. Proc. STOC 2000.

Digital Library

[3]

R. Albert, and A.-L. Barabási. Statistical Mechanics of Complex Networks, Rev. of Modern Physics (74), 2002.

[4]

R. Albert, H. Jeong, and A.-L. Barabási. Attack and error tolerance of complex networks, Nature 406, 378--382 (2000).

[5]

D. Alderson. Technological and Economic Drivers and Constraints in the Internet's "Last Mile", Tech Report CIT-CDS-04-004, California Institute of Technology (2004).

[6]

D. Alderson, J. Doyle, R. Govindan, and W. Willinger. Toward an Optimization-Driven Framework for Designing and Generating Realistic Internet Topologies. In ACM SIGCOMM Computer Communications Review, (2003).

Digital Library

[7]

A.-L. Barabási and R. Albert. Emergence of scaling in random networks, Science 286, 509--512 (1999).

[8]

B. Bollobás and O. Riordan. Robustness and vulnerability of scale-free random graphs, Internet Math. 1, pp. 1--35, 2003.

[9]

L. Briesemeister and P. Lincoln and P. Porras, Epidemic Profles and Defense of ScaleFree Networks, ACM Workshop on Rapid Malcode (WORM) October, 2003.

Digital Library

[10]

A. Broido and k. Claffy. Internet Topology: Connectivity of IP Graphs, Proceeding of SPIE ITCom WWW Conf. (2001).

[11]

T. Bu and D. Towsley. On distinguishing Between Internet Power Law Topology Generators, IEEE INFOCOM 2002.

[12]

K.L. Calvert, M. Doar, and E. Zegura., Modeling Internet topology, IEEE Communications Magazine, June (1997).

Digital Library

[13]

J.M. Carlson and J.Doyle. Complexity and Robustness PNAS, 99, Suppl. 1, 2539--2545 (2002).

[14]

H. Chang, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. Towards Capturing Representative AS-Level Internet Topologies Proc. of ACM SIGMETRICS 2002 (2002).

Digital Library

[15]

H. Chang, S. Jamin, and W. Willinger. Internet Connectivity at the AS-level: An Optimization-Driven Modeling Approach Proc. of MoMeTools 2003 (Extended version, Tech Report UM-CSE-475-03, 2003).

Digital Library

[16]

Q. Chen, H. Chang, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. The Origin of Power Laws in Internet Topologies Revisited, Proc. IEEE INFOCOM 2002.

[17]

F. Chung and L. Lu. The average distance in a random graph with given expected degrees, Internet Mathematics, 1, 91--113, 2003.

[18]

Corporation for Education Network Intitiatives in California (CENIC). Available at http://www.cenic.org.

[19]

Cooperative Association for Internet Data Analysis (CAIDA), Skitter. Available at http://www.caida.org/tools/measurement/skitter/.

[20]

M. B. Doar. A Better Model for Generating Test Networks. In Proc. of GLOBECOM 1996.

[21]

P. Erdos and A. Renyi. On random graphs I Publ. Math. (Debrecen) 9 (1959), 290--297.

[22]

A. Fabrikant, E. Koutsoupias, and C. Papadimitriou. Heuristically Optimized Trade-offs: A new paradigm for Power-laws in the Internet, Proc. ICALP 2002, 110--122.

Digital Library

[23]

M. Faloutsos, P. Faloutsos, and C. Faloutsos. On Power-Law Relationships of the Internet Topology, SIGCOMM 1999.

Digital Library

[24]

L. Gao. On inferring autonomous system relationships in the Internet, in Proc. IEEE Global Internet Symposium, 2000.

[25]

C. Gkantsidis, M. Mihail, A. Saberi. Conductance and congestion in power law graphs, ACM Sigmetrics 2003.

Digital Library

[26]

R. Govindan and H. Tangmunarunkit. Heuristics for Internet Map Discovery, Proc. IEEE INFOCOM 2000.

[27]

Internet2 Consortium. Internet2 NetFlow: Weekly Reports, Available at http://netflow.internet2.edu/weekly/.

[28]

C. Jin, Q. Chen, and S. Jamin. Inet: Internet Topology Generator. Technical Report CSE-TR443-00, Department of EECS, University of Michigan, 2000.

[29]

B.B. Mandelbrot. Fractals and Scaling in Finance: Discontinuity, Concentration, Risk. Springer-Verlag, 1997.

Digital Library

[30]

A. Medina, A. Lakhina, I. Matta, and J. Byers. BRITE: An Approach to Universal Topology Generation, in Proceedings of MASCOTS '01, August 2001.

Digital Library

[31]

A. Medina, I. Matta, and J. Byers. On the Origin of Power Laws in Internet Topologies, ACM SIGCOMM Computer Communications Review 30(2), 2000.

Digital Library

[32]

M. Mitzenmacher. A Brief History of Generative Models for Power Law and Lognormal Distributions, Internet Mathematics. To appear. (2003).

[33]

M.E.J. Newman Assortative Mixing in Networks, Phys. Rev. Lett. 89, 208701(2002).

[34]

M.E.J. Newman. The Structure and Function of Complex Networks, SIAM Review 45, 167--256 (2003).

Digital Library

[35]

A. M. Odlyzko. Internet traffic growth: Sources and implications, in Optical Transmission Systems and Equipment for WDM Networking II, B. B. Dingel, W. Weiershausen, A. K. Dutta, and K.-I. Sato, eds., Proc. SPIE, vol. 5247, 2003, pp. 1--15.

[36]

C. R. Palmer and J. G. Steffan. Generating network topologies that obey power laws. Proc. GLOBECOM 2000.

[37]

R. Pastor-Satorras and A. Vespignani. Epidemic spreading in scale-free networks Physical Review Letters, 86(14), pp. 3200--3203, April 2, 2001.

[38]

M. Roughan, A. Greenberg, C. Kalmanek, M. Rumsewicz, J. Yates and Y. Zhang. Experience in Measuring Backbone Traffic Variability: Models, Metrics, Measurements and Meaning International Teletraffic Congress (ITC) 18, 2003.

[39]

Route Views, University of Oregon Route Views Project, Available at http://www.antc.uoregon.edu/route-views/.

[40]

N. Spring, R. Mahajan, and D. Wetherall. Measuring ISP Topologies with Rocketfuel, Proc. ACM SIGCOMM 2002.

Digital Library

[41]

L. Subramanian, S. Agarwal, J. Rexford, and R. Katz. Characterizing the Internet Hierarchy from Multiple Vantage Points, Proc. IEEE INFOCOM 2002.

[42]

H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. Network Topology Generators: Degree-Based vs. Structural, In Proc. ACM SIGCOMM 2002.

Digital Library

[43]

State of Washington Master Contract for Cisco Products, June 2002. Available from http://techmall.dis.wa.gov/master_contracts/intranet/routers_switches.asp

[44]

B.M. Waxman. Routing of multipoint connections, IEEE Jour. of Selected Areas in Comm., Vol. 6, No. 9, 1988.

[45]

W. Willinger, R. Govindan, S. Jamin, V. Paxson and S. Shenker. Scaling Phenomena in the Internet: Critically examining Criticality Proc. Nat. Acad. Sci., 99, suppl. 1, pp. 2573--2580 (2002).

[46]

K.Wu and A. Liu. The Rearrangement Inequality http://matholymp.com/TUTORIALS/Rear.pdf

[47]

S.-H. Yook, H. Jeong, and A.-L. Barabási. Modeling the Internet's large-scale topology, PNAS 99, 13382-86 (2002).

[48]

E. Zegura, K.L. Calvert, and M.J. Donahoo. A quantitative comparison of graph-based models for Internet topology. IEEE/ACM Transactions on Networking, Vol. 5, No. 6, 1997.

Digital Library

Cited By

Liu YWang ZLi PWang C(2024)Research on Modeling Technology for the Internet Routing System Based on Knowledge Graph2024 9th International Conference on Computer and Communication Systems (ICCCS)10.1109/ICCCS61882.2024.10602828(660-665)Online publication date: 19-Apr-2024
https://doi.org/10.1109/ICCCS61882.2024.10602828
Ivanko EChernoskutov M(2022)The Random Plots Graph Generation Model for Studying Systems with Unknown Connection StructuresEntropy10.3390/e2402029724:2(297)Online publication date: 20-Feb-2022
https://doi.org/10.3390/e24020297
Alderson DDoyle JWillinger W(2019)Lessons from "a first-principles approach to understanding the internet's router-level topology"ACM SIGCOMM Computer Communication Review10.1145/3371934.337196449:5(96-103)Online publication date: 8-Nov-2019
https://dl.acm.org/doi/10.1145/3371934.3371964
Show More Cited By

Index Terms

A first-principles approach to understanding the internet's router-level topology
1. Networks
  1. Network architectures

Recommendations

A first-principles approach to understanding the internet's router-level topology

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 ...
Understanding internet topology: principles, models, and validation

Building on a recent effort that combines a first-principles approach to modeling router-level connectivity with a more pragmatic use of statistics and graph theory, we show in this paper that for the Internet, an improved understanding of its physical ...
Analyzing and Modeling Router---Level Internet Topology
Information Networking. Towards Ubiquitous Networking and Services

Measurement studies on the Internet topology show that connectivities of nodes exhibit power---law attribute, but it is apparent that only the degree distribution does not determine the network structure, and especially true when we study the network---...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGCOMM '04: Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications

August 2004

402 pages

ISBN:1581138628

DOI:10.1145/1015467

General Chair:
Raj Yavatkar
Intel Corporation
,
Program Chairs:
Ellen Zegura
Georgia Institute of Technology
,
Jennifer Rexford
AT&T Labs -- Research

ACM SIGCOMM Computer Communication Review Volume 34, Issue 4
October 2004
385 pages
ISSN:0146-4833
DOI:10.1145/1030194
Issue’s Table of Contents

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 August 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGCOMM04

Sponsor:

SIGCOMM04: ACM SIGCOMM 2004 Conference

August 30 - September 3, 2004

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

298
Total Citations
View Citations
2,744
Total Downloads

Downloads (Last 12 months)242
Downloads (Last 6 weeks)34

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu YWang ZLi PWang C(2024)Research on Modeling Technology for the Internet Routing System Based on Knowledge Graph2024 9th International Conference on Computer and Communication Systems (ICCCS)10.1109/ICCCS61882.2024.10602828(660-665)Online publication date: 19-Apr-2024
https://doi.org/10.1109/ICCCS61882.2024.10602828
Ivanko EChernoskutov M(2022)The Random Plots Graph Generation Model for Studying Systems with Unknown Connection StructuresEntropy10.3390/e2402029724:2(297)Online publication date: 20-Feb-2022
https://doi.org/10.3390/e24020297
Alderson DDoyle JWillinger W(2019)Lessons from "a first-principles approach to understanding the internet's router-level topology"ACM SIGCOMM Computer Communication Review10.1145/3371934.337196449:5(96-103)Online publication date: 8-Nov-2019
https://dl.acm.org/doi/10.1145/3371934.3371964
Gullapalli YKoritzinsky JSyamkumar MBarford PDurairajan RSommers J(2019)BokehProceedings of the 3rd ACM SIGSPATIAL International Workshop on Location-based Recommendations, Geosocial Networks and Geoadvertising10.1145/3356994.3365501(1-10)Online publication date: 5-Nov-2019
https://dl.acm.org/doi/10.1145/3356994.3365501
Tune PRoughan MWiren C(2018)Hierarchical Traffic Matrices: Axiomatic Foundations to Practical Traffic Matrix Synthesis2018 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC)10.23919/APSIPA.2018.8659593(1591-1600)Online publication date: Nov-2018
https://doi.org/10.23919/APSIPA.2018.8659593
Mourrat JValesin D(2018)Spatial Gibbs random graphsThe Annals of Applied Probability10.1214/17-AAP131628:2Online publication date: 1-Apr-2018
https://doi.org/10.1214/17-AAP1316
Kaur NSingh AKumar NSrivastava SShekhawat RGaur MElci AVaidya JMakarevich OPoet ROrgun MDhaka VBohra MSingh VBabenko LSheykhkanloo NRahnama B(2017)Performance impact of topology poisoning attack in SDN and its countermeasureProceedings of the 10th International Conference on Security of Information and Networks10.1145/3136825.3136881(179-184)Online publication date: 13-Oct-2017
https://dl.acm.org/doi/10.1145/3136825.3136881
Luckie MBeverly R(2017)The Impact of Router Outages on the AS-level InternetProceedings of the Conference of the ACM Special Interest Group on Data Communication10.1145/3098822.3098858(488-501)Online publication date: 7-Aug-2017
https://dl.acm.org/doi/10.1145/3098822.3098858
Kamamura SFukuda AYamamoto HDate HHayashi RUematsu Y(2017)Resolution of network topology using fast graph mining2017 IEEE International Conference on Communications (ICC)10.1109/ICC.2017.7997447(1-6)Online publication date: May-2017
https://doi.org/10.1109/ICC.2017.7997447
Nicholas PTkacheff JKuhns CHuschka TChick S(2016)Measuring the operational impact of military SATCOM degradationProceedings of the 2016 Winter Simulation Conference10.5555/3042094.3042478(3087-3097)Online publication date: 11-Dec-2016
https://dl.acm.org/doi/10.5555/3042094.3042478
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents