Interdomain Routing

Interdomain Internet Routing

These were lecture notes describing routing between different administrative domains on the Internet. It focused on the financial reasons for how AS's connect and the manner in which BGP connects them. Unlike internal routing protocols such as OSPF, BGP is focused on providing reach-ability information and enabling routing policies.

Routing policies between AS's come down to money. While cooperation is important to route packets, ISPs are interested in routing packets that will generate revenue. Hence, there are a few simple rules, all of which come down to "don't give away anything for free." Always advertise your customers routes (downstream), and never advertise routes you don't want other networks to use, such as your provider's services to a peer.

Things get more interesting when distributing those routes. The paper discusses BGP, both external between AS's and internal within an AS. iBGP is the protocol to distribute external routes among routers within an AS. The interesting things are that iBGP doesn't scale well, and the solutions to make it scale are fairly hacky. Avoiding loops and ensuring routes are properly advertised within the AS in a scalable manner is a subject for future research. Another issue that they didn't bring up is how the routers agree on possibly conflicting external information. Two different externally facing routers within an AS may both want to use their own route, until they hear about the others's route. I'm sure this is sorted out.

The paper brings up a few other interesting issues, such as the difficulties in multi-homing, and overall provided a nice introduction to BGP and some of its issues in the real world.

We should definitely keep this on the syllabus. I'm a firm believer in knowing as much as possible about the actual systems in order to do worthwhile research. The paper presented the material in a clear manner and effectively bridged the gap between generic BGP theory and actual implementation.

On Inferring Autonomous System Relationships in the Internet

This was rather painful, and I am glad I read the other paper first. That being said, it is somewhat interesting of an idea. As mentioned above, BGP policies are determined by business. Many ISPs keep their peer relationships (provider, customer, peer) with other AS's a secret for business reasons. The goal of this paper was to apply heuristics to the data in routing tables to infer these relationships. For the subset of routers they had information for, they confirmed that they were fairly accurate.

Their system came down to parsing routing tables to see which AS's are connected to each other and which allow packets to route through on AS to another. Based on the typical BGP business rules, such as "don't route a peer's packets to your provider" (my words), they could determine who might be in a provider-consumer relationship, among others. Their primary system for determining if someone was a big provider was based on the number of AS's connected to their system.

It was an interesting idea, but terribly boring to read about. The author spent a lot of time formally writing rules that seemed to bury rather clear concepts in jargon and symbols. There were also other fundamental issues, such as that their source of routing tables does not cover deep into the internet. I would have liked to know what sort of coverage they were able to get - even a ballpark figure.

Anyway, it was an interesting technique, though I would have rather read a paper about route flapping or some more arcane aspects of BGP management.

Star This to Save in Your Profile