On inferring autonomous system relationships in the Internet
Top Cited Papers
- 1 December 2001
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 9 (6) , 733-745
- https://doi.org/10.1109/90.974527
Abstract
The Internet consists of rapidly increasing number of hosts interconnected by constantly evolving networks of links and routers. Interdomain routing in the Internet is coordinated by the Border Gateway Protocol (BGP). The BGP allows each autonomous system (AS) to choose its own administrative policy in selecting routes and propagating reachability information to others. These routing policies are constrained by the contractual commercial agreements between administrative domains. For example, an AS sets its policy so that it does not provide transit services between its providers. Such policies imply that AS relationships are an important aspect of the Internet structure. We propose an augmented AS graph representation that classifies AS relationships into customer-provider, peering, and sibling relationships. We classify the types of routes that can appear in BGP routing tables based on the relationships between the ASs in the path and present heuristic algorithms that infer AS relationships from BGP routing tables. The algorithms are tested on publicly available BGP routing tables. We verify our inference results with AT&T internal information on its relationship with neighboring ASs. As much as 99.1% of our inference results are confirmed by the AT&T internal information. We also verify our inferred sibling relationships with the information acquired from the WHOIS lookup service. More than half of our inferred sibling-to-sibling relationships are confirmed by the WHOIS lookup service. To the best of our knowledge, there has been no publicly available information about AS relationships and this is the first attempt in understanding and inferring AS relationships in the Internet. We show evidence that some routing table entries stem from router misconfigurations.Keywords
This publication has 15 references indexed in Scilit:
- Experimental study of Internet stability and backbone failuresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- An analysis of Internet inter-domain topology and route stabilityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Heuristics for Internet map discoveryPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On the placement of Internet instrumentationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- IP network configuration for intradomain traffic engineeringIEEE Network, 2001
- The end-to-end effects of Internet path selectionACM SIGCOMM Computer Communication Review, 1999
- On power-law relationships of the Internet topologyACM SIGCOMM Computer Communication Review, 1999
- An architecture for a global Internet host distance estimation servicePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1999
- End-to-end routing behavior in the InternetIEEE/ACM Transactions on Networking, 1997
- A Border Gateway Protocol 4 (BGP-4)Published by RFC Editor ,1995