Departure Process in Finite-Buffer Queue with Batch Arrivals (Queueing Theory) (Analytical and Stochastic Modeling) Part 1

Abstract

A finite-buffer queueing system with batch Poisson arrivals is considered. A system of integral equations for the distribution function of the number of customers h(t) served before t, conditioned by the initial state of the system, is built. A compact formula for probability generating function of the Laplace transform of distribution of h(t) is found using the potential technique. From this representation the mean of h(t) can be effectively calculated numerically using one of the inverse Laplace transform approximation algorithms. Moreover a limit behavior of departure process as the buffer size tends to infinity is investigated. Numerical examples are attached as well.

Keywords: Departure process; Finite-buffer queue; Numerical inverse Laplace transform; Poisson arrivals; Potential method.

Introduction

Finite-buffer queueing systems are intensively investigated nowadays due to their applications in modelling of Internet routers. Of special significance is the analysis of systems in transient state i.e. at fixed moment t. We are often interested in the investigation of key system characteristics during a short period of time only since, because of permanent changing of Internet traffic, the notion of "stationary state" in reality does not occur. Besides, especially the analysis of systems with batch arrivals is desired and expected from the practical point of view. In real Internet traffic the incoming packets have different sizes measured in bytes, thus treating a byte as a unit we can consider a stream of different-sized packets as a stream of single one-byte packets arriving in groups of random sizes.

One of the essential characteristics determining the efficiency (the "function") of the service process with respect to the intensity of the arrival stream is departure process h(t), that at any fixed moment t takes on a random value equal to the number of packets completely served before t. In the paper we investigate this characteristic in the MX/G/l/N system with Poisson batch arrivals. The main goal of the analysis is to find an explicit, compact representation for probability generating function of the Laplace transform of the distribution of the departure counting process, conditioned on the number of packets present in the system at t = 0. According to the best knowledge of the author such a result is new in finite-buffer systems analysis. In any case the bibliography on transient departure processes is rather modest. In [6] a steady-state joint density function of k successive departure intervals is derived for the M/G/l/N system. Besides the problem of correlation of such intervals is discussed. Some problems connected with the service process in MX/G/1/N are solved in [2]. In particular, a joint distribution function of the length of the first lost series of batches and the time of the first loss is found. An interesting technique of investigation of finite-buffer systems is developed in [7]. The approach is based on resolvent sequences of the process being the difference of a compound Poisson process and a compound general-type renewal process. An overview of results related to finite-buffer systems with Markovian input streams can be found in [13] and [3]. Transient results for the departure process in the case of the system with batch arrivals and infinite queue can be found in [8] and [9], [10], where additionally multiple and single vacation policies are analyzed.

In the article we use the technique of potential introduced in [11] and developed in [12]. Some details connected with this approach are stated in the next Section 2 where a precise system description is given as well. In Section 3 we obtain the main result i.e. the explicit representation for the expression

tmp4A2-1_thumb

where 0 < n < N, t > 0, \z\ < 1, Re(s) > 0, and £(0) denotes the number of packets present in the system at the opening. In Section 4 we derive a limit representation for 2-fold transform of departure process as the buffer size tends to infinity. The last Section 5 contains sample numerical results for the mean of departure process obtained using one of the algorithms for numerical Laplace transform inversion.

System Description and Potential Approach

In this article we consider the MX/G/1/N queueing system in that the incoming batches of packets arrive according to a Poisson process with intensity A and the size of the arriving batch is k with probabilitytmp4A2-2_thumb. Packets are served individually with a distribution function F(•). The system capacity is assumed to be N i.e. we have N — 1 places in the buffer queue and one place for service. To complete necessary notation let us put

tmp4A2-4_thumb

By pj we denote the jth term of the i-fold convolution of the sequence (pk) with itself. Besides, let 5i}j denotes the Kronecker delta function.

The notion of potential of a random walk continuous from below was introduced in [11] (see also [12]). Here we state only selected elements of potential theory, which will be used later. Originally (see [ll]) the potential is defined as follows. Introduce a discrete-time random walk Yn in the following way:

tmp4A2-5_thumb

where Xn are independent and identically distributed random variables with a discrete distribution rk = P{Xn = k}, k = —l, 0, l,…, where r-\ > 0. A sequencetmp4A2-6_thumbsatisfying condition

tmp4A2-7_thumbtmp4A2-8_thumb

wheretmp4A2-9_thumbis called a potential of random walk Yn or, simply, a potential of the sequence (rk). Thus, the potential (Rk) of the sequence (rk) is such a sequence the generating function of which can be written down using the generating function of the sequence (rk) as in (4).

In the analysis of finite-buffer queue characteristics the following property of sequencetmp4A2-10_thumbcan be applied ([ll]):

Theorem 1. Introduce two number sequencestmp4A2-11_thumbwith the assumptiontmp4A2-12_thumbThe general solution of the following boundary problem:

tmp4A2-17_thumb

can be written in the form

tmp4A2-18_thumb

where C is a constant independent on n and Rk is the potential connected with sequence (an) i.e.

tmp4A2-19_thumb

and, besides, Rk can be found in the following recurrent way:

tmp4A2-20_thumb

Theorem l is essential for the analysis. Its importance lies in the fact that it allows to write down in a compact form the general solution of a specific-type system of equations, which appears in the transient investigation of finite-buffer queues with Poisson arrivals. A detailed proof of this theorem can be found in [ll]. Theorem l, perhaps in a slightly different form, was applied e.g. in [2], [3] and [4].

System of Integral Equations for Departure Process

In this section we will write the system of integral equations for conditional distributions of departure process h(t) and obtain the explicit formula for probability generating function of Laplace transform of probabilities P{h(t) = m \ £(0) = n}. Introduce the following notation:

tmp4A2-21_thumb

Note that the following equation is true:

tmp4A2-22_thumb

Indeed, if the system is initially empty the first summand in (10) relates to the situation in that the first group of packets enters before t. The number of packets in the system after the first arrival differs in dependence on the first group size, and for groups of size k > N reaches the maximum level N. In the second summand the first arrival epoch is after t, so h(t) = m if and only if m = 0.

As it is well known (see e.g. [5]) departure epochs are Markov moments in the queueing system with Poisson arrivals. Hence the formula of total probability used with respect to the first (after t = 0) departure epoch x > 0 leads to the following system of integral equations:

tmp4A2-23_thumb

where 1 < n < N, and

tmp4A2-24_thumb

denotes the probability that exactly k customers enters to the system before time x.

The interpretation of both sides of (11) is similar to that in the case of (10). The first summand in the integral on the right in (11) denotes the situation in that the first departure epoch occurs at time x < t. If exactly k packets have entered until x then, since x is a Markov moment, we can consider x as the initial moment of the system starting with n + k — 1 packets (k arrivals till x and one departure), and the event {h(t) = m} will become {h(t — x) = m — l}. In the second summand in the integral on the right in (ll) the number of packets which arrive before the first departure epoch x equals at least N — n, so N — n packets are enqueued only (to saturate the buffer), the remaining ones are lost. Thus, after the first departure epoch the number of packets in the system is N — l. The last summand on the right side in (ll) describes the situation in that the first departure occurs after t.

Introduce the Laplace transform of Hn(t,m) with respect to argument t as follows:

tmp4A2-25_thumb

Now (l0)-(ll) lead to

tmp4A2-26_thumb

where

tmp4A2-27_thumb

To eliminate dependence on m let us now introduce a generating function of Hn(s, m) of the form

tmp4A2-28_thumb

Equations (l4)-(l5) will take now the form

tmp4A2-29_thumb

where ak(s,z) = zak(s).

Now let us make the following substitution:

tmp4A2-30_thumb

Introducing (20) into (18)-(19) gives

tmp4A2-31_thumb

where

tmp4A2-32_thumb

Note that the system (22) has the form stated in (5). The only difference is in that functions depend on arguments s and z. The general solution of (22) can be written in the form (compare (6))

tmp4A2-33_thumb

where (see (8))

tmp4A2-34_thumb

Of course, taking into consideration that

tmp4A2-35_thumb

we get from (7)

tmp4A2-36_thumb

Now we must find the representation for C(s,z). Substituting n = 0 to (24) leads to

tmp4A2-37_thumb

Taking n = 0 in (22) we obtain

tmp4A2-38_thumb

that, since

tmp4A2-39_thumbtmp4A2-40_thumb

Introduce the following functionals:

tmp4A2-41_thumb

and

tmp4A2-42_thumb

Now, substituting n = N to (24) and using (23), (27) and (28) we get

tmp4A2-43_thumb

Similarly, introducing (23), (24), (27) and (28) into (2l), after a little laborious calculations we obtain

tmp4A2-44_thumb

where

tmp4A2-45_thumb

Comparing the right sides of (3l) and (32) we eliminate D0(s, z) as follows:

tmp4A2-46_thumb

Now from (24) (applying (29) and (30)) we get for 1 < n < N

tmp4A2-47_thumb

and hence, after operation on indexes, we obtain

tmp4A2-48_thumb

Collecting formulae (34) and (36) we can state the following main theorem:

Theorem 2. For any \z\ < 1 and Re(s) > 0 the following representations hold true:

tmp4A2-49_thumb

Limit Theorem

This section is devoted to the limit behavior of 2-fold transform of departure process in the case of infinitely increasing buffer size i.e. as N ^ m. We start with the formula (24). Taking into consideration (27) we have

tmp4A2-50_thumb

Multiplying (39) by 0n and, under the assumptiontmp4A2-51_thumbtaking a sum over n from 0 to to we obtain, along the way applying identity (26)

tmp4A2-53_thumb

where \0\ < 1. Using in (40) representations (23) and (28) we derive

tmp4A2-54_thumb

Taking into consideration the formula (26) we get from (4l) for \0\ < l

tmp4A2-55_thumb

where we denote

tmp4A2-56_thumb

Let us take into consideration the following equation:

tmp4A2-57_thumb

Treat the left side as a function Q of variable 0, for fixed 0 < z < l and s such that Im(s) = 0, Re(s) > 0. Substituting 0 = 0 we havetmp4A2-58_thumb and similarly taking 0 = l we get Q(l) = zf(s) — l <z — l < 0. Since Q’(0) =

tmp4A2-59_thumbthus there exists a unique roottmp4A2-60_thumb of (43) between 0 and l. The series on the left side of (42) is convergent in particular for 0 < 0 < l, hence the numerator of the expression on the right side of (42) should be 0 at 00.

Substituting 00 to the numerator of the expression on the right side of (42) we eliminate D0(s,z) as follows:

tmp4A2-64_thumb

Since fortmp4A2-65_thumbwe havetmp4A2-66_thumbwe can now formulate the following limit theorem:

Theorem 3. For conditional 2-fold transform of departure process as the initial number of packets tends to infinity the following limit representation holds:

tmp4A2-69_thumbtmp4A2-70_thumb

Next post:

Previous post: