Interdomain Internet Routing

This note set is an interesting choice for a third reading because it covers a topic that has not been focused on very heavily in research, and is mostly in the realm of commercial providers - interdomain routing. Because of this, the protocols and algorithms used are shaped primarily by a commercial goal - enforcing policies to minimize monetary costs given the various business relationships between AS'es - rather than more "intellectually beautiful" goals such as performance, reliability, load-balancing, etc. The only feature BGP tries to provide is reachability while following policies. Beyond that that, its other design goal is scalability, which is handled by making the protocol relatively simple (dropping the more expensive features that could improve performance, load balancing, etc) and using long timeouts and damped propagation for route changes (decreasing reliability). The combination of policy-motivated goals and confidentiality of business relationships has likely contributed to lowered research interest in BGP compared to other protocols such as TCP, OSPF, or even IP, because a) the problem is difficult to fully understand, b) it is less "sexy" than working on mathematically clean issues like fairness and performance, and c) even if one develops an alternative system for interdomain routing, it's hard to evaluate the system for the purpose of scientific publication. This is a problem that all researchers have to deal with - how can we do socially relevant research if the parties involved are not interested in sharing information and the problem is confined to a small set of providers? Nonetheless, the note shows that interdomain routing is a serious concern with great potential for improvement, especially in reliability (speed of recovery after failures).

In terms of content, there are four main takeaways:

• AS'es come in different sizes, and have both client-provider and peering relationships. They advertise only routes that are necessary for serving their customers while minimizing monetary cost (both from paying a provider and from transfering packets through one's own network).
  
• BGP advertises complete paths annotated with attributes, to avoid loops and provide information for selecting between the paths based on commercial agreements and policies (e.g. MED).
• Paths are chosen according to a hierarchy of goals: local policy, shortness of path (in AS hops), MED (preferred entry point inside a customer), "closeness" of egress router (get the packet out of the ISP as fast as possible), and finally some tiebreak condition.
• Recovering from problems is slow: it normally takes at least several minutes, and sometimes 30 minutes or more.

One criticism of the note set is that it does not provide more recent data on prevalence of failures. Also, the failures caught by the various traces are likely not representative of the average failures experienced by users of the Internet: Users spend most of their time on very popular sites, which tend to have multiple ISPs, perhaps even multiple data centers, CDNs hosting data within the users' own regions, etc. How often are these Internet destinations "down" compared to routes between random pairs of nodes set up by universities? Apart from these huge destinations, other destinations are likely local sites (e.g. as a Berkeley student I want to see Randy's course webpage), so there are fewer opportunities for route failures, or peer-to-peer networks, which work despite some links being down. It would be interesting to study reliability of specific applications for users in various regions, not random Internet paths.

There are obviously many possible places for improvement in BGP, starting with reliability. It would be great if BGP focused more on path costs, for example. With all these things, it's important to ask not "is BGP providing optimal routes" but "how much better can we really do"? For example, on the throughput front, it's likely that we can't really increase Internet throughput through a better interdomain protocol - the backbone is often overprovisioned, and last-mile links or servers are the bottleneck. However, perhaps latency could be improved by a significant amount.