Asynchronous Distributed Flow Control Algorithms.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1984
- Accession Number
- ADA148452
Entities
People
- J. Mosely
Organizations
- Massachusetts Institute of Technology