Timothy G. Griffin
Abstract
Dynamic routing protocols such as RIP and OSPF essentially implement distributed algorithms for solving the shortest paths problem. The border gateway protocol (BGP) is currently the only interdomain routing protocol deployed in the Internet. BGP does not solve a shortest paths problem since any interdomain protocol is required to allow policy-based metrics to override distance-based metrics and enable autonomous systems to independently define their routing policies with little or no global coordination. It is then natural to ask if BGP can be viewed as a distributed algorithm for solving some fundamental problem. We introduce the stable paths problem and show that BGP can be viewed as a distributed algorithm for solving this problem. Unlike a shortest path tree, such a solution does not represent a global optimum, but rather an equilibrium point in which each node is assigned its local optimum.We study the stable paths problem using a derived structure called a dispute wheel, representing conflicting routing policies at various nodes. We show that if no dispute wheel can be constructed, then there exists a unique solution for the stable paths problem. We define the simple path-vector protocol (SPVP), a distributed algorithm for solving the stable paths problem. SPVP is intended to capture the dynamic behavior of BGP at an abstract level. If SPVP converges, then the resulting state corresponds to a stable paths solution. If there is no solution, then SPVP always diverges. In fact, SPVP can even diverge when a solution exists. We show that SPVP will converge to the unique solution of an instance of the stable paths problem if no dispute wheel exists.
- D. Bertsekas and R. Gallagher, Data Networks. Englewood Cliffs, NJ: Prentice Hall, 1992.]] Google Scholar
- K. Bhargavan, D. Obradovic, and C. Gunter, "Formal verification of standards for distance vector routing protocols," Univ. of Pennsylvania, Philadelphia, PA, Tech. Rep., 1999.]]Google Scholar
- K. Binmore, Fun and Games. Lexington, MA: Heath, 1992.]]Google Scholar
- L. Gao and J. Rexford, "Stable internet routing without global coordination," in Proc. ACM SIGMETRICS, 2000, pp. 307-317.]] Google Scholar
- M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, CA: Freeman, 1979.]] Google Scholar
- M. G. Gouda, Elements of Network Protocol Design. New York: Wiley, 1998.]] Google Scholar
- M. G. Gouda and M. Schneider, "Maximizable routing metrics," in Proc. 6th Int. Conf. Network Protocols (ICNP'98), 1998, pp. 71-78.]] Google Scholar
- ____, "Stabilization of maximal metric trees," presented at the Workshop on Self-Stabilizing Systems, 1999.]] Google Scholar
- R. Govindan, C. Alaettinoglu, G. Eddy, D. Kessens, S. Kumar, and W. S. Lee, "An architecture for stable, analyzable internet routing," IEEE Network, vol. 13, pp. 29-35, Jan. 1999]]Google Scholar
- T. Griffin, F. B. Shepherd, and G. Wilfong, "Policy disputes in path vector protocols," in Proc, 7th Int. Conf. Network Protocols (ICNP'99), 1999, pp. 21-30.]] Google Scholar
- T. Griffin and G. Wilfong, "An analysis of BGP convergence properties," in Proc. ACM SIGCOMM'99, 1999, pp. 277-288.]] Google Scholar
- ____, "A safe path vector protocol," in Proc. IEEE INFOCOM, vol. 2, 2000, pp. 490-499.]]Google Scholar
- B. Halabi, Internet Routing Architectures. Indianapolis, IN: Cisco Press, 1997.]] Google Scholar
- C. Hendrick, "Routing Information Protocol,", RFC 1058, 1988.]] Google Scholar
- G. Huston, ISP Survival Guide. New York: Wiley, 1999.]]Google Scholar
- C. Labovitz, G. R. Malan, and F. Jahanian, "Internet routing instability," IEEE/ACM Trans. Networking, vol. 6, pp. 515-528, Oct. 1998.]] Google Scholar
- ____, "Origins of internet routing instability," in Proc. IEEE INFOCOM, vol. 1, 1999, pp. 218-226.]]Google Scholar
- Y. Rekhter and T. Li, "A border gateway protocol,", RFC 1771 (BGP version 4), 1995.]]Google Scholar
- J. W. Stewart, BGP4, Inter-Domain Routing in The Internet. Reading, MA: Addison-Wesley, 1998.]] Google Scholar
- P. Traina, "Autonomous systems confederations for BGP,", RFC 1965, 1996.]] Google Scholar
- K. Varadhan, R. Govindan, and D. Estrin, "Persistent route oscillations in inter-domain routing," Univ. of Southern California Information Sciences Institute, Marina del Rey, CA, ISI Tech. Rep. 96-631, 1996.]]Google Scholar
- C. Villamizar, R. Chandra, and R. Govindan, "BGP route flap damping,", RFC 2439, 1998.]] Google Scholar
Index Terms
- The stable paths problem and interdomain routing
Recommendations
On understanding transient interdomain routing failures
The convergence time of the interdomain routing protocol, BGP, can last as long as 30 minutes. Yet, routing behavior during BGP route convergence is poorly understood. During route convergence, an end-to-end Internet path can experience a transient loss ...
Architecture of the remote routing validation tool for BGP anomaly detection
RACS '12: Proceedings of the 2012 ACM Research in Applied Computation SymposiumThe Border Gateway Protocol (BGP) is an Inter-domain routing protocol that has gradually evolved over the past few decades. The main functionality of BGP is to exchange Network Layer Reachability Information (NLRI) between ASes so that a BGP speaker can ...
Network routing with path vector protocols: theory and applications
SIGCOMM '03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communicationsPath vector protocols are currently in the limelight, mainly because the inter-domain routing protocol of the Internet, BGP (Border Gateway Protocol), belongs to this class. In this paper, we cast the operation of path vector protocols into a broad ...
Comments