On inferring autonomous system relationships in the Internet

As its name suggests, the purpose of the work is to infer relationships (peering, transit etc.) between ASes in the Internet, by analyzing BGP routing tables. I have to quickly admit that I do not understand the purpose of such an endeavour. The author hints at the role that such relationships play on the "structure of the Internet and the end-to-end performance characteristics", but its not clear how elucidating the actual relationships between ASes will improve that understanding. The author does give two other examples of using this information in the conclusion, although I think the paper would have been better served by putting it in the introduction in order to better motivate the problem. Anyway, the two examples are that "ISPs can reduce misconfiguration and debug router configuration files" and to "plan for future contractual agreements."

The work uses some interesting heuristics. First is the heuristic that the size of an AS can be determined by the degree of its (logical) connections. Second, the work assumes a reasonable route export/import policy based on the nature of the relationship between ASes. This assumption is then used to prove a key theorem, that is, all AS paths in any BGP routing entry satisfies the following:

"(i) A provider-to-customer edge can be followed by only provide-to-customer or sibling-to-sibling edges;

(ii) A peer-to-peer edge can be followed by only provide-to-customer or sibling-to-sibling edges"

The basic algorithm looks at each AS path, and guesses the top provider to be the one with the highest degree. Pairs of routers before (after) the top provider are then inferred to be either sibling-to-sibling or customer-to-provider (provider-to-customer). Sibling-to-sibling are simply connections where a transit relationship occur in both directions. A more refined algorithm makes use of soft information, in that each AS path provides evidence in support of a transit relationship, but a minimum number of such evidence needs to be present. A separate step is used to infer peering relationship based on certain heuristics, which I admit I do not fully understand (hence a suitable point of discussion =p).

It was difficult to make sense of the experimental results. In V.A., the main claim is that the numbers are fairly consistent over 3 different readings, but perhaps what this is saying is just that given fairly similar routing entries (how similar??), the algorithm would not give wildly different results. The results presented in V.B. could also be misleading. For example, even if confirmation of customers is 100%, it is just saying that there were no false positives of identifying of customers; there could have been a missed detection (please correct me if I'm wrong).

One possible extension is a refinement of the refined algorithm. Instead of using a simple count, perhaps some notion of either AS path reliability can be used in a weighting. Also, as the author pointed out, the heuristic that a top provider is one with the highest degree may in fact not be true. Is some kind of consistency check among the AS paths able to more reliably find the top providers? At the end of the day, it might boil down to the algorithms doing a effective one pass through all the AS paths, whereas an iterative inference algorithm could have sorted things out better.

highest degree - top provider

Interdomain Internet Routing

Coming with minimal background in computer networks, each paper is a fascinating study into the inner workings of the Internet. The lecture "Interdomain Internet Routing" attempts to discuss how routing works between autonomous systems (AS) which consist of networks of nodes, but within the context of commercial operation of ASes by ISPs. The 0th order item that the paper points out is the fact that a routing entry equals connectivity, and that in effect an ISP is charging a node for advertising routing information to it (which was non-obvious to me). Related to that are the concepts of transit, where ISP charges for access to its routing table, and peering, where two ASes exchanges a subset of their routing tables (financial or otherwise). Exporting and importing routes (connectivity) costs the ISP money, thus it requires a set of policies that are commercially sound. 

The paper then goes on to describe the Border Gateway Protocol (BGP), which is used primarily by routers of different ASes to exchange route information, its design goals and how it can be used to implement routing policies. The main design goals are scalability, policy (expressiveness) and cooperation under competitive circumstance (imho ensuring things go well in a distributed manner even among selfish ISPs).

The paper also addresses how BGP can be used in internal sessions (iBGP) by routers on the edge (eBGP) within an AS to exchange routing information about the external world. While eBGP routers can be fully connected to exchange such information, this is not scalable. Thus, two techniques, router reflectors and confederations, were discussed. Both however have to be configured manually, which naturally leads to the question if such a process (exchanging routing information among all eBGP routers) can be done autonomously for ease of deployment.

Finally, two open problems are discussed. First is multi-homing, where a customer might want to have access through two ISPs, e.g. for redundancy reasons. The two main issues seem to be scalability, since hacks to make multi-homing work by tweaking the ASPATH seem to require some knowledge of the AS topology, and size constraints on ISP routing tables, which impose a high minimum of nodes the customer pays for. Second is the slow convergence of BGP after the occurrence of a fault.

This piece is obviously meant as a tutorial, and for me, its main value is in shedding light on how ISP actually inter-connect (and the role that routing plays), and in a way that makes sense commercially. For obvious reasons, it assumes that the reader has sufficient exposure to the material, so for me, reading it involved a lot of searching on Wikipedia.