On Inferring Autonomous System Relationships in the Internet/Interdomain Internet Routing

Hari Balakrishnan, Nick Feamster, "Interdomain Internet Routing"
Lixin Gao, "On Inferring Autonomous System Relationships in the Internet"

The notion of the "Autonomous System" is central. A routing protocols inside an AS are called IGP and all routers are programmed to find the optimal path through the network. All these routers are run by the same administration.

A routing protocols for routing between ASs is called an EGP. BGP is the EGP deployed today on the Internet. The design of such a routing protocol has to take into account that different ASs are run by different enterprises which are competitors or have customer-provider relationships. Hence a router is driven by commerical interests when deciding whose packets to forward to who. The goal of BGP is to honor these interests and at the same time establish routing tables allowing global reachability if possible. (Cooperation between competitors) Notice that this prioritizes the accountability in the original list of goals of the DARPA Internet (Clarke). This means that the AS is dividing line between two very different kinds of routing, and why I said that the notion of the AS is central.

Technically speaking, BGP routers enter BGP sessions and exchange reachability information in the forms of routes of AS numbers by enumerating the routes (during initialization) and then updating about new/changed or deleted routes. When the routing information is advertised, i.e. sent from one host to another, that host has to append its AS number to the route. Each BGP router has a choice which of these routes to incorporate into the routing table. It also has a choice which of the routes from the routing table to advertise. "A route advertisement from B to A for a destination prefix is an agreement by B that it will forard packets sent via A destined for any destination in the prefix." To avoid cycles, a router has to drop a route when it notices that it already is on the path. There are two kinds of sessions (but which speak the same "language"): iBGP and eBGP, the first one is to synchronize routing information between different BGP routers in the same AS, the latter one to exchange routes with other eBGPs. iBGP is for merging routing information, but in eBGP, routers have the choice to advertise or import only certain routes. There are further variables (MED) in BGP to decide which exchange point to use in case two ASs are linked at multiple places.

Each time a router exports a route, it could draw more traffic which could flow through other networks to itself. Hence, to understand which routes a BGP router imports and exports, one has to look at the relations between ASs: the major ones are customer-provider transit and peering. In a customer-provider relation, the provider will export routes from its customers to all other ASs the provider is connected to and give the customers routes to all other ASs, since the customer pays for being reachable.
Peering means that two providers A and B agree to forward packets which are going between customers of each other to avoid paying for traffic through a third, higher provider C. Peer A will not export a route to B's customer to, say, C because that would mean A pays for B's customers traffic to C.

ASs are roughly categorized as Tier-1, Tier-2, Tier-3 networks which corresponds to their size and hence to their relationships. For example, Tier-3 networks are small and are customers of Tier-2 networks.

I like the Interdomain Internet Routing paper for illustrating the different business relationships between ASs. It could make more clear to what parts of the text are business-driven policies and which parts of the text are really protocol specifications a router has to adhere to.

The information about the relationships of ASs are in general not known, sometimes under non-disclosure agreement.
The second paper is discussing in detail certain heuristics (like a larger AS is probably a provider of a smaller AS) and how the relationships influence which routers are exporting which routes (III A). It is important to note that there assumptions made about how a router behaves. Under this assumptions certain theorems can be shown, essentially that when looking at the customer-provider, peer-peer and provider-customer edges of an AS path, a path can only "bounce" once, e.g. an AS path like provider-customer-provider-customer is impossible.
Using this knowledge, an algorithm is given which uses routing information from several routers to reverse engineer the relationships between ASs. This algorithm is refined to be more robust because not all routers behave as assumed, e.g. a mal-configured router of a multi-homed customer exported a route linking its providers.
Experimental results are compared to internal data of AT&T.