Session 11, Paper 2: Bootstrapping evolvability for inter-domain routing with D-BGP (Raja R. Sambasivan, David Tran-Lam, Aditya Akella, Peter Steenkiste)

Presented by: Raja Sambasivan

Raja proposed the question: What evolvability features are needed in any inter-domain routing protocol?

BGP is todays inter-domain routing protocol; however it: cannot limit ingress traffic, it has a high convergence time, has no QoS guarantees, it uses only one best path, and ASes can be spoofed. We have many great new protocols; however, unfortunately, very few have actually been deployed. The problem is that BGP is rigid in that it requires neighbors to use the same protocol and thus it is very difficult to evolve. The rigidity of BGP results in isolated islands, subsets of ASes that can use a different routing protocol within each other, that have to use BGP outside of those islands so that they can cross the "gulf" of ASes not using the same protocol. This reduces the benefits of new protocols and reduce the incentives to operate with those new protocols. One current solution is to use tunnels, established out of band, however they interfere and increase other ASes' cost, creating push-back against changes.

The authors analyzed 14 recently proposed changes to BGP and found that only two properties are necessary to allow a protocol to evolve. The first is pass-through support, to allow ASes to disseminate information across gulfs, disseminate the routes in-band, and enable discovery of other islands. The second property is a multi-protocol data structure that informs islands about what they use and provides a common framework to express end-to-end paths.

They then designed Darwin's BGP, D-BGP, which includes these two features and find that it isn't very far from BGP and that BGP already has pass-through support. D-BGP uses "path vectors" which contain the AS # and the Island ID. Within islands it uses a set of ASes to prevent other ASes from discounting end-to-end, within island paths.

They evaluate D-BGPs potential for accelerating the benefits of new protocols. They used a 1000 node simulation and randomly choose which ASes are using the different protocol SCION. And they found that D-BGP always allows extra paths to be used over BGP.

Q: Can we use D-BGP to still allow for the deployment of new functionality in the data plane?

A: Yes, those systems that we analyzed allow for different data plane functionality, they just modify the control information.

Q: Can you speak to the correctness of the protocol you ended up with? You have many ASes using many different protocols, will it ever converge?

A: I can't comment on that specifically. BGP already provides tons of flexibility and with the modifications of D-BGP it's not clear whether it makes it worse or not.

Q: When looking at what we need did you come away with any lessons about how we can move forward given that we have BGP now?

A: I would propose the question of how would you incrementally deploy D-BGP? The key-fixed point is that the path vector field is correct when it is being deployed.