An algebraic theory of dynamic network routing

ABSTRACT

We develop a non-classic algebraic theory for the purpose of investigating the convergence properties of dynamic routing protocols. The algebraic theory can be regarded as a generalization of shortest-path routing, where the new concept of free cycle generalizes that of a positive-length cycle. A primary result then states that routing protocols always converge, though not necessarily onto optimal paths, in networks where all cycles are free. Monotonicity and isotonicity are two algebraic properties that strengthen convergence results. Monotonicity implies protocol convergence in every network, and isotonicity assures convergence onto optimal paths.A great many applications arise as particular instances of the algebraic theory. In intra-domain routing, we show that routing protocols can be made to converge to shortest and widest paths, for example, but that the composite metric of Internet Gateway Routing Protocol (IGRP) does not lead to optimal paths. The more interesting applications, however, relate to inter-domain routing and its Border Gateway Protocol (BGP), where the algebraic framework provides a mathematical template for the specification, design, and verification of routing policies. We formulate existing guidelines for inter-domain routing in algebraic terms, propose new guidelines contemplating backup relationships between domains, and derive a sufficient condition for signaling correctness of internal-BGP.

REFERENCES

• 1: {1} G. Malkin, "RIP Version 2," RFC 2453, Nov. 1998.
• 2: Gary Scott Malkin, RIP: an intra-domain routing protocol, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 3: {3} J. Doyle, Routing TCP/IP. Indianapolis, IN: Cisco Press, 1998.
• 4: {4} J. T. Moy, "OSPF Version 2," RFC 2328, Apr. 1998.
• 5: John T. Moy, OSPF: Anatomy of an Internet Routing Protocol, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 6: Christian Huitema, Routing in the Internet (2nd ed.), Prentice Hall PTR, Upper Saddle River, NJ, 1999
• 7: {7} Y. Rekhter and T. Li, "A Border Gateway Protocol 4 (BGP-4)," RFC 1771, Mar. 1995.
• 8: John W. Stewart, III, BGP4: Inter-Domain Routing in the Internet, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 9: 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]
• 10: Dimitri Bertsekas , Robert Gallager, Data networks (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 11: Mohamed G. Gouda , Marco Schneider, Maximizable routing metrics, IEEE/ACM Transactions on Networking (TON), v.11 n.4, p.663-675, August 2003 [doi>10.1109/TNET.2003.815294]
• 12: 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]
• 13: {13} T. Bates and R. Chandra, "BGP Route Reflection: An Alternative to Full Mesh IBGP," RFC 1966, Jun. 1996.
• 14: Rohit Dube, A comparison of scaling techniques for BGP, ACM SIGCOMM Computer Communication Review, v.29 n.3, July 1999 [doi>10.1145/505724.505729]
• 15: John G. Scudder , Rohit Dube, BGP scaling techniques revisited, ACM SIGCOMM Computer Communication Review, v.29 n.5, October 1999 [doi>10.1145/505696.505699]
• 16: 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
• 17: 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
• 18: João Luis Sobrinho, Network routing with path vector protocols: theory and applications, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863963]
• 19: {19} B. Carré, Graphs and Networks. Oxford, U.K.: Clarendon Press, 1979.
• 20: {20} M. Gondran and M. Minoux, Graphes et Algorithmes, 3rd ed. Paris, France: Eyrolles, 1995.
• 21: {21} M. Gondran and M. Minoux, Graphes, Dioïdes et Semi-Anneaux . Paris, France: Editions Tec & Doc, 2001.
• 22: 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
• 23: 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
• 24: {24} L. Lamport, "An assertional correctness proof of a distributed algorithm," Sci. Comput. Program., vol. 2, no. 3, pp. 175-206, Dec. 1982.
• 25: 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]
• 26: 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 [doi>10.1145/863955.863964]
• 27: {27} C. Alaettinoǧlu, "Scalable router configuration for the Internet," in Proc. 5th Int. Conf. Computer Communications and Networks, Rockville, MD, Oct. 1996, pp. 325-328.
• 28: {28} G. Huston, "Interconnections, peering and financial settlements," in Proc. INET'99, San Jose, CA, Jun. 1999.
• 29: Lixin Gao, On inferring autonomous system relationships in the internet, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.733-745, December 2001 [doi>10.1109/90.974527]
• 30: {30} L. Gao, T. Griffin, and J. Rexford, "Inherently safe backup routing with BGP," in Proc. IEEE INFOCOM, Anchorage, AK, Apr. 2001, pp. 547-556.
• 31: Timothy Griffin , Gordon T. Wilfong, Analysis of the MED Oscillation Problem in BGP, Proceedings of the 10th IEEE International Conference on Network Protocols, p.90-99, November 12-15, 2002

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.3 Languages and Systems
          Subjects: Special-purpose algebraic systems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Performance

Keywords:
algebra, convergence, inter-domain routing, intra-domain routing, routing protocols