Optimal Transmission Scheduling in Symmetric Communication Models With Intermittent Connectivity
Authors:
- Eytan ModianoEMEytan Modiano
- John N. TsitsiklisJTJohn N. Tsitsiklis
- 20 February 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 53 (3) , 998-1008
Abstract
We consider a slotted system with N queues, and independent and identically distributed (i.i.d.) Bernoulli arrivals at each queue during each slot. Each queue is associated with a channel that changes between "on" and "off" states according to i.i.d. Bernoulli processes. We assume that the system has K identical transmitters ("servers"). Each server, during each slot, can transmit up to C packets from each queue associated with an "on" channel. We show that a policy that assigns the servers to the longest queues whose channel is "on" minimizes the total queue size, as well as a broad class of other performance criteria. We provide several extensions, as well as some qualitative results for the limiting case where N is very large. Finally, we consider a "fluid" model under which fractional packets can be served, and subject to a constraint that at most C packets can be served in total from all of the N queues. We show that when K=N, there is an optimal policy which serves the queues so that the resulting vector of queue lengths is "Most Balanced" (MB)Keywords
This publication has 9 references indexed in Scilit:
- Pathwise optimality of the exponential scheduling rule for wireless channelsAdvances in Applied Probability, 2004
- SCHEDULING IN A QUEUING SYSTEM WITH ASYNCHRONOUSLY VARYING SERVICE RATESProbability in the Engineering and Informational Sciences, 2004
- Queueing Dynamics and Maximal Throughput Scheduling in Switched Processing SystemsQueueing Systems, 2003
- Power allocation and routing in multibeam satellites with time-varying channelsIEEE/ACM Transactions on Networking, 2003
- Communication over fading channels with delay constraintsIEEE Transactions on Information Theory, 2002
- ON PARALLEL QUEUING WITH RANDOM SERVER CONNECTIVITY AND ROUTING CONSTRAINTSProbability in the Engineering and Informational Sciences, 2002
- Dynamic server allocation to parallel queues with randomly varying connectivityIEEE Transactions on Information Theory, 1993
- Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networksIEEE Transactions on Automatic Control, 1992
- Encyclopaedia of Mathematics1988