Resolving inter-domain policy disputes

ABSTRACT

The Border Gateway Protocol (BGP) allows each autonomous system (AS) to select routes to destinations based on semantically rich and locally determined policies. This autonomously exercised policy freedom can cause instability, where unresolvable policy-based disputes in the network result in interdomain route oscillations. Several recent works have established that such instabilities can only be eliminated by enforcing a globally accepted preference ordering on routes (such as shortest path). To resolve this conflict between policy autonomy and system stability, we propose a distributed mechanism that enforces a preference ordering only when disputes resulting in oscillations exist. This preserves policy freedom when possible, and imposes stability when required.

REFERENCES

• 1: J. A. Cobb, M. G. Gouda, and R. Musunuri. A Stabilizing Solution to the Stable Paths Problem. In Symposium on Self-Stabilizing Systems, Springer-Verlag LNCS, pages 169--183. ACM Press, 2003.
• 2: Nick Feamster , Ramesh Johari , Hari Balakrishnan, Implications of autonomy for the expressiveness of policy routing, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 3: Lixin Gao, On inferring autonomous system relationships in the internet, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.733-745, December 2001 [doi>10.1109/90.974527]
• 4: L. Gao, T. G. Griffin, and J. Rexford. Inherently Safe Backup Routing with BGP. In Proceedings of IEEE INFOCOM 2001. IEEE Computer Society, IEEEPress, April 2001.
• 5: 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]
• 6: Timothy Griffin , Gordon T. Wilfong, Analysis of the MED Oscillation Problem in BGP, Proceedings of the 10th IEEE International Conference on Network Protocols, p.90-99, November 12-15, 2002
• 7: 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]
• 8: 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
• 9: T. G. Griffin and G. Wilfong. A Safe Path Vector Protocol. In Proceedings of IEEE INFOCOM 2000. IEEE Communications Society, IEEE Press, March 2000.
• 10: A. D. Jaggard and V. Ramachandran. Robustness of Class-Based Path-Vector Systems. In Proceedings of ICNP'04, pages 84--93. IEEE Computer Society, IEEE Press, October 2004.
• 11: Aaron Jaggard , Vijay Ramachandran, Robust Path-Vector Routing Despite Inconsistent Route Preferences, Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, p.270-279, November 12-15, 2006 [doi>10.1109/ICNP.2006.320220]
• 12: Y. Rekhter, T. Li, and e. Susan Hares. A Border Gateway Protocol 4 (BGP-4). RFC 4271, January 2006.
• 13: University of Oregon RouteViews Project. http://www.routeviews.org.
• 14: João Luís Sobrinho, An algebraic theory of dynamic network routing, IEEE/ACM Transactions on Networking (TON), v.13 n.5, p.1160-1173, October 2005 [doi>10.1109/TNET.2005.857111]
• 15: L. Subramanian, S. Agarwal, J. Rexford, and R. H. Katz. Characterizing the internet hierarchy from multiple vantage points. In Proc. of IEEE INFOCOM 2002, New York, NY, Jun 2002.
• 16: H. Tangmunarunkit, R. Govindan, S. Shenker, and D. Estrin. The impact of routing policy on internet paths. In Proc. of IEEE INFOCOM 2001, Anchorage, AK, Apr 2001.
• 17: K. Varadhan, R. Govindan, and D. Estrin. Persistent Route Oscillations in Inter-domain Routing. Computer Networks, 32(1):1--16, March 2000.

INDEX TERMS

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

General Terms:
Algorithms, Design, Theory

Keywords:
BGP, convergence, inter-domain routing, policy disputes