Decentralized Algorithms for Optimization of Single Commodity Flows

Abstract

Message routing was studied in a data communication network in which all messages are addressed to the same node of the network. We approach this problem by the minimization of a linear, increasing function of the message flow in the links of the network. In this minimization we consider explicitly the capacities of the links. We present two algorithms which can be executed in a distributed manner, i.e. the data processing facilities at the nodes of the network cooperate in this minimization by interchanging messages and processing them. One of the algorithms is an adaptation of the primal simplex method of linear programming. The other is an adaptation of D.R. Fulkerson's 'out-of- kilter' algorithm. We give simulation results of the performance of the first algorithm, and a bound on the total number of messages required by the second algorithm.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1980
Accession Number
ADA086736

Entities

People

  • Isidro M. Castineyra

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Ground and Sea Platforms
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Communication Networks
  • Computations
  • Computer Networks
  • Computer Programming
  • Computer Science
  • Computers
  • Data Processing
  • Digital Communications
  • Electrical Engineering
  • Information Processing
  • Information Systems
  • Linear Programming
  • Military Research
  • New York
  • Simplex Method
  • Simulations

Fields of Study

  • Computer science

Readers

  • Distributed Systems and Data Platform Development
  • Operations Research
  • Radio communications and signal processing.