
-
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
Multiserver retrial queue with setup time and its application to data centers
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 |
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.
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. Google Scholar |
[8] |
A. Gandhi, M. Harchol-Balter and I. Adan, Server farms with setup costs, Performance Evaluation, 67 (2010), 1123-1138. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[8] |
A. Gandhi, M. Harchol-Balter and I. Adan, Server farms with setup costs, Performance Evaluation, 67 (2010), 1123-1138. Google Scholar |
[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. Google Scholar |
[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. |




| | | |
| 1203 | 150 | 59 |
| | | |
| | | |
| 1203 | 150 | 59 |
| | | |
| | | |
| 1203 | 149 | 58 |
| | | |
| | | |
| 1203 | 149 | 58 |
| | | |
| ||||
| | | | |
0.1 | 39 | | 39 | |
0.2 | 66 | | 66 | |
0.3 | 92 | | 92 | |
0.4 | 118 | | 118 | |
0.5 | 144 | | 144 | |
0.6 | 170 | | 170 | |
0.7 | 197 | | 196 | |
0.8 | 228 | | 227 | |
0.9 | 349 | | 321 | |
| ||||
| | | | |
0.1 | 39 | | 39 | |
0.2 | 66 | | 66 | |
0.3 | 92 | | 92 | |
0.4 | 118 | | 118 | |
0.5 | 144 | | 144 | |
0.6 | 170 | | 170 | |
0.7 | 197 | | 196 | |
0.8 | 228 | | 227 | |
0.9 | 349 | | 321 | |
[1] |
Habib Ammari, Josselin Garnier, Vincent Jugnon. Detection, reconstruction, and characterization algorithms from noisy data in multistatic wave imaging. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 389-417. doi: 10.3934/dcdss.2015.8.389 |
[2] |
Mikhail Gilman, Semyon Tsynkov. Statistical characterization of scattering delay in synthetic aperture radar imaging. Inverse Problems & Imaging, 2020, 14 (3) : 511-533. doi: 10.3934/ipi.2020024 |
[3] |
Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367 |
[4] |
Valery Y. Glizer. Novel Conditions of Euclidean space controllability for singularly perturbed systems with input delay. Numerical Algebra, Control & Optimization, 2020 doi: 10.3934/naco.2020027 |
[5] |
Yunfei Lv, Rong Yuan, Yuan He. Wavefronts of a stage structured model with state--dependent delay. Discrete & Continuous Dynamical Systems - A, 2015, 35 (10) : 4931-4954. doi: 10.3934/dcds.2015.35.4931 |
[6] |
Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]