Accession Number:

ADA148452

Title:

Asynchronous Distributed Flow Control Algorithms.

Descriptive Note:

Doctoral thesis,

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS

Personal Author(s):

Report Date:

1984-10-01

Pagination or Media Count:

199.0

Abstract:

This document considers algorithms for flow control in computer networks with fixed routing. The goal is to establish input rates, for each source-destination pair, that satisfy a particular fairness criterion. Described are several algorithms in which the input rates are calculated based on controls established by the links of the network. These controls are updated iteratively, using feedback information from the network. It is shown that the rates thus calculated converge to the desired values when the links are assumed to update synchronously, and without feedback delay. A model for asynchronous operation with delay is given, and we demonstrate for this model that the input rates calculated by the synchronous algorithms may fail to converge. We show how to modify the algorithms, by the introduction of an update protocol and by using more of the available feedback information, so that convergence of the rates is guaranteed. The author extends the model for asynchronous computation developed by Bertsekas to get some results relating to general asynchronous distributed algorithms with update protocols. These results are used to give an alternate proof of the correct operation of one of the flow control algorithms. A computer program is developed to simulate the flow control algorithms for a voice packet network. The simulation results indicate that the algorithms behave as expected for a network with static loads. However, when input loads change in imitation of real conversations, the control algorithms do not adapt fast enough to control the flows effectively. Author

Subject Categories:

  • Administration and Management
  • Computer Programming and Software
  • Voice Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE