skip to main content
10.1145/1282380.1282416acmconferencesArticle/Chapter ViewAbstractPublication PagescommConference Proceedingsconference-collections
Article
Free access

Observing the evolution of internet as topology

Published: 27 August 2007 Publication History

Abstract

Characterizing the evolution of Internet topology is important to our understanding of the Internet architecture and its interplay with technical, economic and social forces. A major challenge in obtaining empirical data on topology evolution is to identify real topology changes from the observed topology changes, since the latter can be due to either topology changes or transient routing dynamics. In this paper, we formulate the topology liveness problem and propose a solution based on the analysis of BGP data. We find that the impact of transient routing dynamics on topology observation decreases exponentially over time, and that the real topology dynamics consist of a constant-rate birth process and a constant-rate death process. Our model enables us to infer real topology changes from observation data with a given confidence level. We demonstrate the usefulness of the model by applying it to three applications: providing more accurate views of the topology, evaluating theoretical evolution models, and empirically characterizing the trends of topology evolution. We find that customer networks and provider networks have distinct evolution trends, which can provide an important input to the design of future Internet routing architecture.

References

[1]
Internet Routing Registry. http://www.irr.net/.
[2]
Regional Internet Registry data. ftp://www.ripe.net/pub/stats.
[3]
RIPE routing information service project. http://www.ripe.net/.
[4]
RouteViews routing table archive. http://www.routeviews.org/.
[5]
Skitter AS adjacency list. http://www.caida.org/tools/measurement/skitter/as_adjacencies.xml.
[6]
Skitter destination list. http://www.caida.org/analysis/topology/macroscopic/list.xml.
[7]
R. Albert and A.-L. Barabasi. Topology of evolving networks: local events and universality. Physical Review Letters, 85(24):5234--5237, 2000.
[8]
A.-L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509--512, 1999.
[9]
T. Bu and D. Towsley. On distinguishing between Internet power law topology generators. In Proc. of IEEE INFOCOM, 2002.
[10]
H. Chang, R. Govindan, S. Jamin, S. J. Shenker, and W. Willinger. Towards capturing representative AS-level Internet topologies. Elsevier Computer Networks Journal, 44(6):737--755, 2004.
[11]
H. Chang, S. Jamin, and W. Willinger. Inferring AS-level Internet topology from router-level path traces. In Proc. of SPIE ITCom, 2001.
[12]
H. Chang, S. Jamin, and W. Willinger. Internet connectivity at the AS-level: an optimization-driven modeling approach. In Proc ACM SIGCOMM MoMeTools workshop, 2003.
[13]
H. Chang, S. Jamin, and W. Willinger. To peer or not to peer: modeling the evolution of the Internet's AS-level topology. In Proc. of IEEE INFOCOM, 2006.
[14]
Q. Chen, H. Chang, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. The origin of power-laws in Internet topologies revisited. In Proc. of IEEE INFOCOM, 2002.
[15]
B. Chun, D. Culler, T. Roscoe, A. Bavier, L. Peterson, M. Wawrzoniak, and M. Bowman. Planetlab: an overlay testbed for broad-coverage services. ACM SIGCOMM Computer Comm. Review (CCR), 33(3):3--12, 2003.
[16]
A. Fabrikant, E. Koutsoupias, and C. Papadimitriou. Heuristically optimized tradeoffs: a new paradigm for power laws in the Internet. In Proc. of ICALP, 2002.
[17]
M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the internet topology. In Proc. of ACM SIGCOMM, 1999.
[18]
L. Gao. On inferring autonomous system relationships in the Internet. IEEE/ACM Transactions on Networking, 9(6):733--745, 2001.
[19]
R. Govindan and A. Reddy. An analysis of Internet inter-domain topology and route stability. In Proc. of IEEE INFOCOM, 1997.
[20]
G. Huston. AS Number Consumption. The ISP Column, September 2005.
[21]
Y. Hyun, A. Broido, and kc claffy. On third-party addresses in traceroute paths. In Proc. of Passive and Active Measurement Workshop (PAM), 2003.
[22]
L. Li, D. Alderson, W. Willinger, and J. Doyle. A first-principles approach to understanding the Internet's router-level topology. In Proc. of ACM SIGCOMM, 2004.
[23]
H. Madhyastha, T. Isdal, M. Piatek, C. Dixon, T. Anderson, A. Krishnamurthy, and A. Venkataramani. iPlane: an information plane for distributed services. In Proc. of OSDI, 2006.
[24]
P. Mahadevan, D. Krioukov, K. Fall, and A. Vahdat. Systematic topology analysis and generation using degree correlations. In Proc. of ACM SIGCOMM, 2006.
[25]
P. Mahadevan, D. Krioukov, M. Fomenkov, X. Dimitropoulos, kc claffy, and A. Vahdat. The Internet AS-level topology: three data sources and one definitive metric. ACM SIGCOMM Computer Comm. Review (CCR), 36(1):17--26, 2006.
[26]
Z. M. Mao, J. Rexford, J. Wang, and R. H. Katz. Towards an accurate AS-level traceroute tool. In Proc. of ACM SIGCOMM, 2003.
[27]
X. Meng, Z. Xu, B. Zhang, G. Huston, S. Lu, and L. Zhang. IPv4 address allocation and the BGP routing table evolution. SIGCOMM Computer Comm. Review (CCR), 35(1):71--80, 2005.
[28]
D. Raz and R. Cohen. The Internet dark matter: on the missing links in the AS connectivity map. In Proc. of IEEE INFOCOM, 2006.
[29]
Y. Shavitt and E. Shir. DIMES: Let the Internet measure itself. ACM SIGCOMM Computer Comm. Review (CCR), 35(5):71--74, 2005.
[30]
W. B. Norton. The art of peering: the peering playbook, 2002.
[31]
X. Wang and D. Loguinov. Wealth-based evolution model for the Internet AS-level topology. In Proc. of IEEE INFOCOM, 2006.
[32]
Y. He, G. Siganos, M. Faloutsos, S. V. Krishnamurthy. A systematic framework for unearthing the missing links: measurements and impact. In Proc. of NSDI, 2007.
[33]
B. Zhang, R. Liu, D. Massey, and L. Zhang. Collecting the Internet AS-level topology. ACM SIGCOMM Computer Comm. Review (CCR), 35(1):53--61, 2005.
[34]
S. Zhou and R. J. Mondragón. Accurately modeling the Internet topology. Physical Review E, 70(6):066108, 2004.

Cited By

View all
  • (2024)metAScritic: Reframing AS-Level Topology Discovery as a Recommendation SystemProceedings of the 2024 ACM on Internet Measurement Conference10.1145/3646547.3688429(337-364)Online publication date: 4-Nov-2024
  • (2024)The Use of Mobile Applications in the L2 Learning Classroom: Is it Worth the While?Smart Mobile Communication & Artificial Intelligence10.1007/978-3-031-54327-2_29(281-289)Online publication date: 27-Feb-2024
  • (2023)Research on predicting trusted business relationships in autonomous system based on neural networksThird International Conference on Green Communication, Network, and Internet of Things (CNIoT 2023)10.1117/12.3010226(6)Online publication date: 20-Oct-2023
  • Show More Cited By

Index Terms

  1. Observing the evolution of internet as topology

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SIGCOMM '07: Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications
    August 2007
    432 pages
    ISBN:9781595937131
    DOI:10.1145/1282380
    • cover image ACM SIGCOMM Computer Communication Review
      ACM SIGCOMM Computer Communication Review  Volume 37, Issue 4
      October 2007
      420 pages
      ISSN:0146-4833
      DOI:10.1145/1282427
      Issue’s Table of Contents
    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: 27 August 2007

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. internet topology
    2. topology evolution

    Qualifiers

    • Article

    Conference

    SIGCOMM07
    Sponsor:
    SIGCOMM07: ACM SIGCOMM 2007 Conference
    August 27 - 31, 2007
    Kyoto, Japan

    Acceptance Rates

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

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)125
    • Downloads (Last 6 weeks)20
    Reflects downloads up to 13 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)metAScritic: Reframing AS-Level Topology Discovery as a Recommendation SystemProceedings of the 2024 ACM on Internet Measurement Conference10.1145/3646547.3688429(337-364)Online publication date: 4-Nov-2024
    • (2024)The Use of Mobile Applications in the L2 Learning Classroom: Is it Worth the While?Smart Mobile Communication & Artificial Intelligence10.1007/978-3-031-54327-2_29(281-289)Online publication date: 27-Feb-2024
    • (2023)Research on predicting trusted business relationships in autonomous system based on neural networksThird International Conference on Green Communication, Network, and Internet of Things (CNIoT 2023)10.1117/12.3010226(6)Online publication date: 20-Oct-2023
    • (2022)Searching Personalized $k$-wing in Bipartite GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.3199592(1-14)Online publication date: 2022
    • (2022)Peering Only? Analyzing the Reachability Benefits of Joining Large IXPs TodayPassive and Active Measurement10.1007/978-3-030-98785-5_15(338-366)Online publication date: 22-Mar-2022
    • (2021)A square law revisitedACM SIGCOMM Computer Communication Review10.1145/3477482.347749051:3(41-45)Online publication date: 23-Jul-2021
    • (2018)Leveraging interconnections for performanceProceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication10.1145/3230543.3230576(206-220)Online publication date: 7-Aug-2018
    • (2018)Inferring persistent interdomain congestionProceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication10.1145/3230543.3230549(1-15)Online publication date: 7-Aug-2018
    • (2018)Evolution of the Internet AS-level topology: From nodes and edges to componentsChinese Physics B10.1088/1674-1056/27/12/12050127:12(120501)Online publication date: 19-Dec-2018
    • (2017)Preventing Distributed Denial-of-Service Flooding Attacks With Dynamic Path IdentifiersIEEE Transactions on Information Forensics and Security10.1109/TIFS.2017.268841412:8(1801-1815)Online publication date: 1-Aug-2017
    • Show More Cited By

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media