Multi-Server Queueing Systems with Multiple Priority Classes

We present the first near-exact analysis of an M/PH/k queue with m > 2 preemptive-resume priority classes. Our analysis introduces a new technique, which we refer to as Recursive Dimensionality Reduction (RDR). The key idea in RDR is that the m-dimensionally infinite Markov chain, representing the m class state space, is recursively reduced to a 1-dimensionally infinite Markov chain, that is easily and quickly solved. RDR involves no truncation and results in only small inaccuracy when compared with simulation, for a wide range of loads and variability in the job size distribution. Our analytic methods are then used to derive insights on how multi-server systems with prioritization compare with their single server counterparts with respect to response time. Multi-server systems are also compared with single server systems with respect to the effect of different prioritization schemes—“smart” prioritization (giving priority to the smaller jobs) versus “stupid” prioritization (giving priority to the larger jobs). We also study the effect of approximating m class performance by collapsing the m classes into just two classes. Supported by NSF Career Grant CCR-0133077, NSF Theory CCR-0311383, NSF ITR CCR-0313148, and IBM Corporation via Pittsburgh Digital Greenhouse Grant 2003. AMS subject classification: 60K25, 68M20, 90B22, 90B36     

Equivalences of Batch-Service Queues and Multi-Server Queues and Their Complete Simple Solutions in Terms of Roots

Abstract

In this article, we first present a unified discussion of several equivalence relationships among (as well as between) batch-service queues and multi-server queues, in terms of the stationary queue-length and waiting-time distributions. Then, we present a complete and simple solution for the queue-length and waiting-time distributions of the discrete-time multi-server deterministic-service Geo/D/b queue, in terms of roots of the so-called characteristic equation. This solution also represents the solutions for the other equivalent queues, as a result of the equivalence relationships. To aid in the applications of these results, sample numerical results are presented at the end.     

非强占优先权下的M/M/1排队

分析带有两个优先权的非强占M/M/1系统的性能,用补充变量法构造向量马尔可夫过程对此排队系统的状态转移方程进行分析,得到两类顾客在非强占优先权的队长联合分布的母函数,进一步讨论,得出了服务台被两类顾客占有和闲置的概率以及两类信元各自的平均队长.     

Optimal Policies for Multi-server Non-preemptive Priority Queues

We consider a multi-server non-preemptive queue with high and low priority customers, and a decision maker who decides when waiting customers may enter service. The goal is to minimize the mean waiting time for high-priority customers while keeping the queue stable. We use a linear programming approach to find and evaluate the performance of an asymptotically optimal policy in the setting of exponential service and inter-arrival times.     

带有阈值转换和启动时间的优先权排队

在诸如ＩＳＤＮ的通信网络中,多种信息共用一条线路,为了满足不同类型信息的服务质量要求,带有阈值转换的优先权排队系统应是一种合适的模型。本文研究单服务员、两类顾客的带有阈值转换和启动时间的优先权排队系统,首先,分别就抢占和非抢占情形讨论了具有泊松到达、服务时间和启动时间均有指数贩系统,然后就非抢占情况进上步考虑了服务时间和启动时间有一般分布的系统,求出了系统中两类顾客队长的稳态联合概率母函数,藉助这     

Many-Sources Delay Asymptotics with Applications to Priority Queues

In this paper, we study discrete-time priority queueing systems fed by a large number of arrival streams. We first provide bounds on the actual delay asymptote in terms of the virtual delay asymptote. Then, under suitable assumptions on the arrival process to the queue, we show that these asymptotes are the same. As an application of this result, we then consider a priority queueing system with two queues. Using the earlier result, we derive an upper bound on the tail probability of the delay. Under certain assumptions on the rate function of the arrival process, we show that the upper bound is tight. We then consider a system with Markovian arrivals and numerically evaluate the delay tail probability and validate these results with simulations.     

Tail Asymptotics for HOL Priority Queues Handling a Large Number of Independent Stationary Sources

In this paper we study the asymptotics of the tail of the buffer occupancy distribution in buffers accessed by a large number of stationary independent sources and which are served according to a strict HOL priority rule. As in the case of single buffers, the results are valid for a very general class of sources which include long-range dependent sources with bounded instantaneous rates. We first consider the case of two buffers with one of them having strict priority over the other and we obtain asymptotic upper bound for the buffer tail probability for lower priority buffer. We discuss the conditions to have asymptotic equivalents. The asymptotics are studied in terms of a scaling parameter which reflects the server speed, buffer level and the number of sources in such a way that the ratios remain constant. The results are then generalized to the case of M buffers which leads to the source pooling idea. We conclude with numerical validation of our formulae against simulations which show that the asymptotic bounds are tight. We also show that the commonly suggested reduced service rate approximation can give extremely low estimates.     

Predicting Time-Dependent Distributions of Queues and Delays for Road Traffic at Roundabouts and Priority Junctions

Vehicle queues and delays at busy road junctions have to be treated time-dependently when the traffic demand and the available capacity are approximately equal. Existing methods allow the queue length at a given time to be directly estimated as an average over all possible evolutions of the queueing system consistent with the given initial conditions and the time-dependent arrival and service rates. The paper describes the development of methods to predict the underlying distributions. Estimates of the variance and the overall frequency distribution for queue length and delay are obtained by simulating an M/M/1 queueing model with parameters varying with time. Predictive models are developed to represent the simulation results. They require as input values of parameters describing the duration of the peak and the time-average traffic intensities and capacities.     

Nonpreemptive flowshop scheduling with machine dominance

Flowshop scheduling deals with processing a set of jobs through a set of machines, where all jobs have to pass among machines in the same order. With the exception of minimizing a makespan on two machines, almost all other flowshop problems in a general setup are known to be computationally intractable. In this paper we study special cases of flowshop defined by additional machine dominance constraints. These constraints impose certain relations among the job processing times on different machines and make the studied problems tractable.     

Heavy Tails in Multi-Server Queue

In this paper, the asymptotic behaviour of the distribution tail of the stationary waiting time W in the GI/GI/2 FCFS queue is studied. Under subexponential-type assumptions on the service time distribution, bounds and sharp asymptotics are given for the probability P{W > x}. We also get asymptotics for the distribution tail of a stationary two-dimensional workload vector and of a stationary queue length. These asymptotics depend heavily on the traffic load. AMS subject classification: 60K25     

On Nonpreemptive LCFS Scheduling with Deadlines

We investigate some real time behaviour of a (discrete time) single server system with nonpreemptive LCFS task scheduling. The main results deal with the probability distribution of a random variable SRD(T), which describes the time the system operates without any violation of a fixed task service time deadline T. A tree approach, similar to those already used for the derivation of the same quantities for other scheduling disciplines (e.g., FCFS) is suitable here again, establishing the power of such techniques once more. Relying on a simple general probability model, asymptotic formulas concerning all moments of SRD(T) are determined; for example, the expectation of SRD(T) is proved to grow exponentially in T, i.e., E[SRD(T)] ∼ CT^3/2ρ^T for some ρ > 1. Our computations rely on a multivariate (asymptotic) coefficient extraction technique which we call asymptotic separation.     

多服务台可修系统的优化分析

机器可修系统是可修排队的一个重要研究方向,研究了具有止步,中途退出和服务台可发生故障的M/M/R机器可修问题.利用矩阵几何解法,得到了稳态概率的矩阵几何解,在此基础上建立了系统的费用模型,并进行了数值分析.     

Work-Conserving Tandem Queues

Consider a tandem queue of two single-server stations with only one server for both stations, who may allocate a fraction α of the service capacity to station 1 and 1−α to station 2 when both are busy. A recent paper treats this model under classical Poisson, exponential assumptions.Using work conservation and FIFO, we show that on every sample path (no stochastic assumptions), the waiting time in system of every customer increases with α. For Poisson arrivals and an arbitrary joint distribution of service times of the same customer at each station, we find the average waiting time at each station for α = 0 and α = 1. We extend these results to k ≥ 3 stations, sample paths that allow for server breakdown and repair, and to a tandem arrangement of single-server tandem queues.This revised version was published online in June 2005 with corrected coverdate     

On Markovian Multi-Class,Multi-Server Queueing

Multi-class multi-server queueing problems are a generalisation of the well-known M/M/k queue to arrival processes with clients of N types that require exponentially distributed service with different average service times. In this paper, we give a procedure to construct exact solutions of the stationary state equations using the special structure of these equations. Essential in this procedure is the reduction of a part of the problem to a backward second order difference equation with constant coefficients. It follows that the exact solution can be found by eigenmode decomposition. In general eigenmodes do not have a simple product structure as one might expect intuitively. Further, using the exact solution, all kinds of interesting performance measures can be computed and compared with heuristic approximations (insofar available in the literature). We provide some new approximations based on special multiplicative eigenmodes, including the dominant mode in the heavy traffic limit. We illustrate our methods with numerical results. It turns out that our approximation method is better for higher moments than some other approximations known in the literature. Moreover, we demonstrate that our theory is useful to applications where correlation between items plays a role, such as spare parts management.     

Nonpreemptive open shop with restricted processing times

A polynomial time algorithm was given by Fiala for the nonpreemptivem-processor open shop problem whenever the sum of processing times for one processor is large enough with respect to the maximal processing time. Here a special case where all processing times are from a bounded cardinality set of nonnegative integers is studied. For such a situation we give anO(nm) algorithm while the algorithm of Fiala works inO(n ² m ³) wheren is the number of jobs.     

Queues with random back-offs

We consider a broad class of queueing models with random state-dependent vacation periods, which arise in the analysis of queue-based back-off algorithms in wireless random-access networks. In contrast to conventional models, the vacation periods may be initiated after each service completion, and can be randomly terminated with certain probabilities that depend on the queue length. We first present exact queue-length and delay results for some specific cases and we derive stochastic bounds for a much richer set of scenarios. Using these, together with stochastic relations between systems with different vacation disciplines, we examine the scaled queue length and delay in a heavy-traffic regime, and demonstrate a sharp trichotomy, depending on how the activation rate and vacation probability behave as function of the queue length. In particular, the effect of the vacation periods may either (i) completely vanish in heavy-traffic conditions, (ii) contribute an additional term to the queue lengths and delays of similar magnitude, or even (iii) give rise to an order-of-magnitude increase. The heavy-traffic trichotomy provides valuable insight into the impact of the back-off algorithms on the delay performance in wireless random-access networks.