\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

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

  • * Corresponding author

    * Corresponding author 

The reviewing process of this paper was handled by Yutaka Takahashi and Wuyi Yue

Abstract Full Text(HTML) Figure(7) / Table(3) Related Papers Cited by
  • 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.

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

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  The power consumption versus retrial rate for $c = 50$

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

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

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

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

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

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

    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$120315059
    $\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$ $1.0060\times 10^{-11}$ $1.6243\times 10^{-10}$ $2.2090\times 10^{-15}$
     | Show Table
    DownLoad: CSV

    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$120314958
    $\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$ $4.6265\times 10^{-11}$ $2.4851\times 10^{-10}$ $1.1490\times 10^{-16}$
     | Show Table
    DownLoad: CSV

    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.139 $2.3871 \times 10^{-19}$39 $1.3689 \times 10^{-25}$
    0.266 $3.3924 \times 10^{-15}$66 $1.0369 \times 10^{-17}$
    0.392 $3.7031 \times 10^{-13}$92 $3.1474 \times 10^{-14}$
    0.4118 $9.5226 \times 10^{-12}$118 $4.7215 \times 10^{-12}$
    0.5144 $1.4487 \times 10^{-10}$144 $2.1293 \times 10^{-10}$
    0.6170 $1.7715 \times 10^{-09}$170 $5.4344 \times 10^{-09}$
    0.7197 $1.7430 \times 10^{-08}$196 $1.0141 \times 10^{-07}$
    0.8228 $1.0765 \times 10^{-07}$227 $1.0942 \times 10^{-06}$
    0.9349 $1.5416 \times 10^{-06}$321 $7.4458 \times 10^{-07}$
     | Show Table
    DownLoad: CSV
  •   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.
      L. A. Barroso  and  U. Hölzle , The case for energy-proportional computing, Computer, 40 (2007) , 33-37.  doi: 10.1109/MC.2007.443.
      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.
      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.
      J. E. Diamond  and  A. S. Alfa , The MAP/PH/1 retrial queue, Stochastic Models, 14 (1998) , 1151-1177.  doi: 10.1080/15326349808807518.
      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.
      G. I. Falin and J. G. C. Templeton, Retrial Queues, Chapman & Hall, London, 1997.
      A. Gandhi , M. Harchol-Balter  and  I. Adan , Server farms with setup costs, Performance Evaluation, 67 (2010) , 1123-1138. 
      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.
      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.
      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.
      G. Latouche and V. Ramaswami, Matrix Analytic Methods in Stochastic Modelling, ASA-SIAM Series on Statistics and Applied Probability, SIAM, Philadelphia PA, 1999.
      E. Morozov , A multiserver retrial queue: Regenerative stability analysis, Queueing Systems, 56 (2007) , 157-168.  doi: 10.1007/s11134-007-9024-y.
      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.
      M. F. Neuts, Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Dover Publications, Inc., New York, 1994.
      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.
      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.
      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.
      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).
      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. 
      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.
      T. Phung-Duc , Exact solutions for M/M/c/Setup queues, Telecommunication Systems, 64 (2017) , 309-324.  doi: 10.1007/s11235-016-0177-z.
      T. Phung-Duc , Single server retrial queues with setup time, Journal of Industrial and Management Optimization, 13 (2017) , 1329-1345. 
      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.
      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.
  • 加载中

Figures(7)

Tables(3)

SHARE

Article Metrics

HTML views(2056) PDF downloads(536) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return