Published: 30 June 2017

On extreme values in queues in series

Saulius Minkevičius1
Edvinas Greičius2
1, 2Vilnius University, Faculty of Mathematics and Informatics, Naugarduko 24, 03225 Vilnius, Lithuania
Corresponding Author:
Saulius Minkevičius
Views 79
Reads 23
Downloads 1312

Abstract

A model of queues in series under conditions of heavy traffic is developed in this paper. This is a mathematical model to measure performance of complex computer networks operating under conditions of heavy traffic. Two limit theorems are derived by investigating extreme values of a virtual waiting time of customers in queues in series. Due to serious technical difficulties, research does not often consider intermediate models of queues in series. Note that the research of extreme values in more specific systems than the classical example GI/G/N (multiserver queue, queues in series, etc.) was introduced only 20 years ago [1]. There are many real-world applications at various hierarchical levels for both queues in series and tandem queues, for example, in high-speed communication networks (from architecture of the router to protocol stacks [2]).

1. Introduction

A brief review of the latest achievements in the theory of queues in series after the year of 2005 is provided in this paper. A good example of studying queues in series behavior and valuable insights in order to understand the behavior of manufacturing systems is provided by Wu and McGinnis, [3]. Generally speaking, there are many practical manufacturing systems that can be modeled as queues in series. For example, any mixed-model assembly process has the structure of queues in series [3]. A realistic case, corresponding to this model, can be found in publishing companies, printing shops, etc. [4].

A practical multi-server case is a lot more sophisticated than single-server queues in series [5], since each workstation may have multiple servers with different capabilities and each server may have a complicated configuration. Obviously, such technical combinations suffer different types of interruptions. Modelling the behaviour of such a technical configuration by analysis of all the details is a formidable task [5].

In this paper, functional limit theorems for extreme values of the main characteristics of queues in series are proved in heavy traffic (maximum of the total virtual waiting time of a customer, maximum of the virtual waiting time of a customer). Recent investigations [6] show that under conditions of heavy traffic the network does not always agree with the regulated Brownian motion diffusion limit for the standard network without special arrivals. However, if the traffic fed into the system is generated by independent or weakly dependent sources and the smallest relevant time scale is not too fine, the central limit theorem suggests that the input traffic is close to Gaussian [2].

The main tool used in this paper for the analysis of queues in series in heavy traffic is functional limit theorems for renewal and compound renewal processes (the proof can be found in Billingsley, [7]). The same heavy traffic fluid limits for multi-server models were investigated by Liu and Whitt, [8]. Renewal process approximation and network performance measures of the single-server system are investigated in detail by S. Yeong Lin et al. [9], and Mei and Winands [10], where new fundamental insights on heavy traffic are provided and revealed explicitly, especially how the expected delay at each of the queues depends on the system parameters, and on the interarrival time distributions at each of the queues.

In this paper, the natural setting for functional limit theorems is the weak convergence of probability measures on the function space D0,1(D). Since an excellent treatment of this subject has been published by Billingsley [7], we shall only make a few remarks in regards to our terminology and notation. Stochastic processes characterizing a queueing system give rise to sequences of random functions in D, the space of all right-continuous functions on [0,1] having left limits and endowed with the Skorohod metric, d [11]. In Billingsley [7], this metric is denoted by d0. With d, D is a complete, separable metric space. Let D be a class of Borel sets of D. Then, if Pn and P are probability measures on D which satisfy:

limnDfdPn=DfdP,

for every bounded, continuous, real-valued function f on D, we say that Pn weakly converges to P, as n, and write PnP. A random function X is a measurable mapping from some probability space (Ω,B,P) into D having the distribution P=PX-1 on (D,D). We say that a sequence of random functions {Xn} weakly converges to the random function X, and write XnX, if the distribution Pn of Xn weakly converges to the distribution P of X. A sequence of random functions {Xn} converges to X in probability, if Xn and X are defined on a common domain and for any ε>0, P{d(Xn,X)ε}0. When X is a constant function (not random), the convergence in probability is equivalent to a weak convergence. In such cases, we write d(Xn,X)0 or XnX. If Xn and Yn have a common domain, we also write d(Xn,Yn)0, when for all ε>0, P{d(Xn,Yn)>ε}0. We also use the uniform metric ρ which is defined by ρ(x,y)=sup0t1|x(t)-y(t)| for x,yD. Also, note that d(x,y)ρ(x,y) for x,yD.

2. Statement of the problem

In this paper, we state that queue in series is a k-phase system, when k2. We investigate a k-phase queue in series (i.e., k-phase queue means that the system has k servers connected sequentially in such a way, that the customer after being served by the j-th server, goes to the (j+1)-th server, while j<k, or leaves the system when j=k). Denote the phase of the queueing system by the sum of the waiting time of the customer and the service time of the customer. Let us denote tm as a time of arrival of the m-th customer, Sm(j) as a service time of the m-th customer in the j-th phase of a queue in series; zm=tm+1-tm. Let us introduce independent renewal processes xj(t)={maxk:i=1kSi(j)t} (the number of customers that can be served in the j-th phase of the queues in series in the interval [0,t] if devices are working without time waste), e(t)={maxk:i=1kzit} (the number of customers who arrive to the queues in series in the interval [0,t]. Next, denote by τj(t) the number of customers that were served at the j-th phase in the interval [0,t], j=1,2,,k, t>0.

Suppose that the virtual waiting time of the customer in each phase of the queues in series is unlimited, the discipline service of customers is “first come, first served” (FCFS). All random variables are defined in one common probability space (Ω,F,P).

Let interarrival times (zm) to the queues in series and service times (Sm(j)) in each phase of the queues in series as j=1,2,,k, be mutually independent identically distributed random variables.

Assume:

α^j=ESn(j), α^0=Ezn, σ-j=DSn(j)>0, σ-0=Dzn>0,
σj2=σ-jα^j+σ-j-1(α^j-1)-3α^j2>0, βj=α^jα^j-1-1, γj=i=1jβi, j=1,2,,k.

Also, denote by Wj(t) a virtual waiting time of arrival of the customer up to the j-th phase of the queues in series at time t (the total virtual waiting time of a customer), by Vj(t) – a virtual waiting time of the customer in the j-th phase of the queues in series at time t (the time one must wait until a customer arrives at the j-th phase of the queues in series to be served); and by Sj(t) the time of service of customers, arriving at the j-th phase of the queues in series in the interval [0,t], j=1,2,,k, t>0. Note that Wj(t)=i=1jVi(t), j=1,2,,k, t>0.Wj(t) can be interpreted as a continuous analog of the sojourn time process, j=1,2,,k, t>0 [12].

Note that Sj(t)=i=1τj-1(t)Si(j), j=1,2,,k, t>0.

Also, let:

yjt=Sjt-t, ft(y())=y(t)-inf0sty(s), y^j(t)=i=1xj-1(t)Si(t)-t,
V^j(t)=ft(y^j()), W^j(t)=i=1jV^i(t), x0(t)=e(t), j=1,2,,k, t>0.

If V(0)=0 (a queueing system at time 0 is empty), then [13]:

Vj(t)=ft(yj()), j=1,2,,k, t>0.

Let us consider a sequence of queues in series as in Minkevičius [14]: we assume that sequences of queues in series tend to grow to infinity as n. Thus, Sm,n(j) are identically distributed random variables in the n-th queues in series, j=1,2,,k, Sm,n(0)=zm,n,m1, n1.

Define Gj,n(x)=P(Sm,n(j)<x), α^j,n=ESm,n(j), j=0,1,2,,k, βn=min1jkβj,n.

Let:

1
limnDSm,n(j)ESm,n(j)+DSm,n(j-1)(ESm,n(j-1))-3(ESm,n(j))2=σj2>0, j=1,2,,k,

and:

2
βn>0.

Note that, if βn>0, then βj,n>0, j=1,2,,k and α^k,n>α^k-1,n>>α^1,n>α^0,n>0. It must be mentioned that, under conditions of heavy traffic, βn>0 and βn0, n [15].

3. The main results

First, we prove a functional limit theorem on the maximum of the total virtual waiting time of a customer in queues in series.

Theorem 3.1. If conditions Eq. (1) and (2) are fulfilled, then:

sup0stW1(ns)-γ1ntn;;sup0stWk(ns)-γkntny1(t);y2(t);;yk(t),

where yj(t)=i=1j{σizi(t)} and zj(t) are independent standard Wiener processes, j=1,2,,k, 0t1.

Proof. Denote a family of random functions in D as follows:

Wjn(t)=sup0stWj(ns)-γjntn,
W^~jn(t)=sup0stW^j(ns)-γjntn,
W-jn(t)=Wj(nt)-γjntn, W^jn(t)=W^j(nt)-γjntn,
M-jn(t)=sup0st{i=1jy^i(ns)}-γjntn,
Mjn(t)=i=1jy^i(nt)-γjntn,
N-jn(t)=V^j(nt)-βjntn, N~jn(t)=sup0sty^j(ns)-βjntn,
N^jn(t)=y^j(nt)-βjntn, j=1,2,,k, 0t1.

Applying a triangle inequality, we obtain that for j=1,2,,k:

3
d(Wjn,Mjn)dWjn,W^~jn+dW^~jn,M^~jn+dM^~jn,Mjn
dW-jn,W^jn+dW^jn,Mjn+dM^~jn,MjnρW-jn,W^jn
+ρ(W^jn,Mjn)+ρ(M^~jn,Mjn)=sup0t1|Wj(nt)-W^j(nt)|n
+sup0t1|W^j(nt)-{i=1jy^i(nt)}|n+sup0t1|sup0st(i=1jy^i(ns))-{i=1jy^i(nt)}|n.

But:

0sup0sti=1jy^is-i=1jy^iti=1ksup0sty^i(s)-i=1jy^i(t)
=i=1jsup0sty^is-y^it, j=1,2,,k, t>0.

Therefore, from this and Eq. (3) we achieve that:

4
d(Wjn,Mjn)sup0t1|Wj(nt)-W^j(nt)|n+sup0t1|i=1jfnt(y^j())-i=1jy^i(nt)|n
+sup0t1|i=1j{sup0st(y^j(ns))-y^i(nt)}|nsup0t1|Wj(nt)-W^j(nt)|n
+i=1jsup0t1|fnt(y^i()-y^i(nt)|n+i=1jsup0t1|sup0st(y^i(ns))-y^i(nt)|n
sup0t1|Wj(nt)-W^j(nt)|n+i=1ksup0t1|fnt(y^i()-y^i(nt)|n
+i=1ksup0t1|sup0st(y^i(ns))-y^i(nt)|n
=ρ(W-jn,W^jn)+i=1kρ(N-in,N^in)+i=1kρ(N^in,N~in)
i=1kρW-in,W^in+ρN-in,N^in+ρN^in,N~in, j=1,2,,k.

Finally, from Eq. (4) we obtain that:

5
dWjn,Mjni=1kρW-in,W^in+ρN-in,N^in+ρN^in,N~in, j=1,2,,k.

The proof that [16]:

6
ρW-in,W^in0, i=1,2,,k.

Also, note that for i=1,2,,k:

7
ρN-in,N^in=sup0t1-inf0sty^insn=sup0t1sup0st-y^insn.

If Eqs. (1) and (2) are satisfied, then:

8
y^j(nt)n=l=1xj-1(nt)Slij-αjαj-1ntn+βj,nntz^jt,

where z^j(t), j=1,2,,k and t>0 are Wiener processes with a positive endless drift.

Moreover, applying a continuous mapping theorem [7], we obtain that:

9
|sup0st(-y^j(ns))|nsup0stz^js, j=1,2,,k, t>0.

Thus, we prove that:

10
sup0st(-y^j(ns))n0, j=1,2,,k, t>0,

if conditions Eq. (2) are fulfilled.

The method for proving Eq. (10) is the same as applying the formula from Harrison’s book, [15]. For any ε>0 and β=-, we obtain:

11
P(sup0stz^j(t)<ε)=Φε-βtσt-e2βεΦ-ε-βtσt=1,

where Φ() is a normal distribution function, j=1,2,,k and t>0.

Note that if z(0)=0, then sup0stz^j(t)0, j=1,2,,k and t>0. Consequently:

P(|sup0stz^j(t)|<ε)=P(0sup0stz^j(t)<ε)
=P(sup0stz^j(t)<ε)-P(sup0stz^j(t)<0)=P(sup0stz^j(t)<ε)=1.

Thus:

P(|sup0stz^j(s)|<ε)=1,

which proves Eq. (10). Thus (see again a continuous mapping theorem):

12
sup0t1|sup0st(-y^j(ns))|n0, j=1,2,,k.

from Eqs. (11) and (7) we achieve that ρ(N-jn,N^jn)0, j=1,2,,k.

Finally, proving:

13
ρN-jn,N^jn0, j=1,2,,k,

is similar to Eqs. (8)-(12).

We denote X~Y, if the random variables X and Y have the same distribution function. It is clear, that:

14
sup0sty^j(ns)-y^j(nt)nsup0stz^j(s)-z^j(t)
=sup0st(z^j(s)-z^j(t))=sup0st(-(z^j(t)-z^j(s)))
~sup0st-z^jt-s=sup0st-z^js, j=1,2,,k, t>0.

If conditions Eq. (2) are satisfied, then, similarly as in Eqs. (8)-(12), we can prove that:

15
sup0sty^j(ns)-y^j(nt)n0, j=1,2,,k, t>0.

Again, by applying a continuous mapping theorem to the supremum function, we obtain that:

sup0t1(sup0st(y^i(ns))-y^i(nt))n0, i=1,2,,k.

It follows, that:

16
ρ(N^in,N~in)0, i=1,2,,k.

From Eqs. (4), (12) and (15) we obtain that d(Wjn,Mjn)0, j=1,2,,k. However [13]:

17
Mjn(t)={i=1jy^i(nt)}-γjntn=i=1jy^i(nt)-βintni=1j{σizi(t)},

where zi(t) are independent standard Wiener processes, j=1,2,,k, 0t1.

Hence and applying Eqs. (2) we derive that:

18
Wjn(t)yj(t), j=1,2,,k, 0t1.

In order to secure a multivariate weak convergence, it suffices for individual components of a limit process to be continuous in [0,1] [14]. Therefore, the proof is complete.

Next, we prove a functional limit theorem on the maximum of the virtual waiting time of a customer in queues in series.

Theorem 3.2. If conditions Eqs. (1) and (2) are fulfilled, then:

sup0stV1(ns)-β1ntn;;sup0stVk(ns)-βkntn
σ1z1(t);σ2z2(t);;σkzk(t),

where zj(t) are independent standard Wiener processes, j=1,2,,k, 0t1.

Proof. The proof is similar to that of Theorem 3.1, and we omit it. The proof is complete.

4. Final note on the theorems

If all the servers in the queues in series configuration are asymptotically busy at all the phases, the service processes at different phases are asymptotically independent and form the differences of independent renewal processes. Thus, the processes zj(t), j=1,2,,k, 0t1 in Theorems 3.1, 3.2 are independent.

5. Computational simulation

In this section, we provide a simulation to illustrate an intuitive queues in series network model. We use “Simul8” software to imitate model’s behavior.

In order to simulate heavy traffic conditions, we choose an input of independent identically distributed process, having constant mean and standard deviation. The network model has an increasing virtual waiting time in each of the evolving phase of the network. In further examples, theoretical models with 2, 4 and 24 servers will be presented. In all of the network configurations, a constantly decaying service rate is set for each server in order to decrease xj(t) (the number of customers that can be served in the j-th phase of the network in the interval [0,t]). E.g., in 2-server configuration with arrival rate of 100 customers/minute and σ2=25 standard deviation, service rates are set as α^1=ESn(1)=90, and α^2=ESn(2)=80, which satisfies the main requirement for heavy traffic, βj=α^j/α^j-1-1>0.

One can notice from the Fig. 1, that in the first phase the network is working in almost full capacity with some of the customers stopped due to heavy traffic, whilst in the second phase the server is utilized only by 67 percent, with more customers stopped (6.6 percent) and most of the customers waiting to be served (26 percent).

Timeline decomposition (Fig. 2) illustrates the periods of waiting and service times between each server in the network more clearly. Further, we provide graphical illustrations from the queues in series network model with 4 and 24 phases, accordingly (Figs. 3-6).

Graphical results show the same network behavior as in 2-server queues in series configuration, with an increasing virtual waiting time with each evolving phase of the network.

Fig. 12-server model of queues in series

2-server model of queues in series

Fig. 2Timeline decomposition of 2-server queues in series

Timeline decomposition of 2-server queues in series

Fig. 34-server model of queues in series

4-server model of queues in series

Fig. 4Timeline decomposition of 4-server queues in series

Timeline decomposition of 4-server queues in series

Fig. 524-server model of queues in series

24-server model of queues in series

Fig. 6Timeline decomposition of 24-server queues in series

Timeline decomposition of 24-server queues in series

6. Conclusions

All the provided examples show that the queue of customers and the virtual waiting time grows indefinitely when the network of queues in series operates under conditions of heavy traffic. That proofs the operation of theoretical model described in this paper.

References

  • Asmussen S. Extreme value theory for queues via cycle maxima. Extremes, Vol. 76, Issue 1, 1998, p. 137-168.
  • Norros Mandjes I. M., Mannersalo P. Gaussian tandem queues with an application to dimensioning of switch fabric interfaces. Computer Networks, Vol. 51, 2007, p. 781-797.
  • Wu K., Mcginnis L. Interpolation approximations for queues in series. IIE Transactions, Vol. 45, 2013, p. 273-290.
  • Kapoor Agrawal S. S., Tiwari L. M. Bi-Tandem Queues with Multi Input Arrival and with Linear and Non Linear Service Rates, 2011.
  • Wu K., Mcginnis L. Interpolation approximations for queues in series. IIE Transactions, Vol. 45, 2013, p. 273-290.
  • Knottenbelt Harrison W. P., Hayden R. A. Product-forms in batch networks: approximation and asymptotics. Performance Evaluation, Vol. 70, Issue 10, 2013, p. 822-840.
  • Billingsley P. Convergence of Probability Measures. Wiley, New York, 1968.
  • Liu Y., Whitt W. Stabilizing customer abandonment in many-server queues with time-varying arrivals. Operations Research, Vol. 60, Issue 6, 2012, p. 1551-1564.
  • Noh Yeong Li S. J. S., Hur S. Departure process of a single server queueing system with Markov renewal input and general service time distribution. Computers and Industrial Engineering, Vol. 51, Issue 31, 2006, p. 519-525.
  • Van Der Mei R. D., Winands E. M. M. Polling models with renewal arrivals: A new method to derive heavy-trac asymptotics. Performance Evaluation, Vol. 64, 2007, p. 1029-1040.
  • A. V. Skorohod Limit theorems for stochastic processes. Theory of Probability and its Applications, Vol. 1, Issue 3, 1956, p. 261-290.
  • Reiman M. Open queueing networks in heavy traffic. Mathematics of Operations Research, Vol. 9, 1984, p. 441-459.
  • Borovkov A. Stochastic Processes in Queueing Theory. Nauka, Moscow, 1972.
  • Harrison J. Brownian Motion and Stochastic flow Processes. Wiley, New York, 1985.
  • Minkevičius S. Weak convergence in multiphase queues. Lietuvos Matematikos Rinkinys, Vol. 26, 1986, p. 717-722.
  • Minkevičius S. On the law of the iterated logarithm in multiphase queueing systems. Informatica, Vol. 8, Issue 3, 1997, p. 367-376.

About this article

Received
04 October 2016
Accepted
25 January 2017
Published
30 June 2017
Keywords
queues in series
performance evaluation
heavy traffic
queueing systems