Stalling for solving slow server problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 4, pp. 1097-1107.

The model of stalling in queueing system (QS) with two heterogeneous severs is considered, the probabilities of steady states by means of Tchebyshev polynomials of second order are derived. The obtained expressions are stable numerically, their complexity does not depend on the number of states, and they enable us to study QS characteristics analytically. Optimization of a stalling buffer is considered as well and it was shown that stalling helps us to solve the slow server problems under an appropriate choice of stalling buffer size, making a slow server usable under various values of system load. Asymptotic conditions of optimal query distribution in servers are established, when the ratio of capacities of fast and slow channels is increasing. Application of the model developed in computer networks is discussed as well.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2018056
Classification : 60K25, 90B22
Mots-clés : Heterogeneous severs, stalling buffer, queueing system
Kaklauskas, Liudvikas 1 ; Sakalauskas, Leonidas 1 ; Denisovas, Vitalijus 1

1 
@article{RO_2019__53_4_1097_0,
     author = {Kaklauskas, Liudvikas and Sakalauskas, Leonidas and Denisovas, Vitalijus},
     title = {Stalling for solving slow server problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {1097--1107},
     publisher = {EDP-Sciences},
     volume = {53},
     number = {4},
     year = {2019},
     doi = {10.1051/ro/2018056},
     mrnumber = {3986370},
     zbl = {1439.60086},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2018056/}
}
TY  - JOUR
AU  - Kaklauskas, Liudvikas
AU  - Sakalauskas, Leonidas
AU  - Denisovas, Vitalijus
TI  - Stalling for solving slow server problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2019
SP  - 1097
EP  - 1107
VL  - 53
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2018056/
DO  - 10.1051/ro/2018056
LA  - en
ID  - RO_2019__53_4_1097_0
ER  - 
%0 Journal Article
%A Kaklauskas, Liudvikas
%A Sakalauskas, Leonidas
%A Denisovas, Vitalijus
%T Stalling for solving slow server problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2019
%P 1097-1107
%V 53
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2018056/
%R 10.1051/ro/2018056
%G en
%F RO_2019__53_4_1097_0
Kaklauskas, Liudvikas; Sakalauskas, Leonidas; Denisovas, Vitalijus. Stalling for solving slow server problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 4, pp. 1097-1107. doi : 10.1051/ro/2018056. http://www.numdam.org/articles/10.1051/ro/2018056/

M.O. Abou-El-Ata and A.I. Shawky, A simple approach for the slower server problem. Commun. Faculty Sci. Ankara Univ. Ser. A 1 (1999) 1–6. | MR | Zbl

M. Abramowitz and I.A. Stegun, Handbook of mathematical functions with formulas, graphs, and mathematical tables. In Vol. 55 of National Bureau of Standards, Applied Mathematics Series. (1983). | Zbl

A.K. Agrawala, E.G. Coffman Jr, M.R. Garey and S.K. Tripathi, A stochastic optimization algorithm minimizing expected flow times on uniforn processors. IEEE Trans. Comput. 33 (1984) 351–356. | DOI | MR | Zbl

K.E. Avrachenkov, G.L. Shevlyakov and N.O. Vilchevskii, Randomized push-out disciplines in priority queueing. J. Math. Sci. 122 (2004) 3336–3342. | DOI | MR | Zbl

B.R. Bilel, N. Navid, M.S.M. Bouksiaa, Hybrid cpu-gpu distributed framework for large scale mobile networks simulation. In Proceedings of the 2012 IEEE/ACM 16th International Symposium on Distributed Simulation and Real Time Applications. IEEE Computer Society (2012, October) 44–53. | DOI

F. De Vericourt and Y.P. Zhou, On the incomplete results for the heterogeneous server problem. Queue. Syst. 52 (2006) 189–191. | DOI | MR | Zbl

D. Efrosinin and J. Sztrik, Performance analysis of a two-server heterogeneous retrial queue with threshold policy. Qual. Technol. Quant. Manage. 8 (2011) 211–236. | DOI

D. Efrosinin and V. Rykov, Heuristic solution for the optimal thresholds in a controllable multi-server heterogeneous queueing system without preemption. In: International Conference on Distributed Computer and Communication Networks. Springer, Cham (2015) 238–252. | Zbl

D. Efrosinin and J. Sztrik, Optimal control of a two-server heterogeneous queueing system with breakdowns and constant retrials. In: International Conference on Information Technologies and Mathematical Modelling. Springer, Cham (2016) 57–72. | Zbl

G. Giambene, Queuing Theory and Telecommunications. Springer US (2005).

V. Goswami and S.K. Samanta, Discrete-time bulk-service queue with two heterogeneous servers. Comput. Ind. Eng. 56 (2009) 1348–1356. | DOI

T.H. Hetherington, T.G. Rogers, L. Hsu, M. O’Connor and T.M. Aamodt, Characterizing and evaluating a key-value store application on heterogeneous CPU-GPU systems. In: IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). IEEE (2012) 88–98. | DOI

D. Kadjo, R. Ayoub, M. Kishinevsky and P.V. Gratz, A control-theoretic approach for energy efficient CPU-GPU subsystem in mobile platforms. In: Proceedings of the 52nd Annual Design Automation Conference. ACM (2015) 62.

G. Koole, A simple proof of the optimality of a threshold policy in a two-server queueing system. Syst. Control Lett. 26 (1995) 301–303. | DOI | MR | Zbl

R.L. Larsen, Control of multiple exponential servers with application to computer systems. Ph.D. thesis, University of Maryland, College Park, MD, USA (1981).

R.L. Larsen and A.K. Agrawala, Control of a heterogeneous two-server exponential queueing system. IEEE Trans. Softw. Eng. 4 (1983) 522–526. | DOI | Zbl

W. Lin and P. Kumar, Optimal control of a queueing system with two heterogeneous servers. IEEE Trans. Autom. Control 29 (1984) 696–703. | DOI | MR | Zbl

M.F. Neuts, Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach, Baltimore, Johns Hopkins University Press (1981). | MR | Zbl

E. Ozkan and J.P. Kharoufeh, Optimal control of a two-server queueing system with failures. Probab. Eng. Info. Sci. 28 (2014) 489–527. | DOI | MR | Zbl

PassMark software, CPU Benchmarks. Interactyve. Available at: https://www.cpubenchmark.net/high_end_cpus.html (2017)

V.V.E. Rykov and D.V. Efrosinin, On the slow server problem. Autom. Remote Control 70 (2009) 2013–2023. | DOI | MR | Zbl

V.V. Rykov, Monotone control of queueing systems with heterogeneous servers. Queue. Syst. 37 (2001) 391–403. | DOI | MR | Zbl

Z. Rosberg and A.M. Makowski, Optimal routing to parallel heterogeneous servers-small arrival rates. IEEE Trans. Autom. Control 35 (1990) 789–796. | DOI | MR | Zbl

M. Rubinovitch, The slow server problem: a queue with stalling. J. Appl. Probab. 22 (1985) 879–892. | DOI | MR | Zbl

C. Shi, Y. Li, J. Zhang, Y. Sun and S.Y. Philip, A survey of heterogeneous information network analysis. IEEE Trans. Knowl. Data Eng. 29 (2017) 17–37. | DOI

H. Takagi and A.M. Tarabia, Explicit probability density function for the length of a busy period in an M/M/1/K queue. Advances in Queueing Theory and Network Applications. Springer, New York (2009) 213–226. | DOI | MR

I. Viniotis and A. Ephremides, Extension of the optimality of the threshold policy in heterogeneous multiserver queueing systems. IEEE Trans. Autom. Control 33 (1988) 104–109. | DOI | MR | Zbl

S.H. Xu, A duality approach to admission and scheduling controls of queues. Queue. Syst. 18 (1994) 273–300. | DOI | MR | Zbl

Cité par Sources :