Shortest paths and loop-free routing in dynamic networks

ABSTRACT

In this paper, we survey the existing methods for designing shortest paths routing algorithms for dynamic networks. We compare them based on worst-case communication and message complexity, and suggest new approach that yields a protocol with linear time and polynomial communication. The main idea behind our approach is to use a “dynamic synchronizer”, which transforms a dynamic asynchronous network into static synchronous one. We believe this is an important methodology in design and analysis of communication protocols, that can be applied to other problems as well.

REFERENCES

• AAG87: Yehuda Afek, Baruch Awerbuch, and Eli G#fni. Applying static network protocols to dynamic networks. In 28th A nnz#al Symposium on Foundations of Computer Scier#ce. IEEE, October 1987.
• AG87: Baruch Awerbuch , Robert G. Gallager, A new distributed algorithm to find breadth first search trees, IEEE Transactions on Information Theory, v.33 n.3, p.315-322, May 1, 1987 [doi>10.1109/TIT.1987.1057314]
• AS88: Baruch Awerbuch #nd Michael Sipser. Dynamic networks are as fast as static networks. In 29tu Annual Symposium on Foundations o.f Computer Science, pages 206-220. IEEE, October 1988.
• Awe85: Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
• CRKG89: C. Cheng , R. Riley , S. P. R. Kumar , J. J. Garcia-Luna-Aceves, A loop-free extended Bellman-Ford routing protocol without bouncing effect, Symposium proceedings on Communications architectures & protocols, p.224-236, September 25-27, 1989, Austin, Texas, United States
• DS80: Edsger W. Dijkstra and C. S. Scholten. Termination detectiol# for diffusirtg computations. lnfo. Process. Letters, 11(1):1-4, August 1980.
• Fin79: Steven G. Finn. Resynch procedures #nd a fail-safe network protocol. 1EEE Trans. on Commun., COM-27(6):840-845, June 1979.
• Fre85: G N Frederickson, A single source shortest path algorithm for a planar distributed network, Proceedings on STACS 85 2nd annual symposium on theoretical aspects of computer science, p.143-150, December 1985, Saarbru:9Aicken, Germany
• Gal82: Robert G. Gallager. Distributed minimum hop algorithms. Technical Report LIDS-P-1175, MIT, Lab. for Information and Decision Systems, January 1982.
• Gar89a: J. J. Garcia-Luna-Aceves, A minimum-hop routing algorithm bases on distributed information, Computer Networks and ISDN Systems, v.16 n.5, p.367-382, May 1989 [doi>10.1016/0169-7552(89)90011-1]
• Gar89b: J. J. Garcia-Luna-Aceves, A unified approach to loop-free routing using distance vectors or link states, Symposium proceedings on Communications architectures & protocols, p.212-223, September 25-27, 1989, Austin, Texas, United States
• Hum81: Pierre A. Humblet. An adaptive distributed dijkstra shortest path algorithm. Technical Report CICS-P-60, Center for Intelligent Control Systems, MIT, May 19881.
• Jaf8O: Jeffrey Jaffe. Using sign all il#g messages instead of clocks. Unpublished manuscript., 1980.
• JM82: J. Jaffe and F. Moss. A responsive distributed routing protocol. 1EEE Trans. on Commun., COM-30(7, Part II):1758-1762, July 1982.
• KT87: Richard Koo , Sam Toueg, Checkpointing and rollback-recovery for distributed systems, IEEE Transactions on Software Engineering, v.13 n.1, p.23-31, Jan. 1987 [doi>10.1109/TSE.1987.232562]
• MRR80: John McQuillan, Ira Richer, and Eric Rosen. The new routing algorithm for the arpanet. IEEE Trans. on Commun., 28(5):711-719, May 1980.
• MS79: P. Merlin and A. SegM1. Failsafe distributed routing protocol. IEEE Trans. on Commun., COM-27:1280-1288, September 1979.
• RF89: B. Rajagopalan , M. Fairman, A new responsive distributed shortest-path rounting algorithm, Symposium proceedings on Communications architectures & protocols, p.237-246, September 25-27, 1989, Austin, Texas, United States
• Seg83: Adrian SegMl. Distributed network protocols. IEEE Trans. on Info. Theory, IT-29(1):23-35, January 1983. Some details in technical report of szune name, MIT Lab. for Info. and Decision Syst., LIDS-P.1015; Technion Dept. EE, Publ. 414, July 1981.
• SH87: Stuart R. Soloway and Pierre A. Humbler. On distributed network protocols for cha#,ging topologies. Technical Report LIDS-P-1564, MIT, Lab. for Information and Decision Systems, May 1987. Also have version from May 1986.
• SS81: A. Segall and M. Sidi. A failsafe distributed protocol for minimum delay routing. IEEE Trans. on Commun., COM-29(5):689- 695, May 1981,
• Taj77: William D. Tajibnapis, A correctness proof of a topology information maintenance protocol for a distributed computer network, Communications of the ACM, v.20 n.7, p.477-485, July 1977 [doi>10.1145/359636.359701]

INDEX TERMS

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

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Design