# Analysis of the queueing network with a random bounded waiting time of positive and negative customers at a non-stationary regime

### Mikhail Matalytski

,### Victor Naumenko

Journal of Applied Mathematics and Computational Mechanics |
Download Full Text |

ANALYSIS OF THE QUEUEING NETWORK WITH A RANDOM BOUNDED WAITING TIME OF POSITIVE AND NEGATIVE CUSTOMERS AT A NON-STATIONARY REGIME

Mikhail Matalytski^{ 1}, Victor Naumenko^{ }^{2}

^{1} Institute of Mathematics, Czestochowa University of Technology

Częstochowa, Poland

^{2} Faculty of Mathematics and Computer
Science, Grodno State University

Grodno, Belarus

m.matalytski@gmail.com, victornn86@gmail.com

Received: 14 October 2016; accepted:
17 November 2016

**Abstract****.**
In the first part of the article, an investigation of an open Markov queueing
network with positive and negative customers (G-networks) has been carried out.
The network receives two exponential arrivals of
positive and negative customers. Negative customers do not receive service. The
waiting time of customers of both types in each system is bounded by a random
variable having an exponential distribution with different parameters. When the
waiting time of a negative customer in the queue is over it reduces the number
of positive customers per unit if the system has positive customers. The
Kolmogorov system of difference-differential equations for non-stationary state
probabilities has been derived. The method for finding state probabilities of an
investigated network, based on the use of apparatus of multidimensional
generating functions has been proposed. Expressions for finding the mean
number of positive and negative customers in the network systems have also been found. In the second part the same network has been investigated, but with
revenues. The case when revenues from the network transitions between states
are random variables with given mean values has been considered. A method for
finding expected revenues of the network systems has been proposed. Obtained
results may be used for modeling
of computer viruses in information systems and networks and also for
forecasting of costs, considering the viruses
penetration.

*MSC 2010:** 49K45, 60K20*

*Keywords**: **G-network, positive** and negative customers, random bounded waiting time
of customers, non-stationary regime, generation function, non-stationary state
probabilities, expected revenues*

1. Introduction

Queueing Networks (QN) with negative customers and other features cause a special interest of researchers. Negative customers differ from ordinary customers in that they require no service and have an impact on the state of the queueing system (QS). They reduce a queue of ordinary customers of a nonempty QS per [1].

In the present article, we consider an open QN, in which two simple streams of positive and negative customers arrive. Services require only positive customers. The waiting time in the queue for positive and negative customers is bounded by the random variables having an exponential distribution with different parameters. A negative customer, by the end of waiting time, reduces the count of positive customers in the system by unity, if there is such a system.

This assumption can find its application in modeling the behavior of information systems and networks. When transferring a query (positive requests) there is often a break or pause established, after which it means that the transfer request does not fit in the planned time interval, after which the request is removed from the queue. Negative customers in the model can describe the viruses in the system, which start acting through a random time and destroy positive customers in the system.

Recently, attention has been paid to the study of Markov chains with revenues (HM-networks), and various features, for example with a bounded waiting time of customers [2], or positive and negative customers [3]. This article discusses a few more of these features. Namely, the presence in a Markov network with revenues of negative customers and a bounded waiting time of positive and negative customers in network systems.

In other words, we investigate the synthesis of QN-HM-networks [4] with positive and negative customers. While waiting time of such customers in each system are bounded by the random variables. We consider the case when the revenue from the network transitions between states are random variables with given mean values.

2. Network description. Problem formulation

Consider an open G-network [1] with single-queues QS. An independent Poisson flow of positive customers with
rate and a Poisson flow of negative customers with rate arrive to QS from
outside (system ), All
customer flows arriving to QS are assumed to be independent. A positive
customer arriving to the system increases the count of customers in the system
by unity and requires service. Requests are serviced in the order received.
Service times of
customers in the *i*-th QS independent, not dependent on the receipt of
the processes and for positive
customers have an exponential distribution with rate where *k _{i}*-count
of positive customers in the

*i*-th QS Each positive customer, located in the system, has a waiting time bounded exponentially distributed random variable with rate for and it does not depend on other factors for example waiting time of other customers in the queue,

A negative customer, arriving to QS,
increases the length of the queue of negative customers for one, and requires
no service. Each negative customer, located
in *i*-th QS, stays in the queue for a random time according to a Poisson
process of rate for where
*l _{i}*-count of
negative customers in

*i*-th QS, By the end of this time, the negative customer destroys one positive customer in the QS and leaves the network. If after this random time in the system there are no positive customers, then a given negative customer leaves the network, without exerting any influence on the operation of the network as a whole. Wherein the probability that in QS a negative customer leaves the queue during on the condition that, in this QS at time there are negative customers, equals

If at time positive
customer is located on servicing in the *i*-th system, then on interval it will finish service with probability
If on interval the waiting time of customer
in the queue of *i*-th QS is up, then it leaves the queue with probability

The positive customer gets serviced in with probability move to QS as a positive customer and with probability - as a negative customer and with probability come out of the network to the external environ- ment,

A positive customer, waiting time of which in
the queue of *i*-th QS has expired, move to *j*-th system with probability
as a positive customers, and with
probabil-
ity as a negative customer, and with a
probability leave the network.

The network state at time described by the vector which forms a homogeneous Markov process with a countable count of states, where the state means that at time in QS there are positive customers and negative customers,

In the first part of the article we shall find probabilities of the network states, and the mean number of customers in the systems at the transient regime.

3. The system of the Kolmogorov difference-differential equations for the network state probabilities

We introduce some notations. Let - vector, which is *i*-th component equal to 1, all the others are 0, - state probability at moment time - Heaviside function, .

The possible transitions of our Markov process in the state during time

– from the state in this case into QS for the time a positive customer will arrive with probability

– from
the state while to the *i*-th QS for the
time a negative customer will arrive with
probability

– from
the state in this case the positive customer
after servicing or at the end of waiting time (timeout) in the *i*-th QS,
comes out of the network to the external environment with probability

– from
the state in the given case into* i*-th QS
after timeout
of negative customer it destroys in the QS the positive customer, the
probability of such an event is equal to

– from
the state while in the *i*-th QS the
residence time in the queue of the negative customer finished, if in time there were negative
customers and there were no positive customers; the probability of such
an event is equal to ,

– from
the state in a given case after finishing the
service
or timeout of the positive customer in the *i*-th QS it moves to
the *j*-th QS again as a positive
customer with probability

– from the state in this case after finishing the service
or timeout of the positive customer, in *i*-th QS it moves to the *j*-th
QS as
a negative customer; the probability of such an event is equal to

– from
the state while in each *i*-th QS, no positive nor any negative customers
arrive, and in which for the time no customer not have
been serviced, no negative customer will come out of the queue; the probability
of such event is equal to

– from other states with probability .

We will assume that the service and waiting
time of positive customers in the
*i*-th QS has an exponential distribution with the rate and respectively, but the waiting time of negative customers in the *i*-th QS -
an exponential distribution with the rate Consequently, in this case Then, using the formula of
total probability, we can
obtain, as previously for other networks [3], in this case the system of
difference-differential equations for the non-stationary state probabilities of
the considered network:

(1)

.

4. Finding the state probabilities and the mean number of customers in the queueing system

Denote by** ** where the generating function of the dimension of

(2) |

the summation is taking for each from 0 to We will assume that

Multiplying each of the equations (1) to and summing up all possible values and from 1 to Here the summation for all and is taken from 1 to i. e. all summands in (1), for which in the network state there are components and due to the assumptions put forward above. Because, for example Then we obtain

(3) |

Using (3), we can show that for a multidimensional generating function there is a valid homogeneous linear differential equation, the general solution having the form

Let’s consider, that at the initial moment of time, the network is in a state

Then the initial condition for the last equation will be

from which we obtain

**Theorem****.** *If at the initial moment of time the QN is in a state then
the expression for the generating function taking
into account the expansions appearing in it exponent Maclaurin, has
the form*

(4) |

*where*

The theorem is proved similarly as, for example, in the works [3, 4].

With the obtained
expression for the generating function can be found
state probabilities of the considered network. State probability of * *is the coefficient at in
the expansion of (2) in multiple series (4), on condition, that at the initial
time
the network is in a state

**Remark.** *If the waiting time of positive customers not to bound by a random variable, then we
obtain results similar to those that is in the work [3].*

The mean number of the customers in the
network systems can be found, differentiating (4) by and
suppose Therefore for the mean number of
positive customers in the network system at time *t *in the QS with
the number *x *we will use the relation,

(5) |

The change of variables will be done in the expression (5) and considering, all network QS operating under heavy-traffic regime, e.g. and, consequently, therefore obtain for all

.

5. Analysis of the queueing networks with revenues

Let’s find the mean expected revenues, which
make customers of the *i*-th QS
of service in it. We assume, that service and waiting times of positive
customers
in the *i*-th QS has an
exponential distribution with rates and respectively, and waiting times in
the *i*-th QS of negative customers - an exponential distribution with rate In addition also assume, that all systems
operate under heavy-traffic regime, i.e. in this case
In the simulation, the effect of the virus penetration into a computer
network or by a computer attacks on it takes place just such a situation. In
this case the busy
period of QS is infinite and, therefore, the stationary distribution does not
exist,
the load factor of QS exceeds unity. However, it should be noted that in these
conditions various real objects may operate on most time intervals.

Consider
the dynamics of revenue changes of the *i*-th QS, Let at the ini-
tial moment of time the income of this QS be equal to We are inter-
ested in income at time *t*. The income
of its QS at moment time can be represented
in the form

(6) |

where - revenue changes of
the *i*-th system at the time interval To find the revenues of the *i*-th
QS we write the conditional probabilities of the events that may occur during The
following cases are possible:

– with
probability to the *i-*th QS from the external
environment
a positive customer will arrive, which will bring a revenue in the amount of where - random variable (RV)
with expectation (*E*) of which equals

– with
probability to the *i-*th QS from the external
environment
a negative customer will arrive, revenue change of
the system in this case does not occur;

– with probability a positive customer after servicing
or at the end of waiting time (timeout) in the *i*-th QS, comes out
of the network to the external environment, while a revenue of the *i*-th
QS decreases by
an amount where - RV with

– with
probability to the *i*-th QS after timeout of
negative customer it destroys the positive customer in the QS and leaves the
network,
in this case a revenue of the *i*-th QS decreases by an amount where

– after
finishing the service or timeout of the positive customer in the *i*-th QS
it moves to the *j*-th QS again as a positive customer with probability by
such a transition a revenue of the *i*-th QS decreases by an amount and revenue of the *j*-th QS will
increase by this amount, where

– if
in the *j*-th QS there is a positive customer, service time or waiting
which
ended, then after the termination of it service in the *j*-th
QS it moves to the* i-*th QS again as a positive customer with probability while a revenue of the *i*-th QS decreases by an amount and revenue of
the *j*-th QS will increase by this amount, where

– with probability service time or waiting time of
the positive customer ended in the *i*-th QS and it, after
finishing the service
in the *i*-th QS, moves to the *j*-th QS as a negative customer,
by such a transition a revenue of the
*i*-th QS decreases by an amount and revenue of the *j*-th QS
will not occur, where

– with probability

on the time interval state
changes of the *i*-th system will not happen,
in this case a revenue of the *i*-th system may increase (decrease) by the
value where

Then we get, that revenue changes of the *i*-th
system on the time interval can be written as

(7)

For practical reasons, we may assume that all values are bounded. Then in view of (6) and (7) for the expectation can be written:

,

i.e. where

We introduce the notation From (6) we have from where, by going to the limit and setting the initial conditions we can find the expected revenues of the network systems. This implies, that expected revenues are linear functions of time:

6. Conclusions

In the paper, the Markov G-network with a random bounded waiting time of positive and negative customers at a transient regime has been investigated. For such a network that operates under heavy-traffic regime, non-stationary state probabilities and relations for the mean number of customers with the help of the apparatus of multivariate generating functions has been founded. And a similar network with revenues has been considered. The expressions for the expected revenues of the network systems has been obtained.

Further investigations in this direction will be associated with obtaining similar results, taking into account falling into the signals (triggers) to the queueing network.

References

[1] Gelenbe E., Product form queueing networks with negative and positive customers, Journal of Applied Probability 1991, 28, 656-663.

[2] Matalytski M., Statkevich S., Stochastic Network with Bounded Waiting Time of Requests and Unreliable Service, GrSU, Grodno 2014.

[3] Matalytski M., Naumenko V., Stochastic Networks with Non-Standard Customers Movement, GrSU, Grodno 2016.

[4] Matalytski M., On some results in analysis and optimization of Markov networks with incomes and their applications, Automation and Remote Control. 2009, 70, 10, 1683-1697.