Abstract: A simple coordination mechanism for interdomain routing

Ratul Mahajan, Microsoft Research, David Wetherall & Thomas Anderson, University of Washington

Routing information in BGP today carries little information about path quality. Upstream ISPs often select paths based on what is locally optimal. This can lead to poor end-to-end paths because decisions that appear locally sound may be globally poor. For instance, "hot potato" routing may not send packets in the direction of the ultimate destination. While MEDs, which enable downstream ISPs to share their preferences with upstream ISPs, are useful in some cases, they do not generally improve end-to-end paths. They enable "cold potato" routing, which simply means that paths are now optimized with respect to the downstream ISP. Additionally, MEDs have meaning only across two adjacent ISPs. Neither can an ISP meaningfully compare MEDs received from two different downstream ISPs nor can an intermediate ISP transmit MEDs received from a downstream ISP to an upstream ISP.

We present Wiser, an extension to BGP that produces efficient end-to-end paths. Wiser retains ISP independence in that providers are not required to disclose sensitive internal information (such as path length) and ISPs can make optimize for their own criteria (such as a mix of latency and utilization). With Wiser, downstream ISPs advertise routes tagged with costs that are similar to MEDs. Upstream ISPs then select paths with an amended BGP decision process that considers the sum of its internal costs and the costs reported by the downstreams. The costs of the downstream ISP are normalized such that they become comparable to the costs of the upstream ISP. To discourage abuse, such as when an upstream ISP refuses to consider downstream costs, there is a contractual limit on the average cost an ISP incurs for carrying traffic received from another ISP.

We have evaluated Wiser using measured ISP topologies and a router-level prototype. We find that, unlike routing today, the efficiency of Wiser is close to that of an ideal routing that globally optimizes network paths for metrics such as path length and bandwidth provisioning. We also find that these benefits come at a low cost: the overhead of Wiser is similar to that of BGP in terms of routing messages and computation.

About the Presenter
Ratul Mahajan is a researcher at Microsoft Research. He obtained a Ph.D. from the University of Washington, Seattle and a B.Tech. from the Indian Institute of Technology, Delhi (India), both in Computer Science and Engineering. His research interests lie in the area of networked systems, and his work addresses several problems in network measurement, diagnosis, and routing.

Link to this presentation

A simple coordination mechanism for interdomain routing - Real Video Real Video Presentation