TY - CONF T1 - Implications of autonomy for the expressiveness of policy routing T2 - Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications Y1 - 2005 A1 - Feamster, Nick A1 - Johari,Ramesh A1 - Balakrishnan,Hari KW - autonomy KW - BGP KW - Internet KW - policy KW - protocol KW - Routing KW - Safety KW - stability AB - Thousands of competing autonomous systems must cooperate with each other to provide global Internet connectivity. Each autonomous system (AS) encodes various economic, business, and performance decisions in its routing policy. The current interdomain routing system enables each AS to express policy using rankings that determine how each router inthe AS chooses among different routes to a destination, and filters that determine which routes are hidden from each neighboring AS. Because the Internet is composed of many independent, competing networks, the interdomain routing system should provide autonomy, allowing network operators to set their rankings independently, and to have no constraints on allowed filters. This paper studies routing protocol stability under these conditions. We first demonstrate that certain rankings that are commonly used in practice may not ensure routing stability. We then prove that, when providers can set rankings and filters autonomously, guaranteeing that the routing system will converge to a stable path assignment essentially requires ASes to rank routes based on AS-path lengths. We discuss the implications of these results for the future of interdomain routing. JA - Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications T3 - SIGCOMM '05 PB - ACM CY - New York, NY, USA SN - 1-59593-009-4 UR - http://doi.acm.org/10.1145/1080091.1080096 M3 - 10.1145/1080091.1080096 ER -