Interdomain Internet Routing; Balakrishnan

This paper describes interdomain routing in the Internet. It first details the decentralized nature of routing, detailing how layered tiers of Internet Service Providers engage in a complicated game of competition and cooperation to best serve customers while maximizing their profits. ISPs engage in both transit and peering relationships with one another; transit is a customer-provider relationship in which a provider makes the guarantee to its customer that any sender on the Internet will be able to reach them.

However, the ISPs will be selective about which routes they share so as to minimize all non-customer routing that goes through them. Choosing which routes to export is a complicated matter of economics and resource tradeoffs, keeping customers happy and not wasting one's own resources. I thought the paper mentioned a very interesting way of looking at a transit relationship: that what ISPs are charging their customers for is, in essence, an entry in a routing table. I was also curious as to how the different tier ISPs came about: did the multiple layers get added on gradually over time as the Internet grew, or was it a clean break from the centralized system of the ARPANET? Furthermore, when did the notion of making money as an ISP really start to come into the picture?

The paper then moves on to discuss autonomous systems and how they exchange routing info via Border Gateway Protocol (BGP) and use IGP to optimize their own internal paths. BGP is a path vector protocol that has internal and external flavors, iBGP and eBGP, which it uses internal to an AS and between ASes, respectively. BGP is used to exchange route information and keep track of numerous attributes of the route, including a vector of ASes the route should follow. BGP is not a complicated protocol, sending a few simple messages, including UPDATE when routes change, NOTIFICATION when routes go down, and KEEPALIVE to ensure that routes are still up. It selects routes based on some of the attributes associated with a route, including whether or not the route originated from a customer and based on shortest AS length.

BGP's working properly requires putting a lot of trust in all ASes; the fact that any AS can originate a route for any prefix seems like a bad idea that has caused some serious (though easily-fixed and short-lived) problems. Some sort of network sentinels that watch for unexpected changes in advertised routes seems like a very worthwhile idea, though apparently logging is not particularly reliable either, meaning that we're left with a lack of accountability in the case of route hijacks. For a highly trafficked site like youtube, it doesn't take long for the world to notice that routing tables world-wide have been poisoned, but how long would it take to find problems with more subtle misconfigurations?