Hostname: page-component-76fb5796d-qxdb6 Total loading time: 0 Render date: 2024-04-26T10:25:28.659Z Has data issue: false hasContentIssue false
  • English
  • Français

Pathwise optimality of the exponential scheduling rule for wireless channels

Part of: Markov processes Special processes Operations research and management science

Published online by Cambridge University Press:  01 July 2016

Sanjay Shakkottai ,
R. Srikant  and
Alexander L. Stolyar
Sanjay Shakkottai*
Affiliation:
The University of Texas at Austin
R. Srikant*
Affiliation:
University of Illinois at Urbana-Champaign
Alexander L. Stolyar*
Affiliation:
Bell Labs Lucent Technologies
*
∗ Postal address: Wireless Networking and Communications Group, Department of Electrical and Computer Engineering, The University of Texas at Austin, 1 University Station C0803, Austin, TX 78712-0240, USA. Email address: shakkott@ece.utexas.edu
∗∗∗ Postal address: Coordinated Science Laboratory and Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA. Email address: rsrikant@uiuc.edu
∗∗∗∗ Postal address: Mathematical Sciences Research Center, Bell Labs Lucent Technologies, 600 Mountain Avenue, Murray Hill, NJ 07974, USA. Email address: stolyar@research.bell-labs.com
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the problem of scheduling the transmissions of multiple data users (flows) sharing the same wireless channel (server). The unique feature of this problem is the fact that the capacity (service rate) of the channel varies randomly with time and asynchronously for different users. We study a scheduling policy called the exponential scheduling rule, which was introduced in an earlier paper. Given a system with N users, and any set of positive numbers {an}, n = 1, 2,…, N, we show that in a heavy-traffic limit, under a nonrestrictive ‘complete resource pooling’ condition, this algorithm has the property that, for each time t, it (asymptotically) minimizes maxnanq̃n(t), where q̃n(t) is the queue length of user n in the heavy-traffic regime.

Keywords

Wireless networkschedulingquality of serviceexponential ruleheavy-traffic limitqueueing networkcomplete resource poolingworkloadstate space collapseoptimality

MSC classification

Primary: 60K25: Queueing theory 90B15: Network models, stochastic 60J70: Applications of Brownian motions and diffusion theory (population genetics, absorption problems, etc.)
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 36 , Issue 4 , December 2004 , pp. 1021 - 1045
Copyright
Copyright © Applied Probability Trust 2004 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Partially supported by NSF Grants ACI-0305644, CNS-0325788 and CNS-0347400.

Supported by NSF Grant ITR 00-85929.

References

[1] Andrews, M. et al., (2004). Scheduling in a queueing system with asynchronously varying service rates. Prob. Eng. Inf. Sci. 18, 191–217.CrossRefGoogle Scholar
[2] Bell, S. L. and Williams, R. J. (2001). Dynamic scheduling of a system with two parallel servers in heavy traffic with complete resource pooling: asymptotic optimality of a continuous review threshold policy. Ann. Appl. Prob. 11, 608–649.CrossRefGoogle Scholar
[3] Bramson, M. (1998). State space collapse with applications to heavy traffic limits for multiclass queueing networks. Queueing Systems 30, 89–148.CrossRefGoogle Scholar
[4] Buche, R. and Kushner, H. J. (2002). Control of mobile communications with time-varying channels in heavy traffic. IEEE Trans. Automatic Control 47, 992–1003.CrossRefGoogle Scholar
[5] Bender, P. et al., (2000). CDMA/HDR: A bandwidth efficient high speed wireless data service for nomadic users. IEEE Commun. Magazine, July 2000, 70–77.CrossRefGoogle Scholar
[6] Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes: Characterization and Convergence. John Wiley, New York.CrossRefGoogle Scholar
[7] Glynn, P. W. (1990). Diffusion approximations. In Stochastic Models (Handbooks Operat. Res. Manag. Sci. 2), eds Heyman, D. P. and Sobel, M. J., North-Holland, Amsterdam, pp. 145–198.CrossRefGoogle Scholar
[8] Harrison, J. M. (1998). Heavy traffic analysis of a system with parallel servers: asymptotic optimality of discrete review policies. Ann. Appl. Prob. 8, 822–848.CrossRefGoogle Scholar
[9] Harrison, J. M. (2000). Brownian models of open processing networks: canonical representation of workload. Ann. Appl. Prob. 10, 75–103.CrossRefGoogle Scholar
[10] Harrison, J. M. and Lopez, M. J. (1999). Heavy traffic resource pooling in parallel-server systems. Queueing Systems 33, 339–368.CrossRefGoogle Scholar
[11] Harrison, J. M. and van Mieghem, J. A. (1997). Dynamic control of Brownian networks: state space collapse and equivalent workload formulations. Ann. Appl. Prob. 7, 747–771.CrossRefGoogle Scholar
[12] Jakes, W. C. (ed.) (1974). Microwave Mobile Communications. John Wiley, New York.Google Scholar
[13] Reiman, M. I. (1984). Some diffusion approximations with state space collapse. In Modelling and Performance Evaluation Methodology (Paris, 1983; Lecture Notes Control Inf. Sci. 60), Springer, New York, pp. 209–240.Google Scholar
[14] Reiman, M. I. (1988). A multiclass feedback queue in heavy traffic. Adv. Appl. Prob. 20, 179–207.CrossRefGoogle Scholar
[15] Shakkottai, S. and Stolyar, A. L. (2002). Scheduling for multiple flows sharing a time-varying channel: the exponential rule. In Analytic Methods in Applied Probability (Amer. Math. Soc. Trans. Ser. 2, 207), ed. Suhov, Yu. M., American Mathematical Society, Providence, RI, pp. 185–201.Google Scholar
[16] Stolyar, A. L. (2004). Maxweight scheduling in a generalized switch: state space collapse and workload minimization in heavy traffic. Ann. Appl. Prob. 14, 1–53.CrossRefGoogle Scholar
[17] Whitt, W. (1971). Weak convergence theorems for priority queues: preemptive-resume discipline. J. Appl. Prob. 8, 74–94.CrossRefGoogle Scholar
[18] Williams, R. J. (1998). Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse. Queueing Systems 30, 27–88.CrossRefGoogle Scholar
[19] Williams, R. J. (2000). On dynamic scheduling of a parallel server system with complete resource pooling. In Analysis of Communication Networks: Call Centres, Traffic and Performance (Toronto, 1998; Fields Inst. Commun. 28), American Mathematical Society, Providence, RI, pp. 49–71.Google Scholar