On Inferring Autonomous System Relationships in the Internet

ASes connect to each other in several different relationships - either customer-provider, peering, or sibling relationships. However, companies are quite secret about what their actual relationships are with other ASes. This paper uses several heuristics to try to infer the relationships between ASes. The connections between ASes can be thought of as graphs, with each vertex being an AS and each edge being a relationship to another AS. The degree of a vertex can give an idea how big an AS is. Furthermore, customer-provider edges are directed, while peering and sibling edges are undirected.

Based on the nature of these relationships, ASes have selective export policies which can be observed and can be identified into different patterns which can help determine the relationship among ASes. After some initial tweaking of the heuristic, the paper was able to confirm its findings from internal AT&T information and from WHOIS databases. A portion of the incorrect findings are posited to be a result of incorrectly configured routers who are not following selective export policies.

Reading the Interdomain Internet Routing paper helps in understanding the different types of relationships between ASes, and the motivation behind selective export policies. These relationships, and thus the routing in wide area networks, are constantly changing as a result of the corporate nature of the system. ISPs can buy eachother out, ASes can change providers at any point in time, etc.

The paper notes that ASes themselves should probably confirm their routing policies against their AS relationships, as there were instances of misconfigured routers. It is interesting that the heuristic detected this, and it is somewhat surprising that anamolies like this have persisted. Furthermore, from the perspective of ASes themselves, they do not necessarily know the relationships of another AS, so by using similar techniques to this, they could potentially make better contractual agreements to each other.