Large Deviations of Max-Weight Scheduling Policies on Convex Rate Regions

References

• Andrews M., Kumaran K. K., Ramanan K., Stolyar A. L., Vijayakumar R., Whiting P. Scheduling in a queueing system with asynchronously varying service rates. Probab. Engrg. Inform. Sci. (2004) 18(2):191–217Crossref, Google Scholar
• Atar R., Budhiraja A., Ramanan K. Deterministic and stochastic differential inclusions with multiple surfaces of discontinuity. Probab. Theory Related Fields (2008) 142(1–2):249–283Crossref, Google Scholar
• Bertsimas D., Paschalidis I. Ch., Tsitsiklis J. N. Asymptotic buffer overflow probabilities in multi-class multiplexers: An optimal control approach. IEEE Trans. Automatic Control (1998) 43(3):315–335Crossref, Google Scholar
• Billingsley P. Convergence of probability measures. Wiley Series in Probability and Statistics: Probability and Statistics (1999) 2nd ed.(A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York) Google Scholar
• Borovkov A. A. Boundary value problems for random walks and large deviations in function spaces. Theory Probab. Appl. (1967) 12(4):635–654Crossref, Google Scholar
• Botvich D. D., Duffield N. G. Large deviations, the shape of the loss curve, and economies of scale in large multiplexers. Queueing Systems Theory Appl. (1995) 20(3–4):293–320Crossref, Google Scholar
• Brézis H. Opérateurs maximaux monotones et semigroups de contractions dans les espaces de Hilbert. North-Holland Mathematics Studies, Vol. 5, Notes in Mathematics (50) (1973) (North-Holland Publishing Co., Amsterdam) Google Scholar
• Browder F. E. Nonlinear operators and nonlinear equations of evolution in Banach spaces. Proc. Sympos. Pure Math. (1976) 2(American Mathematical Society, Providence, RI) Crossref, Google Scholar
• Cépa E. Problème de Skorohod multivoque. Ann. Probab. (1998) 26(2):500–532Crossref, Google Scholar
• Chen H., Yao D. D.Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization. Applications of Mathematics (2001) 46(Springer-Verlag, New York) Crossref, Google Scholar
• Cover T. M., Thomas J. A.Elements of Information Theory (2006) 2nd ed.(Wiley-Interscience, Hoboken, NJ) Google Scholar
• Dembo A., Zajic T. Large deviations: From empirical mean and measure to partial sums process. Stochastic Process. Appl. (1995) 57(2):191–224Crossref, Google Scholar
• Dembo A., Zeitouni O.Large Deviations Techniques and Applications (1998) 382nd ed.(Springer, New York) Applications of MathematicsCrossref, Google Scholar
• Doob J. L. Measure theory. Graduate Texts in Mathematics (1994) 143(Springer-Verlag, New York) Google Scholar
• Dudley R. M. Real analysis and probability. Cambridge Studies in Advanced Mathematics (2002) 74(Cambridge University Press, Cambridge, UK) Crossref, Google Scholar
• Dupuis P., Leder K., Wang H., Newman C., Resnick S. I., Sidoravicius V., Vares M. E. On the large deviations properties of the weighted-serve-the-longest-queue policy. In and Out of Equilibrium, 2, Progress in Probability (2008) 60(Birkhäuser, Basel, Switzerland) 229–256Crossref, Google Scholar
• Ethier S. N., Kurtz T. G. Markov processes: Characterization and convergence. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics (1986) (John Wiley & Sons, New York) Google Scholar
• Feng J., Kurtz T. G. Large deviations for stochastic processes. Mathematical Surveys and Monographs (2006) 131(American Mathematical Society, Providence, RI) Google Scholar
• Foss S., Konstantopoulos T. An overview of some stochastic stability methods. J. Oper. Res. Soc. Japan (2004) 47(4):275–303Crossref, Google Scholar
• Garcia J. An extension of the contraction principle. J. Theoret. Probab. (2004) 17(2):403–434Crossref, Google Scholar
• Jacod J., Shiryaev A. N. Limit theorems for stochastic processes. Grundlehren der Mathematischen WissenschaftenFundamental Principles of Mathematical Sciences (2003) 2882nd ed.(Springer-Verlag, Berlin) Google Scholar
• Kittipiyakul S., Javidi T. Optimal operating point for MIMO multiple access channel with bursty traffic. IEEE Trans. Wireless Comm. (2007) 6(12):4464–4474Crossref, Google Scholar
• Maglaras C., Van Mieghem J. A. Queueing systems with leadtime constraints: A fluid-model approach for admission and sequencing control. Eur. J. Oper. Res. (2005) 167(1):179–207Crossref, Google Scholar
• McKeown N., Mekkittikul A., Anantharam V., Walrand J. Achieving 100% throughput in an input-queued switch. IEEE Trans. Comm. (1999) 47(8):1260–1267Crossref, Google Scholar
• Mogul′skiĭ A. A. Large deviations for the trajectories of multidimensional random walks. Theory Probab. Appl. (1976) 21(2):309–323Google Scholar
• Mogul′skiĭ A. A. Large deviations for processes with independent increments. Ann. Probab. (1993) 21(1):202–215Crossref, Google Scholar
• Puhalskii A. A. Large deviations and idempotent probability. Chapman & Hall/CRC Monographs and Surveys in Pure and Applied Mathematics (2001) 119(Chapman & Hall/CRC, Boca Raton, FL) Crossref, Google Scholar
• Puhalskii A. A. Large deviations for stochastic processes. (2006) . Notes for LMS/EPSRC Short Course: Stochastic Stability, Large Deviations and Coupling Methods. Heriot-Watt University, Edinburgh, UK, http://www-math.cudenver.edu/puhalski/ld/course_1.pdfGoogle Scholar
• Puhalskii A. A. The action functional for the Jackson network. Markov Processes and Related Fields (2007) 13(1):99–136Google Scholar
• Puhalskii A. A., Vladimirov A. A. A large deviation principle for join the shortest queue. Math. Oper. Res. (2007) 32(3):700–710Link, Google Scholar
• Rockafellar R. T. Convex analysis. Princeton Mathematical Series (1970) 28(Princeton University Press, Princeton, NJ) Crossref, Google Scholar
• Rockafellar R. T., Wets R. J.-B. Variational analysis. Grundlehren der Mathematischen WissenschaftenFundamental Principles of Mathematical Sciences (1998) 317(Springer-Verlag, Berlin) Google Scholar
• Shwartz A., Weiss A., Vanderbei R. J.Large Deviations for Performance Analysis (1995) (Chapman & Hall/CRC, London) Stochastic Modeling SeriesQueues, Communications, and ComputingGoogle Scholar
• Stolyar A. L. Control of end-to-end delay tails in a multiclass network: LWDF discipline optimality. Ann. Appl. Probab. (2003) 13(3):1151–1206Crossref, Google Scholar
• Stolyar A. L., Ramanan K. Largest weighted delay first scheduling: Large deviations and optimality. Ann. Appl. Probab. (2001) 11(1):1–48Crossref, Google Scholar
• Tassiulas L., Ephremides A. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Automatic Control (1992) 37(12):1936–1948Crossref, Google Scholar
• Tse D. N. C., Hanly S. V. Multiaccess fading channels. I. Polymatroid structure, optimal resource allocation and throughput capacities. IEEE Trans. Inform. Theory (1998) 44(7):2796–2815Crossref, Google Scholar
• Tse D. N. C., Viswanath P., Zheng L. Diversity-multiplexing tradeoff in multiple-access channels. IEEE Trans. Inform. Theory (2004) 50(9):1859–1874Crossref, Google Scholar
• Venkataramanan V. J., Lin X. On wireless scheduling algorithms for minimizing the queue-overflow probability. IEEE/ACM Trans. Networking (2010) . http://cobweb.ecn.purdue.edu/∼linx/paper/ton08-ldp.pdfCrossref, Google Scholar
• Whitt W. Stochastic-process limits. An Introduction to Stochastic-Process Limits and Their Application to Queues (2002) (Springer-Verlag, New York) Springer Series in Operations ResearchGoogle Scholar
• Wischik D. Tutorial on queueing theory for switched networks. ICMS Workshop on Stochastic Processes in Communication Networks for Young Researchers (2010) Edinburgh, UKAccessed June 30, 2010, http://www.cs.ucl.ac.uk/staff/d.wischik/Talks/netsched.htmlGoogle Scholar
• Yosida K. Functional analysis. Classics in Mathematics (1995) (Springer-Verlag, Berlin) Google Scholar