Implications of autonomy for the expressiveness of policy routing

ABSTRACT

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.

REFERENCES

• 1: Alaettinoglu, C., et al. Routing policy specification language (RPSL). RFC 2622, June 1999.
• 2: Private communication with Randy Bush, May 2004.
• 3: Feamster, N., and Balakrishnan, H. Detecting BGP Configuration Faults with Static Analysis. In Proc. 2nd Symposium on Networked Systems Design and Implementation (Boston, MA, May 2005), pp. 49--56.
• 4: Nick Feamster , Jay Borkenhagen , Jennifer Rexford, Guidelines for interdomain traffic engineering, ACM SIGCOMM Computer Communication Review, v.33 n.5, October 2003 [doi>10.1145/963985.963988]
• 5: Feamster, N., Johari, R., and Balakrishnan, H. Stable policy routing with provider independence. Tech. Rep. MIT-LCS-TR-981, Massachusetts Institute of Technology, February 2005.
• 6: Joan Feigenbaum , Rahul Sami , Scott Shenker, Mechanism design for policy routing, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011770]
• 7: Gao, L., Griffin, T. G., and Rexford, J. Inherently safe backup routing with BGP. In Proc. IEEE INFOCOM (Anchorage, AK, April 2001), pp. 547--556.
• 8: Lixin Gao , Jennifer Rexford, Stable internet routing without global coordination, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.681-692, December 2001 [doi>10.1109/90.974523]
• 9: Govindan, R., Alaettinoglu, C., Eddy, G., Kessens, D., Kumar, S., and Lee, W. An architecture for stable, analyzable Internet routing. IEEE Network Magazine 13, 1 (January/February 1999), 29--35.
• 10: Ramesh Govindan , Cengiz Alaettinoğlu , Kannan Varadhan , Deborah Estrin, Route servers for inter-domain routing, Computer Networks and ISDN Systems, v.30 n.12, p.1157-1174, July 13, 1998 [doi>10.1016/S0169-7552(98)00008-7 ]
• 11: Timothy G. Griffin , Aaron D. Jaggard , Vijay Ramachandran, Design principles of policy languages for path vector protocols, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863964]
• 12: Timothy G. Griffin , F. Bruce Shepherd , Gordon Wilfong, The stable paths problem and interdomain routing, IEEE/ACM Transactions on Networking (TON), v.10 n.2, April 2002
• 13: Griffin, T., and Wilfong, G. A safe path vector protocol. In Proc. IEEE INFOCOM (March 2000), pp. 490--499.
• 14: Aaron D. Jaggard , Vijay Ramachandran, Documentation of the HTTP Protocol Includes Precise, Proceedings of the Network Protocols, 12th IEEE International Conference on (ICNP'04), p.84-93, October 05-08, 2004
• 15: Machiraju, S., and Katz, R. Verifying global invariants in multi-provider distributed systems. In Proc. SIGCOMM Workshop on Hot Topics in Networking (HotNets) (November 2004), pp. 149--154.
• 16: Rekhter, Y., and Li, T. A Border Gateway Protocol. RFC 1771, March 1995.
• 17: João Luis Sobrinho, Network routing with path vector protocols: theory and applications, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863963]
• 18: Varadhan, K., Govindan, R., and Estrin, D. Persistent route oscillations in inter-domain routing. Tech. Rep. 96-631, USC/ISI, February 1996.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Design, Performance, Reliability, Theory

Keywords:
BGP, autonomy, internet, policy, protocol, routing, safety, stability