Analysis of the queueing network with a random bounded waiting time of positive and negative customers at a non-stationary regime
Journal of Applied Mathematics and Computational Mechanics
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
2 Faculty of Mathematics and Computer Science, Grodno State University
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
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 .
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 , or positive and negative customers . 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  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  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 ki-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 li-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 , in this case the system of difference-differential equations for the non-stationary state probabilities of the considered network:
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
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
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
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 .
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,
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
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
For practical reasons, we may assume that all values are bounded. Then in view of (6) and (7) for the expectation can be written:
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:
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.
 Gelenbe E., Product form queueing networks with negative and positive customers, Journal of Applied Probability 1991, 28, 656-663.
 Matalytski M., Statkevich S., Stochastic Network with Bounded Waiting Time of Requests and Unreliable Service, GrSU, Grodno 2014.
 Matalytski M., Naumenko V., Stochastic Networks with Non-Standard Customers Movement, GrSU, Grodno 2016.
 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.