ON APPROXIMATION OF RETRIAL QUEUES WITH VARYING SERVICE RATE V. Ponomarov Taras Shevhenko National University of Kyiv Kyiv, Ukraine vponomarovgmail.om The paper deals with Markov model of retrial queueing system in whih servie rate depends on queue length. Investigation method is based on an approximation of the input system by the system with trunated state spae. The auray of suh approximation is also disussed. Keywords: Stohasti system, retrials, steady state. 1. INTRODUCTION The researh of wide lass of stohasti systems with repeated alls faes the problem of alulating harateristis of the system with the poisson inoming ow. Markov proess that desribes the behavior of suh system has an innite state spae and the transation matrix usually does not have speial properties that simplify the proess of nding Kolmogorov set of equations expliit solution. Desribed features lead to the fat that only few simple models were examined in details [1℄. Usually the problem of omputing stationary probabilities for suh systems is solved by omputation algorithms or reurrent shemas [2℄. To apply them system with nite state spae is taken into aount. Usually it is onsidered that the queue length does not exeed the value of M . If the request omes to the system when there is no free server and there are M soures of repeated alls already it is lost. It is intuitively obvious that by hoosing M big enough we an approximate harateristis of the input system with the predened auray. In this paper we present the desribed above tehni for the retrial system with Poisson input ow and varying servie rate. Its integral harateristis are approximated by harateristis of the system with trunated spae state whih an be expliitly written in terms of system's parameters. The error of suh approximation for dierent servie rate swithing poliies is also disussed. 2. MARKOV MODELS OF THE INPUT AND TRUNCATED SYSTEMS Consider ontinuous time Markov hain X (t) = (C (t); N (t)), C (t) 2 f0; 1; : : : ; g, N (t) 2 f0; 1; : : : g, whih is dened by its innitesimal harateristis a(i;j )(i ;j ) , (i; j ), (i0; j 0) 2 S (X ) = f0; 1; : : : ; g f0; 1; : : :g: 0 213 0 1) if i = f0; 1; : : : ; 1g, then a i;j ( 2) if i ;j ) )( 0 0 8 > ; > > > > > <j; (i0 ; j 0) = (i + 1; j ); (i0 ; j 0) = (i + 1; j 1); = >ij ; (i0 ; j 0) = (i 1; j ); > > [ + j + ij ℄; (i0 ; j 0) = (i; j ); > > > :0; otherwise. i = , then a ;j ( i ;j ) )( 0 0 8 > ; (i0; j 0) = (; j + 1); > > < ; (i0; j 0) = ( 1; j ); => j [ + j ℄; (i0; j 0) = (; j ); > > > :0; otherwise. Proess X (t) desribes the behavior of the following system. The inoming ow of events is Poisson with rate . There are idential servers. If there is any free server the request is served immediately. Servie time is exponentially distributed random variable with parameter j that depends on the urrent queue of repeated alls length. If request nds all servers busy it tries to get servie in a random period of time that has exponential distribution with parameter . The number of busy servers at any time t is dened by the rst omponent of X (t) and the number of retrials by the seond. Let us nd up the ondition of X (t); t > 0 stationary mode existene. Lemma 1. Let = lim j . Then if j !1 < 1 proess X (t) is ergodi and its boundary distribution ij ; (i; j ) 2 S (X ) oinides with a single stationary. Proof. Consider the following Lyapunov funtions '(i; j ) = i + j; (i; j ) 2 S (X ); where parameter will be determined later on. Then the mean drifts X yij = i ;j )6=(i;j ) ( are given by yij = 0 a i;j ( 0 0) i ;j ) ('(i ; j )( 0 0 '(i; j ) 0 ( ij + j( 1); 0 i 1; j ; i = : < 1 for any value of 2 ( ; 1) there exists suh " > 0 that yij < " for all (i; j ) 2 S (X ) exluding nite number of states (i; j ). So the assumptions of Tweedie's ; 1). theorem[[?℄, p.97℄ are hold for funtions '(i; j ) = i + j; 2 ( When Consider trunated system. It funtions in the same way as an input system but has the limitation on maximum number of retrials. This means that inoming alls are lost when all servers are busy and there are M soures of repeated alls already. Formally the system is desribed by the Markov hain X (t; M ) = (C (t; M ); N (t; M )), 214 where C (t; M ) 2 f0; 1; : : : ; g, N (t; M ) 2 f0; 1; : : : ; M g with innitesimal harateris(M ) tis a(i;j )(i ;j ) ; (i; j ); (i0 ; j 0 ) 2 S (X; M ) = f0; 1; : : : ; g f0; 1; : : : ; M g: 0 1) if 0 i = f0; 1; : : : ; 1g; j = f0; 1; : : : ; M g, then 8 ; > > > > > > <j; (i0; j 0) = (i + 1; j ); (i0; j 0) = (i + 1; j 1); aM (i0; j 0) = (i 1; j ); i;j i ;j = >ij ; > > > [ + j + ij ; (i0; j 0) = (i; j ); > > :0; otherwise. 2) if i = ; j = f0; 1; : : : ; M 1g, then 8 > ; (i0; j 0) = (; j + 1); > > > <j ; ( i0 ; j 0 ) = ( 1; j ); M a ;j i ;j = > [ + j ℄; (i0; j 0) = (; j ); > > > :0; otherwise. 3) if i = ; j = M , then 8 > M ; (i0 ; j 0 ) = ( 1; M ); < 0 0 aM ;M i ;j = > M ; (i ; j ) = (; M ); :0; otherwise. The state spae S (X; M ) of proess X (t; M ) is nite thus the stationary mode always exists and by ij (M ); (i; j ) 2 S (X; M ) we dene its stationary probabilities. ( ) ( )( 0 0 ) ( ) ( )( 0 ( ( 0 ) ) )( 0 0 ) Let us onsider the servie proess of the trunated system in more detail. 3. STATIONARY PROBABILITIES OF THE TRUNCATED SYSTEM For the given system stationary probabilities satisfy the following set of Kolmogorov equations and normalizing ondition: [ + j + ij ℄ij (M ) = (j + 1)i j 1 +1 (M ) + i j (M ) + (i + 1)j i j (M ); (1) 1 +1 j = 0; : : : ; M 1; i = 0; :::; 1; [ + M + iM ℄iM (M ) = i M (M ) + (i + 1)M i M (M ); i = 0; :::; 1; [ + j ℄j (M ) = (j + 1) j (M ) + j (M ) + j (M ); j = 0; : : : ; M M M (M ) = M (M ) + M (M ); 1 +1 1 +1 1 1 X M X i=0 j =0 ij (M ) = 1: 215 1 1 (2) 1; (3) Consider the following denitions: ei (n) = (Æi ; Æi ; : : : ; Æin )T ; Æij = 0 1() - vetor of length 1 i 6= 0; 1. In ase 1 1; i = j ; 0; i 6= j ; that onsists from 1, Aj = kajik ki;k if ( i=0 1 =0 8 > ; k = i 1; > > > < + j + ij ; k = i; ; ajik = > (i + 1)j ; k = i + 1; > > > :0; otherwise; 8 > < + j; k = 0; j ak= j ; k = 1; > :0; otherwise; 0 i= 1 8 > k = 2; < ; j a k = + j + ( 1)j ; k = 1; > :0; otherwise; ( (j + 1); k = i 1; Bj = kbjik ki;k ; bjik = 0; otherwise; if i 6= 0; 1. In ase i = 0,bj k = 0; k = 0; 1; : : : ; 1, and if i = 1 ( j j ; k 6= 2; bj k = j j ; k = 2; ( 1; k = 0; i = 0; C = kik ki;k ; ik = M ai k ; otherwise; ! M Y j = Ai Bi C e (): and if 1 1 =0 0 ( +1) 1 ( +1) [ + ℄ 1 =0 1 1 1 1 0 i=j 1 6= 0 Vetor j is dened orretly by the last equation. As jC j = ( 1) 1 ( 1)M so C 1 always exists. Matries Aj ; j = 0; 1; : : : ; M are not singular beause they satisfy the Adamar olumn ondition ([3℄ p. 406). Probabilities ij (M ); (i; j ) 2 S (X; M ) an be expliitly expressed in terms of the system's parameters. 216 Theorem 1. of equations: Stationary probabilities of the system are dened by the following set j (M ) = j M (M ); j = 0; : : : ; M; 0 j (M ) = (j + 1) 1()T (M ); j = 0; : : : ; M 1; j M +1 0 eT () + M1()T C e () M (M ); M where j (M ) = ( j (M ); j (M ); : : : ; j (M ))T ; M (M ) = 0 1 1 0 1 0 1 (M ) T () + M1()T X e j M (M ) = 1 + 1()T j + M : M j 1 1 0 =0 It should be notied that in ase of = 1; 2 the above formulas turn into equations of the salar type [4℄. Next we will show that the system with trunated state spae approximates the input system. 4. APPROXIMATION RESEARCH To proof that harateristis of the nite system approximate harateristis of the input system let us use stohasti order onept [5℄. If onditions of lemma 1 are true and : 1) if X (0; M ) st X (0), then X (t; M ) st X (t) for all t 0 and X (M ) st X , where X = (C; N ), X (M ) = (C (M ); N (M )) random vetors distributed as ij ; (i; j ) 2 S (X ) and ij (M ); (i; j ) 2 S (X; M ) orrespondingly; 2) if X (0; M ) st X (0; M + 1), then X (t; M ) st X (t; M + 1) for all t 0 and X (M ) st X (M + 1). Lemma 2 appears from the results of stohasti order of migration proesses. It leades to the following theorem. Theorem 2. If onditions of lemma 1 take plae, then for any (i; j ) 2 S (X ) ij = Lemma 2. lim ij (M ): M !1 We have already shown that the probabilities ij (M ) tend to ij as the value of M inreases. It is interesting to nd the value of dierene between them. Let us examine it for some pretty general types of poliies. If onditions of lemma 1 take plae and the sequene j is stritly monotone, then for (i; j ) 2 f1; : : : ; g f0; 1; : : :g Theorem 3. M M ( ) 1 0 ij ij (M ) (j j ) P M ! 1 1 =0 217 M Q =0 + + ! ( ) [ + ℄ 1 Q 1 =0 + ; where ij = P i; j i; N (M ) j ). Theorem 4. then ( = P (C i; N j ), ij (M ) = P (M ) = P (C (M ) i; j If onditions of lemma 1 take plae and j sup (ij ij (M )) i;j )2S (X ) j ; j = 0; 1; : : :, < +1 [(+)+(M +)0 ℄ M +1 ( ) M !0 ( 0 ) M P =0 ( ) [ + 1 ! M Q 0 + =0 ; 1 + ℄ + =0 Q In monograph of Failn and Tempelton the dierenes between some major integral funtionals of the input and the trunated system were estimated in ase of unontrolled retrial queues [5℄. In ase of ontrolled retrial queues similar results an be found but suh an estimate strongly relates on the ontrol poliy properties. We have provided suh estimates for few of them. REFERENCES 1. Artalejo J. R., Gomez-Corral A. Retrial queueing systems // Springer-Verlag, Berlin, 2008. 2. Semenova O. V., Dudin A. N. M/M/N queueing system with ontrolled servie mode and disaster // Avtomatika i Vyhislitel'naya Tekhnika. 2007. No. 6. P. 72 80. 3. Gantmaher F. R. Matrix theory //Nauka, Mosow, 1967. 4. Lebedev E. O., Ponomarov V. D. Optimization of nitesoure retrial queues // Bulletin of Kiev University. 2008. V. 2. P. 9197. 5. Falin G. I., Templeton J. G. C. Retrial Queues // Chapman and Hall, London, 1997. 218

© Copyright 2021 DropDoc