Accession Number:

ADA101685

Title:

A Distributed Shortest Path Protocol.

Descriptive Note:

Technical rept.,

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS

Personal Author(s):

Report Date:

1981-06-01

Pagination or Media Count:

32.0

Abstract:

We present a distributed protocol for obtaining the shortest paths between all pairs of nodes in a network with weighted links. The protocol is based on an extension of the Dijkstra centralized shortest path algorithm and uses collaboration between neighboring nodes to transfer the information needed at the nodes for the successive construction of the shortest paths. A formal description of the protocol is given by indicating the exact algorithm performed by each node. The validation proofs are greatly simplified by separating the communication mechanism from the computation at the nodes, the latter being the transposition of the Dijkstra shortest path algorithm to the decentralized protocol. Author

Subject Categories:

  • Theoretical Mathematics
  • Computer Systems
  • Non-Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE