Unlocking the Internet’s Secrets

The paper by Lixin Gao, titled “On Inferring Autonomous System Relationships in the Internet,”[1] discusses an algorithm that her group has developed for determining the relationships of various ASs. Based on her account, there are no available public records specifying inter-AS relationships. What exist, though, are publicly available BGP routing tables and these served as their source of data for inferring relationships.

Their approach uses an annotated graph to represent ASs and their relationships. Nodes represent ASs and edges represent relationships, which they classified as provider-to-customer, customer-to-provider, peer-to-peer, and sibling-to-sibling.

Export Policies
Vital to the design of their algorithm are their derived BGP export policies [1]:

“Exporting to a provider: In exchanging routing information with a provider, an AS can export its routes and its customer routes, but usually does not export its provider or peer routes.

Exporting to a customer: In exchanging routing information with a customer, an AS can export its routes and its customer routes, and as well as its provider or peer routes.

Exporting to a peer: In exchanging routing information with a peer, an AS can export its routes and its customer routes, but usually does not export its provider or peer routes.

Exporting to a sibling: In exchanging routing information with a sibling, an AS can export its routes and routes of its customers, and as well as its provider or peer routes.”

From these export policies, they formulated what they consider as the selective export rule, which summarizes the above policies. I’d like to note that, as this paper and the previously discussed lecture on AS have also emphasized, policies regarding exporting and importing of routes are only privy to ASs involved in a deal. So what they have here are mere descriptions of what’s likely to be the case, as suggested by the phrase “but usually does not export,” and these hardly qualify as scientific. From my perspective, I find it hard to image that such assumptions are capable of producing accurate results. But as their experimental results suggest, my perception is the one that is inaccurate.

From here, I’ll go straight (I’ll skip their proving parts) to their algorithm.

Algorithm
Based from BGP routing tables, an augmented graph can be derived using the policies described by the paper. This graph will serve as the input for their algorithm. The first part of the algorithm simply determines the degree of each AS in a graph. A higher degree suggests that a node is likely a provider, since customers are connected to them.

The next phase of the algorithm is meant for reducing the inconsistencies that are possibly caused by misconfigured routers. In some cases, two AS pairs appear to have both provider-to-customer and customer-to-provider relationships in various routing table entries. This could lead to mislabeling in some AS paths. To correct this, they used a variable L to serve as a threshold for determining the dominant relationship. If a relationship of two pairs appear in more than L entries, then that is used as the correct relationship. But if both the provider-to-customer and customer-to-provider relationships both appear in less than L entries or more than L entries, then they are considered to provide transit to one another.

The third part of the algorithm is the labeling of edges. For each AS path, the AS with the highest degree is considered as the “top provider.” Once a top provider is determined, ASs with customer-to-provider and provider-to-customer relationships can be easily identified. All transits before the top provider are customer-to-provider edges, since providers are generally known to have higher degrees, while transits appearing after are provider-to-customer edges. If two pairs both provide transit to each other (i.e. they both appear before the top provider and also after it in a reversed order), then this pair is classified as a sibling-to-sibling edge. This part of the algorithm simply traverses all consecutive pairs in a path, which means it has an efficient linear run time (O(n)).

The last part of the algorithm is for determining peering relationships. In each AS path, the top provider can have a peering relationship with at most one of its neighbors. The heuristic considered for determining a top provider’s peer is the tendency of a top provider to peer with a neighbor with a higher degree. However, this could erroneously produce many peering relationships. To handle this, a variable R is introduced as measure for the similarity of two peers in terms of their degree. The author said, though, that this value still needs to be fine-tuned, though its effects are less influential if there are more routing tables used as references.

Experimental Results
Their experimental results, to say the least, are impressive. Here are some of their results that were confirmed by AT&T internal information: 100% of their inferred customers, 100% of their inferred peers, 20% of their inferred siblings. 98.9% of all their inference results were confirmed by AT&T internal information. For an algorithm that is based on simple heuristics, including some variables that may need further adjustment, it is really surprising to see that they were able to come up with accurate results concerning data that are meant to be confidential. Even better, they were able to accomplish this through a series of sequential data processing, resulting to quite an efficient algorithm.

Aside from confirming the correctness of their algorithms, their results also prove the validity of certain assumptions made on routing policies. Although these assumptions are based on what makes sense, there are still no hard evidences to prove these. But now that a well known ISP has confirmed their results based on these notions, then maybe it’s time for ISPs to make their routing policies and relationships open for research purposes, since they’re slowly being exposed anyway.

References:
[1] L. Gao. On Inferring Autonomous System Relationships in the Internet. IEEE/ACM Transactions on Networking, vol.9, no.6, p.733-745. December 2001