1, 2Vilnius University, Faculty of Mathematics and Informatics, Naugarduko 24, 03225 Vilnius, Lithuania
Mathematical Models in Engineering, Vol. 3, Issue 1, 2017, p. 17-26.
Received 4 October 2016; received in revised form 24 January 2017; accepted 25 January 2017; published 30 June 2017
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 . 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 ).
Keywords: queues in series, performance evaluation, heavy traffic, queueing systems.
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, . 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 . A realistic case, corresponding to this model, can be found in publishing companies, printing shops, etc. .
A practical multi-server case is a lot more sophisticated than single-server queues in series , 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 .
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  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 .
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, ). The same heavy traffic fluid limits for multi-server models were investigated by Liu and Whitt, . Renewal process approximation and network performance measures of the single-server system are investigated in detail by S. Yeong Lin et al. , and Mei and Winands , 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 Since an excellent treatment of this subject has been published by Billingsley , 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 , the space of all right-continuous functions on having left limits and endowed with the Skorohod metric, . In Billingsley , this metric is denoted by With , is a complete, separable metric space. Let be a class of Borel sets of . Then, if and are probability measures on which satisfy:
for every bounded, continuous, real-valued function on , we say that weakly converges to , as , and write A random function is a measurable mapping from some probability space () into having the distribution on (). We say that a sequence of random functions weakly converges to the random function , and write , if the distribution of weakly converges to the distribution of . A sequence of random functions converges to in probability, if and are defined on a common domain and for any , When is a constant function (not random), the convergence in probability is equivalent to a weak convergence. In such cases, we write or . If and have a common domain, we also write , when for all , . We also use the uniform metric which is defined by for . Also, note that for .
2. Statement of the problem
In this paper, we state that queue in series is a -phase system, when . We investigate a -phase queue in series (i.e., -phase queue means that the system has servers connected sequentially in such a way, that the customer after being served by the -th server, goes to the -th server, while , or leaves the system when ). 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 as a time of arrival of the -th customer, as a service time of the -th customer in the -th phase of a queue in series; . Let us introduce independent renewal processes (the number of customers that can be served in the -th phase of the queues in series in the interval if devices are working without time waste), (the number of customers who arrive to the queues in series in the interval . Next, denote by the number of customers that were served at the -th phase in the interval , , .
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 ().
Let interarrival times to the queues in series and service times in each phase of the queues in series as be mutually independent identically distributed random variables.
Also, denote by a virtual waiting time of arrival of the customer up to the -th phase of the queues in series at time (the total virtual waiting time of a customer), by – a virtual waiting time of the customer in the -th phase of the queues in series at time (the time one must wait until a customer arrives at the -th phase of the queues in series to be served); and by the time of service of customers, arriving at the -th phase of the queues in series in the interval , , Note that , , can be interpreted as a continuous analog of the sojourn time process, , .
Note that , ,
If (a queueing system at time 0 is empty), then :
Let us consider a sequence of queues in series as in Minkevičius : we assume that sequences of queues in series tend to grow to infinity as . Thus, are identically distributed random variables in the -th queues in series, , ,
Define , , ,
Note that, if , then and It must be mentioned that, under conditions of heavy traffic, and , .
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:
where and are independent standard Wiener processes, ,
Proof . Denote a family of random functions in as follows:
Applying a triangle inequality, we obtain that for :
Therefore, from this and Eq. (3) we achieve that:
Finally, from Eq. (4) we obtain that:
The proof that :
Also, note that for :
If Eqs. (1) and (2) are satisfied, then:
where , and are Wiener processes with a positive endless drift.
Moreover, applying a continuous mapping theorem , we obtain that:
Thus, we prove that:
if conditions Eq. (2) are fulfilled.
The method for proving Eq. (10) is the same as applying the formula from Harrison’s book, . For any and , we obtain:
where is a normal distribution function, and
Note that if then , and Consequently:
which proves Eq. (10). Thus (see again a continuous mapping theorem):
from Eqs. (11) and (7) we achieve that ,
is similar to Eqs. (8)-(12).
We denote , if the random variables and have the same distribution function. It is clear, that:
If conditions Eq. (2) are satisfied, then, similarly as in Eqs. (8)-(12), we can prove that:
Again, by applying a continuous mapping theorem to the supremum function, we obtain that:
It follows, that:
From Eqs. (4), (12) and (15) we obtain that , However :
where are independent standard Wiener processes, , .
Hence and applying Eqs. (2) we derive that:
In order to secure a multivariate weak convergence, it suffices for individual components of a limit process to be continuous in [0,1] . 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:
where are independent standard Wiener processes, ,
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 , , 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 (the number of customers that can be served in the -th phase of the network in the interval ). E.g., in 2-server configuration with arrival rate of 100 customers/minute and standard deviation, service rates are set as and which satisfies the main requirement for heavy traffic, .
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. 1. 2-server model of queues in series
Fig. 2. Timeline decomposition of 2-server queues in series
Fig. 3. 4-server model of queues in series
Fig. 4. Timeline decomposition of 4-server queues in series
Fig. 5. 24-server model of queues in series
Fig. 6. Timeline decomposition of 24-server queues in series
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.
- Asmussen S. Extreme value theory for queues via cycle maxima. Extremes, Vol. 76, Issue 1, 1998, p. 137-168. [Search CrossRef]
- 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. [Search CrossRef]
- Wu K., Mcginnis L. Interpolation approximations for queues in series. IIE Transactions, Vol. 45, 2013, p. 273-290. [Search CrossRef]
- Kapoor Agrawal S. S., Tiwari L. M. Bi-Tandem Queues with Multi Input Arrival and with Linear and Non Linear Service Rates, 2011. [Search CrossRef]
- Wu K., Mcginnis L. Interpolation approximations for queues in series. IIE Transactions, Vol. 45, 2013, p. 273-290. [Search CrossRef]
- 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. [Search CrossRef]
- Billingsley P. Convergence of Probability Measures. Wiley, New York, 1968. [Search CrossRef]
- 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. [Search CrossRef]
- 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. [Search CrossRef]
- 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. [Search CrossRef]
- A. V. Skorohod Limit theorems for stochastic processes. Theory of Probability and its Applications, Vol. 1, Issue 3, 1956, p. 261-290. [Search CrossRef]
- Reiman M. Open queueing networks in heavy traﬃc. Mathematics of Operations Research, Vol. 9, 1984, p. 441-459. [Search CrossRef]
- Borovkov A. Stochastic Processes in Queueing Theory. Nauka, Moscow, 1972. [Search CrossRef]
- Harrison J. Brownian Motion and Stochastic ﬂow Processes. Wiley, New York, 1985. [Search CrossRef]
- Minkevičius S. Weak convergence in multiphase queues. Lietuvos Matematikos Rinkinys, Vol. 26, 1986, p. 717-722. [Search CrossRef]
- Minkevičius S. On the law of the iterated logarithm in multiphase queueing systems. Informatica, Vol. 8, Issue 3, 1997, p. 367-376. [Search CrossRef]