Abstract
A dual tandem consisting of multi-server queueing systems without buffers is considered. Customers of two types arrive to Station 1 in the MMAP (Marked Markovian Arrival Process). The first type customers aim to be served at Station 1 only while the second type customers should be served at both stations. The stationary distribution of the system states and the main performance measures of the tandem queue under consideration are calculated. Illustrative numerical examples are presented.
Keywords: Tandem queueing model, heterogeneous customers, stationary state distribution, optimization.
Introduction
Consideration of the particular kind of a tandem queueing model in this paper is motivated by its practical importance when the optimal topology, technology, hardware and software of an office local area network with restricted access to an external network (e.g., Internet) should be designed. It is assumed that possibly a part of users (officers) will be granted access to the external network while the rest of users can work only with local resources. Authorized officers intended to start access to the external network should first go through the local recourses to reach the router to the external network. Sometimes, the use of external network is quite expensive. So, important problem is to properly match architecture of the local network to the rate (bandwidth) of access to the external network. The lack of this rate and the absence of control by the access of the users of the local network to the bandwidth can cause congestion in the network. The excessive bandwidth rate and too strict restriction of access of users of the local network to the external network leads to poor utilization of the bandwidth while it can be rather expensive.
The model considered in this paper can be helpful in solution of this problem. Aiming to better accounting the possible activity of both types of customers we assume quite general models of the heterogeneous arrival process and service time distribution.
Literature relating to multi-server tandem queues is not rich. As the recent paper worth to mentioning we can refer to [3].
The rest of the text is organized as follows. In section 2, the mathematical model is described. In section 3, we describe the multi-dimensional Markov chain defining behavior of the queueing model under study and present the generator of this chain. Algorithm for computing the steady state distribution of the system states is presented in section 4. Some important performance measures of the system are given in section 5. Section 6 contains some numerical results and section 7 concludes the paper.
Model Description
We consider a tandem queueing system consisting of two stations in series. Station 1 is represented by the N-server queue without a buffer. The input flow at this station consists of two types of customers which arrive in the correlated flow described as MMAP (Marked Markovian Arrival Process). The first type customers aim to be served at Station 1 only while the second type customers should be served at both stations. Arrival of customers in the MMAP is directed by the underlying random process vt, t > 0. The process vt, t > 0, is an irreducible continuous time Markov chain with state space {0,1, …,W}. The sojourn time of this chain in state v is exponentially distributed with the positive finite parameterWhen the sojourn time in the state v expires, with probabilitythe process vt jumps into the state v’ without generation of customers,and with probability the process vt jumps into the state v’ with generation of a customer of type
The behavior of the MMAP is completely characterized by the matrices
r = 1, 2, and defined by their entries
The matrixis the generator of the processThe fundamental arrival rate A is defined by
where 9 is the row vector of a stationary probabilities of the Markov chain The vector 9 is the unique solution to the system
Here and in the sequel e is the column-vector of appropriate size consisting of 1′s and 0 is the row-vector of appropriate size consisting of zeros.
The arrival rateof the type r customers, is defined by
The coefficient of variationof inter-arrival times for the type r customers is given by
The coefficient of correlationof two successive intervals between type r customers arrival is computed by
The coefficient of variation,of intervals between successive arrivals is defined byThe coefficient of correlation ccor of the successive intervals between arrivals is given by
For more information about the MMAP see, e.g., [2].
Assumption that the arrival process of customers of two types is defined by the MMAP instead of the model with more simple two independent stationary Poisson arrival processes allows to effectively take into account different variance of inter-arrival times and possible correlation of successive inter-arrival times of customers of the same type and cross-correlation between two types.
If an arriving customer of any type sees all servers of Station 1 busy it leaves the system. Otherwise the customer occupies any idle server and its service starts immediately. Service time is assumed to be exponentially distributed with parameter pr depending on the type r of the customer, r = 1, 2. After the service completion, the customer of type 2 leaves the system forever while the customer of type 1 proceeds to Station 2.
Station 2 is represented by R -server queue without a buffer. If a customer proceeding from Station 1 finds an idle server his (her) service is started immediately. In the opposite case this customer is lost. Service time at Station 2 is exponentially distributed with parameter y.
The structure of the system is presented in Figure 1.
Our aim is to calculate the steady state distribution of the system states and the main performance measures of the system. The obtained results are used to solve numerically the problem of optimal choice of the number of servers at Station 1 and Station 2.
Process of the System States
The process of the system states is described in terms of the irreducible multidimensional continuous-time Markov chainwhere it is the number of busy servers at Station 1; rt is the number of busy servers at Station 2, nt is the number of servers of Station 1 performing the service of customers of type 1, vt is the state of the MMAP underlying process at time t,
Let us enumerate the states of the Markov chainin lexicographic order.
Fig. 1. The structure of the system
The matricescontain the transition rates from the states having the value i of the component it to the states having the value l of this component.
Lemma 1. Infinitesimal generator A of the Markov chainhas the following block structure:
where
and the matrices
are represented in the block form
where the non-zero blocks are defined as follows:
Here & is a symbol of Kronecher’s product of matrices, see, e.g., [1];is equal to 1 if i = N and is equal to 0 otherwise, _ 0,…,i} stands for the diagonal matrix defined by the diagonal entries listed in the brackets.
Proof of the lemma is implemented by analyzing the intensities of transition of the multi-dimensional Markov chain
Stationary Distribution
Because the four-dimensional Markov chainis an irreducible and regular and has the finite state space, the following limits (stationary probabilities) exist for any set of the system parameters:
Let us enumerate the probabilities corresponding the value i of the first component in lexicographic order and form from these probabilities the row vectors . These vectors satisfy the following Chapman-Kolmogorov’s equations (equilibrium equations)
The rank of the system is equal to (N + 1)(N + 2)(R + 1)(W + 1)/2) and can be very large. E.g., in case N = 10, R = 2, W =1 the rank is equal to 396, in case N = 20, R = 2, W = 1 it is equal to 2310, in case N = 30, R = 2, W =1 it is equal to 6944 etc. Thus, the direct solution of system (1) can be time and resource consuming.
In the case when at least one of values N, R, W is large, the numerically stable algorithm based on probabilistic meaning of the matrix Q can be applied (see [4]). This algorithm is given by the following assertion.
Theorem 1. The stationary probability vectorsare computed by
where the matrices Fi are computed recurrently:
the matrices
are computed from the backward recursion:
with the terminal condition
the vector po is calculated as the unique solution to the following system of linear algebraic equations:
Note that all inverse matrices in the theorem statement exist and are non-singular because the inverted matrices are all sub-generators.
The straightforward algorithmic way for calculating the stationary probability vectorsgiven by this theorem well suits for realization on computer.
Performance Measures
Having the stationary distributioncalculated we can find a number of stationary performance measures of the system. Below we give formulas for computing some of them.
• Mean number of busy servers at Station 1
• Mean number of type 1 customers at Station 1
• Mean number of type 2 customers at Station 1
• Probability that a customer of type k will be lost at Station 1
• Probability that a customer of type k will be successfully served at Station 1
• The rate of input flow at Station 2 (coincides with the rate of output flow of type 1 customers from Station 1)
• The rate of output flow from Station 2
Mean number of busy servers at Station 1
• Probability that a customer of type 1 will be lost at Station 2
• Probability that a customer of type 1 will be successfully served at both stations