Class dependent departure process from multiclass phase queues: Exact and approximate analyses

In this paper we study class dependent departure processes from phase type queues. When the arrival process for a subset of the classes is a Poisson process, we determine the Laplace-Stieltjes transform of the stationary inter-departure times of the combined output of all the other classes. We also propose and test approximations for the squared coefficient of variation of the stationary inter-departure times of each customer class. The approximations are based on the detailed structure of the second order measures of the aggregate departure process. Finally, we propose renewal approximations for the class dependent departure process that take into account the utilization of the queue that customers next visit.     

The last departure time from an M t /G/∞ queue with a terminating arrival process

This paper studies the last departure time from a queue with a terminating arrival process. This problem is motivated by a model of two-stage inspection in which finitely many items come to a first stage for screening. Items failing first-stage inspection go to a second stage to be examined further. Assuming that arrivals at the second stage can be regarded as an independent thinning of the departures from the first stage, the arrival process at the second stage is approximately a terminating Poisson process. If the failure probabilities are not constant, then this Poisson process will be nonhomogeneous. The last departure time from an M _t /G/∞ queue with a terminating arrival process serves as a remarkably tractable approximation, which is appropriate when there are ample inspection resources at the second stage. For this model, the last departure time is a Poisson random maximum, so that it is possible to give exact expressions and develop useful approximations based on extreme-value theory.      

Exact and approximate numerical solutions to steady-state single-server queues:M/G/1 — a unified approach

This paper presents a unified approach for the numerical solutions of anM/G/1 queue. On the assumption that the service-time distribution has a rational Laplace-Stieltjes transform (LST), explicit closed-form expressions have been obtained for moments, distributions of system length and waiting time (in queue) in terms of the roots of associated characteristic equations (c.e.'s). Approximate analyses for the tails of the distributions based on one or more roots are also discussed. Numerical aspects have been tested for a variety of complex service-time distributions including but not restricted to only mixed generalized Erlang and generalized hyperexponential. A sample of numerical computations is also included. It is hoped that the results obtained would prove to be beneficial to both practitioners and theorists dealing with bounds, inequalities, approximations, and other aspects.     

A BMAP/SM/1 queue with service times depending on the arrival process

We study a BMAP/>SM/1 queue with batch Markov arrival process input and semi‐Markov service. Service times may depend on arrival phase states, that is, there are many types of arrivals which have different service time distributions. The service process is a heterogeneous Markov renewal process, and so our model necessarily includes known models. At first, we consider the first passage time from level {κ+1} (the set of the states that the number of customers in the system is κ+1) to level {κ} when a batch arrival occurs at time 0 and then a customer service included in that batch simultaneously starts. The service descipline is considered as a LIFO (Last‐In First‐Out) with preemption. This discipline has the fundamental role for the analysis of the first passage time. Using this first passage time distribution, the busy period length distribution can be obtained. The busy period remains unaltered in any service disciplines if they are work‐conserving. Next, we analyze the stationary workload distribution (the stationary virtual waiting time distribution). The workload as well as the busy period remain unaltered in any service disciplines if they are work‐conserving. Based on this fact, we derive the Laplace–Stieltjes transform for the stationary distribution of the actual waiting time under a FIFO discipline. In addition, we refer to the Laplace–Stieltjes transforms for the distributions of the actual waiting times of the individual types of customers. Using the relationship between the stationary waiting time distribution and the stationary distribution of the number of customers in the system at departure epochs, we derive the generating function for the stationary joint distribution of the numbers of different types of customers at departures. This revised version was published online in June 2006 with corrections to the Cover Date.     

Asymptotics for M/G/1 low-priority waiting-time tail probabilities

We consider the classical M/G/1 queue with two priority classes and the nonpreemptive and preemptive-resume disciplines. We show that the low-priority steady-state waiting-time can be expressed as a geometric random sum of i.i.d. random variables, just like the M/G/1 FIFO waiting-time distribution. We exploit this structures to determine the asymptotic behavior of the tail probabilities. Unlike the FIFO case, there is routinely a region of the parameters such that the tail probabilities have non-exponential asymptotics. This phenomenon even occurs when both service-time distributions are exponential. When non-exponential asymptotics holds, the asymptotic form tends to be determined by the non-exponential asymptotics for the high-priority busy-period distribution. We obtain asymptotic expansions for the low-priority waiting-time distribution by obtaining an asymptotic expansion for the busy-period transform from Kendall's functional equation. We identify the boundary between the exponential and non-exponential asymptotic regions. For the special cases of an exponential high-priority service-time distribution and of common general service-time distributions, we obtain convenient explicit forms for the low-priority waiting-time transform. We also establish asymptotic results for cases with long-tail service-time distributions. As with FIFO, the exponential asymptotics tend to provide excellent approximations, while the non-exponential asymptotics do not, but the asymptotic relations indicate the general form. In all cases, exact results can be obtained by numerically inverting the waiting-time transform. This revised version was published online in June 2006 with corrections to the Cover Date.     

Infinite-server systems with Coxian arrivals

We consider a network of infinite-server queues where the input process is a Cox process of the following form: The arrival rate is a vector-valued linear transform of a multivariate generalized (i.e., being driven by a subordinator rather than a compound Poisson process) shot-noise process. We first derive some distributional properties of the multivariate generalized shot-noise process. Then these are exploited to obtain the joint transform of the numbers of customers, at various time epochs, in a single infinite-server queue fed by the above-mentioned Cox process. We also obtain transforms pertaining to the joint stationary arrival rate and queue length processes (thus facilitating the analysis of the corresponding departure process), as well as their means and covariance structure. Finally, we extend to the setting of a network of infinite-server queues.

     

The discrete-time MAP/PH/1 queue with multiple working vacations

We consider a discrete-time single-server queueing model where arrivals are governed by a discrete Markovian arrival process (DMAP), which captures both burstiness and correlation in the interarrival times, and the service times and the vacation duration times are assumed to have a general phase-type distributions. The vacation policy is that of a working vacation policy where the server serves the customers at a lower rate during the vacation period as compared to the rate during the normal busy period. Various performance measures of this queueing system like the stationary queue length distribution, waiting time distribution and the distribution of regular busy period are derived. Through numerical experiments, certain insights are presented based on a comparison of the considered model with an equivalent model with independent arrivals, and the effect of the parameters on the performance measures of this model are analyzed.     

Characterizing the departure process of a single server queue from the embedded Markov renewal process at departures

In the literature, performance analyses of numerous single server queues are done by analyzing the embedded Markov renewal processes at departures. In this paper, we characterize the departure processes for a large class of such queueing systems. Results obtained include the Laplace–Stieltjes transform (LST) of the stationary distribution function of interdeparture times and recursive formula for {_cn ≡ the covariance between interdeparture times of lag n}. Departure processes of queues are difficult to characterize and for queues other than M/G/1 this is the first time that {_cn} can be computed through an explicit recursive formula. With this formula, we can calculate {_cn} very quickly, which provides deeper insight into the correlation structure of the departure process compared to the previous research. Numerical examples show that increasing server irregularity (i.e., the randomness of the service time distribution) destroys the short-range dependence of interdeparture times, while increasing system load strengthens both the short-range and the long-range dependence of interdeparture times. These findings show that the correlation structure of the departure process is greatly affected by server regularity and system load. Our results can also be applied to the performance analysis of a series of queues. We give an application to the performance analysis of a series of queues, and the results appear to be accurate. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the departure process of a leaky bucket system with long-range dependent input traffic

Due to the strong experimental evidence that the traffic to be offered to future broadband networks will display long-range dependence, it is important to study the possible implications that such traffic may have for the design and performance of these networks. In particular, an important question is whether the offered traffic preserves its long-range dependent nature after passing through a policing mechanism at the interface of the network. One of the proposed solutions for flow control in the context of the emerging ATM standard is the so-called leaky bucket scheme. In this paper we consider a leaky bucket system with long-range dependent input traffic. We adopt the following popular model for long-range dependent traffic: Time is discrete. At each unit time a random number of sessions is initiated, having the distribution of a Poisson random variable with mean λ. Each of these sessions has a random duration τ, where the integer random variable τ has finite mean, infinite variance, and a regularly varying tail, i.e., P(τ >К) ~ К^-Lα L(К), where 1 < α < 2 L(·) is a slowly varying function. Once a session is initiated, it generates one cell at each unit of time until its termination. We examine the departure process of the leaky bucket policing mechanism driven by such an arrival process, and show that it too is long-range dependent for any token buffer size and any - finite or infinite - cell buffer size. Moreover, upper and lower bounds for the covariance sequence of the output process are established. The above results demonstrate that long-range dependence cannot be removed by the kinds of flow control schemes that are currently being envisioned for broadband networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

On effects of arrival rate and burstiness in the queueing system: Analysis ofLb/D/1

This paper studies a single-server queueing system with deterministic service time in which arrivals are regulated by the leaky-bucket mechanism. This paper intends to improve quantitative understanding of the effects of arrival rate and burstiness on the average delay of queueing systems. The study is directed toward identifying the worst traffic of arrivals allowed by the leaky-bucket regulation and clarifying the effects of the leaky bucket parameters (which represent the arrival rate and burstiness) on the average queueing delay. The arrival traffic that maximizes the average queueing delay is characterized as the repetition of the following three phases: bulky arrival, greedy arrival for a specified length of interval, and then no arrival till the token bucket is full. The average queueing delay for the worst traffic is expressed as a function the leaky bucket parameters.Research was partially supported by the NSF under grant ECS-8552419. Research was conducted at the Laboratory for Information and Decision Systems of the Massachusetts Institute of Technology and the U.S. Naval Research Laboratory.     

Analysis of an MMPP/G/1/K queue with queue length dependent arrival rates,and its application to preventive congestion control in telecommunication networks

Recently telecommunication networks have been designed in order to transfer all types of information services such as voice, data and video. Next generation wireless networks has been developed to integrate the existing technologies and to support comprehensive services. As the traffics of diverse services have properties of timecorrelation and burstiness, unpredictable statistical fluctuation of traffic streams may cause congestion. To suggest a congestion control scheme which controls arrival rates according to the queue length, we consider an MMPP/G/1/K queue with queue length dependent arrival rates. The effect of system parameters on performance measures also is explained with the numerical examples.     

The queue length distributions in the finite buffer bulk-service MAP/G/1 queue with multiple vacations

We consider a finite buffer batch service queueing system with multiple vacations wherein the input process is Markovian arrival process (MAP). The server leaves for a vacation as soon as the system empties and is allowed to take repeated (multiple) vacations. The service- and vacation- times are arbitrarily distributed. We obtain the queue length distributions at service completion, vacation termination, departure, arbitrary and pre-arrival epochs. Finally, some performance measures such as loss probability, average queue lengths are discussed. Computational procedure has been given when the service- and vacation- time distributions are of phase type (PH-distribution).     

具有可变到达率的多重休假Geo~(λ_1,λ_2)/G/1排队分析

本文考虑顾客到达与服务员休假相关的多重休假离散时间排队系统,用更新过程及u-变换分析了系统的队长性质.分别得到系统在三种时点(n~-,n~+,n)处的队长分布的递推解,进而揭示了在不同到达率条件下系统队长分布不再具有随机分解特性,得到了系统在四种时点(n~-,n~+,n,离去时点D_n)处稳态队长分布的重要关系(不同于连续时间排队系统).     

Analytic approximations of queues with lightly- and heavily-correlated autoregressive service times

We consider a single-server queueing system. The arrival process is modelled as a Poisson process while the service times of the consecutive customers constitute a sequence of autoregressive random variables. Our interest into autoregressive service times comes from the need to capture temporal correlation of the channel conditions on wireless network links. If these fluctuations are slow in comparison with the transmission times of the packets, transmission times of consecutive packets are correlated. Such correlation needs to be taken into account for an accurate performance assessment. By means of a transform approach, we obtain a functional equation for the joint transform of the queue content and the current service time at departure epochs in steady state. To the best of our knowledge, this functional equation cannot be solved by exact mathematical techniques, despite its simplicity. However, by means of a Taylor series expansion in the parameter of the autoregressive process, a “light-correlation” approximation is obtained for performance measures such as moments of the queue content and packet delay. We illustrate our approach by some numerical examples, thereby assessing the accuracy of our approximations by simulation. For the heavy correlation case, we give differential equation approximations based on the time-scale separation technique, and present numerical examples in support of this approximation.     

M/G/1 queue with event-dependent arrival rates

Motivated by experiments on customers’ behavior in service systems, we consider a queueing model with event-dependent arrival rates. Customers’ arrival rates depend on the last event, which may either be a service departure or an arrival. We derive explicitly the performance measures and analyze the impact of the event-dependency. In particular, we show that this queueing model, in which a service completion generates a higher arrival rate than an arrival, performs better than a system in which customers are insensitive to the last event. Moreover, contrary to the M/G/1 queue, we show that the coefficient of variation of the service does not necessarily deteriorate the system performance. Next, we show that this queueing model may be the result of customers’ strategic behavior when only the last event is known. Finally, we investigate the historical admission control problem. We show that, under certain conditions, a deterministic policy with two thresholds may be optimal. This new policy is easy to implement and provides an improvement compared to the classical one-threshold policy.     

A Simple and Complete Computational Analysis of MAP/R/1 Queue Using Roots

In this paper, we present (in terms of roots) a simple closed-form analysis for evaluating system-length distribution at three epochs of time (arbitrary, pre-arrival, and post-departure) and queueing-time distribution (virtual and actual) of the MAP/R/1 queue, where R represents the class of distributions whose Laplace–Stieltjes transforms are rational functions. Our analysis is based on roots of the associated characteristic equations of the (i) vector-generating function of system-length distribution and (ii) Laplace–Stieltjes transform of the virtual queueing-time distribution. The proposed method for evaluating boundary probabilities is an alternative to the matrix-analytic method as well as spectral method. Numerical aspects have been tested for a variety of arrival and service-time (including matrix-exponential (ME)) distributions and a sample of numerical outputs is presented. The method is analytically quite simple and easy to implement. It is hoped that the results obtained would prove to be beneficial to both theoreticians and practitioners.     

Departures inGR^{X{n}} /G_n /\infty

Departure processes in infinite server queues with non-Poisson arrivals have not received much attention in the past. In this paper, we try to fill this gap by considering the continuous time departure process in a general infinite server system with a Markov renewal batch arrival process ofM different types of customers. By a conditional approach, analytical results are obtained for the generating functions and binomial moments of the departure process. Special cases are discussed, showing that while Poisson arrival processes generate Poisson departures, departure processes are much more complicated with non-Poisson arrivals.This research has been supported in part by the Natural Science and Engineering Research Council of Canada (Grant A5639).     

A markov-modulated M/M/1 queue with group arrivals

We study anM/M/1 group arrival queue in which the arrival rate, service time distributions and the size of each group arrival depend on the state of an underlying finite-state Markov chain. Using Laplace transforms and matrix analysis, we derive the results for the queue length process, its limit distribution and the departure process. In some special cases, explicit results are obtained which are analogous to known classic results.     

Analysis of a finite MAP/G/1 queue with group services

The finite capacity queues, GI/PH/1/N and PH/G/1/N, in which customers are served in groups of varying sizes were recently introduced and studied in detail by the author. In this paper we consider a finite capacity queue in which arrivals are governed by a particular Markov renewal process, called a Markovian arrival process (MAP). With general service times and with the same type of service rule, we study this finite capacity queueing model in detail by obtaining explicit expressions for (a) the steady-state queue length densities at arrivals, at departures and at arbitrary time points, (b) the probability distributions of the busy period and the idle period of the server and (c) the Laplace-Stieltjes transform of the stationary waiting time distribution of an admitted customer at points of arrivals. Efficient algorithmic procedures for computing the steady-state queue length densities and other system performance measures when services are of phase type are discussed. An illustrative numerical example is presented.