Review: On Inferring Autonomous System Relationships in the Internet

Summary
Global connectivity of millions of end-hosts worldwide is possible through interdomain routing in the Internet coordinated by BGP. BGP allows each AS to set its own routing policies. Oftentimes, contractual commercial agreements between administrative domains poses constraint on these routing policies e.g. A customer must not provide transit services between its providers. Indeed, policies like this shows that AS relationships stand as important features in Internet architecture.

“On Inferring Autonomous System Relationships in the Internet” by Lixin Gao [1] proposes an augmented graph representation that infers AS relationships classified as customer-provider, peering or sibling relationships. The author also presents heuristic algorithms for inferring these relationships. But first, the concept of an annotated AS graph and the theorems regarding the selective export rule (and the routing table entry patterns derived from it) are formally discussed. The author presents algorithms for the mentioned AS relationships based on the patterns. For inferring the first two relationships, the author constructed two algorithms: Basic and Refined. The difference of the two is that the first assumes that all BGP routers are configured correctly while the last perceives possible misconfigured BGP routers. For inferring peering relationships, the author presents the Final algorithm that simply checks if an AS pair does not transit traffic for each other. To test the accuracy of these algorithms, an experimental study of AS relationships in the Internet was done using BGP routing tables retrieved from the Route Views server in Oregon. Based from the results, more than 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. AT&T internal information checked the inference results and confirmed 100% of the inferred customers and peers and 20% of the inferred siblings. As a whole, 98.9% of all the inference results are confirmed by AT&T internal information. The inferred sibling results are also verified from WHOIS lookup service and more than half are confirmed. At the end of the paper, the author discussed the possible causes of unconfirmed siblings and these are: router configuration typo, misconfiguration of small ISPs, unusual AS relationships, and inaccuracy of the heuristic.


Evaluation
I think that this is a good study that must be continued rather updated since the Internet has experienced a huge increase in its size and complexity since it was commercialized and since the date that this paper was published. An example of updating would be to check the constants used for each algorithms like the constant R indicated in the Final Algorithm. Would it still be applicable today? Would it produce better results if it would increase its value?

A further study that must follow this research could be looking for solutions on the possible causes of unconfirmed cases. With the current technology, these misconfigurations may be lessened by improving the physical devices used for interdomain routing which could in turn improve also inferring AS relationships.


Reference:
[1] Lixin Gao, On inferring autonomous system relationships in the internet, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.733-745, December 2001

Lecture on Interdomain Internet Routing

Summary
The lecture entitled “Interdomain Internet Routing”, from the name itself explains how routing between different administrative domains works in the Internet. An important issue in the current Internet routing layer is tackled initially which pertains to the difficulty of global connectivity of various end-hosts in the Internet. This is due to unequal creation of Internet service providers (ISPs) which are categorized according to the size of their network. Meanwhile, a true picture of the Internet routing is introduced. The existing Internet routing infrastructure is divided into autonomous systems (ASes) that exchange reachability information using the current wide-area routing protocol called BGP (Border Gateway Protocol).

The next part discusses two prevalent forms of relationships happening between different ASes namely transit and peering. The former which involves a financial settlement, requires an ISP to provide access to all (or most) destinations in its routing tables. The latter allows two ASes to provide mutual access to a subset of each others' routing tables and may not involve any financial transactions. ASes involved in either transit or peering needs to construct export policies (rules on what routes to export) and import policies (rules on what routes to install) so as not to lose revenue.

The third section is dedicated to BGP which includes the protocol's design goals, its attributes, and how it disseminates routes within an AS. The current structure of BGP was influenced by these 3 factors: scalability (the Internet routing infrastructure must be scalable as the size of the network increases); policy (AS must enforce various routing policies); and cooperation under competitive circumstances. A BGP consists of several attributes such as NEXT HOP (IP address of the next-hop router), ASPATH (sequence of AS identifiers that the route has traversed), LOCAL PREF (first attribute considered in selecting routes) , and MED (multiple-exit descriminator). Among these, the last three are the most important. Disseminating routes within an AS are done using two types of BSP sessions: eBGP are between BGP in different ASes while iBGP are between BGP in the same AS. The dissemination is done with care using two important goals: loop-free forwarding and complete visibility.

Lastly, failures over BGPs are discussed, including its causes and solutions that has already been made. Moreover, scalability is further explained with the discussion of multi-homing.

Evaluation
This lecture provides a good background on the technicalities behind interdomain Internet routing. The authors have done a great job of including a detailed discussion of BGP’s structure and the goals that served as bases for the protocol’s creation.

Open issues regarding interdomain Internet routing have also been recently identified through surveys and studies done by a group of researchers [1]. Some of these include slow convergence and chattiness of BGP, scalability problems due to multi-homing which is discussed in the paper, security issues, etc. They searched for the possible causes of these issues and if there are any studies done to resolve these issues.

Reference:
[1] M. Yannuzzi, X. Masip-Bruin, and O. Bonaventure, Open Issues in Interdomain Routing: A Survey, IEEE Network, November/December 2005.