Distributed shortest path algorithms for computer networks
By: by Jin Y. Yen
Contributors: Naval Postgraduate School (U.S.)
Publisher: Naval Postgraduate School
Published: 1979
Place of publication: Monterey, California
Language: eng
Number of pages: 32
Subjects: Computer networks; Network analysis (Planning); Algorithms
Description: This paper presents two distributed algorithms for finding shortest paths from a source node to all other nodes in an N-node network. These algorithms are executed at individual nodes using only local information. Algorithm 1 works in networks where there are no topological changes such as link failures, link recoveries or changes of link lengths. Algorithm 2 is a mofification of Algorithm 1 for networks where there are topological changes. Algorithm 1 determines the optimal shortest paths in at most N3/4 steps, which is only one-half of the computational upper bounds of Abram and Rhodes' and Segall, Merlin and Gallager's algorithms. After the last topological change, Algorithm 2 determines the optimal shortest paths in the same number of steps as Algorithm 1. There are many situations where the present algorithms will work up to N/2 times faster than the algorithms proposed by these authors.
Notes: Title from cover.

"NPS55-79-017"--Cover.

"August 1979"--Cover.

"Prepared for: Chief of Naval Research, Arlington, VA 22217."

Includes bibliographical references (p. 28-29).

"Approved for public release; distribution is unlimited"--Cover.

Technical report; 1979.

ck/ 6/2/09.