• Previous Article
    Unified and refined analysis of the response time and waiting time in the M/M/m FCFS preemptive-resume priority queue
  • JIMO Home
  • This Issue
  • Next Article
    Analysis of a discrete-time queue with general service demands and phase-type service capacities
October  2017, 13(4): 1927-1943. doi: 10.3934/jimo.2017025

Single server retrial queues with speed scaling: Analysis and performance evaluation

1. 

Division of Policy and Planning Sciences, Faculty of Engineering, Information and Systems, University of Tsukuba, Ibaraki 305-8573, Japan

2. 

Department of Telecommunications and Information Processing, Ghent University, St.-Pietersnieuwstraat 41, B-9000 Gent, Belgium

* Corresponding author

Received  October 2015 Published  April 2017

Fund Project: The reviewing process of the paper was handled by Wuyi Yue and Yutaka Takahashi as Guest Editors.

Recently, queues with speed scaling have received considerable attention due to their applicability to data centers, enabling a better balance between performance and energy consumption. This paper proposes a new model where blocked customers must leave the service area and retry after a random time, with retrial rate either varying proportionally to the number of retrying customers (linear retrial rate) or non-varying (constant retrial rate). For both, we first study a basic case and then subsequently incorporate the concepts of a setup time and a deactivation time in extended versions of the model. In all cases, we obtain a full characterization of the stationary queue length distribution. This allows us to evaluate the performance in terms of the mentioned balance between performance and energy, using an existing cost function as well as a newly proposed variant thereof. This paper presents the derivation of the stationary distribution as well as several numerical examples of the cost-based performance evaluation.

Citation: Tuan Phung-Duc, Wouter Rogiest, Sabine Wittevrongel. Single server retrial queues with speed scaling: Analysis and performance evaluation. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1927-1943. doi: 10.3934/jimo.2017025
References:
[1]

J. R. ArtalejoA. Economou and M. J. Lopez-Herrero, Analysis of a multiserver queue with setup times, Queueing Systems, 51 (2005), 53-76.  doi: 10.1007/s11134-005-1740-6.  Google Scholar

[2]

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.  Google Scholar

[3]

L. A. Barroso and U. Holzle, The case for energy-proportional computing, Computer, 40 (2007), 33-37.  doi: 10.1109/MC.2007.443.  Google Scholar

[4]

R. Conway and W. L. Maxwell, A queueing model with state dependent service rate, Journal of Industrial Engineering, 12 (1961), 132-136.   Google Scholar

[5]

A. GandhiM. Harchol-Balter and I. Adan, Server farms with setup costs, Performance Evaluation, 67 (2010), 1123-1138.   Google Scholar

[6]

A. GandhiS. DoroudiM. Harchol-Balter and A. Scheller-Wolf, Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward, Proceedings of the ACM SIGMETRICS, (2013), 153-166.   Google Scholar

[7]

A. GandhiS. DoroudiM. Harchol-Balter and A. Scheller-Wolf, 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.  Google Scholar

[8]

X. LuS. Aalto and P. Lassila, Performance-energy trade-off in data centers: Impact of switching delay, Proceedings of 22nd IEEE ITC Specialist Seminar on Energy Efficient and Green Networking (SSEEGN), (2013), 50-55.  doi: 10.1109/SSEEGN.2013.6705402.  Google Scholar

[9]

V. J. Maccio and D. G. Down, On optimal policies for energy-aware servers, Performance Evaluation, 90 (2014), 36-52.  doi: 10.1109/MASCOTS.2013.11.  Google Scholar

[10]

I. Mitrani, Managing performance and power consumption in a server farm, Annals of Operations Research, 202 (2013), 121-134.  doi: 10.1007/s10479-011-0932-1.  Google Scholar

[11]

P. R. Parthasarathy and R. Sudhesh, Time-dependent analysis of a single-server retrial queue with state-dependent rates, Operations Research Letters, 35 (2007), 601-611.  doi: 10.1016/j.orl.2006.12.005.  Google Scholar

[12]

T. Phung-DucW. RogiestY. Takahashi and H. Bruneel, Retrial queues with balanced call blending: Analysis of single-server and multiserver model, Annals of Operations Research, 239 (2016), 429-449.  doi: 10.1007/s10479-014-1598-2.  Google Scholar

[13]

T. Phung-Duc, Impatient customers in power-saving data centers, Analytical and Stochastic Modeling Techniques and Applications, Lecture Notes in Computer Science, LNCS, 8499 (2014), 185-199.  doi: 10.1007/978-3-319-08219-6_13.  Google Scholar

[14]

T. Phung-Duc, Server farms with batch arrival and staggered setup, Proceedings of the Fifth Symposium on Information and Communication Technology -ACM, (2014), 240-247.  doi: 10.1145/2676585.2676613.  Google Scholar

[15]

T. Phung-Duc, Exact solutions for M/M/c/Setup queues, Telecommunication Systems, 64 (2017), 309-324.  doi: 10.1007/s11235-016-0177-z.  Google Scholar

[16]

T. Phung-Duc, Multiserver queues with finite capacity and setup time, Analytical and Stochastic Modeling Techniques and Applications, Lecture Notes in Computer Science, LNCS, 9081 (2015), 173-187.  doi: 10.1007/978-3-319-18579-8_13.  Google Scholar

[17]

T. Phung-Duc and W. Rogiest, Analysis of an M/M/1 retrial queue with speed scaling, Proceedings of QTNA 2015, Advances in Intelligent Systems and Computing, 383 (2015), 113-124.  doi: 10.1007/978-3-319-22267-7_11.  Google Scholar

[18]

C. SchwartzR. Pries and P. Tran-Gia, A queuing analysis of an energy-saving mechanism in data centers, Proceedings of International Conference on Information Networking (ICOIN), (2012), 70-75.  doi: 10.1109/ICOIN.2012.6164352.  Google Scholar

[19]

W. Van HeddeghemS. LambertB. LannooD. ColleM. Pickavet and P. Demeester, Trends in worldwide ICT electricity consumption from 2007 to 2012, Computer Communications, 50 (2014), 64-76.  doi: 10.1016/j.comcom.2014.02.008.  Google Scholar

[20]

A. WiermanL. Andrew and A. Tang, Power-aware speed scaling in processor sharing systems, Proceedings of IEEE INFOCOM 2009, (2009), 2007-2015.  doi: 10.1109/INFCOM.2009.5062123.  Google Scholar

[21]

F. YaoA. Demers and S. Shenker, A scheduling model for reduced CPU energy, Proceedings 36th Annual Symposium on Foundations of Computer Science, (1995), 374-382.  doi: 10.1109/SFCS.1995.492493.  Google Scholar

show all references

References:
[1]

J. R. ArtalejoA. Economou and M. J. Lopez-Herrero, Analysis of a multiserver queue with setup times, Queueing Systems, 51 (2005), 53-76.  doi: 10.1007/s11134-005-1740-6.  Google Scholar

[2]

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.  Google Scholar

[3]

L. A. Barroso and U. Holzle, The case for energy-proportional computing, Computer, 40 (2007), 33-37.  doi: 10.1109/MC.2007.443.  Google Scholar

[4]

R. Conway and W. L. Maxwell, A queueing model with state dependent service rate, Journal of Industrial Engineering, 12 (1961), 132-136.   Google Scholar

[5]

A. GandhiM. Harchol-Balter and I. Adan, Server farms with setup costs, Performance Evaluation, 67 (2010), 1123-1138.   Google Scholar

[6]

A. GandhiS. DoroudiM. Harchol-Balter and A. Scheller-Wolf, Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward, Proceedings of the ACM SIGMETRICS, (2013), 153-166.   Google Scholar

[7]

A. GandhiS. DoroudiM. Harchol-Balter and A. Scheller-Wolf, 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.  Google Scholar

[8]

X. LuS. Aalto and P. Lassila, Performance-energy trade-off in data centers: Impact of switching delay, Proceedings of 22nd IEEE ITC Specialist Seminar on Energy Efficient and Green Networking (SSEEGN), (2013), 50-55.  doi: 10.1109/SSEEGN.2013.6705402.  Google Scholar

[9]

V. J. Maccio and D. G. Down, On optimal policies for energy-aware servers, Performance Evaluation, 90 (2014), 36-52.  doi: 10.1109/MASCOTS.2013.11.  Google Scholar

[10]

I. Mitrani, Managing performance and power consumption in a server farm, Annals of Operations Research, 202 (2013), 121-134.  doi: 10.1007/s10479-011-0932-1.  Google Scholar

[11]

P. R. Parthasarathy and R. Sudhesh, Time-dependent analysis of a single-server retrial queue with state-dependent rates, Operations Research Letters, 35 (2007), 601-611.  doi: 10.1016/j.orl.2006.12.005.  Google Scholar

[12]

T. Phung-DucW. RogiestY. Takahashi and H. Bruneel, Retrial queues with balanced call blending: Analysis of single-server and multiserver model, Annals of Operations Research, 239 (2016), 429-449.  doi: 10.1007/s10479-014-1598-2.  Google Scholar

[13]

T. Phung-Duc, Impatient customers in power-saving data centers, Analytical and Stochastic Modeling Techniques and Applications, Lecture Notes in Computer Science, LNCS, 8499 (2014), 185-199.  doi: 10.1007/978-3-319-08219-6_13.  Google Scholar

[14]

T. Phung-Duc, Server farms with batch arrival and staggered setup, Proceedings of the Fifth Symposium on Information and Communication Technology -ACM, (2014), 240-247.  doi: 10.1145/2676585.2676613.  Google Scholar

[15]

T. Phung-Duc, Exact solutions for M/M/c/Setup queues, Telecommunication Systems, 64 (2017), 309-324.  doi: 10.1007/s11235-016-0177-z.  Google Scholar

[16]

T. Phung-Duc, Multiserver queues with finite capacity and setup time, Analytical and Stochastic Modeling Techniques and Applications, Lecture Notes in Computer Science, LNCS, 9081 (2015), 173-187.  doi: 10.1007/978-3-319-18579-8_13.  Google Scholar

[17]

T. Phung-Duc and W. Rogiest, Analysis of an M/M/1 retrial queue with speed scaling, Proceedings of QTNA 2015, Advances in Intelligent Systems and Computing, 383 (2015), 113-124.  doi: 10.1007/978-3-319-22267-7_11.  Google Scholar

[18]

C. SchwartzR. Pries and P. Tran-Gia, A queuing analysis of an energy-saving mechanism in data centers, Proceedings of International Conference on Information Networking (ICOIN), (2012), 70-75.  doi: 10.1109/ICOIN.2012.6164352.  Google Scholar

[19]

W. Van HeddeghemS. LambertB. LannooD. ColleM. Pickavet and P. Demeester, Trends in worldwide ICT electricity consumption from 2007 to 2012, Computer Communications, 50 (2014), 64-76.  doi: 10.1016/j.comcom.2014.02.008.  Google Scholar

[20]

A. WiermanL. Andrew and A. Tang, Power-aware speed scaling in processor sharing systems, Proceedings of IEEE INFOCOM 2009, (2009), 2007-2015.  doi: 10.1109/INFCOM.2009.5062123.  Google Scholar

[21]

F. YaoA. Demers and S. Shenker, A scheduling model for reduced CPU energy, Proceedings 36th Annual Symposium on Foundations of Computer Science, (1995), 374-382.  doi: 10.1109/SFCS.1995.492493.  Google Scholar

Figure 1.  Transitions among states.
Figure 2.  Transitions among states.
Figure 3.  Transitions among states.
Figure 4.  Transitions among states.
Figure 5.  Cost $z$ as function of the service rate $\mu$
Figure 6.  Cost $z$ as function of the service rate $\mu$
Figure 7.  Cost $z$ as function of the service rate $\mu$
Figure 8.  Cost $y$ (second cost function) as function of the service rate $\mu$
[1]

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

[2]

Tuan Phung-Duc. Single server retrial queues with setup time. Journal of Industrial & Management Optimization, 2017, (3) : 1329-1345. doi: 10.3934/jimo.2016075

[3]

Shaojun Lan, Yinghui Tang. Performance analysis of a discrete-time $ Geo/G/1$ retrial queue with non-preemptive priority, working vacations and vacation interruption. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1421-1446. doi: 10.3934/jimo.2018102

[4]

Arnaud Devos, Joris Walraevens, Tuan Phung-Duc, Herwig Bruneel. Analysis of the queue lengths in a priority retrial queue with constant retrial policy. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-30. doi: 10.3934/jimo.2019082

[5]

Linna Li, Changjun Yu, Ning Zhang, Yanqin Bai, Zhiyuan Gao. A time-scaling technique for time-delay switched systems. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020108

[6]

Feng Zhang, Jinting Wang, Bin Liu. On the optimal and equilibrium retrial rates in an unreliable retrial queue with vacations. Journal of Industrial & Management Optimization, 2012, 8 (4) : 861-875. doi: 10.3934/jimo.2012.8.861

[7]

Bara Kim, Jeongsim Kim. Explicit solution for the stationary distribution of a discrete-time finite buffer queue. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1121-1133. doi: 10.3934/jimo.2016.12.1121

[8]

Zsolt Saffer, Wuyi Yue. A dual tandem queueing system with GI service time at the first queue. Journal of Industrial & Management Optimization, 2014, 10 (1) : 167-192. doi: 10.3934/jimo.2014.10.167

[9]

Yung Chung Wang, Jenn Shing Wang, Fu Hsiang Tsai. Analysis of discrete-time space priority queue with fuzzy threshold. Journal of Industrial & Management Optimization, 2009, 5 (3) : 467-479. doi: 10.3934/jimo.2009.5.467

[10]

Yongjiang Guo, Yuantao Song. The (functional) law of the iterated logarithm of the sojourn time for a multiclass queue. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-28. doi: 10.3934/jimo.2018192

[11]

Di Wu, Yanqin Bai, Fusheng Xie. Time-scaling transformation for optimal control problem with time-varying delay. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020098

[12]

Muberra Allahverdi, Ali Allahverdi. Minimizing total completion time in a two-machine no-wait flowshop with uncertain and bounded setup times. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-19. doi: 10.3934/jimo.2019062

[13]

Hideaki Takagi. Unified and refined analysis of the response time and waiting time in the M/M/m FCFS preemptive-resume priority queue. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1945-1973. doi: 10.3934/jimo.2017026

[14]

Yutaka Sakuma, Atsushi Inoie, Ken’ichi Kawanishi, Masakiyo Miyazawa. Tail asymptotics for waiting time distribution of an M/M/s queue with general impatient time. Journal of Industrial & Management Optimization, 2011, 7 (3) : 593-606. doi: 10.3934/jimo.2011.7.593

[15]

Dhanya Shajin, A. N. Dudin, Olga Dudina, A. Krishnamoorthy. A two-priority single server retrial queue with additional items. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-22. doi: 10.3934/jimo.2019085

[16]

Philippe Chartier, Norbert J. Mauser, Florian Méhats, Yong Zhang. Solving highly-oscillatory NLS with SAM: Numerical efficiency and long-time behavior. Discrete & Continuous Dynamical Systems - S, 2016, 9 (5) : 1327-1349. doi: 10.3934/dcdss.2016053

[17]

Zhanyou Ma, Pengcheng Wang, Wuyi Yue. Performance analysis and optimization of a pseudo-fault Geo/Geo/1 repairable queueing system with N-policy, setup time and multiple working vacations. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1467-1481. doi: 10.3934/jimo.2017002

[18]

Runqin Hao, Guanwen Zhang, Dong Li, Jie Zhang. Data modeling analysis on removal efficiency of hexavalent chromium. Mathematical Foundations of Computing, 2019, 2 (3) : 203-213. doi: 10.3934/mfc.2019014

[19]

Lihua Min, Xiaoping Yang. Finite speed of propagation and algebraic time decay of solutions to a generalized thin film equation. Communications on Pure & Applied Analysis, 2014, 13 (2) : 543-566. doi: 10.3934/cpaa.2014.13.543

[20]

Jean-Daniel Djida, Juan J. Nieto, Iván Area. Nonlocal time-porous medium equation: Weak solutions and finite speed of propagation. Discrete & Continuous Dynamical Systems - B, 2019, 24 (8) : 4031-4053. doi: 10.3934/dcdsb.2019049

2018 Impact Factor: 1.025

Article outline

Figures and Tables

[Back to Top]