A Distributed Shortest - Path Algorithm

Abstract

The problem of routing in a data network is often treated by assigning traffic dependent lengths to the links of the network and routing traffic from node i to node j along the shortest path from i to j. A distributed algorithm is presented in which the nodes cooperate to find all shortest paths. It runs asynchronously in every node and does not require the network topology, or even the number of nodes in the network, to be known a priori by the nodes.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1978
Accession Number
ADA059838

Entities

People

  • Pierre A. Humblet

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Ground and Sea Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Networks
  • Computers
  • Corporations
  • Information Processing
  • Information Systems
  • Instructions
  • Massachusetts
  • Military Research
  • Network Topology
  • Networks
  • New York
  • Simulations
  • Terminals
  • Topology
  • Virginia

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Parallel and Distributed Computing.