On inferring autonomous system relationships in the Internet

By Lixin Gao. Global Communications Conference, 2000

1,291 citations recorded by the source corpus.

Interdomain routing in the Internet is coordinated by the border gateway protocol (BGP). BGP allows each autonomous system (AS) to choose its own policy in selecting routes and propagating reachability information to others. These routing policies are constrained by the contractual commercial agreements between administrative domains. Such policies imply that connectivity alone can not fully characterize the structural properties of the Internet. We propose an augmented AS graph representation that classifies AS relationships into customer-to-provider, peer-to-peer, and sibling to-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 that contains dose to 1 million route entries. The algorithms infer that more than 90.5% of the connected AS pairs have customer-to-provider relationships, less than 1.5% of the connected AS pairs have sibling-to-sibling relationships, and less than 8% of the connected AS pairs have peer-to-peer relationships. We verify our inference results with AT&T internal information on its relationship with neighboring ASs. 99% of our inference results are confirmed by the AT&T internal information. We also verify our inferred sibling-to-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 this is the first attempt in understanding and inferring AS relationships in the Internet. We show evidence that some routing table entries stem from unusual AS relationships or router misconfiguration.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/87c0f731c204e2c8f1bb6ef481fd961b4224e430

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Stable Internet routing without global coordination (2000, methodology): “Then, Section 6 discusses the robustness of our guidelines to changes in network topology, routing policies, and relationships between ASes.”
The origin of power laws in Internet topologies revisited (2002, background): “) and peers tend to be of comparable sizes [27].”
AS relationships: inference and validation (2006, methodology): “Gao assumed that every BGP path must comply with the following hierarchical pattern: an uphill segment of zero or more c2p or s2s links, followed by zero or one p2p links, followed by a downhill segment of zero or more p2c or s2s links.”
BRITE: an approach to universal topology generation (2001, background): “At the Autonomous System (AS) level, available information is richer because it can b e o tained or inferred from BGP tables [12, 7].”
Can internet video-on-demand be profitable? (2007, background): “Historically, the inference of AS relationships has been conservative [ 9 ], which is largely due to the fact that ISPs are unwilling to share their sibling and peering relationships.”
Network Discovery and Verification (2005, background): “There is an extensive body of related work studying various aspects of this approach, see e.g. [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12].”
Users get routed: traffic correlation on tor by realistic adversaries (2013, methodology): “We then use relationships identiﬁed in the CAIDA AS Relationships Dataset for July 2012, overwriting any relationships previously identiﬁed through Gao’s algorithm as necessary [10].”
A study of prefix hijacking and interception in the internet (2007, background): “We assume that Internet paths follow the “Valley-free” property [30], i.”
The impact of Internet policy and topology on delayed routing convergence (2001, result): “8 we could also presume that the graph G is acyclic; an assumption support by recent studies [16].”
Network topology generators: degree-based vs. structural (2002, methodology): “We use the results in [18] to infer provider-customer relation ships.”
Object replication strategies in content distribution networks (2002, methodology): “As discussed in [5], this method is slightly inaccurate because we cannot infer that all the connections are valid.”
Characterizing the Internet hierarchy from multiple vantage points (2002, background): “If every AS adheres to the customer and provider export rules, then no path should traverse a customer-provider edge after traversing a provider-customer or peer-peer edge, and no path would ever traverse more than one peer-peer edge [ 10 ], [16].”
MIRO: multi-path interdomain routing (2006, methodology): “To infer the relationships between ASes, we apply the algorith ms presented by Gao [11] and Agarwal [12], but only present results for the algorithm in [11] due to space limitation; a previous stu dy suggested that the Gao algorithm produces more accurate infere nc results [21].”
Locating internet routing instabilities (2004, background): “The policies outlined above capture only a small subset of all possible relationships between two ASes, but they seem to apply to a substantial part of the relationships [24, 25].”
Towards an accurate AS-level traceroute tool (2003, result): “As part our future work, we plan to compare our sibling inferences with the results of algorithms for inferring AS relationships from BGP AS paths [19, 20].”
Understanding BGP misconfiguration (2002, methodology): “Gao infers these relationships from the BGP tables based on the following observations [14].”
BRITE: Universal Topology Generation from a User''s Perspective (2001, background): “At the Autonomous System (AS) level, available information is richer because it can be obtained or inferred from BGP tables [17, 10].”