|
 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
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
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
|
C. Alaettino{glu. RAToolSet - A Routing Policy Analysis Tool Set. http://www, isi. edu/ra/RAToolSet.
|
| |
3
|
|
| |
4
|
|
| |
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
|
|
| |
7
|
|
| |
8
|
C. Hendrick. Routing information protocol. RFC 1058, 1988.
|
| |
9
|
|
| |
10
|
IRR. Internet Route Registy. Internet Route Registy Project, http://www .merit. edu/radb/docs/irr, html.
|
| |
11
|
D. S. Johnson. The NP-completeness column: An ongoing guide. Journal of Algorithms, 6(2):291-305, 1985.
|
 |
12
|
Craig Labovitz , G. Robert Malan , Farnam Jahanian, Internet routing instability, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.115-126, September 14-18, 1997, Cannes, France
|
| |
13
|
C. Labovitz, G. R. Malan, and F. Jahanian. Origins of internet routing instability. In INFOCOM'99, 1997.
|
| |
14
|
|
| |
15
|
|
| |
16
|
Y. Rekhter and T. Li. A Border Gateway Protocol. RFC 1771 (BGP version 4), 1995.
|
| |
17
|
|
| |
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
|
C. Villamizar, R. Chandra, and R. Govindan. BGP route flap damping. RFC 2439, 1998.
|
CITED BY 60
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Paul Barford , Azer Bestavros , John Byers , Mark Crovella, On the marginal utility of network topology measurements, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
Steve Uhlig , Oliver Bonaventure , Vincent Magnin , Chris Rapier , Luca Deri, Implications of the topological properties of Internet traffic on traffic engineering, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jaideep Chandrashekar , Zhi-Li Zhang , Hal Peterson, Fixing BGP, one as at a time, Proceedings of the ACM SIGCOMM workshop on Network troubleshooting: research, theory and operations practice meet malfunctioning reality, September 03-03, 2004, Portland, Oregon, USA
|
|
|
|
|
|
|
|
|
Lakshminarayanan Subramanian , Matthew Caesar , Cheng Tien Ee , Mark Handley , Morley Mao , Scott Shenker , Ion Stoica, HLP: a next generation inter-domain routing protocol, ACM SIGCOMM Computer Communication Review, v.35 n.4, October 2005
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Alex Fabrikant , Christos H. Papadimitriou, The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.844-853, January 20-22, 2008, San Francisco, California
|
|
|
|
|
|
Yong Liao , Lixin Gao , Roch Guerin , Zhi-Li Zhang, Reliable interdomain routing through multiple complementary routing processes, Proceedings of the 2008 ACM CoNEXT Conference, p.1-6, December 09-12, 2008, Madrid, Spain
|
|
|
|
|
|
Anat Bremler-Barr , Nir Chen , Jussi Kangasharju , Osnat Mokryn , Yuval Shavitt, Bringing order to BGP: Decreasing time and message complexity, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.53 n.12, p.2241-2256, August, 2009
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
C.2