Towards Capturing Representative AS-Level Internet Topologies

TitleTowards Capturing Representative AS-Level Internet Topologies
Publication TypeConference Paper
Year of Publication2002
AuthorsChang, H., Govindan R., Jamin S., Shenker S., & Willinger W.
Published inProceedings of the International Conference on Measurements and Modeling of Computer Systems (SIGMETRICS 2002)
Other Numbers241

For the past two years,there has been a significant increase in research activities related to studying and modeling the Internet's topology, especially at the level of autonomous systems (ASs). A closer look at the measurements that form the basis for all these studies reveals that the data sets used consist of the BGP routing tables collected by the Oregon route server (henceforth, the Oregon route-views) [1]. So far, there has been anecdotal evidence and an intuitive understanding among researchers in the field that BGP-derived AS connectivity is not complete. However, as far as we know, there has been no systematic study on quantifying the completeness of currently known AS-level Internet topologies. Our main objective in this paper is to quantify the completeness of Internet AS maps constructed from the Oregon route-views and to attempt to capture more representative AS-level Internet topology. One of the main contributions of this paper is in developing a methodology that enables quantitative investigations into issues related to the (in)completeness of BGP-derived AS maps.


This work was partially supported by funding provided through National Science Foundation grants CNS:0082287 (“How to Generate Random Topologies with Internet-like Characteristics”) and through Office of Naval Research grant N000140110617. Sugih Jamin is further supported by the NSF CAREER Award ANI-9734145, the Presidential Early Career Award for Scientists and Engineers (PECASE) 1998, and the Alfred P. Sloan Foundation Research Fellowship 2001. Additional funding is provided by AT&T Research, and by equipment grants from Sun Microsystems Inc. and Compaq Corp. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors or originators and do not necessarily reflect the views of the funders.

Bibliographic Notes

Proceedings of the International Conference on Measurements and Modeling of Computer Systems (SIGMETRICS 2002), Marina Del Rey, California, pp. 280-281.

Abbreviated Authors

H. Chang, R. Govindan, S. Jamin, S. Shenker, and W. Willinger

ICSI Research Group

Networking and Security

ICSI Publication Type

Article in conference proceedings