An analysis of BGP convergence properties

ABSTRACT

The Border Gateway Protocol (BGP) is the de facto inter-domain routing protocol used to exchange reachability information between Autonomous Systems in the global Internet. BGP is a path-vector protocol that allows each Autonomous System to override distance-based metrics with policy-based metrics when choosing best routes. Varadhan et al. [18] have shown that it is possible for a group of Autonomous Systems to independently define BGP policies that together lead to BGP protocol oscillations that never converge on a stable routing. One approach to addressing this problem is based on static analysis of routing policies to determine if they are safe. We explore the worst-case complexity for convergence-oriented static analysis of BGP routing policies. We present an abstract model of BGP and use it to define several global sanity conditions on routing policies that are related to BGP convergence/divergence. For each condition we show that the complexity of statically checking it is either NP-complete or NP-hard.

References

1. 1.C. Alaettinoglu, T. Bates, E. Gerich, D. Karrenberg, D. Meyer, M. Terpstra, and C. Villamizar. Routing Policy Specification Language (RPSL). RFC 2280, 1998.]]
2. 2.C. Alaettino{glu. RAToolSet - A Routing Policy Analysis Tool Set. http://www, isi. edu/ra/RAToolSet.]]
3. 3.D. Bertsekas and R. Gallagher. Data Networks. Prentice Hall, 1992.]]
4. 4.M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., 1979.]]
5. 5.R. Govindan, C. Alaettinoglu, G. Eddy, D. Kessens, S. Kumar, and W.S. Lee. An architecture for stable, analyzable internet routing. IEEE Network, 13(1):29-35, 1999.]]
6. 6.R. Govindan and A. Reddy. An analysis of inter-domain topology and route stability. In INFOCOMM'97, 1997.]]
7. 7.B. Halabi. Internet Routing Architectures. Cisco Press, 1997.]]
8. 8.C. Hendrick. Routing information protocol. RFC 1058, 1988.]]
9. 9.C. Huitema. Routing in the Internet. Prentice Hall, 1995.]]
10. 10.IRR. Internet Route Registy. Internet Route Registy Project, http://www .merit. edu/radb/docs/irr, html.]]
11. 11.D. S. Johnson. The NP-completeness column: An ongoing guide. Journal of Algorithms, 6(2):291-305, 1985.]]
12. 12.C. Labovitz, G. R. Malan, and F. Jahanian. Internet routing instability. In SIGCOMM'97, 1997.]]
13. 13.C. Labovitz, G. R. Malan, and F. Jahanian. Origins of internet routing instability. In INFOCOM'99, 1997.]]
14. 14.V. Paxson. End-to-end routing behavior in the internet. Transactions on Networking, 5(5), 1997.]]
15. 15.R. Perlman. Interconnections: Bridges and Routers. Addison-Wesley, 1995.]]
16. 16.Y. Rekhter and T. Li. A Border Gateway Protocol. RFC 1771 (BGP version 4), 1995.]]
17. 17.J. W. Stewart. BGP~, Inter-Domain Routing in The Internet. Addison-Wesley, 1998.]]
18. 18.K. Varadhan, R. Govindan, and D. Estrin. Persistent route oscillations in inter-domain routing. ISI technical report 96-631, USC/Information Sciences Institute, 1996.]]
19. 19.C. Villamizar, R. Chandra, and R. Govindan. BGP route flap damping. RFC 2439, 1998.]]

Index Terms

• Computer systems organization

  • Dependable and fault-tolerant systems and networks

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Networks

  • Network components

  • Network performance evaluation

  • Network protocols

  • Network types

    • Public Internet

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Routing and network design problems