The (functional) law of the iterated logarithm of the sojourn time for a multiclass queue

Yongjiang Guo; Yuantao Song

doi:10.3934/jimo.2018192

Article Contents

2020, Volume 16, Issue 3: 1049-1076. Doi: 10.3934/jimo.2018192

This issue Previous Article Empirical analysis and optimization of capital structure adjustment Next Article Priority queueing analysis of transaction-confirmation time for Bitcoin

The (functional) law of the iterated logarithm of the sojourn time for a multiclass queue

Yongjiang Guo^a, , and
Yuantao Song^b,

a.
School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China
b.
School of Engineering Science, University of the Chinese Academy of Sciences, Beijing, 100049, China

* Corresponding author
* Corresponding author

Received: September 2017

Revised: January 2018

Early access: December 2018

Published: March 2020

Abstract Full Text(HTML) Figure(1) / Table(4) Related Papers Cited by

Abstract

Two types of the law of iterated logarithm (LIL) and one functional LIL (FLIL) are established for the sojourn time process for a multiclass queueing model, having a priority service discipline, one server and $K$ customer classes, with each class characterized by a batch renewal arrival process and independent and identically distributed (i.i.d.) service times. The LIL and FLIL limits quantify the magnitude of asymptotic stochastic fluctuations of the sojourn time process compensated by its deterministic fluid limits in two forms: the numerical and functional. The LIL and FLIL limits are established in three cases: underloaded, critically loaded and overloaded, defined by the traffic intensity. We prove the results by a approach based on strong approximation, which approximates discrete performance processes with reflected Brownian motions. We conduct numerical examples to provide insights on these LIL results.

Keywords:

Mathematics Subject Classification: Primary: 60K25, 90B36; Secondary: 90B22, 68M20.

Citation:

Full Text(HTML)

Figure 1. The LIL limits in Example 3

Download: Full-size image PowerPoint slide

Table 1. The LIL and FLIL limits for (Ⅰ) in Example 1

$k$	1	2	3	4	5	6
$Z^_k=Z^_{sup, k}$	$0$	$0$	$0$	$\sqrt{3}$	$\sqrt{3.9}$	$\sqrt{4.8}$
$Z^*_{inf, k}$	$0$	$0$	$0$	$0$	$-\sqrt{3.9}$	$-\sqrt{4.8}$
$\mathcal{K}_{Z_{k}}$	$\{0\}$	$\{0\}$	$\{0\}$	$\Phi(\mathcal{G} (\sqrt{3}))$	$\mathcal{G} (\sqrt{3.9})$	$\mathcal{G} (\sqrt{4.8})$
$\mathcal{S}^_{k}=\mathcal{S}^_{sup, k}$	$0$	$0$	$0$	$10\sqrt{3}$
$\mathcal{S}^*_{inf, k}$	$0$	$0$	$0$	$0$
$\mathcal{K}_{\mathcal{S}_{k}}$	$\{0\}$	$\{0\}$	$\{0\}$	$\Phi(\mathcal{G} (10\sqrt{3}))$

| Show Table

DownLoad: CSV

Table 2. The LIL and FLIL limits for (Ⅱ) in Example 1

$k$	1	2	3	4	5	6
$Z^_k=Z^_{sup, k}$	$0$	$0$	$0$	$\sqrt{3.6}$	$\sqrt{4.5}$	$\sqrt{5.4}$
$Z^*_{inf, k}$	$0$	$0$	$0$	$-\sqrt{3.6}$	$-\sqrt{4.5}$	$-\sqrt{5.4}$
$\mathcal{K}_{Z_{k}}$	$\{0\}$	$\{0\}$	$\{0\}$	$\mathcal{G} (3.6)$	$\mathcal{G} (4.5)$	$\mathcal{G} (5.4)$
$\mathcal{S}^_{k}=\mathcal{S}^_{sup, k}$	$0$	$0$	$0$	$20\sqrt{3}$
$\mathcal{S}^*_{inf, k}$	$0$	$0$	$0$	$-20\sqrt{3}$
$\mathcal{K}_{\mathcal{S}_{k}}$	$\{0\}$	$\{0\}$	$\{0\}$	$\mathcal{G} (20\sqrt{3})$

| Show Table

DownLoad: CSV

Table 3. The LIL and FLIL limits for (Ⅱ) in Example 2

$k$	1	2	3	4	5
$Z^_k=Z^_{sup, k}$	$0$	$0$	$C_{3}$	$C_{4}$	$C_{5}$
$Z^*_{inf, k}$	$0$	$0$	$0$	$-C_{4}$	$-C_{5}$
$\mathcal{K}_{Z_{k}}$	$\{0\}$	$\{0\}$	$\Phi(\mathcal{G} (C_{3}))$	$\mathcal{G} (C_{4})$	$\mathcal{G} (C_{5})$
$\mathcal{S}^_{k}=\mathcal{S}^_{sup, k}$	$0$	$0$	$5C_{3}$
$\mathcal{S}^*_{inf, k}$	$0$	$0$	$0$
$\mathcal{K}_{\mathcal{S}_{k}}$	$\{0\}$	$\{0\}$	$\Phi(\mathcal{G} (5C_{3}))$

| Show Table

DownLoad: CSV

Table 4. The LIL and FLIL limits for (Ⅲ) in Example 2

$k$	1	2	3	4	5
$Z^_{k}=Z^_{sup, k}$	$0$	$0$	$D_{3}$	$D_{4}$	$D_{5}$
$Z^*_{inf, k}$	$0$	$0$	$-D_{3}$	$-D_{4}$	$-D_{5}$
$\mathcal{K}_{Z_{k}}$	$0$	$0$	$\mathcal{G}(D_{3})$	$\mathcal{G}(D_{4})$	$\mathcal{G}(D_{5})$
$\mathcal{S}^_{k}=\mathcal{S}^_{sup, k}$	0	0	$D$
$\mathcal{S}^*_{inf, k}$	$0$	$0$	$-D$
$\mathcal{K}_{\mathcal{S}_{k}}$	$0$	$0$	$\mathcal{G}(D)$

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

	M. Bramson and J. G. Dai , Heavy traffic limits for some queueing networks, Annals of Applied Probability, 11 (2001) , 49-90. doi: 10.1214/aoap/998926987.
	L. Caramellino , Strassen's law of the iterated logarithm for diffusion processes for small time, Stochastic Processes and their Applications, 74 (1998) , 1-19. doi: 10.1016/S0304-4149(97)00100-2.
	H. Chen and A. Mandelbaum, Hierarchical modeling of stochastic network, part Ⅱ: Strong approximations, Stochastic Modeling and Analysis of Manufacturing Systems, Yao, D. D. (Eds), (1994), 107-131.
	H. Chen and X. Shen , Strong approximations for multiclass feedforward queueing networks, Annals of Applied Probability, 10 (2000) , 828-876. doi: 10.1214/aoap/1019487511.
	H. Chen and D. D. Yao, Fundamentals of Queueing Networks, Springer-Verlag, New York, 2001. doi: 10.1007/978-1-4757-5301-1.
	H. Chen and H. Q. Zhang , A sufficient condition and a necessary condition for the diffusion approximations of multiclass queueing networks under priority service disciplines, Queueing Systems, 34 (2000) , 237-268. doi: 10.1023/A:1019113204634.
	M. Csörgő ang P. Révész, Strong Approximations in Probability and Statistics, Academic Press, New York, 1981.
	M. Csörgő , P. Deheuvels and L. Horváth , An approximation of stopped sums with applications in queueing theory, Advances in Applied Probability, 19 (1987) , 674-690. doi: 10.2307/1427412.
	M. Csörgő , Z. S. Hu and H. W. Mei , Strassen-type law of the iterated logarithm for self-normalized increments of sums, Journal of Mathematical Analysis and Applications, 393 (2012) , 45-55. doi: 10.1016/j.jmaa.2012.03.047.
	C. Cuny , F. Merlevéde and M. Peligrad , Law of the iterated logarithm for the periodogram, Stochastic Processes and their Applications, 123 (2013) , 4065-4089. doi: 10.1016/j.spa.2013.05.009.
	J. G. Dai , On the positive Harris recurrence for multiclass queueing networks: a unified approach via fluid limit models, Annals of Applied Probability, 5 (1995) , 49-77. doi: 10.1214/aoap/1177004828.
	S. N. Ethier and T. G. Kurtz, Markov Processes: Characterization and Convergence, Wiley, New York, 1986. doi: 10.1002/9780470316658.
	P. W. Glynn and W. Whitt , A new view of the heavy-traffic limit for infinite-server queues, Advances in Applied Probability, 23 (1991) , 188-209. doi: 10.2307/1427517.
	P. W. Glynn and W. Whitt , Departures from many queues in series, Annals of Applied Probability, 1 (1991) , 546-572. doi: 10.1214/aoap/1177005838.
	P. W. Glynn and W. Whitt , A central-limit-theorem version of L=λW, Queueing Systems, 1 (1986) , 191-215. doi: 10.1007/BF01536188.
	P. W. Glynn and W. Whitt , Sufficient conditions for functional limit theorem versions of L=λW, Queueing Systems, 1 (1987) , 279-287. doi: 10.1007/BF01149539.
	P. W. Glynn and W. Whitt , An LIL version of L=λW, Mathematics of Operations Research, 13 (1988) , 693-710. doi: 10.1287/moor.13.4.693.
	Y. Guo and Z. Li , Asymptotic variability analysis for a two-stage tandem queue, part Ⅰ: The functional law of the iterated logarithm, J. Math. Anal. Appl., 450 (2017) , 1479-1509. doi: 10.1016/j.jmaa.2017.01.062.
	Y. Guo and Z. Li , Asymptotic variability analysis for a two-stage tandem queue, part Ⅱ: The law of the iterated logarithm, J. Math. Anal. Appl., 450 (2017) , 1510-1534. doi: 10.1016/j.jmaa.2016.10.054.
	Y. Guo and Y. Liu , A law of iterated logarithm for multiclass queues with preemptive priority service discipline, Queueing Systems, 79 (2015) , 251-291. doi: 10.1007/s11134-014-9419-5.
	Y. Guo , Y. Liu and R. Pei , Functional law of iterated logarithm for multi-server queues with batch arrivals and customer feedback, Annals of Operations Research, 264 (2018) , 157-191. doi: 10.1007/s10479-017-2529-9.
	J. M. Harrison, Brownian Motion and Stochastic Flow System, Wiley, New York, 1985.
	L. Horváth , Strong approximation of renewal processes, Stochastic Process. Appl., 18 (1984) , 127-138. doi: 10.1016/0304-4149(84)90166-2.
	L. Horváth , Strong approximation of extended renewal processes, The Annals of Probability, 12 (1984) , 1149-1166. doi: 10.1214/aop/1176993145.
	L. Horváth , Strong approximations of open queueing networks, Mathematics of Operations Research, 17 (1992) , 487-508. doi: 10.1287/moor.17.2.487.
	G. L. Iglehart , Multiple channel queues in heavy traffic: IV. Law of the iterated logarithm, Z.Wahrscheinlichkeitstheorie verw. Geb., 17 (1971) , 168-180. doi: 10.1007/BF00538869.
	P. Lévy, Théorie de L'addition des Variables Aléatories, Gauthier-Villars, Paris, 1937.
	P. Lévy, Procesus Stochastique et Mouvement Brownien, Gauthier-Villars, Paris, 1948.
	E. Löcherbach and D. Loukianova , The law of iterated logarithm for additive functionals and martingale additive functionals of Harris recurrent Markov processes, Stochastic Processes and their Applications, 119 (2009) , 2312-2335. doi: 10.1016/j.spa.2008.11.006.
	A. Mandelbaum and W. A. Massey , Strong approximations for time-dependent queues, Mathematics of Operations Research, 20 (1995) , 33-64. doi: 10.1287/moor.20.1.33.
	A. Mandelbaum , W. A. Massey and M. Reiman , Strong approximations for Markovian service networks, Queueing Systems, 30 (1998) , 149-201. doi: 10.1023/A:1019112920622.
	S. Minkevi$\check{c}$ius and S. Stei$\check{s}\bar{u}$nas , A law of the iterated logarithm for global values of waiting time in multiphase queues, Statistics and Probability Letters, 61 (2003) , 359-371. doi: 10.1016/S0167-7152(02)00393-0.
	S. Minkevi$\check{c}$ius , On the law of the iterated logarithm in multiserver open queueing networks, Stochastics, 86 (2014) , 46-59. doi: 10.1080/17442508.2012.755625.
	S. Minkevi$\check{c}$ius , V. Dolgopolovas and L. L. Sakalauskas , A law of the iterated logarithm for the sojourn time process in queues in series, Methodology and Computing in Applied Probability, 18 (2016) , 37-57. doi: 10.1007/s11009-014-9402-y.
	K. Miyabea and A. Takemura , The law of the iterated logarithm in game-theoretic probability with quadratic and stronger hedges, Stochastic Processes and their Applications, 123 (2013) , 3132-3152. doi: 10.1016/j.spa.2013.03.018.
	W. P. Peterson , A heavy traffic limit theorem for networks of queues with multiple customer types, Mathematics of Operations Research, 16 (1991) , 90-118. doi: 10.1287/moor.16.1.90.
	L. L. Sakalauskas and S. Minkevi$\check{c}$ius , On the law of the iterated logarithm in open queueing networks, European Journal of Operational Research, 120 (2000) , 632-640. doi: 10.1016/S0377-2217(99)00003-X.
	V. Strassen , An invariance principle for the law of the iterated logarithm, Z. Wahrscheinlichkeitstheorie Verw. Geb., 3 (1964) , 211-226. doi: 10.1007/BF00534910.
	T. H. Tsai , Empirical law of the iterated logarithm for Markov chains with a countable state space, Stochastic Processes and their Applications, 89 (2000) , 175-191. doi: 10.1016/S0304-4149(00)00019-3.
	Y. Wang, The law of the iterated logarithm for p-random sequences. In: Proc. 11th IEEE Conference on Computational Complexity (CCC), (1996), 180-189.
	W. Whitt , Weak convergence theorems for priority queues: Preemptive-Resume discipline, Journal of Applied Probability, 8 (1971) , 74-94. doi: 10.2307/3211839.
	H. Q. Zhang and G. X. Hsu , Strong approximations for priority queues: Head-of-the-line-first discipline, Queueing Systems, 10 (1992) , 213-233. doi: 10.1007/BF01159207.
	H. Q. Zhang , G. X. Hsu and R. X. Wang , Strong approximations for multiple channels in heavy traffic, Journal of Applied Probability, 27 (1990) , 658-670. doi: 10.2307/3214549.
	H. Q. Zhang , Strong approximations of irreducible closed queueing networks, Advances in Applied Probability, 29 (1997) , 498-522. doi: 10.2307/1428014.