Network routing with path vector protocols: theory and applications

ABSTRACT

Path 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 algebraic framework and relate the convergence of the protocol, and the characteristics of the paths to which it converges, with the monotonicity and isotonicity properties of its path compositional operation. Here, monotonicity means that the weight of a path cannot decrease when it is extended, and isotonicity means that the relationship between the weights of any two paths with the same origin is preserved when both are extended to the same node. We show that path vector protocols can be made to converge for every network if and only if the algebra is monotone, and that the resulting paths selected by the nodes are optimal if and only if the algebra is isotone as well.Many practical conclusions can be drawn from instances of the generic algebra. For performance-oriented routing, typical in intra-domain routing, we conclude that path vector protocols can be made to converge to widest or widest-shortest paths, but that the composite metric of IGRP (Interior Gateway Protocol), for example, does not guarantee convergence to optimal paths. For policy-based routing, typical in inter-domain routing, we formulate existing guidelines as instances of the generic algebra and we propose new ones. We also show how a particular instance of the algebra yields a sufficient condition for signaling correctness of internal BGP.

REFERENCES

• 1: M. Blanchet, F. Parent, and B. St-Arnaud. Optical BGP (OBGP): InterAS lightpath provisioning. Internet draft draft-parent-obgp-01.txt, January 2001.
• 2: J. Doyle. Routing TCP/IP. Cisco Press, Indianapolis, IN, 1998. ISBN 1-57870-041-8.
• 3: L. Gao, T. Griffin, and J. Rexford. Inherently safe backup routing with BGP. In Proc. INFOCOM 2001, pages 547--556, Anchorage, AK, April 2001.
• 4: 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]
• 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:29--35, January/February 1999.
• 6: Timothy G. Griffin , F. Bruce Shepherd , Gordon Wilfong, Policy Disputes in Path-Vector Protocols, Proceedings of the Seventh Annual International Conference on Network Protocols, p.21, October 31-November 03, 1999
• 7: 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
• 8: Timothy G. Griffin , Gordon Wilfong, On the correctness of IBGP configuration, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 9: Bassam Halabi, Internet Routing Architectures, Cisco Press, 1997
• 10: G. Huston. Interconnections, peering and financial settlements. In Proc. INET'99, San Jose, CA, June 1999.
• 11: L. Lamport. An assertional correctness proof of a distributed algorithm. Science of Computer Programming, 2(3):175--206, December 1982.
• 12: Leslie Lamport, The temporal logic of actions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.872-923, May 1994 [doi>10.1145/177492.177726]
• 13: Y. Rekhter and T. Li. A Border Gateway Protocol 4 BGP-4. RFC 1771, March 1995.
• 14: J. Rosenberg, H. Salma, and M. Squire. Telephony routing over IP TRIP. RFC 3219, January 2002.
• 15: João Luís Sobrinho, Algebra and algorithms for QoS path computation and hop-by-hop routing in the internet, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.541-550, August 2002 [doi>10.1109/TNET.2002.801397]
• 16: John W. Stewart, III, BGP4: Inter-Domain Routing in the Internet, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 17: Li Xiao , King-Shan Lui , Jun Wang , Klara Nahrsted, QoS Extension to BGP, Proceedings of the 10th IEEE International Conference on Network Protocols, p.100-109, November 12-15, 2002

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms, Theory

Keywords:
BGP, algebra, border gateway protocol, path vector protocols