New dynamic SPT algorithm based on a ball-and-string model

ABSTRACT

A key functionality in today's widely used interior gateway routing protocols such as OSPF and IS-IS involves the computation of a shortest path tree (SPT). In many existing commercial routers, the computation of an SPT is done from scratch following changes in the link states of the network. As there may coexist multiple SPTs in a network with a set of given link states, such recomputation of an entire SPT not only is inefficient but also causes frequent unnecessary changes in the topology of an existing SPT and creates routing instability.This paper presents a new dynamic SPT algorithm that makes use of the structure of the previously computed SPT. Our algorithm is derived by recasting the SPT problem into an optimization problem in a dual linear programming framework, which can also be interpreted using a ball-and-string model. In this model, the increase (or decrease) of an edge weight in the tree corresponds to the lengthening (or shortening) of a string. By stretching the strings until each node is attached to a tight string, the resulting topology of the model defines an (or multiple) SPT(s). By emulating the dynamics of the ball-and-string model, we can derive an efficient algorithm that propagates changes in distances to all affected nodes in a natural order and in a most economical way. Compared with existing results, our algorithm has the best-known performance in terms of computational complexity as well as minimum changes made to the topology of an SPT. Rigorous proofs for correctness of our algorithm and simulation results illustrating its complexity are also presented.

REFERENCES

• 1: C. Baransel, W. Dobosiewicz, and P. Gburzynski, "Routing in multihop packet switching networks: Gb/s challenge," 1EEL Network, vol. 9, pp. 38-61, May/June 1995.
• 2: R. Bellman, "On a routing problem," Quarterly Appl. Mathemat., vol. 16, pp. 87-90, 1958.
• 3: Dimitri P. Bertsekas, Linear network optimization: algorithms and codes, MIT Press, Cambridge, MA, 1991
• 4: L. Breslau , D. Estrin, Design of inter-administrative domain routing protocols, Proceedings of the ACM symposium on Communications architectures & protocols, p.231-241, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 5: Introduction to algorithms, MIT Press, Cambridge, MA, 2001
• 6: Stephen E. Deering , David R. Cheriton, Multicast routing in datagram internetworks and extended LANs, ACM Transactions on Computer Systems (TOCS), v.8 n.2, p.85-110, May 1990 [doi>10.1145/78952.78953]
• 7: Paolo Giulio Franciosa , Daniele Frigioni , Roberto Giaccio, Semi-Dynamic Shortest Paths and Breadth-First Search in Digraphs, Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science, p.33-46, February 27-March 01, 1997
• 8: Daniele Frigioni , Alberto Marchetti-Spaccamela , Umberto Nanni, Fully dynamic output bounded single source shortest path problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.212-221, January 28-30, 1996, Atlanta, Georgia, United States
• 9: Daniele Frigioni , Alberto Marchetti-Spaccamela , Umberto Nanni, Incremental Algorithms for the Single-Source Shortest Path Problem, Proceedings of the 14th Conference on Foundations of Software Technology and Theoretical Computer Science, p.113-124, December 15-17, 1994
• 10: Christian Huitema, Routing in the Internet, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 11: Giorgio Ausiello , Giuseppe F. Italiano , Alberto Marchetti Spaccamela , Umberto Nanni, Incremental algorithms for minimal length paths, Journal of Algorithms, v.12 n.4, p.615-638, Dec. 1991 [doi>10.1016/0196-6774(91)90036-X]
• 12: J. McQuillan, L Richer, and E. Rosen, "The new routing algorithm for the ARPANET," 1EEE Trans. Commun., vol. COM-28, pp. 711-719, May 1980.
• 13: Paolo Narváez , Kai-Yeung Siu , Hong-Yi Tzeng, New dynamic algorithms for shortest path tree computation, IEEE/ACM Transactions on Networking (TON), v.8 n.6, p.734-746, Dec. 2000 [doi>10.1109/90.893870]
• 14: R. Perlman , G. Varghese, Pitfalls in the design of distributed routing algorithms, Symposium proceedings on Communications architectures and protocols, p.43-54, August 16-18, 1988, Stanford, California, United States
• 15: R. Perlman, "A comparison between two routing protocols: OSPF and IS-IS," 1EEENetwork, vol. 5, pp. 18-24, Sept. 1991.
• 16: G. Ramalingam , Thomas Reps, An incremental algorithm for a generalization of the shortest-path problem, Journal of Algorithms, v.21 n.2, p.267-305, Sept. 1996 [doi>10.1006/jagm.1996.0046]
• 17: E. Spira and A. Pan, "On finding and updating spanning trees and shortest paths," SIAM J. Computing, vol. 4, no. 3, pp. 375-380, Sept. 1975.
• 18: R. Tarjan, "Amortized computational complexity," SIAM J. Algorithms and Discrete Methods, vol. 6, no. 2, pp. 306-318, Apr. 1985.
• 19: Esteban Feuerstein , Alberto Marchetti-Spaccamela, Dynamic algorithms for shortest paths in planar graphs, Theoretical Computer Science, v.116 n.2, p.359-371, Aug. 16, 1993 [doi>10.1016/0304-3975(93)90328-Q]
• 20: E. Dijkstra, "A note two problems in connection with graphs," Numerical Mathemat., vol. 1, pp. 269-271, 1959.
• 21: 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
• 22: J. Moy, "OSPF Version 2," Internet Draft, rfc 2178, July 1997.
• 23: Vern Paxson, End-to-end routing behavior in the Internet, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.601-615, Oct. 1997 [doi>10.1109/90.649563]
• 24: Y. Rekhter and T. P. Gross, "Applications of the border gateway protocol in the Internet," DDN Network Information Center, Chantilly, VA, RFC 1772, Mar. 1995.
• 25: M. Schwartz and T. Stern, "Routing techniques used in computer communication networks," IEEE Trans. Commun., vol. 28, pp. 539-552, Apr. 1980.
• 26: Martha Steenstrup, Routing in communications networks, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1995
• 27: P. Traina, Ed., "BGP-4 protocol analysis," DDN Network Information Center, Chantilly, VA, RFC 1774, Mar. 1995.
• 28: L. Wei. Random topology generator (RTG). Univ. of Southern California, Los Angeles, CA. {Online}. Available: http://netweb.usc.edu/ daniel/research/sims/topology/.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

          Nouns: Internet

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

General Terms:
Algorithms, Performance, Theory, Verification

Keywords:
Algorithms, communication system routing, graph theory, graphs, trees