Discrete Time Geo/Geo/1 Retrial G – Queue with Server Break Down and Repair

Discrete Time Geo/Geo/1 Retrial G – Queue with Server Break Down and Repair

1. zhagappan, St.Annes college of Engg. & Tech. A.Sridevi, Theivanai Ammal College for Wemen

   T. Deepa, Theivanai Ammal College for Wemen

   AbstractThis paper deals with discrete-time Geo/Geo/1 retrial queue with negative customers where the server is subject to breakdown and repair due to the negative arrivals. If the server is idle, negative customer break the server down, if the server is busy, it kill a customer in service and break the server down and if the server is under repair, it has no effect. If the server is breakdown, it is sent to repair immediately and after repair it is as good as new. We analyze the Markov chain underlying the queueing system and obtain its ergodicity condition.

   Keywordsretrial queue; negative customer; break down and repair.

   1. INTRODUCTION

      G-networks were first introduced by Gelenbe in 1989 (see [1]) with a view to modelling neural networks and they are characterized by the following feature: in contrast with the normal positive customers, negative customers arriving to a non-empty queue remove an amount of work from the queue. The G-networks systems have a rich and wide range of real applications in areas such as computers, communications and manufacturing.

      In the retrial queueing literature, Artalejo and G´omez- Corral[27] have investigated single server queues operating under the simultaneous presence of negative arrivals and repeated attempts. However, these works focus on the continuous cases. It is well known that in the field of telecommunications modern systems are more digital than analogue, hence the studies of the modern communication systems are based more on discrete-time analysis. But, as far as we know, there are no results for the discrete retrial G- queueing systems although the analysis of discrete-time retrial queueing models has received considerable attention in the literature.

      The present paper studies a discrete-time single-server retrial queue with both positive and negative customers. An example of a queueing system with both positive and negative flows of arrivals is computer networks with virus infection. When there are no viruses, computer networks have been modeled and analyzed using conventional queueing networks with or without retrials. The customers represent the execution of algorithmic and logic operations, and the nodes represent CPUs, I/O devices, etc. When a virus enters a node, one or more files may be infected, and the system manager may have to go through a number of backups to recover the infected files. In some cases, they may not be recoverable. A virus may originate from outside the network, e.g., through a floppy disk,

      or may come from another node in the network, e.g., by an electronic mail. The recovery time of the infected files can be regarded as repair time of the server (node) due to an arrival of negative customer (virus).

   2. MODEL DESCRIPTION

      The time axis is divided into a sequence of equal subintervals (called slot or epoch) and the ends of the subinterval be marked by 0, 1,, m. It is assumed that all queueing activities (arrivals, departures, retrials, breakdowns and repairs) occur at the slot boundaries. Different from continuous-time queues, the probability of an arrival and a departure and other queueing activities occurring concurrently may be not zero in discrete-time queues anymore. So it is necessary to specify the order in which the arrivals and departures take place in case of simultaneity. For mathematical clarity, we assume that the departures and the end of the repairs occur in the interval (m,m), and the arrivals, the retrials and the beginning of the repairs occur in the interval (m,m+); that is, the arrivals, the retrials and the beginning of the repairs occur at the moment immediately after the slot boundaries and the departures and the end of the repairs occurs at the moment immediately before the slot boundaries. In the literature it is called early arrival system (EAS).

      New customers arrive from outside the system according to a geometric arrival process with rate p. The arriving customers have two types: positive customers (with probability q+) and negative customer (with probability q).

      Positive customer (external or repeated) receives the service immediately when the server is found free. If the server is found busy or down, the customer must join the orbit and return after random amount of time (in slots). Each customer in the orbit generates independently a Bernoulli stream with rate r = 1 r, where r is the probability that a repeated customer does not make a retrial in a slot.

      The arrival of a negative customer causes one positive customer to be killed if any is present, and simultaneously breaks the server down. The failed server is sent to repair immediately and after repair it is assumed as good as new. The negative customer also causes the server breakdown if the server is found idle, but has no effect on the system if the server is under repair.

      The repair times are independent and geometrically distributed with parameter = 1, where is the probability that the repair process does not complete in a slot. The service times are independent and geometrically distributed with probability s = 1s, where s is the probability that a customer does not conclude his service in a slot. After service completion, the customer leaves the system immediately forever. Finally, various stochastic processes involved in the system are assumed to be independent of each other. To avoid trivial cases, we suppose 0 < p < 1, 0 r < 1, 0 q+ 1 and 0 < s 1.

   3. The Markov Chain

At time m+, the system can be described by the process Ym

= (Cm , Nm), where Cm denotes the state of the server (0, 1 or 2 according to whether the server is free, busy or down) and Nm, the number of repeated customers in the retrial orbit. It can be shown that {Ym , m N} is the Markov chain of our queueing system, whose state space is = {(i, k) : i = 0, 1, 2; k 0}. Let

0,k = lim m P[Cm = 0, Nm = k], k 0, 1,k = lim m P[Cm = 1, Nm = k], k 0, 2,k = lim m P[Cm = 2, Nm = k], k 0,

be the stationary distributions of the Markov chain {Ym,m

N}. Our object is to find the stationary distributions.

By routine method, the Kolmogorov equations for the stationary distribution of our system

0,k = (1-p)rk0,k + (1-p)(1-s)rk1,k + (1-p)(1-)rk2,k (3.1) 1,k = pq+0,k + ((1-p)s + pq+(1-s))1,k + pq+(1-)2,k

+ (1-p)(1 rk+1)0,k+1+ (1-p)(1-s)(1 rk+1)1,k+1

+ (1- p)(1-)(1 rk+1)2,k+1 + (1 0,k)pq+s1,k1,

(3.2)

2,k = pq0,k + pq1,k + ((1-p) + pq)2,k +(1 0,k)pq+2,k1,

1(z) = pq+0(z) + ((1-p)s + pq+(1-s))1(z) + pq+(1-)2(z)

+ (1-p)/z 0(z) (1-p)/z 0(rz)+ (1-p)(1-s)/z 1(z)

(1-p)(1-s)/z 1(rz) + (1-p)(1-)/z 2(z)

(1-p)(1-)/z 2(rz) + pq+sz1(z), (3.5)

2(z) = pq0(z) + pq1(z) + ((1-p) + pq)2(z)

+pq+z2(z). (3.6)

By substituting (3.4) into (3.5) we obtain

1(z) = (pq++ (1- p)/z)0(z)

+ ((1-p)s + pq+(1-s) + (1- p)(1-s)/z + pq+sz)1(z)

+ (pq+(1-) + (1-p)(1-)/z)2(z) 1/z 0(z) (3.7)

Solving the system (3.6) and (3.7), and after simplifying the expressions we find the following generating function:

1(z) = {[(1 z)pq+(pq+z + (1-p)(1-) + p)]0(z)}/(z)

(3.8)

2(z) = {[(1 z)pq(pq+sz + (1-p)(1-s) + p)]0(z)}/(z)

(3.9)

where

(z) pq(pq+(1-)z + (1-p)(1-) ((1-p)sz + pq+(1-s)z

<>+ pq+sz2 +(1- p)(1-s) z)((1-p) + pq + pq+z 1).

Lemma 1.

1. The inequality (z) > 0 holds for 0 z < 1 if and only if pq+/[(1-s) + spq]< 1 pq/[(1-) + pq-];

2. Under the above condition there exists

Lim (1 z)/(z)=1/[(pq + (1-p)(1-s) pq+s)((1-p)(1-) + z1 pq+(1-)) pq+pq].

Using the previous lemma, the auxiliary generating functions

(z), (z) are defined for 0 z < 1, and in z = 1 are

1 2

(3.3)

where i,j denotes Kroneckers delta. The normalization condition is given by

extended by continuity if and only if pq+/[(1-s) + spq]< 1 pq/[(1-) + pq-]

k 0

0,k

k 0

1,k

k 0

2,k 1

From equation (3.8) and (3.9), we can get

(1) = [pq+((1-) + pq) (1)]/[(pq + (1-p)(1-s)

1

In order to solve Eqs.(3.1)(3.3), we introduce the following generating functions: ,

0

pq+s)((1-p)(1-) + pq+(1-)) pq+pq-]

2(1) = [pq((1-s) + spq) 0(1)]/[(pq + (1-p)(1-s)

k

k

pq+s)((1-p)(1-) + pq+(1-)) pq+pq-]

2

2

k k

k k

0 z 0,k z , 1 z 1,k z , z

2,k z

k 0

k 0

k 0

The normalization condition 0(1) + 1(1) + 2(1) = 1 gives

0(1) = 1pq+/[(1-s) + spq] pq/[(1-) + pq],

Multiplying Eqs.(3.1)(3.3) by zk and summing over k, we get

0(z) = (1-p)0(rz) + (1-p)(1-s)1(rz) + (1-p)(1-)2(rz),

(3.4)

1(1) = pq+/[(1-s) + spq],

2(1) = pq/[(1-) + pq]

Substituting eqns. (3.8) and (3.9) into (3.4) leads to

0(z) = G(rz) 0(rz), (3.10)

where

G(z) =(1-p)(1 z)/(z) × [pq+spq+z2 + pq+((1-p)(1-s) pq

pq+(1-s))z+ pq+s((1-p)(1-) pq+ pq+(1-))z

+ (pq(1-p)(1-) + (1-p)(1-s)(1-p)(1-) + (1-p)(1-s)pq+

+ 2(1-p)(1-s)(1-) + (1-s)p + (1-p)s)]

1. The probability generation function of the number of customers, N, in the orbit is

   (z) = 0(z) + 1(z) + 2(z)

   =1/(z) × {pq+spq+z2 +pq+((1-p)(1-s) p)z

   + pq+s((1-p)(1-) p)z+ (pp + p(1-p)(1-)

   + p(1-p)(1-s) + (1-p)(1-s)(1-p)(1-))].

2. The probability generation function of the number of customers, L, in the system is

   z 0

   Grn z

   (3.11)

   0 0

   n1

   Lemma 2. If pq+/[(1-s) + spq]< 1 pq/[(1-) + pq-], then

   (z) = 0(z) + z 1(z) + 2(z)

   =1/(z)×{pq+s(pq+pq)z2

   +pq+((1-p)(1-s)p)z

   + pq+s((1-p)(1-) pq+)z

   the infinite product Grn z

   n1

   is convergent.

   + pq((1-p)(1-s) + p)z + (pq(1-p)(1-)

   + (1-p)(1-s)(1-p)(1-) + (1-p)(1-s)pq+)}.

   Theorem 3. If pq+/[(1-s) + spq]< 1 pq/[(1-) + pq-] holds, then the stationary distribution of the Markov chain

   Ym = (Cm,Nm) has the following generation functions:

   1. The marginal generating function of the number in the orbit when the server is idle is

      0(z) = {1pq+/[(1-s) + spq] pq/[(1-) + pq]}

      Gr n z/ Gr n

      REFERENCES

      1. Gelenbe, E. Random neural networks with negative and positive signals and product form solution. Neural Comput., 1: 502510 (1989)

      2. Artalejo, J.R., G´omez-Corral, A. Stochastic analysis of the departure and quasi-input processes in a versatile Single server queue. Journal of Applied Mathematics and Stochastic Analysis, 9: 171183 (1996)

      3. Artalejo, J.R., G´omez-Corral, A. Generalized birth and death processes with applications to queues with repeated attempts and negative arrivals.

         n1

         .

         n1

         OR Spektrum, 20: 514 (1998)

      4. Artalejo, J.R., G´omez-Corral, A. Analysis of a stochastic clearing

   2. The marginal generating function of the number in the orbit when the server is busy is

      1(z) = {(1 z)pq+(pq+z (1-)(1-p) + p)

      0(z)}/(z)

   3. The marginal generating function of the number in the orbit when the server is down is

2(z) = {(1 z)pq(pq+sz + (1-p)(1-s) + p)

0(z)}/(z)

system with repeated attempts. Stochastic Models, 14: 623645 (1998)

1. Artalejo, J.R., G´omez-Corral, A. On a singal server queue with negative arrivals and request repated. Journal of Applied Probability, 36(3): 907 918 (1999)

2. Artalejo, J.R., G´omez-Corral, A. Performance analysis of a single- server queue with repeated attempts. Mathematical and Computer Modelling, 30: 7988 (1999)

3. Artalejo, J.R., G´omez-Corral, A. Computation of the limiting distribution in queueing systems with repeated attempts and disasters. RAIRO Operations Research, 33: 371382 (1999)