Date Added: Jan 2011
The substantial complexity of inter-domain routing in the Internet comes from the need to support flexible policies while scaling to a large number of Autonomous Systems. Despite impressive progress in characterizing the various ills of the Border Gateway Protocol (BGP), many problems remain unsolved, and the behavior of the routing system is still poorly understood. This paper argues that the authors must understand inter-domain routing in terms of: intrinsic properties and design tradeoffs of policy-based routing, independent of the specific routing protocol and properties that relate to artifacts in today's protocol. They pose open questions for the research community that, if answered, should help people understand why BGP's many problems are so difficult to fix.