Accession Number : ADA117808


Title :   Distributed Minimum Hop Algorithms


Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS


Personal Author(s) : Gallager, Robert G


Full Text : http://www.dtic.mil/get-tr-doc/pdf?AD=ADA117808


Report Date : Jan 1982


Pagination or Media Count : 37


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.


Descriptors :   *ALGORITHMS , *COMMUNICATIONS NETWORKS , COMMUNICATIONS TRAFFIC , DATA TRANSMISSION SYSTEMS , DISTRIBUTED DATA PROCESSING , MESSAGE PROCESSING , NODES , PATHS


Subject Categories : Theoretical Mathematics
      Non-radio Communications


Distribution Statement : APPROVED FOR PUBLIC RELEASE