Review: On Inferring AS relationships in the Internet

Contractual commercial agreements between administrative domains play a crucial role in shaping the structure of the Internet and the end-to-end performance characteristics. Since interdomain routing is controlled by Border Gateway Protocol (BGP) which is policy-based, connectivity does not imply reachability. A global picture of Autonomous System (AS) relationships is an important aspect of the Internet Architecture.

The paper, On inferring autonomous system relationships in the internet by L. Gao [1] proposes an augmented AS graph representation to capture AS relationships. They classify the relationship between a pair of interconnected ASs as customer-provider, peering and sibling relationship. Since there was no publicly available information about inter-AS relationships, they made use of heuristic algorithms to infer the augmented AS graph from BGP routing tables. Their algorithm is based on the fact that each AS follow the selective export rule which indicates that there should be a certain pattern that can be use to infer export policies from routing table entries. Their final algorithm first coarsely classifies AS pairs into having provider-customer or sibling relationships in phase 1, identify all the AS pairs that cannot peer with each other and finally in phase 3, identify the peering relationships from the rest by using the heuristic that two peering ASs' degree do not differ significantly. They created two algorithms for phase 1, the basic algorithm which assumes that all BGP speaking routers are configured correctly and the refined algorithm that uses counting to reduce the possibility of incorrect inference due to misconfigured routers. They performed an experimental study using routing tables retrieved from Route Views server in Oregon and among the connected AS pairs, 90.5% of the AS pairs have customer-provider relationships, less than 1.5% of the AS pairs have sibling relationships and less than 8% of the AS pairs have peering relationships. Then they were able to verify their results with AT&T and the results show that 100% of their inferred customers and inferred peers were confirmed. Meanwhile only 20.5% of their inferred siblings were confirmed and out of all their inference results, 98.9% were confirmed. They also verified their inferred sibling relationships with the information from WHOIS lookup service and more than half of the inferred sibling relationships were confirmed

However in a more recent study in [2], its author's claim in the Abstract that the approach presented here are local in nature and do not capture the global hierarchical structure. In their work they define a way to infer relationships from collected data adding consideration for the global hierarchy constrains. They define the Acyclic Type of Relationship AToR problem that captures the global hierarchy and present an efficient algorithm that allows determining if there is a hierarchical assignment without invalid paths. They said that their experiments and simulation results shows that their algorithm is able to classify the type of relationship between ASes better than previous algorithms but due to lack of access rights to the whole paper I'm not able to confirm this.

The paper, being the pioneer in this problem of inferring AS relationships in the Internet did a splendid job of explaining and providing the necessary details in introducing and attacking the problem. The Internet was just starting to be popular in the time of the study but has been in use for many years prior to it. The unavailability of public data might have discouraged researchers back then but it's great that the authors of this paper were able to find a way that is like reverse engineering.

The problem of inferring or deducing the AS relationships in the Internet is indeed an interesting topic that could prove to be useful if the results of algorithms like this reach a certain level of reliability. The fault in their algorithm was in their assumption that the degree of two ASes that has a peering relationship do not differ by more than a value R. They made this assumption without providing a clear way of how to set it. The value (60) that they have chosen in the paper may not provide the best result today because of the massive increase in the users and usage of the Internet. However, they do suggest making use of other information that may not be available in the time of their writing with the inference techniques to improve accuracy.

References:

[1] L. Gao, "On inferring autonomous system relationships in the internet," IEEE/ACM Transactions on Networking,vol.9, no.6, December 2001.

[2] R. Cohen and D. Raz, "Acyclic type of relationships between autonomous systems," INFOCOM 2007. 26^th IEEE International Conference on Computer Communications, pp. 1334-1342, May 2007.