M/G/c/K blocking probability models and system performance

An exact solution for the M/G/c/K model is only possible for special cases, such as exponential service, a single server, or no waiting room at all. Instead of basing the approximation on an infinite capacity queue as is often the case, an approximation based on a closed-form expression derivable from the finite capacity exponential queue is presented. Properties of the closed-form expression along with its use in approximating the blocking probability of M/G/c/K systems are discussed. Extensive experiments are provided to test and verify the efficacy of our approximate results.     

Perturbation analysis of waiting times in the G/G/1 queue

This paper is devoted to perturbation analysis of the stationary distribution of waiting times in the G/G/1 queue with a parameter-dependent service time distribution. We provide sufficient conditions under which the stationary distribution is Lipschitz continuous and we explicitly compute the Lipschitz constant. Thereby, we provide bounds on the effect of a (finite) perturbation of the service time distribution on the stationary waiting time. The case of infinitesimal perturbations (read, derivatives) is treated as well.     

Analysis of the M/G/1 queue with discriminatory random order service policy

We consider an M/G/1 queue with different classes of customers and discriminatory random order service (DROS) discipline. The DROS discipline generalizes the random order service (ROS) discipline: when the server selects a customer to serve, all customers waiting in the system have the same selection probability under ROS discipline, whereas customers belonging to different classes may have different selection probabilities under DROS discipline. For the M/G/1 queue with DROS discipline, we derive equations for the joint queue length distributions and for the waiting time distributions of each class. We also obtain the moments of the queue lengths and the waiting time of each class. Numerical results are given to illustrate our results.     

A conservation law based approximate analysis for a class of simultaneous resource possession problems

In this paper we analyze a single server queueing model in which there are two types of jobs, one of which must wait in an external queue until a token is available, and only then may join the service queue. The interarrival times and service requirements for both types of jobs are assumed to be independent and exponentially distributed.

We derive the stability condition for such a model where the service queue discipline is either FCFS (First-Come-First-Serve) or PS (Processor-Sharing). We then propose analytic approximations for the mean waiting times for both types of jobs, relying heavily on the M/G/1 conservation law. Numerical results show that our approximations are very accurate (within a few percent of the simulated results) even when the system is heavily loaded. The approximations are also shown to be asymptotically exact as the number of tokens N → ∞.     

On the Overflow Process from a Finite Markovian Queue

We determine the distribution of the time between overflows for a single server Markovian queueing system with finite waiting room and state-dependent service and arrival rates. The result is subsequently used to analyse a GI/M/∞ system where the arrival process is the overflow process from the M/M/s/r queue.     

Comparison of stability and queueing times for reader-writer queues

A reader-writer queue manages two classes of customers: readers and writers. An unlimited number of readers can be processed in parallel; writers are processed serially. Both classes arrive according to a Poisson process. Reader and writer service times are general iid random variables. There is infinite room in the queue for waiting customers.

In this paper, a reader-writer queue is considered under the following priority disciplines: strong reader preference (SRP), reader preference (RP), alternating exhaustive priority (AEP), writer preference (WP), and strong writer preference (SWP). Preemptive priority is given to readers under the SRP discipline, or to writers under the SWP discipline. Non-preemptive priority is accorded to readers with the RP discipline, or to writers with the WP discipline. For the AEP discipline, customers of a given class are served exhaustively in an alternating fashion.

For the five priority disciplines, a stability condition and first moments for the steady-state reader and writer queueing times are given. Using these analytical results, each of the five priority disciplines is seen to be optimal (among the five) in some region of the parameter space. Simulation results are also presented.     

On a singular feature of critical G/M/1 queues

In this paper, we consider a critically loaded G/M/1 queue and contrast its transient behaviour with the transient behaviour of stable (or unstable) G/M/1 queues. We show that the departure process from a critical G/M/1 queue converges weakly to a Poisson process. However, as opposed to the stable (or unstable) case, we show that the departure process of a critical GI/M/1 queue does not couple in finite time with a Poisson process (even though it converges weakly to one). Thus, as the traffic intensity (ratio of arrival to service rates), , ranges over (0, ∞), the point = 1 represents a singularity with regard to the convergence mode of the departure process.     

Regulating an M/G/1 queue when customers know their demand

Customers do not necessarily join a queue at a socially optimal rate. Hence, queueing systems may call for regulation. For customers in an M/G/1 unobservable (not necessarily FCFS) queue and homogeneous with respect to waiting costs and service rewards, we show how queueing systems can be regulated by imposing an entry fee, a holding fee (based on time in the system), or a service fee (based on the required service time) when customers know their service requirements. We start with a unified approach and state the socially optimal fees. We show that customers are always worse off under a flat entry fee in comparison with holding and service fees. As for holding vs. service fees, the answer depends on the queueing regime and/or the service length itself. For example, under FCFS, service fees are preferred by all. Details are given on some common service regimes. We also review the case where customers know only the common distribution of service times, but not their actual requirements.     

Analysis of waiting time of M/G/1/K system with vacations under random scheduling and LCFS

This paper considers an M/G/1/K queueing system with multiple vacations under random scheduling and LCFS disciplines. As for M/G/1/K vacation models, Lee obtained the results of the joint distribution of the number of messages in the system and the remaining service or vacation time for a message. Using these expressions, we derive LSTs of the waiting time distribution under the two service disciplines. We show the calculation method for the first and the second moments of the waiting time under two service disciplines. Furthermore, we illustrate some numerical results of the mean waiting times and the coefficient of variations of the waiting time under FCFS, random scheduling and LCFS.     

Approximating the departure and the overflow processes from a G/G/K loss system

Both the departure and the overflow processes from a G/G/K loss system with generally distributed interarrival times, generally distributed service times, K parallel servers, no waiting room, and the random access processing discipline are approximated in steady state. Numerical results are provided and are compared against those from a simulation study.     

Stochastic bounds for queueing systems with limited service schedules

Motivated by the study of cyclic service queue processor schedules and token ring local area networks, upper and lower stochastic bounds for a GI/G/1 vacation model with limited service are developed. The limited service vacation model is compared with the Bernoulli schedule vacation model. For the case of Poisson arrivals and infinitely divisible vacation durations simple, closed-form expressions are given for upper and lower bounds of the first two moments of the waiting time. Some upper and lower bounds are also derived for cyclic queues with limited service. The quality of the bounds is illustrated through numerical examples.     

Computing steady state probabilities in λ(n)/G/1/K queue

In this paper a recursive method is developed to obtain the steady state probability distribution of the number in system at arbitrary and departure time epochs of a single server state-dependent arrival rate queue λ(n)/G/1/K in which the arrival process is Markovian with arrival rates λ(n) which depend on the number of customers n in the system and general service time distribution. It is assumed that there exists an integer K such that λ(n) > 0 for all 0 n < K and λ(n) = 0 for all n K. Numerical results have been presented for many queueing models by suitably defining the function λ(n). These include machine interference model, queues with balking, queues with finite waiting space and machine interference model with finite waiting space. These models have wide application in computer/communication networks.     

Analysis of a BMAP/D/1-Timer Multiplexer

In this paper we introduce and analyze a model of a multiplexer queue with a batch Markovian arrival process and a special, timer based, non-work-conserving service discipline. We show that the embedded process at departures is an M/G/1 type process with proper state partitioning, which can be efficiently analyzed by matrix geometric methods. We derive the expressions to compute the distribution of the waiting time. The paper ends with numerical experiments, and points out some interesting features of the system.     

非强占有限优先权M/G/1排队系统

针对部分数据帧有完全优先权发送的计算机网络数据服务系统存在的网络拥塞风险问题,提出了一种非强占有限优先权M/G/1排队系统模型的方法。该系统模型引入控制完全优先权的参数n,使得数据帧的完全优先权变成有限优先权,考虑了不同优先级队伍之间的公平性,降低了计算机网络数据服务系统拥塞的风险,使得网络系统在有限优先权下有较好的稳定性。在模型研究中,运用全概率拆解方法获得各级队伍平均等待时间、平均逗留时间和平均队长的理论结果。对模型采用Matlab 2010a软件实验仿真,实验得到的各级队伍平均等待时间和理论平均等待时间的平均绝对误差为0.951%。实验中,有限优先权条件下各级顾客的平均等待时间比值显著小于完全优先权条件下各级顾客的平均等待时间比值。实验结果表明对非强占有限优先权M/G/1排队系统模型研究的理论结果是正确的,该模型具有更稳定的系统特性。     

Analysis of the discrete-time Geo/G/1 working vacation queue and its application to network scheduling

In this paper we present an exact steady-state analysis of a discrete-time Geo/G/1 queueing system with working vacations, where the server can keep on working, but at a slower speed during the vacation period. The transition probability matrix describing this queuing model can be seen as an M/G/1-type matrix form. This allows us to derive the probability generating function (PGF) of the stationary queue length at the departure epochs by the M/G/1-type matrix analytic approach. To understand the stationary queue length better, by applying the stochastic decomposition theory of the standard M/G/1 queue with general vacations, another equivalent expression for the PGF is derived. We also show the different cases of the customer waiting to obtain the PGF of the waiting time, and the normal busy period and busy cycle analysis is provided. Finally, we discuss various performance measures and numerical results, and an application to network scheduling in the wavelength division-multiplexed (WDM) system illustrates the benefit of this model in real problems.     

A note on mixed exponential approximations for Gi/G/1 waiting times

A method is offered for the effective estimation of the stationary waiting-time distribution of the GI/G/1 queue by a (possibly nonconvex) mixed exponential CDF. The approach relies on obtaining a generalized exponential mixture as an approximation for the distribution of the service times. This is done by the adaptation of a nonlinear optimization algorithm previously developed for the maximum-likelihood estimation of parameters from mixed Weibull distributions. The approach is particularly well-suited for obtaining the delay distribution beginning from raw interarrivai and service-time data.     

Analysis of a finite buffer queue with different scheduling and push-out schemes

A queueing system M₁, M₂/G₁, G₂/1/N with different scheduling and push-out scheme is analyzed in this paper. This work is motivated by the study of the performance of an output link of ATM switches with traffic of two classes with different priorities. However, the queueing model developed in this paper is more general than that of the output link of ATM switches with two-class priority traffic. General service time distributions are allowed for classes 1 and 2 and a general service discipline function, ₁(i, j), is introduced where ₁(i, j) is the probability that a class 1 packet will be served, given that there are i class 1 and j class 2 packets waiting for service. An exact solution is obtained for the loss probabilities for classes 1 and 2, the queue length distribution and the mean waiting time for class 1. The queue length distribution and the mean waiting time for class 2 are calculated approximately. It is shown that the approximation is an upper bound and the error due to the approximation is very small when the loss probability of class 2 is small (e.g., less than 0.01).     

Steady state analysis of the GI/M/1/N queue with a variant of multiple working vacations

This paper studies the GI/M/1/N queue with a variant of multiple working vacations, where the server leaves for a working vacation as soon as the system becomes empty. The server takes at most H consecutive working vacations if the system remains empty after the end of a working vacation. Employing the supplementary variable and embedded Markov chain methods, we obtain the queue length distribution at different time epochs. Based on the various system length distribution, the probability of blocking, mean waiting times and mean system lengths have been derived. Finally, numerical results are discussed.     

基于离散时间排队的ARQ性能分析

基于自动请求重传(ARQ)协议的工作原理,提出基于离散时间带有启动机制的Geom/G/1排队模型。使用嵌入马尔可夫链方法推导出排队系统的稳态队长、等待时间、忙期和忙循环等性能指标的解析表达式,给出ARQ协议中数据帧的平均响应时间、信道利用率、系统吞吐量等性能指标的解析表达式。利用仿真工具Matlab进行计算机仿真,数值例子证明了性能指标解析表达式的正确性。     

Information theoretic approximations for M/G/1 and G/G/1 queuing systems

Summary This paper presents new results concerning the use of information theoretic inference techniques in system modeling and concerning the widespread applicability of certain simple queuing theory formulas. For the case when an M/G/1 queue provides a reasonable system model but when information about the service time probability density is limited to knowledge of a few moments, entropy maximization and cross-entropy minimization are used to derive information theoretic approximations for various performance distributions such as queue length, waiting time, residence time, busy period, etc. Some of these approximations are shown to reduce to exact M/M/1 results when G = M. For the case when a G/G/1 queue provides a reasonable system model, but when information about the arrival and service distributions is limited to the average arrival and service rates, it is shown that various well known M/M/1 formulas are information theoretic approximations. These results not only provide a new method for approximating the performance distributions, but they help to explain the widespread applicability of the M/M/1 formulas.