Communication Complexity of Distributed Shortest Path Algorithms
Abstract
One routing strategy frequently used in computer networks assigns traffic dependent distances to the links of the network and then increases the traffic flow on shortest paths. If a central facility monitors all network traffic, classical algorithms can be readily employed to compute shortest paths. If traffic is only locally monitored, we wish to have distributed procedures in which the nodes begin with only local information and compute shortest paths by communicating with one another. We present several such distributed shortest path algorithms and analyze their communication cost. Since the transmission of control information required for network operation reduces the bandwidth available to users, we concentrate on finding algorithms that use a minimum of information exchange.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1979
- Accession Number
- ADA066152
Entities
People
- Daniel U. Friedman
Organizations
- Massachusetts Institute of Technology