Tandem Queueing System with Different Types of Customers (Queueing Theory) (Analytical and Stochastic Modeling) Part 1

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 parametertmp4A2-395_thumbWhen the sojourn time in the state v expires, with probabilitytmp4A2-396_thumbthe process vt jumps into the state v’ without generation of customers,tmp4A2-397_thumband with probabilitytmp4A2-398_thumb the process vt jumps into the state v’ with generation of a customer of type

tmp4A2-403_thumb

The behavior of the MMAP is completely characterized by the matrices

tmp4A2-404_thumb r = 1, 2, and defined by their entries

tmp4A2-405_thumb 

tmp4A2-406_thumb

The matrixtmp4A2-407_thumbis the generator of the processtmp4A2-408_thumbThe fundamental arrival rate A is defined by

tmp4A2-411_thumb

where 9 is the row vector of a stationary probabilities of the Markov chain tmp4A2-412_thumbThe vector 9 is the unique solution to the system

tmp4A2-414_thumb

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 ratetmp4A2-415_thumbof the type r customers, is defined bytmp4A2-416_thumb

The coefficient of variationtmp4A2-417_thumbof inter-arrival times for the type r customers is given by

tmp4A2-421_thumb

The coefficient of correlationtmp4A2-422_thumbof two successive intervals between type r customers arrival is computed by

The coefficient of variation,tmp4A2-425_thumbof intervals between successive arrivals is defined bytmp4A2-426_thumbThe coefficient of correlation ccor of the successive intervals between arrivals is given by

tmp4A2-429_thumb

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 chaintmp4A2-430_thumbwhere 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,

tmp4A2-433_thumb

Let us enumerate the states of the Markov chaintmp4A2-434_thumbin lexicographic order.

The structure of the system

Fig. 1. The structure of the system

The matricestmp4A2-435_thumbcontain 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 chaintmp4A2-436_thumbhas the following block structure:

tmp4A2-441_thumb

where

tmp4A2-442_thumb

and the matrices

tmp4A2-443_thumb

are represented in the block form

tmp4A2-444_thumb

where the non-zero blocks tmp4A2-445_thumb are defined as follows:

tmp4A2-446_thumbtmp4A2-447_thumb

Here & is a symbol of Kronecher’s product of matrices, see, e.g., [1];tmp4A2-448_thumbis equal to 1 if i = N and is equal to 0 otherwise, _tmp4A2-449_thumb 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 chaintmp4A2-450_thumb

Stationary Distribution

Because the four-dimensional Markov chaintmp4A2-451_thumbis an irreducible and regular and has the finite state space, the following limits (stationary probabilities) exist for any set of the system parameters:

tmp4A2-456_thumbtmp4A2-457_thumb

Let us enumerate the probabilities corresponding the value i of the first component in lexicographic order and form from these probabilities the row vectors tmp4A2-458_thumb. These vectors satisfy the following Chapman-Kolmogorov’s equations (equilibrium equations)

tmp4A2-460_thumb

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 vectorstmp4A2-461_thumbare computed by

tmp4A2-463_thumb

where the matrices Fi are computed recurrently:

tmp4A2-465_thumb 

the matrices

tmp4A2-466_thumb

are computed from the backward recursion:

tmp4A2-467_thumb

with the terminal condition

tmp4A2-468_thumb

the vector po is calculated as the unique solution to the following system of linear algebraic equations:

tmp4A2-469_thumb

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 vectorstmp4A2-470_thumbgiven by this theorem well suits for realization on computer.

Performance Measures

Having the stationary distributiontmp4A2-472_thumbcalculated 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

tmp4A2-474_thumb

• Mean number of type 1 customers at Station 1

tmp4A2-475_thumb

• Mean number of type 2 customers at Station 1

tmp4A2-476_thumb

• Probability that a customer of type k will be lost at Station 1

tmp4A2-477_thumb

• Probability that a customer of type k will be successfully served at Station 1

tmp4A2-478_thumb

• The rate of input flow at Station 2 (coincides with the rate of output flow of type 1 customers from Station 1)

tmp4A2-479_thumb

• The rate of output flow from Station 2

tmp4A2-480_thumb

Mean number of busy servers at Station 1

tmp4A2-481_thumb

• Probability that a customer of type 1 will be lost at Station 2

tmp4A2-482_thumb

• Probability that a customer of type 1 will be successfully served at both stations

tmp4A2-483_thumb

Next post:

Previous post: