On Inferring Autonomous System Relationships in the Internet

This paper proposes heuristic algorithms that infer the AS relationships by constructing an annotated AS graph using BGP routing tables. It starts with a review of BGP using formal notation and a description of what happens when a route is imported and exported between ASes.

An AS graph can be annotated by using directed arcs to denote provider-customer relationships and different types undirected arcs to denote sibling and peer relationships respectively. Based on this annotated graph and observation of the AS_path attirbute, routes are categorized into customer, provider, and peer routes. It then assumes an export rule that indicates what types of routes are to be advertised to what types of neighboring ASes (Selective Export Rule). A reslut of this rule is that AS relationships can be determined: peers do not provide transit for each other, providers provide transit for customers, customers do not provide transit for providers, and siblings provide transit for each other. A path is defined to be valley-free iff a provider-customer edge can be followed by only provider-customer or sibling edges, and a peer edge can be followed by only provider-customer or sibling edges. Assuming the selective export rule, it is shown that BGP routing tables are valley-free. Another important assumption for the heuristic is that the top provider is the AS having the highest edge degree in an AS_path.

Using the top provider as a reference point, the direction of transit is determined within an AS_path and consequently, the links can be labeled sibling, provider-to-customer, or customer-to-provider. Taking into account the possibility that a router can be misconfigured resulting in a corruption of the structure which the labeling decision depends on, a refined algorithm detecting an asymetry of the number of transit is presented. Finally, peer relations are detected using the reasoning that peering can only happen with the neighbor of the top provider and it is likely to have a degree close to the top provider.

The format of this paper using formal notation helped me understand the ideas more effectively with little ambiguity compared to the tutorial. I am curious of what the real world consequences of every entity knowing the full AS relationships will be. And what value this information holds. Also, what attributes of a route entry can be manipulated and what cannot? Especially if the AS_path attribute can be changed freely and redistributed to other ASes, it will have huge consequences. Perhaps only prepending is allowed?