Multiserver retrial queue with setup time and its application to data centers

Tuan Phung-Duc; Ken'ichi Kawanishi

doi:10.3934/jimo.2018030

Previous Article
Delay characteristics in place-reservation queues with class-dependent service times
JIMO Home
This Issue
Next Article
Performance evaluation and optimization of cognitive radio networks with adjustable access control for multiple secondary users

January 2019, 15(1): 15-35. doi: 10.3934/jimo.2018030

Multiserver retrial queue with setup time and its application to data centers

Tuan Phung-Duc ^1,, and Ken'ichi Kawanishi ^2,

1.	Division of Policy and Planning Sciences, Faculty of Engineering, Information and Systems, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki 305-8573, Japan
2.	Division of Electronics and Informatics, Gunma University, 1-5-1 Tenjin-cho, Kiryu, Gunma 376-8515, Japan

* Corresponding author

Received February 2017 Revised July 2017 Published January 2019 Early access February 2018

Fund Project: The reviewing process of this paper was handled by Yutaka Takahashi and Wuyi Yue.

This paper considers a multiserver retrial queue with setup time which is motivated from application in data centers with the ON-OFF policy, where an idle server is immediately turned off. The ON-OFF policy is designed to save energy consumption of idle servers because an idle server still consumes about 60% of its peak consumption processing jobs. Upon arrival, a job is allocated to one of available off-servers and that server is started up. Otherwise, if all the servers are not available upon arrival, the job is blocked and retries in a random time. A server needs some setup time during which the server cannot process a job but consumes energy. We formulate this model using a three-dimensional continuous-time Markov chain obtaining the stability condition via Foster-Lyapunov criteria. Interestingly, the stability condition is different from that of the corresponding non-retrial queue. Furthermore, exploiting the special structure of the Markov chain together with a heuristic technique, we develop an efficient algorithm for computing the stationary distribution. Numerical results reveal that under the ON-OFF policy, allowing retrials is more power-saving than buffering jobs. Furthermore, we obtain a new insight that if the setup time is relatively long, setting an appropriate retrial time could reduce both power consumption and the mean response time of jobs.

Keywords: Data center, power consumption, delay, trade-off, retrials.

Mathematics Subject Classification: 60K25, 68M20, 90B22.

Citation: Tuan Phung-Duc, Ken'ichi Kawanishi. Multiserver retrial queue with setup time and its application to data centers. Journal of Industrial and Management Optimization, 2019, 15 (1) : 15-35. doi: 10.3934/jimo.2018030

References:

[1]	J. R. Artalejo and T. Phung-Duc, Markovian retrial queues with two way communication, Journal of Industrial and Management Optimization, 8 (2012), 781-806. doi: 10.3934/jimo.2012.8.781.
[2]	L. A. Barroso and U. Hölzle, The case for energy-proportional computing, Computer, 40 (2007), 33-37. doi: 10.1109/MC.2007.443.
[3]	L. Bright and P. G. Taylor, Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes, Stochastic Models, 11 (1995), 497-525. doi: 10.1080/15326349508807357.
[4]	J. Chang and J. Wang, Unreliable M/M/1/1 retrial queues with set-up time, Quality Technology & Quantitative Management, (2017), 1-13. doi: 10.1080/16843703.2017.1320459.
[5]	J. E. Diamond and A. S. Alfa, The MAP/PH/1 retrial queue, Stochastic Models, 14 (1998), 1151-1177. doi: 10.1080/15326349808807518.
[6]	J. E. Diamond and A. S. Alfa, Matrix analytic methods for a multiserver retrial queue with buffer, Top, 7 (1999), 249-266. doi: 10.1007/BF02564725.
[7]	G. I. Falin and J. G. C. Templeton, Retrial Queues, Chapman & Hall, London, 1997.
[8]	A. Gandhi, M. Harchol-Balter and I. Adan, Server farms with setup costs, Performance Evaluation, 67 (2010), 1123-1138.
[9]	A. Gandhi, S. Doroudi and M. Harchol-Balter, Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward, Queueing Systems, 77 (2014), 177-209. doi: 10.1007/s11134-014-9409-7.
[10]	Q.-M. He, H. Li and Y. Q. Zhao, Ergodicity of the BMAP/PH/s/s + K retrial queue with PH-retrial times, Queueing Systems, 35 (2000), 323-347. doi: 10.1023/A:1019110631467.
[11]	G. Latouche and V. Ramaswami, A logarithmic reduction algorithm for quasi-birth-death process, Journal of Applied Probability, 30 (1993), 650-674. doi: 10.1017/S0021900200044387.
[12]	G. Latouche and V. Ramaswami, Matrix Analytic Methods in Stochastic Modelling, ASA-SIAM Series on Statistics and Applied Probability, SIAM, Philadelphia PA, 1999.
[13]	E. Morozov, A multiserver retrial queue: Regenerative stability analysis, Queueing Systems, 56 (2007), 157-168. doi: 10.1007/s11134-007-9024-y.
[14]	E. Morozov and T. Phung-Duc, Stability analysis of a multiclass retrial system with classical retrial policy, Performance Evaluation, 112 (2017), 15-26. doi: 10.1016/j.peva.2017.03.003.
[15]	M. F. Neuts, Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Dover Publications, Inc., New York, 1994.
[16]	T. Phung-Duc, H. Masuyama, S. Kasahara and Y. Takahashi, A simple algorithm for the rate matrices of level-dependent QBD processes, Proceedings of the 5th International Conference on Queueing Theory and Network Applications, (2010), 46-52. doi: 10.1145/1837856.1837864.
[17]	T. Phung-Duc, H. Masuyama, S. Kasahara and Y. Takahashi, A matrix continued fraction approach to multiserver retrial queues, Annals of Operations Research, 202 (2013), 161-183. doi: 10.1007/s10479-011-0840-4.
[18]	T. Phung-Duc, Server farms with batch arrival and staggered setup, Proceedings of the Fifth symposium on Information and Communication Technology (SoICT 2014), (2014), 240-247. doi: 10.1145/2676585.2676613.
[19]	T. Phung-Duc and K. Kawanishi, An efficient method for performance analysis of blended call centers with redial, Asia-Pacific Journal of Operational Research, 31 (2014), 1440008 (33 pages).
[20]	T. Phung-Duc, M/M/1/1 retrial queues with setup time, Proceedings of the 10th International Conference on Queueing Theory and Network Applications, (2015), 93-104.
[21]	T. Phung-Duc and K. Kawanishi, Impacts of retrials on power-saving policy in data centers in Proceedings of the 11th International Conference on Queueing Theory and Network Applications, ACM, (2016), Article No. 22. doi: 10.1145/3016032.3016047.
[22]	T. Phung-Duc, Exact solutions for M/M/c/Setup queues, Telecommunication Systems, 64 (2017), 309-324. doi: 10.1007/s11235-016-0177-z.
[23]	T. Phung-Duc, Single server retrial queues with setup time, Journal of Industrial and Management Optimization, 13 (2017), 1329-1345.
[24]	Y. W. Shin, Stability of $MAP/PH/c/K$ queue with customer retrials and server vacations, Bulletin of the Korean Mathematical Society, 53 (2016), 985-1004. doi: 10.4134/BKMS.b150337.
[25]	R. L. Tweedie, Sufficient conditions for regularity, recurrence and ergodicity and Markov processes, Mathematical Proceedings of the Cambridge Philosophical Society, 78 (1975), 125-136. doi: 10.1017/S0305004100051562.

show all references

References:

[1]	J. R. Artalejo and T. Phung-Duc, Markovian retrial queues with two way communication, Journal of Industrial and Management Optimization, 8 (2012), 781-806. doi: 10.3934/jimo.2012.8.781.
[2]	L. A. Barroso and U. Hölzle, The case for energy-proportional computing, Computer, 40 (2007), 33-37. doi: 10.1109/MC.2007.443.
[3]	L. Bright and P. G. Taylor, Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes, Stochastic Models, 11 (1995), 497-525. doi: 10.1080/15326349508807357.
[4]	J. Chang and J. Wang, Unreliable M/M/1/1 retrial queues with set-up time, Quality Technology & Quantitative Management, (2017), 1-13. doi: 10.1080/16843703.2017.1320459.
[5]	J. E. Diamond and A. S. Alfa, The MAP/PH/1 retrial queue, Stochastic Models, 14 (1998), 1151-1177. doi: 10.1080/15326349808807518.
[6]	J. E. Diamond and A. S. Alfa, Matrix analytic methods for a multiserver retrial queue with buffer, Top, 7 (1999), 249-266. doi: 10.1007/BF02564725.
[7]	G. I. Falin and J. G. C. Templeton, Retrial Queues, Chapman & Hall, London, 1997.
[8]	A. Gandhi, M. Harchol-Balter and I. Adan, Server farms with setup costs, Performance Evaluation, 67 (2010), 1123-1138.
[9]	A. Gandhi, S. Doroudi and M. Harchol-Balter, Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward, Queueing Systems, 77 (2014), 177-209. doi: 10.1007/s11134-014-9409-7.
[10]	Q.-M. He, H. Li and Y. Q. Zhao, Ergodicity of the BMAP/PH/s/s + K retrial queue with PH-retrial times, Queueing Systems, 35 (2000), 323-347. doi: 10.1023/A:1019110631467.
[11]	G. Latouche and V. Ramaswami, A logarithmic reduction algorithm for quasi-birth-death process, Journal of Applied Probability, 30 (1993), 650-674. doi: 10.1017/S0021900200044387.
[12]	G. Latouche and V. Ramaswami, Matrix Analytic Methods in Stochastic Modelling, ASA-SIAM Series on Statistics and Applied Probability, SIAM, Philadelphia PA, 1999.
[13]	E. Morozov, A multiserver retrial queue: Regenerative stability analysis, Queueing Systems, 56 (2007), 157-168. doi: 10.1007/s11134-007-9024-y.
[14]	E. Morozov and T. Phung-Duc, Stability analysis of a multiclass retrial system with classical retrial policy, Performance Evaluation, 112 (2017), 15-26. doi: 10.1016/j.peva.2017.03.003.
[15]	M. F. Neuts, Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Dover Publications, Inc., New York, 1994.
[16]	T. Phung-Duc, H. Masuyama, S. Kasahara and Y. Takahashi, A simple algorithm for the rate matrices of level-dependent QBD processes, Proceedings of the 5th International Conference on Queueing Theory and Network Applications, (2010), 46-52. doi: 10.1145/1837856.1837864.
[17]	T. Phung-Duc, H. Masuyama, S. Kasahara and Y. Takahashi, A matrix continued fraction approach to multiserver retrial queues, Annals of Operations Research, 202 (2013), 161-183. doi: 10.1007/s10479-011-0840-4.
[18]	T. Phung-Duc, Server farms with batch arrival and staggered setup, Proceedings of the Fifth symposium on Information and Communication Technology (SoICT 2014), (2014), 240-247. doi: 10.1145/2676585.2676613.
[19]	T. Phung-Duc and K. Kawanishi, An efficient method for performance analysis of blended call centers with redial, Asia-Pacific Journal of Operational Research, 31 (2014), 1440008 (33 pages).
[20]	T. Phung-Duc, M/M/1/1 retrial queues with setup time, Proceedings of the 10th International Conference on Queueing Theory and Network Applications, (2015), 93-104.
[21]	T. Phung-Duc and K. Kawanishi, Impacts of retrials on power-saving policy in data centers in Proceedings of the 11th International Conference on Queueing Theory and Network Applications, ACM, (2016), Article No. 22. doi: 10.1145/3016032.3016047.
[22]	T. Phung-Duc, Exact solutions for M/M/c/Setup queues, Telecommunication Systems, 64 (2017), 309-324. doi: 10.1007/s11235-016-0177-z.
[23]	T. Phung-Duc, Single server retrial queues with setup time, Journal of Industrial and Management Optimization, 13 (2017), 1329-1345.
[24]	Y. W. Shin, Stability of $MAP/PH/c/K$ queue with customer retrials and server vacations, Bulletin of the Korean Mathematical Society, 53 (2016), 985-1004. doi: 10.4134/BKMS.b150337.
[25]	R. L. Tweedie, Sufficient conditions for regularity, recurrence and ergodicity and Markov processes, Mathematical Proceedings of the Cambridge Philosophical Society, 78 (1975), 125-136. doi: 10.1017/S0305004100051562.

Figure 1. The power consumption versus retrial rate for $c = 50$

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2. The power consumption versus setup rate for $c = 30, 50$

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3. The ratio $\mathrm{E}[P]/c$ versus retrial rate for $\alpha = 1/100$

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4. Mean response time versus retrial rate for $c = 30, 50$

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5. Mean response time versus retrial rate for $c = 30, 50$

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6. The power consumption versus traffic intensity for $\mu = 1$ and $\alpha = 1/10$

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7. The power consumption versus retrial rate for $c = 50$ and $\alpha = 1/10$

Figure Options

Download full-size image

Download as PowerPoint slide

Table 1. Truncation point $N$ and $\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$ for $c = 30$ and $\mu = 1/10$

	$c=30$
	$\alpha = 1/100$	$\alpha = 1/10$	$\alpha = 1$
$N$	1203	150	59
$\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$	$1.0060\times 10^{-11}$	$1.6243\times 10^{-10}$	$2.2090\times 10^{-15}$

Table Options

Download as excel

	$c=30$
	$\alpha = 1/100$	$\alpha = 1/10$	$\alpha = 1$
$N$	1203	150	59
$\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$	$1.0060\times 10^{-11}$	$1.6243\times 10^{-10}$	$2.2090\times 10^{-15}$

Table 2. Truncation point $N$ and $\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$ for $c = 50$ and $\mu = 1/10$

	$c=50$
	$\alpha = 1/100$	$\alpha = 1/10$	$\alpha = 1$
$N$	1203	149	58
$\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$	$4.6265\times 10^{-11}$	$2.4851\times 10^{-10}$	$1.1490\times 10^{-16}$

Table Options

Download as excel

	$c=50$
	$\alpha = 1/100$	$\alpha = 1/10$	$\alpha = 1$
$N$	1203	149	58
$\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$	$4.6265\times 10^{-11}$	$2.4851\times 10^{-10}$	$1.1490\times 10^{-16}$

Table 3. Truncation point $N$ and $\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$

	$c=50$		$c=100$
$\rho$	$N$	$\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$	$N$	$\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$
0.1	39	$2.3871 \times 10^{-19}$	39	$1.3689 \times 10^{-25}$
0.2	66	$3.3924 \times 10^{-15}$	66	$1.0369 \times 10^{-17}$
0.3	92	$3.7031 \times 10^{-13}$	92	$3.1474 \times 10^{-14}$
0.4	118	$9.5226 \times 10^{-12}$	118	$4.7215 \times 10^{-12}$
0.5	144	$1.4487 \times 10^{-10}$	144	$2.1293 \times 10^{-10}$
0.6	170	$1.7715 \times 10^{-09}$	170	$5.4344 \times 10^{-09}$
0.7	197	$1.7430 \times 10^{-08}$	196	$1.0141 \times 10^{-07}$
0.8	228	$1.0765 \times 10^{-07}$	227	$1.0942 \times 10^{-06}$
0.9	349	$1.5416 \times 10^{-06}$	321	$7.4458 \times 10^{-07}$

Table Options

Download as excel

	$c=50$		$c=100$
$\rho$	$N$	$\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$	$N$	$\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$
0.1	39	$2.3871 \times 10^{-19}$	39	$1.3689 \times 10^{-25}$
0.2	66	$3.3924 \times 10^{-15}$	66	$1.0369 \times 10^{-17}$
0.3	92	$3.7031 \times 10^{-13}$	92	$3.1474 \times 10^{-14}$
0.4	118	$9.5226 \times 10^{-12}$	118	$4.7215 \times 10^{-12}$
0.5	144	$1.4487 \times 10^{-10}$	144	$2.1293 \times 10^{-10}$
0.6	170	$1.7715 \times 10^{-09}$	170	$5.4344 \times 10^{-09}$
0.7	197	$1.7430 \times 10^{-08}$	196	$1.0141 \times 10^{-07}$
0.8	228	$1.0765 \times 10^{-07}$	227	$1.0942 \times 10^{-06}$
0.9	349	$1.5416 \times 10^{-06}$	321	$7.4458 \times 10^{-07}$

[1]	Yanqin Bai, Yudan Wei, Qian Li. An optimal trade-off model for portfolio selection with sensitivity of parameters. Journal of Industrial and Management Optimization, 2017, 13 (2) : 947-965. doi: 10.3934/jimo.2016055
[2]	Lihui Zhang, Xin Zou, Jianxun Qi. A trade-off between time and cost in scheduling repetitive construction projects. Journal of Industrial and Management Optimization, 2015, 11 (4) : 1423-1434. doi: 10.3934/jimo.2015.11.1423
[3]	Reza Lotfi, Zahra Yadegari, Seyed Hossein Hosseini, Amir Hossein Khameneh, Erfan Babaee Tirkolaee, Gerhard-Wilhelm Weber. A robust time-cost-quality-energy-environment trade-off with resource-constrained in project management: A case study for a bridge construction project. Journal of Industrial and Management Optimization, 2022, 18 (1) : 375-396. doi: 10.3934/jimo.2020158
[4]	Masataka Kato, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Effect of energy-saving server scheduling on power consumption for large-scale data centers. Journal of Industrial and Management Optimization, 2016, 12 (2) : 667-685. doi: 10.3934/jimo.2016.12.667
[5]	Daniel Mckenzie, Steven Damelin. Power weighted shortest paths for clustering Euclidean data. Foundations of Data Science, 2019, 1 (3) : 307-327. doi: 10.3934/fods.2019014
[6]	C. Burgos, J.-C. Cortés, L. Shaikhet, R.-J. Villanueva. A delayed nonlinear stochastic model for cocaine consumption: Stability analysis and simulation using real data. Discrete and Continuous Dynamical Systems - S, 2021, 14 (4) : 1233-1244. doi: 10.3934/dcdss.2020356
[7]	Haoyue Song, Fanwei Meng. Some generalizations of delay integral inequalities of Gronwall-Bellman type with power and their applications. Mathematical Foundations of Computing, 2022, 5 (1) : 45-55. doi: 10.3934/mfc.2021022
[8]	Zuo Quan Xu, Fahuai Yi. An optimal consumption-investment model with constraint on consumption. Mathematical Control and Related Fields, 2016, 6 (3) : 517-534. doi: 10.3934/mcrf.2016014
[9]	Rafael Diaz, Laura Gomez. Indirect influences in international trade. Networks and Heterogeneous Media, 2015, 10 (1) : 149-165. doi: 10.3934/nhm.2015.10.149
[10]	Michael Helmers, Barbara Niethammer, Xiaofeng Ren. Evolution in off-critical diblock copolymer melts. Networks and Heterogeneous Media, 2008, 3 (3) : 615-632. doi: 10.3934/nhm.2008.3.615
[11]	Vitali Kapovitch, Anton Petrunin, Wilderich Tuschmann. On the torsion in the center conjecture. Electronic Research Announcements, 2018, 25: 27-35. doi: 10.3934/era.2018.25.004
[12]	Camillo De Lellis, Emanuele Spadaro. Center manifold: A case study. Discrete and Continuous Dynamical Systems, 2011, 31 (4) : 1249-1272. doi: 10.3934/dcds.2011.31.1249
[13]	Keith Burns, Amie Wilkinson. Dynamical coherence and center bunching. Discrete and Continuous Dynamical Systems, 2008, 22 (1&2) : 89-100. doi: 10.3934/dcds.2008.22.89
[14]	Jingzhen Liu, Ka-Fai Cedric Yiu, Kok Lay Teo. Optimal investment-consumption problem with constraint. Journal of Industrial and Management Optimization, 2013, 9 (4) : 743-768. doi: 10.3934/jimo.2013.9.743
[15]	Lei Sun, Lihong Zhang. Optimal consumption and investment under irrational beliefs. Journal of Industrial and Management Optimization, 2011, 7 (1) : 139-156. doi: 10.3934/jimo.2011.7.139
[16]	Filipe Martins, Alberto A. Pinto, Jorge Passamani Zubelli. Nash and social welfare impact in an international trade model. Journal of Dynamics and Games, 2017, 4 (2) : 149-173. doi: 10.3934/jdg.2017009
[17]	Pau Erola, Albert Díaz-Guilera, Sergio Gómez, Alex Arenas. Modeling international crisis synchronization in the world trade web. Networks and Heterogeneous Media, 2012, 7 (3) : 385-397. doi: 10.3934/nhm.2012.7.385
[18]	Daniele Bartoli, Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Further results on multiple coverings of the farthest-off points. Advances in Mathematics of Communications, 2016, 10 (3) : 613-632. doi: 10.3934/amc.2016030
[19]	Peter E. Kloeden, Thomas Lorenz, Meihua Yang. Reaction-diffusion equations with a switched--off reaction zone. Communications on Pure and Applied Analysis, 2014, 13 (5) : 1907-1933. doi: 10.3934/cpaa.2014.13.1907
[20]	Masakatsu Suzuki, Hideaki Matsunaga. Stability criteria for a class of linear differential equations with off-diagonal delays. Discrete and Continuous Dynamical Systems, 2009, 24 (4) : 1381-1391. doi: 10.3934/dcds.2009.24.1381

2021 Impact Factor: 1.411

Tools

Metrics

Tools

Article outline

Figures and Tables

2021 Impact Factor: 1.411

Tools

Figures and Tables

2021 Impact Factor: 1.411

American Institute of Mathematical Sciences

Multiserver retrial queue with setup time and its application to data centers

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

Multiserver retrial queue with setup time and its application to data centers

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors