Stability of a Queuing System

= Stability of a Queuing Syst= em

This is a chapter from the dissertation: Z.I. Fl= ikop “Structural Optimization of Operational Management System”, Kie= v Poly= technic Institute, Kiev, 197= 3. (In Russian). =

In any queuing system we can define a probability= that customers r= equiring type k service are simultaneous= ly servicing by the system. We also can consider an expected value that _{<=
!--[if gte vml 1]>} customers a= re in the system simultaneously. It is obvious, that different queuing systems ha= ve different acceptable values of and, and, in course of functioning, and can exceed = those values. This can be as a result, for example, changes in intensity of input customer traffic, productivity of servicing elements, queuing system configuration, and so on.

We should find a way to evaluate an effect of those changes on a queuing system performance. We can evaluate this system from point of view of its stabilit= y in average and its stochastic stability.

Let’s start our analysis from studying queuing system stability in average. If considered system allows that

for all k,= = &nb= sp; = &nb= sp; (1)

Then we can define a vector

= &nb= sp; = &nb= sp; = &nb= sp; (2)

And a set values of <= sub> such <= /o:p>

, = &nb= sp; = (3)

where is a maximu= m average accepted value of number of customers of type k that are servicing by system simultaneously.

In corresponding with [1, 2, 3] we will consider that after initial stabilizat= ion at time:

1) queuing system is stable in average on interval = , if

= for = &nb= sp; = &nb= sp; = (4)

2) queuing system is stable in average on interval = in relation= to k type of customers, if

for = = &nb= sp; = &nb= sp; = (5)

We use time interval, because queuing system properties are chancing with time. = &nb= sp; = &nb= sp; =

Condition (1) is satisfied when load of each ser= ver in the system is below one. However, in practice, we need satisfaction conditi= ons (4) or (5) to be able to provide same excesses of system stability. This is needed to compensate for fluctuations in the input traffic intensity, and variations in the system configuration and the serving elements performance= .

We can consider a queuing system that provides s= ervice to a pool of customers. This pool can contain as limited as unlimited numbe= r of customers. In case when pool is limited, number of customers in the pool depends on how many of them are in the servicing system, (customers after service are returning to the pool), i.e. intensity of customers input traff= ic varies and depends on number of customers that are in the pool. =

To evaluate to what limit intensity of input tra= ffic can be increased and conditions (4, 5) still be satisfied we can define inp= ut traffic as follows:

. = &nb= sp; = &nb= sp; = (6)

Where - is intens= ity of a customer traffic interring a system; - is intens= ity of customer traffic, requiring k-th type of service; - number of customers generating request for k-= th type of services; - intensity= of requests for k-th type of service from each customer requesting this kind of service.

Proposed in [4] queuing system model allows defi= ne when conditions (4, 5) continue be satisfied upon changes in number of customers and variations in theirs requests for different kind of service.<= span style=3D'mso-spacerun:yes'> It also allows evaluate how failur= e of different serving links (serving elements) affects satisfaction of (4, 5). =

However, stability in average does not define in= full performance of a queuing system. Since number of customers in service is random, it is possible that at some moments of time (t) can exceed a predefined threshold with probab= ility.

We can define a condition of a queuing system at moment t as d-mention vector

= = &nb= sp; = (7)

Let’s also define as a set of system states z= (t) on interval

= &nb= sp; (8)

and for all k.

When system is stable in average on interval, we can use definition (3)

In the following analysis we will consider an op= en (with unlimited number of customers) queuing system. After initial stabilization this system is equifinal [5] and if for it

then does not depend on .

In analogy with [2] let use the following defini= tions:

1. Queuing system is stochastically stable in relationship to the triad on interval= if from a fact th= at its parameters provide the followi= ng is correct:

for all = = &nb= sp; = &nb= sp; (10)<= /p>

2. Queuing system is stochastically stable in relationship to the triad on interval= if from a fact th= at its parameters provide the followi= ng is correct:

for = &nb= sp; = &nb= sp; (11) = &nb= sp; =

In first case queuing system is stochastically s= table as a whole; in second case it is only partially stochastically stable and o= nly to some types of customers.

Let’s consider second case. Values of and usually are defined by a system designer. However, it will be desirable to define value= of depending on behavior of. Since process of queuing system state changes is differ= ent for different systems, it is difficult to propose a general approach of defining. However, if input and output flows of k-th customers can be consider Pois= son and queuing system as open, then by using and , value of = can be defi= ned via Martingale theory [6]. =

In corresponding with this theory a stochastic p= rocess is martingale if at moments of system state changes increments are the same= and probabilities of such changes are equal. In case of considered now queuing system upon it will pro= vide a condition:

= &nb= sp; = = &nb= sp; = &nb= sp;(12)

We also should mention that process is continui= ng to the right for t and, as a resul= t, is separable. Now, if } is a separable martingale, then, in general [8]:

= &nb= sp; = = &nb= sp; (13)

By using (13) and known , we can approximately define value of . To satisfy condition (11) we have to provide . As a resu= lt

= &nb= sp; = = &nb= sp; = (14)

If condition is satisfie= d for all k, then= , and with probab= ility

= &nb= sp; = = &nb= sp; (15)

Equation (15) defines = system stochastic stability as a whole.

References

1. B.M. Domrachev. R= 20;Komplex technicheskix sredtsv ACYP i voprosi ystoichivistyego = funksionirovaniay”. In publication Voprosi ustoichivosty texnicheskogo i informachionnogo obespechenia ACYP. Novo= sibirsk, 1970 (In Russian).

2. B.B. Kalashnikov. “O = ponyatii ystoichivosty funkchioniro= vania sloznix system”. In the seminar proceedings Bolshie informatchionno-= upravlauchie systemi. 1969. (In Russian).

3. B.A. Gridenko. ̶= 0;Ustoichivost funkchionirovania KTC I optimizatchia sistemi” In publication Voprosi ystoichivosti texticheskogo i informatchionnogo obespechenia ACYP. Novo= sibirsk, 1970. (In Russian).

4. Z.I. Flikop. “Optimiz= atcia raspredelenia potokov zadach v ierarchitcheskix= systemax operativnogo upravlenia. In publication Matematicheskie metodi issledovania i optimixatcii system. Cybernetic Scientific Board = of Ukrainian Academy of Science, 1971.

(In Russian).<= span style=3D'font-size:14.0pt'>

Reprinted in English: Z. Fli= kop. “Routing optimization= in packet switching communication networks”. European Journal of Operational Re= search 19 (1985) pp. 262-267. This paper is on this web site: http://www.zftech.net/id20.html

5. A. Rapoport. Matematicheskie aspekti <= span class=3DSpellE>abstraktnogo analiza syst= em. Issledovania po obschei teorii system. &#= 8220; Progress”, M.,1969 (In Russi= an)

6. D.L. Dub. Veroiatnostnie processi. Pub= lisher of a Foreign Literature. M.,1956. (In Russia= n).