|
 ABSTRACT
The Border Gateway Protocol (BGP) has two distinct modes of operation. External BGP (EBGP) exchanges reachability information between autonomous systems, while Internal BGP (IBGP) exchanges external reachability information within an autonomous system. We study several routing anomalies that are unique to IBGP because, unlike EBGP, forwarding paths and signaling paths are not always symmetric. In particular, we focus on anomalies that can cause the protocol to diverge, and those that can cause a router's chosen forwarding path to an egress point to be deflected by another router on that path. Deflections can greatly complicate the debugging of routing problems, and in the worst case multiple deflections can combine to form persistent forwarding loops. We define a correct IBGP configuration to be one that is anomaly free for every possible set of routes sent by neighboring autonomous systems. We show that determination of IBGP configuration correctness is NP-hard. However, we give simple sufficient conditions on network configurations that guarantee correctness.
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
|
Anindya Basu , Chih-Hao Luke Ong , April Rasala , F. Bruce Shepherd , Gordon Wilfong, Route oscillations in I-BGP with route reflection, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
|
| |
2
|
T. Bates, R. Chandra, and E. Chen. BGP route reflection: An alternative to full mesh IBGP. RFC 2796, 2000.
|
| |
3
|
Marc Blanchet, Florent Parent, and Bill St-Arnaud. Optical BGP (OBGP): InterAS lightpath provisioning. Internet Draft draft-parent-obgp-01.txt. Work in progress.
|
| |
4
|
Cisco. Endless BGP Convergence Problem in Cisco IOS Software Releases. Field Note, October 10 2001, http://www.cisco.com/warp/public/770/fn12942.html.
|
| |
5
|
|
| |
6
|
|
| |
7
|
L. Gao, T. G. Grin, and J. Rexford. Inherently safe backup routing with BGP. In Proceedings of the 20th IEEE Conference on Computer Communications (Infocom 2001), Anchorage, Alaska, April 2001.
|
| |
8
|
|
| |
9
|
|
| |
10
|
T. G. Griffin and G. Wilfong. A safe path vector protocol. In Proceedings of the 19th Annual IEEE Conference on Computer Communications (Infocom 2000), Tel Aviv, Israel, March 2000.
|
| |
11
|
|
| |
12
|
|
| |
13
|
Timothy G. Griffin , Gordon Wilfong, An analysis of BGP convergence properties, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.277-288, August 30-September 03, 1999, Cambridge, Massachusetts, United States
|
| |
14
|
Timothy G. Griffin and Gordon Wilfong. Analysis of the MED oscillation problem in BGP. unpublished manuscript, 2002.
|
| |
15
|
|
| |
16
|
|
| |
17
|
Ratul Mahajan , David Wetherall , Tom Anderson, Understanding BGP misconfiguration, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
|
| |
18
|
D. McPherson, V. Gill, D. Walton, and A. Retana. BGP persistent route oscillation condition. Internet Draft draft-ietf-idr-route-oscillation-01.txt , Work In Progress, 2002.
|
| |
19
|
Y. Rekhter and T. Li. A Border Gateway Protocol. RFC 1771 (BGP version 4), March 1995.
|
| |
20
|
Jonathan Rosenberg, Hussein Salma, and Matt Squire. Telephony routing over IP (TRIP). RFC 3219. January 2002.
|
| |
21
|
P. Traina, D. McPherson, and J. Scudder. Autonomous system confederations for BGP. RFC 3056, 2001.
|
| |
22
|
Kanan Varadhan, Ramesh Govindan, and Deborah Estrin. Persistent route oscillations in inter-domain routing. Computer Networks, 32:1--16, 2000.
|
CITED BY 29
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
Zhuoqing Morley Mao , Jennifer Rexford , Jia Wang , Randy H. Katz, Towards an accurate AS-level traceroute tool, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany
|
|
|
Maruti Gupta , Suresh Singh, Greening of the internet, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany
|
|
|
|
|
|
|
|
|
|
|
|
Nick Feamster , Hari Balakrishnan , Jennifer Rexford , Aman Shaikh , Jacobus van der Merwe, The case for separating routing from routers, Proceedings of the ACM SIGCOMM workshop on Future directions in network architecture, August 30-30, 2004, Portland, Oregon, USA
|
|
|
|
|
|
|
|
|
Patrick Verkaik , Dan Pei , Tom Scholl , Aman Shaikh , Alex C. Snoeren , Jacobus E. van der Merwe, Wresting control from BGP: scalable fine-grained route control, 2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference, p.1-14, June 17-22, 2007, Santa Clara, CA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
John P. John , Ethan Katz-Bassett , Arvind Krishnamurthy , Thomas Anderson , Arun Venkataramani, Consensus routing: the internet as a distributed system, Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation, p.351-364, April 16-18, 2008, San Francisco, California
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
C.2