On Inferring Autonomous System Relationships in the Internet

This paper describes a technique for inferring an annotated graph of AS to AS links. The annotations describe three types of relationships, one of which is directional, based on the export policies of the ASs:

• provider to customer — a provider exports any routes on these links and a customer only exports its and its own customers' routes
  
• peer to peer — only routes to customers (and the parties themselves) are exported
  
• sibling to sibling — both customer and peer and provider routes may be exported
  

The authors infer these relationships from the AS paths in a number of BGP-derived routing tables from various peering points on the Internet. The authors work based on two assumptions:

• AS paths are valley free (that is, they contain zero or more customer-to-provider and sibling-to-sibling links followed by zero or one peer-to-peer links followed by zero or more provider-to-customer and sibling-to-sibling links)
  
• the highest degree AS in a path is the ‘top’ of the path (that is, all customer-to-provider links occur before it appears and all provider-to-customer links occur after it)
  

From these assumptions, the authors can determine that every AS before the ‘top’ AS gets transit from the following AS in the AS path and every AS after the top gives transit to the following AS. These transit relationships distinguish provider-to-customer links from other types of links. Then peering relationships can be found by determining based on no customer-to-provider routes being exported through a peering link. Some extra heuristics are used to deal with misconfigured BGP sites or exceptions where an apparent customer that (probably accidentally, the authors assume) provides transit between their two providers; ordinarily, the algorithm would infer that this was not a provider/customer relationship.

The authors ran their inference algorithm over BGP routing tables observed from 24 sites and compared their results to AT&T internal information about their own AS-AS relationship. They found that the inferences were mostly — approximately 99% — accurate for the AT&T. There were some notable errors; for example, they inferred that AT&T had a provider, characterized several customers (with ASs) as having no relationship to AT&T entirely and most of the sibling-to-sibling relationships they identified AT&T has having were considered other types of relationships by AT&T.

Based on a manual analysis, the authors blame their errors primarily on misconfigurations and inter-AS relationships not fitting into their simplistic model and the inaccuracy of their heuristic. Unfortunately, the authors do not attempt to quantify the relative effect of these issues and it is not apparent from their single example what sort of AS relationships could be added to make a substantially more complete model. The heuristics used are generally a bit disappointing: do the authors have good evidence that AS degree really determines the top of the path? is there a better way to ignore incorrectly advertised customer-to-provider paths (e.g. by noticing they typically won't ever be used).