Summary and Critique: On Inferring Autonomous System relationships in the Internet

The paper by Lixin Gao studies the structure of the internet, its components, and the rules which determine the routing of information across the internet. The internet is composed of Autonomous Systems (ASs) that determines it own routing policies in selecting the best route, and exporting and importing routes. Administrative domains such as ISPs, companies, and universities operate these ASs. The routing policies implemented by each AS are based on the contractual commercial agreements in effect between the administrative domains which operate it. Thus, these contractual agreements have a great influence on how the internet is structured and affect its end-to-end performance

Relationships between ASs can be classified into: peer-to-peer, provider-to-customer, customer-to-provider, or sibling-to-sibling relationship. These relationships are the basis for the import and export policies that an administrative domain can implement on its ASs. Also, there are patterns in the BGP routing entries, and these entries can potentially show what the relationship between ASs are.

Wait, what’s BGP? According to Kurose and Ross (2003), the Border Gateway Protocol (BGP) is the de facto standard interdomain routing protocol of the internet. Neighboring BGP routers exchange path information about routes to destinations. That is, the information propagates in an AS-by-AS manner.
Given these patterns and knowing that import and export policies rely on AS relationships, the author of the paper proceeded to present a heuristic that would determine the relationship between ASs.

There were algorithms presented that would determine provider-to-customer, sibling-to-sibling, and peer-to-peer relationships. When the solutions were tested and compared with AT&T internal information, the Refined algorithm (L=1) and Final algorithm (R=60) showed the best results, with 99.1% of the inference results confirmed. Tweaking of R (ratio between the degrees of two peering ASs) from the original value of ∞ to 60 gave better results. Results were also verified using the WHOIS Server, but only 54.3% of the inferred sibling relationships were confirmed. It was noted that the WHOIS database might also be out of date.
Lastly, the author identified some reasons why some inferred sibling relationships were not confirmed by AT&T or the WHOIS lookup service. These are router configuration typo, misconfiguration of small ISPs, unusual AS relationships, and inaccuracy of the heuristic (the assumption that the top provider has the highest degree may not be true).

But beyond the algorithms and academic exercise why are all these things important?
According to the author, the routing policies are manually configured and prone to error. These errors can affect other ASs and spread throughout the network and may cause outages. It is thus important to monitor routing announcements and filter out erroneous ones. The routing tables may also be checked periodically and the AS that propagated the error can be informed. Thus, these heuristics are aimed to build tools that would improve the reliability of internet routing. The relationship information can also be used by ISPs/ administrative in determining the terms of their contractual commercial agreements.

The article was an extremely long read, but very informative. The author explains the nitty-gritty of the algorithms, and provided ample introduction at the beginning to explain the basis of the calculations. I thought at first that the contractual commercial agreements between ASs was being suggested by the author as a negative constraint. However, I’ve come to realize by the end of reading that these commercial agreements are necessary for the whole thing to work – in a business/ economic point of view. There will always be providers and customers – and each has to protect their own interests. That is, I can’t think of an alternative model/ set-up. It would be good if I can learn more about that in our advanced networking class.

References:
Gao, Lixin. 2001. On Inferring System Relationships in the Internet. IEEE/ ACM Transactions on Networking, Vol 9 No 6
Kurose, J., Ross, K. 2003. Computer Networking: A Top-Down Approach Featuring the Internet