On Inferring Autonomous System Relationships in the Internet

L. Gao, "On Inferring Autonomous System Relationships in the Internet," IEEE/ACM Transactions on Networks, V. 9, N. 6, (December 2001), pp. 733-745.

 This paper talked about how the author classified various types of routes that appeared in BGP routing tables based on AS relationships and presented an heuristic algorithm that inferred these relationships from the routing table. The underlying theme of this paper was that connectivity does not imply reachability. So, in order to study the sturcutre of the Internet, it is not just sufficient to study the graph topologies as reachability also depends a lot on inter domain policies between different ASes managed by different ISPs.

ASes may fall into one or more of the following categories: Provider, Customer, Peer or Sibling. Based on this, we can have following Relationships:

• Customer-AS: AS exports all its routes, other customer's routes as well as provider and peer routes to the customer.
• AS-Provider: AS usually doesn't export its provider and peer routes and only exports customer routes.
• AS-Peer: AS can export its routes and its customers' routes but usually doesn't export its provider or peer routes.
• AS-Sibling: AS exports its routes, routes of customers as well as provider and peer routes.
  

The essential theme of this paper is the 'Valley Free Property" that exists in the Internet between different ASes.  Intituively, considering Customer --> Provider relationship to be "going upwards", Provider --> Customer relationship to be "going downwards", and Peer --> Peer and Sibling --> Sibling relationships to be at the "same level", Gao proved that the Internet can never have a "Valley". This helped her to propose an algorithm that could identify quite accurately how the various ASes were connected. The first phase of the algorithm consisted of walking on a path connecting various ASeS and finding for each node, its set of neighbors as well as its out-degree. This then classified AS pairs into provider-customer or sibling relationships. Then the second phase identified AS pairs that did not have a peering relationships and finally the third phase assigned peering relationships to AS pairs.


Comments

The paper was well written, clear in explanation and it was particularly helpful to understand the algorithm due to the incremental way it was proposed. My only concern would be how much accurate these identification of relationships can be? As highlighted, the repository for BGP routing relationships is not always accurate and peering relationships might well be protected by contractual agreements. Doesn't this puts an open question on the results?