Abstracts

C. Knessl and C. Tier, Asymptotic approximations and bottleneck analysis in product form queueing networks with large populations , Performance Evaluation 41 , 1992, 480-488.
Abstract

Asymptotic approximations are constructed for the performance measures of product form queueing networks consisting of single server, fixed rate nodes with large populations. The approximations are constructed by applying singular perturbation methods to the recursion equations of Mean Value Analysis. Networks with a single job class are studied first to illustrate the use of perturbation techniques. The leading term in the approximation is related to bottleneck analysis, but fails to be accurate if there is more than one bottleneck node. A uniform approximation is constructed which is valid for networks with many bottleneck nodes. The accuracy of the uniform approximation is demonstrated for both small and large population sizes. Next, multiclass networks are considered. The leading term in the asymptotic approximation is again related to bottleneck analysis but fails to be valid across ``switching surfaces''. Across these the bottleneck nodes of the network change as a function of the fraction of jobs in the different job classes. A boundary layer correction is constructed near the switching surfaces which provides an asymptotic connection across the switching surfaces. Numerical examples are presented to demonstrate the accuracy of the results. We illustrate the asymptotic approach on some simple networks and indicate how to treat more complicated problems.

Download paper -- pdf version
C. Knessl and C. Tier, Applications of singular perturbation methods in queueing, Advances in Queueing: Theory, Methods and Open Problems, edited by J.H. Dshalalow, CRC Press, 1995, 311-336.

Abstract
A survey is presented describing the application of singular perturbation techniques to queueing systems. The goal is to compute performance measures by constructing approximate solutions to specific problems involving either the Kolmogorov forward or backward equation which contain a small parameter. These techniques are particularly useful on problems for which exact solutions are not available. Four different classes of problems are surveyed: (i) state-dependent queues; (ii) systems with a processor-sharing server; (iii) queueing networks; (iv) time dependent behavior. For each class, an illustrative example is presented along with the direction of current research.

Download paper -- ps version     pdf version
C. Knessl and C. Tier, Mean time for the development of large workloads and large queue lengths in the GI/G/1 queue, Journal of Applied Mathematics and Stochastic Analysis 9,1996, 107-142.

Abstract
We consider the GI/G/1 queue described by either the workload U(t) (unfinished work) or the number of customers N(t) in the system. We compute the mean time until U(t) reaches or exceeds the level K, and also the mean time until N(t) reaches N0. For the M/G/1 and GI/M/1 models, we obtain exact contour integral representations for these mean first passage times. We then compute the mean times asymptotically, as K and N0 approaches infinity, by evaluating these contour integrals. For the general GI/G/1 model, we obtain asymptotic results by a singular perturbation analysis of the appropriate backward Kolmogorov equation(s). Numerical comparisons show that the asymptotic formulas are very accurate even for moderate values of K and N0.

Download paper -- ps version     pdf version
D.I. Choi, C. Knessl and C. Tier, A queueing system with queue length dependent service times, with application to cell discarding in ATM networks, Journal of Applied Mathematics and Stochastic Analysis , to appear.

Abstract
A queueing system (M/G1,G2/1/K) is considered in which the service time of a customer entering service depends on whether the queue length, N(t), is above or below a threshold L. The arrival process is Poisson and the general service times S1 and S2 depend on whether the queue length at the time service is initiated is < L or >= L , respectively. Balance equations are given for the stationary probabilities of the Markov process (N(t),X(t)) where X(t) is the remaining service time of the customer currently in service. Exact solutions for the stationary probabilities are constructed for both infinite and finite capacity systems. Asymptotic approximations of the solutions are given, which yield simple formulas for performance measures such as loss rates and tail probabilities. The numerical accuracy of the asymptotic results is tested.

Download paper -- ps version     pdf version


Abstract
We consider two tandem queues with exponential servers. Arrivals to the first queue are governed by a general renewal process. If the arrivals were also exponentially distributed, this would be a simple example of a Jackson network. However, the structure of the model is much more complicated for general arrivals. We analyze the joint steady-state queue length distribution for this network, in the heavy traffic limit, where the arrival rate is only slightly less than the service rates. We formulate and solve the boundary value problem for the diffusion approximation to this model. We obtain simple integral representations for the (asymptotic) steady-state queue length distribution. We also do a detailed study of the tail behavior of the diffusion approximation.

by Charles Tier


Go back to my Home Page