Lun Li
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.
- Abilene Network. Detailed information about the objectives, organization, and development of the Abilene network are available from http://www.internet2.edu/abilene.Google Scholar
- W. Aiello, F. Chung, and L. Lu. A Random Graph Model for Massive Graphs. Proc. STOC 2000. Google ScholarDigital Library
- R. Albert, and A.-L. Barabási. Statistical Mechanics of Complex Networks, Rev. of Modern Physics (74), 2002.Google Scholar
- R. Albert, H. Jeong, and A.-L. Barabási. Attack and error tolerance of complex networks, Nature 406, 378--382 (2000).Google ScholarCross Ref
- 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).Google Scholar
- 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). Google ScholarDigital Library
- A.-L. Barabási and R. Albert. Emergence of scaling in random networks, Science 286, 509--512 (1999).Google Scholar
- B. Bollobás and O. Riordan. Robustness and vulnerability of scale-free random graphs, Internet Math. 1, pp. 1--35, 2003.Google Scholar
- L. Briesemeister and P. Lincoln and P. Porras, Epidemic Profles and Defense of ScaleFree Networks, ACM Workshop on Rapid Malcode (WORM) October, 2003. Google ScholarDigital Library
- A. Broido and k. Claffy. Internet Topology: Connectivity of IP Graphs, Proceeding of SPIE ITCom WWW Conf. (2001).Google Scholar
- T. Bu and D. Towsley. On distinguishing Between Internet Power Law Topology Generators, IEEE INFOCOM 2002.Google Scholar
- K.L. Calvert, M. Doar, and E. Zegura., Modeling Internet topology, IEEE Communications Magazine, June (1997). Google ScholarDigital Library
- J.M. Carlson and J.Doyle. Complexity and Robustness PNAS, 99, Suppl. 1, 2539--2545 (2002).Google Scholar
- H. Chang, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. Towards Capturing Representative AS-Level Internet Topologies Proc. of ACM SIGMETRICS 2002 (2002). Google ScholarDigital Library
- 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). Google ScholarDigital Library
- 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.Google Scholar
- F. Chung and L. Lu. The average distance in a random graph with given expected degrees, Internet Mathematics, 1, 91--113, 2003.Google Scholar
- Corporation for Education Network Intitiatives in California (CENIC). Available at http://www.cenic.org.Google Scholar
- Cooperative Association for Internet Data Analysis (CAIDA), Skitter. Available at http://www.caida.org/tools/measurement/skitter/.Google Scholar
- M. B. Doar. A Better Model for Generating Test Networks. In Proc. of GLOBECOM 1996.Google ScholarCross Ref
- P. Erdos and A. Renyi. On random graphs I Publ. Math. (Debrecen) 9 (1959), 290--297.Google Scholar
- 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. Google ScholarDigital Library
- M. Faloutsos, P. Faloutsos, and C. Faloutsos. On Power-Law Relationships of the Internet Topology, SIGCOMM 1999. Google ScholarDigital Library
- L. Gao. On inferring autonomous system relationships in the Internet, in Proc. IEEE Global Internet Symposium, 2000.Google Scholar
- C. Gkantsidis, M. Mihail, A. Saberi. Conductance and congestion in power law graphs, ACM Sigmetrics 2003. Google ScholarDigital Library
- R. Govindan and H. Tangmunarunkit. Heuristics for Internet Map Discovery, Proc. IEEE INFOCOM 2000.Google ScholarCross Ref
- Internet2 Consortium. Internet2 NetFlow: Weekly Reports, Available at http://netflow.internet2.edu/weekly/.Google Scholar
- C. Jin, Q. Chen, and S. Jamin. Inet: Internet Topology Generator. Technical Report CSE-TR443-00, Department of EECS, University of Michigan, 2000.Google Scholar
- B.B. Mandelbrot. Fractals and Scaling in Finance: Discontinuity, Concentration, Risk. Springer-Verlag, 1997. Google ScholarDigital Library
- A. Medina, A. Lakhina, I. Matta, and J. Byers. BRITE: An Approach to Universal Topology Generation, in Proceedings of MASCOTS '01, August 2001. Google ScholarDigital Library
- A. Medina, I. Matta, and J. Byers. On the Origin of Power Laws in Internet Topologies, ACM SIGCOMM Computer Communications Review 30(2), 2000. Google ScholarDigital Library
- M. Mitzenmacher. A Brief History of Generative Models for Power Law and Lognormal Distributions, Internet Mathematics. To appear. (2003).Google Scholar
- M.E.J. Newman Assortative Mixing in Networks, Phys. Rev. Lett. 89, 208701(2002).Google Scholar
- M.E.J. Newman. The Structure and Function of Complex Networks, SIAM Review 45, 167--256 (2003).Google ScholarDigital Library
- 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.Google Scholar
- C. R. Palmer and J. G. Steffan. Generating network topologies that obey power laws. Proc. GLOBECOM 2000.Google ScholarCross Ref
- R. Pastor-Satorras and A. Vespignani. Epidemic spreading in scale-free networks Physical Review Letters, 86(14), pp. 3200--3203, April 2, 2001.Google ScholarCross Ref
- 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.Google Scholar
- Route Views, University of Oregon Route Views Project, Available at http://www.antc.uoregon.edu/route-views/.Google Scholar
- N. Spring, R. Mahajan, and D. Wetherall. Measuring ISP Topologies with Rocketfuel, Proc. ACM SIGCOMM 2002. Google ScholarDigital Library
- L. Subramanian, S. Agarwal, J. Rexford, and R. Katz. Characterizing the Internet Hierarchy from Multiple Vantage Points, Proc. IEEE INFOCOM 2002.Google ScholarCross Ref
- H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. Network Topology Generators: Degree-Based vs. Structural, In Proc. ACM SIGCOMM 2002. Google ScholarDigital Library
- State of Washington Master Contract for Cisco Products, June 2002. Available from http://techmall.dis.wa.gov/master_contracts/intranet/routers_switches.aspGoogle Scholar
- B.M. Waxman. Routing of multipoint connections, IEEE Jour. of Selected Areas in Comm., Vol. 6, No. 9, 1988.Google Scholar
- 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).Google Scholar
- K.Wu and A. Liu. The Rearrangement Inequality http://matholymp.com/TUTORIALS/Rear.pdfGoogle Scholar
- S.-H. Yook, H. Jeong, and A.-L. Barabási. Modeling the Internet's large-scale topology, PNAS 99, 13382-86 (2002).Google ScholarCross Ref
- 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. Google ScholarDigital Library
Index Terms
- A first-principles approach to understanding the internet's router-level topology
Recommendations
Lessons from "a first-principles approach to understanding the internet's router-level topology"
Our main purpose for this editorial is to reiterate the main message that we tried to convey in our SIGCOMM'04 paper but that got largely lost in all the hype surrounding the use of scale-free network models throughout the sciences in the last two ...
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 ...
Comments