Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-05T13:33:55.901Z Has data issue: false hasContentIssue false
  • English
  • Français

Bounding functions of Markov processes and the shortest queue problem

Published online by Cambridge University Press:  01 July 2016

John A. Gubner ,
B. Gopinath  and
S. R. S. Varadhan
John A. Gubner*
Affiliation:
University of Maryland
B. Gopinath*
Affiliation:
Bell Communications Research
S. R. S. Varadhan*
Affiliation:
Courant Institute of Mathematical Sciences
*
∗Present address: Department of Electrical and Computer Engineering, University of Wisconsin, Madison, WI 53706, USA.
∗∗Present address: Department of Electrical Engineering, Rutgers University, New Brunswick, NJ 08903, USA.
∗∗∗Postal address: Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, NY 10012, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove a theorem which can be used to show that the expectation of a non-negative function of the state of a time-homogeneous Markov process is uniformly bounded in time. This is reminiscent of the classical theory of non-negative supermartingales, except that our analog of the supermartingale inequality need not hold almost surely. Consequently, the theorem is suitable for establishing the stability of systems that evolve in a stabilizing mode in most states, though from certain states they may jump to a less stable state. We use this theorem to show that ‘joining the shortest queue' can bound the expected sum of the squares of the differences between all pairs among N queues, even under arbitrarily heavy traffic.

Keywords

STABILITYLYAPUNOV FUNCTIONSUPERMARTINGALELOAD BALANCINGPARALLEL QUEUES
Type
Research Article
Information
Advances in Applied Probability , Volume 21 , Issue 4 , December 1989 , pp. 842 - 860
Copyright
Copyright © Applied Probability Trust 1989 

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

This work was supported by Bell Communications Research. The research of the first author was also supported in part by the University of Maryland Systems Research Center under NSF Grant OIR-85-00108.

References

Billingsley, P. (1979) Probability and Measure. Wiley, New York.Google Scholar
Blanc, J. P. C. (1987) A note on waiting times in systems with queues in parallel. J. Appl. Prob. 24, 540–546.CrossRefGoogle Scholar
Brumelle, S. L. (1971) Some inequalities for parallel-server queues. Operat. Res. 19, 402–413.CrossRefGoogle Scholar
Conolly, B. W. (1984) The autostrada queueing problem. J. Appl. Prob. 21, 394–403.Google Scholar
Ephremides, A., Varaiya, P., and Walrand, J. (1980) A simple dynamic routing problem. IEEE Trans. Autom. Contr. 25, 690–693.CrossRefGoogle Scholar
Flatto, L. and Mckean, H. P. (1977) Two queues in parallel. Comm. Pure Appl. Math. 30, 255–263.Google Scholar
Foschini, G. J. and Salz, J. (1978) A basic dynamic routing problem and diffusion. IEEE Trans. Comm. 26, 320–327.Google Scholar
Haight, F. A. (1958) Two queues in parallel. Biometrika 45, 401–410.Google Scholar
Hajek, B. (1982) Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Prob. 14, 502–525.Google Scholar
Halfin, S. (1985) The shortest queue problem. J. Appl. Prob. 22, 865–878.CrossRefGoogle Scholar
Kingman, J. F. C. (1961) Two similar queues in parallel. Ann. Math. Statist. 32, 1314–1323.Google Scholar
Papadimitriou, I. (1973) A simple proof of the formula Σ∞ k=1 k–2 = π 2/6. Amer. Math. Monthly 80, 424–425.Google Scholar
Stark, E. L. (1974) The series Σ∞ k=1 k –s , s = 2, 3, 4, …, once more. Mathematics Mag. 47, 197–202.Google Scholar
Weber, R. R. (1978) On the optimal assignment of customers to parallel servers. J. Appl. Prob. 15, 406–413.CrossRefGoogle Scholar
Winston, W. (1977) Optimality of the shortest line discipline. J. Appl. Prob. 14, 181–189.CrossRefGoogle Scholar
Wolff, R. W. (1977) An upper bound for multi-channel queues. J. Appl. Prob. 14, 884–888.Google Scholar
Wolff, R. W. (1987) Upper bounds on work in system for multichannel queues. J. Appl. Prob. 24, 547–551.Google Scholar