Distributed Shortest Path Algorithms for Computer Networks.

Abstract

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. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1979
Accession Number
ADA075415

Entities

People

  • Jin Y. Yen

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computer Communications
  • Computer Networks
  • Computers
  • Military Research
  • National Security
  • Network Architecture
  • Network Topology
  • Networks
  • Recovery
  • Schools
  • Security
  • Sequences
  • Test And Evaluation
  • Topology

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Graph Algorithms and Convex Optimization.