Inferring AS Relationships

This paper describes a technique that can be used to infer a set of relationships between different ASes. It first classifies these relationships into several different categories: provider-customer, sibling, and peer. The provider-customer relationship is obvious in that the provider shares its customers' routing information, but the customer does not share its provider's routing information. Peers will share routing information with eachother, but do not forward routing information obtained from one peer to others. And finally, siblings share all routing information with eachother.

The main way that they attempt to classify these relationships from data is to look at all the AS paths in the routing tables. Their assumptions are that for no AS path will the route go from a provider to a customer and then back to a provider. This makes sense, given the definition of the provider-customer relationship, but is not always necessarily the case. The algorithm then attempts to find the topmost provider in the path, and partitions the path accordingly. By repeating this process for a large collection of AS paths, the algorithm gains enough information to determine all of the relationships between ASes.

This algorithm has an interesting application: detecting incorrectly configured routers. By using an automated system to detect the current state of inter-AS relationships, the algorithm can determine when certain gateways have been incorrectly configured, and are forwarding reachability information that they are not supposed to be. By running the algorithm and then comparing the results with the intended use, it is easy to find misconfigured routers.

The most important improvements upon the algorithm seem to be in the area of adjusting for small anomalies in the routing tables. The algorithm was very successful at determining customer-provider relationships, but it was extremely unsuccessful at determining peer or sibling relationships. Part of the issue here may be that the reachability information being shared between different ASes may fall under different policies depending on the IP prefix. It would be interesting to try to separate these different policies for these different prefixes.