Flow Control, Capacity and Coding for Multiple Access Queues


Razvan Cristescu


The mechanism by which different transmitters gain access to a commonly shared channel plays an important role in the efficiency of the transmission over that channel. We study the structure, properties, and long term behavior of such control devices, under modeling assumptions inspired by TCP/IP’s flow control. We consider a bottleneck router with finite buffer and constant service rate, accessed by a variable number of sources that decide to turn between on/off transmitting state independently of each other. The injection rates (control actions) are modeled as Bernoulli random variables: an active source decides between transmitting a packet or staying idle with a certain probability. The goal is to find the optimal control strategy a source should use and to describe its performance in the long term, under the assumption that the only locally available information is the instantaneous feedback received from the router about the successful acceptance of the respective packet by its buffer.

Main contributions

We have found an optimal control policy for this setting, based on the classical theory of control optimization by dynamic programming for partially observed Markov systems, that maximizes the average throughput under some loss constraints. We derived a low complexity but close to optimal algorithm for updating the source transmission rate, as a function of the information state, a quantity which contains all the information about the system given the available sequence of observations and control actions. Our simulations show that if the number of active sources is varying up to some limits, and given an appropriate level for the loss constraint threshold (which for instance measures how much one is concerned about the real time requirements of the transmission), the control algorithm we propose is able to sense in a continuously adaptive manner variations in the available bandwidth, and thus to use the channel efficiently, while still maintaining fairness with respect to the other users. Further, we studied the behavior in the long term of a source implementing such a control algorithm. We showed that an important quantity involved in characterizing a control strategy from various performance criteria (average throughput, average loss probability) is the limit distribution over the simplex of probabilities of the information state, and we proved the existence of this limit. We also showed the uniqueness of this measure and a method to construct it. Our results can be successfully used for deriving provably stable MAC protocols for networks with limited locally available information (e.g. sensor networks or Aloha-based systems).

Current and Future Research

Our current research efforts deal with extensions of the system model analyzed above. One interesting extension consists of designing a controller for a source model with memory, and include in the design random delays in the observations. It it also of interest to consider richer observations for the local controllers, for example notification of the queue length of the shared buffer. Also, we are applying the techniques presented here for the task of target tracking in sensor networks.


Sergio Servetto, Martin Vetterli.


SNF project number 21-61831.00.

Major publications

R. Cristescu and S.D. Servetto, Flow control for multiple access queues, Proc. Conference on Information Sciences and Systems (CISS), 2001.
[detailed record] [bibtex]

R. Cristescu and S.D. Servetto, A convergence theorem for controlled queues with partial observations, Proc. IEEE International Symposium on Information Theory (ISIT), pp. 380, 2002.
[detailed record] [bibtex]