Distributed Minimum Hop Algorithms
Abstract
The control of data communication networks (and any other large distributed systems) must be at least partly distributed because of the need to make observations and exert control at the various nodes of the network. When one also considers the desireability of letting networks grow (or shrink due to failures), it is reasonable to consider control algorithms with minimal or no centralized operations. In developing distributed algorithms for such control functions as routing and flow control, for example, it becomes evident that there are a number of simple network problems which arise repeatedly; distributed algorithms for solving these simple problems are then useful as building blocks in more complex algorithms. Mathematically we model the network as a connected undirected graph with, say, n nodes and e edges. Each node contains the facilities for doing computations, storing data, and sending and receiving messages over the adjoining edges. Messages are assumed to be transmitted without error but with an unknown variable finite delay. Successive messages in a given direction on a given edge are queued for transmission at the sending node, are transmitted, arrive in the order transmitted and are queued waiting for processing by the receiving node.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1982
- Accession Number
- ADA117808
Entities
People
- Robert G. Gallager
Organizations
- Massachusetts Institute of Technology