Smoothed perturbation analysis algorithms for estimating the derivatives of occupancy-related functions in serial queueing networks

We present unbiased Smoothed Perturbation Analysis (SPA) estimators for the derivatives of occupancy-related performance functions in serial networks ofG/G/1 queues with respect to parameters of the distributions of service times at the queues. The sample functions for these performance measures are piecewise constant, and established Infinitesimal Perturbation Analysis (IPA) methods typically fail to provide unbiased estimators in this case. The performance measures considered in this paper are: the average network occupancy as seen by an arrival, the average occupancy of a specific queue as seen by an arrival to it, the probability that a customer is blocked at a specific queue, and the probability that a customer leaves a queue idle. The SPA estimators derived are quite simple and flexible, and they lend themselves to straightforward analysis. Unlike most of the established SPA algorithms, ours are not based on the comparison of hazard rates, and the proofs of their unbiasedness do not require the boundedness of such hazard rates.Supported in part by the National Science Foundation under Grant ECS-8801912, by the Office of Naval Research under Contract N00014-87-K-0304, and by NASA under Contract NAG 2-595.     

On the Queue Length Distribution for the GI/G/1/K/VM Queue

Abstract

We present a transform-free distribution of the steady-state queue length for the GI/G/1/K queueing system with multiple vacations under exhaustive FIFO service discipline. The method we use is a modified supplementary variable technique and the result we obtain is expressed in terms of conditional expectations of the remaining service time, the remaining interarrival time, and the remaining vacation, conditional on the queue length at the embedded points. The case K → ∞ is also considered.     

Convergence of a stochastic approximation algorithm for the GI/G/1 queue using infinitesimal perturbation analysis

Discrete-event systems to which the technique of infinitesimal perturbation analysis (IPA) is applicable are natural candidates for optimization via a Robbins-Monro type stochastic approximation algorithm. We establish a simple framework for single-run optimization of systems with regenerative structure. The main idea is to convert the original problem into one in which unbiased estimators can be derived from strongly consistent IPA gradient estimators. Standard stochastic approximation results can then be applied. In particular, we consider the GI/G/1 queue, for which IPA gives strongly consistent estimators for the derivative of the mean system time. Convergence (w.p.1) proofs for the problem of minimizing the mean system time with respect to a scalar service time parameter are presented.     

Maximum likelihood estimation for single server queues from waiting time data

Maximum likelihood estimators for the parameters of a GI/G/1 queue are derived based on the information on waiting times {W _t },t=1,...,n, ofn successive customers. The consistency and asymptotic normality of the estimators are established. A simulation study of the M/M/1 and M/E _k /1 queues is presented.     

Error analysis for regenerative queueing estimators with special reference to gradient estimators via likelihood ratio

The performance of telecommunications systems is typically estimated (either analytically or by simulation) via queueing theoretic models. The gradient of the expected performance with respect to the various parameters (such as arrival rate or service rate) is very important as it not only measures the sensitivity to change, but is also needed for the solution of optimization problems. While the estimator for the expected performance is the sample mean of the simulation experiment, there are several possibilities for the estimator of the gradient. They include the obvious finite difference approximation, but also other recently advocated techniques, such as estimators derived from likelihood ratio transformations or from infinitesimal perturbations. A major problem in deciding upon which estimator to use and in planning the length of the simulation has been the scarcity of analytical error calculations for estimators of queueing models. It is this question that we answer in this paper for the waiting time moments (of arbitrary order) of theM / G / 1 queue by using the queueing analysis technique developed by Shalmon. We present formulas for the error variance of the estimators of expectation and of its gradient as a function of the simulation length; at arbitrary traffic intensity the formulas are recursive, while the heavy traffic approximations are explicit and of very simple form. For the gradient of the mean waiting time with respect to the arrival (or service) rate, and at 1 percent relative precision, the heavy traffic formulas show that the likelihood ratio estimator for the gradient reduces the length of the simulation required by the finite difference estimator by about one order of magnitude; further increasing the relative precision by a factor increases the reduction advantage by the same factor. At any relative precision, it exceeds the length of the simulation required for the estimation of the mean with the same relative precision by about one order of magnitude. While strictly true for theM / G / 1 queue, the formulas can also be used as guidelines in the planning of queueing simulations and of stochastic optimizations of complex queueing systems, particularly those with Poisson arivals.     

A unified algorithm for computing the stationary queue length distributions inM(k)/G/1/N and GI/M(k)/1/N queues

An iterative algorithm is developed for computing numerically the stationary queue length distributions in M/G/1/N queues with arbitrary state-dependent arrivals, or simply M(k)/G/1/N queues. The only input requirement is the Laplace-Stieltjes transform of the service time distribution.In addition, the algorithm can also be used to obtain the stationary queue length distributions in GI/M/1/N queues with state-dependent services, orGI/M(k)/1/N, after establishing a relationship between the stationary queue length distributions inGI/M(k)/1/N and M(k)/G/1/N+1 queues.Finally, we elaborate on some of the well studied special cases, such asM/G/1/N queues,M/G/1/N queues with distinct arrival rates (which includes the machine interference problems), andGI/M/C/N queues. The discussions lead to a simplified algorithm for each of the three cases.     

A decomposition theorem and related results for the discriminatory processor sharing queue

In this paper, we study a discriminatory processor sharing queue with Poisson arrivals,K classes and general service times. For this queue, we prove a decomposition theorem for the conditional sojourn time of a tagged customer given the service times and class affiliations of the customers present in the system when the tagged customer arrives. We show that this conditional sojourn time can be decomposed inton+1 components if there aren customers present when the tagged customer arrives. Further, we show that thesen+1 components can be obtained as a solution of a system of non-linear integral equations. These results generalize known results about theM/G/1 egalitarian processor sharing queue.     

Fluid approximation and its convergence Rate for GI/G/1 queue with vacations

A GI/G/1 queue with vacations is considered in this paper.We develop an approximating technique on max function of independent and identically distributed(i.i.d.) random variables,that is max{ηi,1 ≤ i ≤ n}.The approximating technique is used to obtain the fluid approximation for the queue length,workload and busy time processes.Furthermore,under uniform topology,if the scaled arrival process and the scaled service process converge to the corresponding fluid processes with an exponential rate,we prove by the...     

A new proof of finite moment conditions for GI/G/1 busy periods

A generalization of the GI/G/1 queue is considered where the service time of the nth customer and the inter-arrival time between arrivalsn andn+1 may be dependent random variables. New proofs are obtained of finite moment conditions for busy periods and the ladder epochs of a corresponding random walk. The method of proof, which is much different from the usual ones, directly relates busy period moments to virtual and actual delay moments.     

Stationary tail asymptotics of a tandem queue with feedback

Motivated by applications in manufacturing systems and computer networks, in this paper, we consider a tandem queue with feedback. In this model, the i.i.d. interarrival times and the i.i.d. service times are both exponential and independent. Upon completion of a service at the second station, the customer either leaves the system with probability p or goes back, together with all customers currently waiting in the second queue, to the first queue with probability 1−p. For any fixed number of customers in one queue (either queue 1 or queue 2), using newly developed methods we study properties of the exactly geometric tail asymptotics as the number of customers in the other queue increases to infinity. We hope that this work can serve as a demonstration of how to deal with a block generating function of GI/M/1 type, and an illustration of how the boundary behaviour can affect the tail decay rate.     

The Unconditional Sojourn Time Distribution in the Queue GI/M/1-K with Processor Sharing Service

We consider a processor shared GI/M/1 queue which can accommodate a finite number K of customers. Using singular perturbation techniques, we construct asymptotic expansions for the distribution of a tagged customer's sojourn time. We assume that K is large and treat several different cases of the model parameters.     

Fluid queue driven by aGI/GI/1 queue

Consider a model consisting of two phases: the GI/GI/1 queue and a buffer which is fed by a fluid arriving from a single-server queue. The fluid output from the GI/GI/1 queue is of the on/off type with on- and off-periods distributed as successive busy and idle periods in the GI/GI/1 queue. The fluid pours out of the buffer at a constant rate. The steady-state performance of this model is studied. We derive the Laplace-Stieltjes transform of the stationary distribution function of the buffer content in the case of the M/GI/1 queue in the first phase. It is shown that this distribution depends on the form of the service-time distribution. Therefore, the replacement of an M/GI/1 queue by an M/M/1 queue is not correct, in general. Continuity estimates are derived in the cast where the buffer is fed from the GI/GI/1 queue. Proceedings of the Seminar on Stability Problems for Stochastic Models, Moscow Russia, 1996, Part II.     

Second derivative estimation using harmonic analysis

Simulation sensitivity analysis is an important problem for simulation practitioners analyzing complex systems. The significance of this problem has resulted in the development of various gradient estimators that can be used to address this issue. Although higher derivative estimators have been discussed concurrently, less attention has been given to assess the efficiency and feasibility of computing such estimators. In this paper, two second derivative estimators are presented. The first estimators, called the HFD estimators, combine harmonic gradient estimators with finite differences second derivative estimators. The resulting hybrid estimators requireO(p) fewer simulation runs to implement compared to the straightforward finite differences approach, wherep is the number of input parameters in the simulation model. The second estimators, called the HA estimators, incorporate harmonic analysis directly, requiring one or two simulation runs to implement, depending on whether a control variate simulation run is made. Expressions for the bias and the variance of the HFD and the HA estimators (with and without variance reduction techniques) are derived. Optimal mean squared error convergence rates are also discussed. In particular, the convergence rates for both these estimators are shown to be the same, though the computational performance of the HFD estimators is better than that for the HA estimators on anM/M/1 queue simulation model. Computational results for the HFD estimators on an (s, S) inventory system simulation model are also included.     

The variance of departure processes: puzzling behavior and open problems

We consider the variability of queueing departure processes. Previous results have shown the so-called BRAVO effect occurring in M/M/1/K and GI/G/1 queues: Balancing Reduces Asymptotic Variance of Outputs. A factor of (1?2/??) appears in GI/G/1 and a factor of 1/3 appears in M/M/1/K, for large K. A missing piece in the puzzle is the GI/G/1/K queue: Is there a BRAVO effect? If so, what is the variability? Does 1/3 play a role? This open problem paper addresses these questions by means of numeric and simulation results. We conjecture that at least for the case of light tailed distributions, the variability parameter is 1/3 multiplied by the sum of the squared coefficients of variations of the inter-arrival and service times.     

TheM/G/1 queue with processor sharing and its relation to a feedback queue

The central model of this paper is anM/M/1 queue with a general probabilistic feedback mechanism. When a customer completes his ith service, he departs from the system with probability 1–p(i) and he cycles back with probabilityp(i). The mean service time of each customer is the same for each cycle. We determine the joint distribution of the successive sojourn times of a tagged customer at his loops through the system. Subsequently we let the mean service time at each loop shrink to zero and the feedback probabilities approach one in such a way that the mean total required service time remains constant. The behaviour of the feedback queue then approaches that of anM/G/1 processor sharing queue, different choices of the feedback probabilities leading to different service time distributions in the processor sharing model. This is exploited to analyse the sojourn time distribution in theM/G/1 queue with processor sharing.Some variants are also considered, viz., anM/M/1 feedback queue with additional customers who are always present, and anM/G/1 processor sharing queue with feedback.     

On some relations between stationary time and customer state probabilities for qneueing systems G/GI/s/r

By means of a general formula for stochastic processes with imbedded marked point processes (PMP) some necessary and sufficient condition is given for the validity of a relationship, which is well-known in the case of exponentially distributed service times, between stationary time and customer state probabilities for loss systems G/GI/s/O (Theorem 3). A result of Miyazawa for the GI/GI/l/∞ queue is generalized to the case of non-recurrent interarrival times (Theorem 4)-. Furthermore, bounds are derived for the mean increment of the waiting time process at arrival epochs and for the mean actual waiting time in multi-server queues.     

Models and Approximations for Call Center Design

A call center is a facility for delivering telephone service, both incoming and outgoing. This paper addresses optimal staffing of call centers, modeled as M/G/n queues whose offered traffic consists of multiple customer streams, each with an individual priority, arrival rate, service distribution and grade of service (GoS) stated in terms of equilibrium tail waiting time probabilities or mean waiting times. The paper proposes a methodology for deriving the approximate minimal number of servers that suffices to guarantee the prescribed GoS of all customer streams. The methodology is based on an analytic approximation, called the Scaling-Erlang (SE) approximation, which maps the M/G/n queue to an approximating, suitably scaled M/G/1 queue, for which waiting time statistics are available via the Pollaczek-Khintchine formula in terms of Laplace transforms. The SE approximation is then generalized to M/G/n queues with multiple types of customers and non-preemptive priorities, yielding the Priority Scaling-Erlang (PSE) approximation. A simple goal-seeking search, utilizing SE/PSE approximations, is presented for the optimal staffing level, subject to GoS constraints. The efficacy of the methodology is demonstrated by comparing the number of servers estimated via the PSE approximation to their counterparts obtained by simulation. A number of case studies confirm that the SE/PSE approximations yield optimal staffing results in excellent agreement with simulation, but at a fraction of simulation time and space.     

Massively time-parallel,approximate simulation of loss queueing systems

A time-parallel simulation obtains parallelism by partitioning the time domain of the simulation. An approximate time-parallel simulation algorithm named GG1K is developed for acyclic networks of loss FCFSG/G/1/K queues. The GG1K algorithm requires two phases. In the first phase, a similar system (i.e. aG/G/1/ queue) is simulated using the GLM algorithm. Then the resultant trajectory is transformed into an approximateG/G/1/K trajectory in the second phase. The closeness of the approximation is investigated theoretically and experimentally. Our results show that the approximation is highly accurate except whenK is very small (e.g. 5) in certain models. The algorithm exploits unbounded parallelism and can achieve near-linear speedup when the number of arrivals simulated is sufficiently large.     

Estimation of a Location Parameter with Restrictions or “vague information” for Spherically Symmetric Distributions

In this article we consider estimating a location parameter of a spherically symmetric distribution under restrictions on the parameter. First we consider a general theory for estimation on polyhedral cones which includes examples such as ordered parameters and general linear inequality restrictions. Next, we extend the theory to cones with piecewise smooth boundaries. Finally we consider shrinkage toward a closed convex set K where one has vague prior information that θ is in K but where θ is not restricted to be in K. In this latter case we give estimators which improve on the usual unbiased estimator while in the restricted parameter case we give estimators which improve on the projection onto the cone of the unbiased estimator. The class of estimators is somewhat non-standard as the nature of the constraint set may preclude weakly differentiable shrinkage functions. The technique of proof is novel in the sense that we first deduce the improvement results for the normal location problem and then extend them to the general spherically symmetric case by combining arguments about uniform distributions on the spheres, conditioning and completeness.     

On the Number of Lost Customers in Stationary Loss Systems in the Light Traffic Case

For the stationary loss systems M/M/m/K and GI/M/m/K, we study two quantities: the number of lost customers during the time interval (0,t] (the first system only), and the number of lost customers among the first n customers to arrive (both systems). We derive explicit bounds for the total variation distances between the distributions of these quantities and compound Poisson–geometric distributions. The bounds are small in the light traffic case, i.e., when the loss of a customer is a rare event. To prove our results, we show that the studied quantities can be interpreted as accumulated rewards of stationary renewal reward processes, embedded into the queue length process or the process of queue lengths immediately before arrivals of new customers, and apply general results by Erhardsson on compound Poisson approximation for renewal reward processes.