On Inferring Autonomous System Relationships in the Internet

Gao essentially classifies ASes as providers, customer, peers, and siblings. Gao's main argument is that by understanding the relationship between these ASes today we may increase our understanding of the current architecture of the internet. She also contests that while studies have been done on the physical existence of links in the internet, these studies do not reveal the true connectivity because of the import and export policies between ASes. Thus, she embarks on a valiant attempt to find out these relationships, despite their confidentiality in the business environment, by developing a set of characteristics of routing tables implementing particularly common import and export policies. Although stated in my previous blog entry, I feel that it is most relevant to this work, so it is repeated here:

Route Export Policy (to whom: what routes are exported to them)
Customer: {provider, customer, peer, internal}
Sibling: {provider, customer, peer, internal}
Peer: {customer, internal}
Provider: {customer, internal}

Using this export policy and a lot of formal mathematics, Gao proves that if ASes all follow these rules then each routing table entry's AS Path fits 1 of 6 explicit patterns of inter AS paths. Given this conclusion, a set of routing tables, some heuristics and a dash of algorithmic magic, Gao produces experimental results of what potentially may be the AS relationships in the internet. Ultimately 99.1% of the relationships inferred by her algorithm were confirmed by AT&T internal information. Quite impressive, if you ask me.

Background material for this paper is the previous paper, "Interdomain Internet Routing".

This paper was very impressive in its results that it presented. 99.1% of the relationships inferred were confirmed by actual information, in the face of a few interesting assumptions and heuristical guesswork. The paper probably could have been a bit easier to read if it had used less formal mathematics, but this is small matter of style; Gao's mathematical formalisms ultimately got the point across. The analysis of the results was also excellent work. Overall an excellent and inspiring paper. Definitely a keeper.