Asymptotics for the sojourn time distribution in the queue defined by a general QBD process with a countable phase space

We consider a FIFO queue defined by a QBD process. When the number of phases of the QBD process is finite, it has been proved that the stationary distribution of sojourn times in that queue can be represented as a phase-type distribution. In this paper, we extend this result to the case where the number of phases of the QBD process is countably many and obtain several kinds of asymptotic formula for the steady-state tail probability of sojourn times in the queue when the tail probability decays in exact exponential form.     

Sojourn Times in the <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">PH</Emphasis>/1 Processor Sharing Queue

We give in this paper an algorithm to compute the sojourn time distribution in the processor sharing, single server queue with Poisson arrivals and phase type distributed service times. In a first step, we establish the differential system governing the conditional sojourn times probability distributions in this queue, given the number of customers in the different phases of the PH distribution at the arrival instant of a customer. This differential system is then solved by using a uniformization procedure and an exponential of matrix. The proposed algorithm precisely consists of computing this exponential with a controlled accuracy. This algorithm is then used in practical cases to investigate the impact of the variability of service times on sojourn times and the validity of the so-called reduced service rate (RSR) approximation, when service times in the different phases are highly dissymmetrical. For two-stage PH distributions, we give conjectures on the limiting behavior in terms of an M/M/1 PS queue and provide numerical illustrative examples.This revised version was published online in June 2005 with corrected coverdate     

Sojourn time distribution in a MAP/M/1 processor-sharing queue

This paper considers the sojourn time distribution in a processor-sharing queue with a Markovian arrival process and exponential service times. We show a recursive formula to compute the complementary distribution of the sojourn time in steady state. The formula is simple and numerically feasible, and enables us to control the absolute error in numerical results. Further, we discuss the impact of the arrival process on the sojourn time distribution through some numerical examples.     

带有Bernoulli控制策略的M/M/1多重休假排队模型

研究具有Bernoulli控制策略的M/M/1多重休假排队模型: 当系统为空时, 服务台依一定的概率或进入闲期, 或进入普通休假状态, 或进入工作休假状态. 对该模型, 应用拟生灭(QBD)过程和矩阵几何解的方法, 得到了过程平稳队长的具体形式, 在此基础上, 还得到了平稳队长和平稳逗留时间的随机分解结果以及附加队长分布和附加延迟的LST的具体形式. 结果表明, 经典的M/M/1排队, M/M/1多重休假排队, M/M/1多重工作休假排队都是该模型的特殊情形.     

The cyclic queue and the tandem queue

We consider a closed queueing network, consisting of two FCFS single server queues in series: a queue with general service times and a queue with exponential service times. A fixed number \(N\) of customers cycle through this network. We determine the joint sojourn time distribution of a tagged customer in, first, the general queue and, then, the exponential queue. Subsequently, we indicate how the approach toward this closed system also allows us to study the joint sojourn time distribution of a tagged customer in the equivalent open two-queue system, consisting of FCFS single server queues with general and exponential service times, respectively, in the case that the input process to the first queue is a Poisson process.     

具有Bernoulli反馈且带有负顾客的PH/M/1排队系统

在PH/M/1排队模型中,引入了负顾客和Bernoulli反馈,并讨论了服务台容量为有限和无限两类模型,其中,模型一为服务台容量为无限的PH/M/1排队模型,利用拟生灭过程和矩阵几何解法得到了系统的转移速率矩阵,给出了系统正常返的充要条件,并得到了系统的稳态队长、忙期长度的拉普拉斯变换,以及系统的其它相关性能指标.模型二为服务台容量为有限的PH/M/1/N排队模型,同样使用拟生灭过程给出了马尔科夫过程的转移速率矩阵,并利用矩阵分析法进行求解,得到了该系统的稳态解和其它相关指标.     

On stochastic decomposition in the GI/M/1 queue with single exponential vacation

We consider a GI/M/1 queueing system in which the server takes exactly one exponential vacation each time the system empties. We derive the PGF of the stationary queue length and the LST of the stationary FIFO sojourn time. We show that both the queue length and the sojourn time can be stochastically decomposed into meaningful quantities.     

M/T-SPH/1排队平稳指标分布的尾部衰减特征

讨论M/T-SPH/1排队平稳队长分布和平稳逗留时间分布的尾部衰减特征,其中T-SPH表示可数状态吸收生灭过程吸收时间的分布。在分布PGF和LST的基础上,给出了两个平稳分布衰减规律的完整分析.结果表明,当参数取不同值时,平稳队长与平稳逗留时间的尾部具有三种不同类型的衰减特征.     

Analysis of a dynamic assignment of impatient customers to parallel queues

Consider a number of parallel queues, each with an arbitrary capacity and multiple identical exponential servers. The service discipline in each queue is first-come-first-served (FCFS). Customers arrive according to a state-dependent Poisson process. Upon arrival, a customer joins a queue according to a state-dependent policy or leaves the system immediately if it is full. No jockeying among queues is allowed. An incoming customer to a parallel queue has a general patience time dependent on that queue after which he/she must depart from the system immediately. Parallel queues are of two types: type 1, wherein the impatience mechanism acts on the waiting time; or type 2, a single server queue wherein the impatience acts on the sojourn time. We prove a key result, namely, that the state process of the system in the long run converges in distribution to a well-defined Markov process. Closed-form solutions for the probability density function of the virtual waiting time of a queue of type 1 or the offered sojourn time of a queue of type 2 in a given state are derived which are, interestingly, found to depend only on the local state of the queue. The efficacy of the approach is illustrated by some numerical examples.     

Age Process, Workload Process, Sojourn Times, and Waiting Times in a Discrete Time SM[K]/PH[K]/1/FCFS Queue

In this paper, we study a discrete time queueing system with multiple types of customers and a first-come-first-served (FCFS) service discipline. Customers arrive according to a semi-Markov arrival process and the service times of individual customers have PH-distributions. A GI/M/1 type Markov chain for a generalized age process of batches of customers is introduced. The steady state distribution of the GI/M/1 type Markov chain is found explicitly and, consequently, the steady state distributions of the age of the batch in service, the total workload in the system, waiting times, and sojourn times of different batches and different types of customers are obtained. We show that the generalized age process and a generalized total workload process have the same steady state distribution. We prove that the waiting times and sojourn times have PH-distributions and find matrix representations of those PH-distributions. When the arrival process is a Markov arrival process with marked transitions, we construct a QBD process for the age process and the total workload process. The steady state distributions of the waiting times and the sojourn times, both at the batch level and the customer level, are obtained from the steady state distribution of the QBD process. A number of numerical examples are presented to gain insight into the waiting processes of different types of customers.AMS subject classification: 60K25, 60J10This revised version was published online in June 2005 with corrected coverdate     

The GI/M/1 queue with exponential vacations

In this paper, we give a detailed analysis of the GI/M/1 queue with exhaustive service and multiple exponential vacation. We express the transition matrix of the imbedded Markov chain as a block-Jacobi form and give a matrix-geometric solution. The probability distribution of the queue length at arrival epochs is derived and is shown to decompose into the distribution of the sum of two independent random variables. In addition, we discuss the limiting behavior of the continuous time queue length processes and obtain the probability distributions for the waiting time and the busy period.     

休假时间服从T-SPH分布的M/M/1多重休假排队

本文研究休假时间服从T-SPH分布的M/M/1多重休假排队,利用拟生灭过程和算子几何解的方法给出了平稳队长分布的概率母函数,并得到了平稳队长和平稳等待时间的随机分解结果以及附加队长和附加延迟的母函数和LST的具体形式.     

对M/T-SPH/1排队平稳指标的进一步研究—数值计算与渐近分析

讨论M/T-SPH/1排队平稳队长分布的数值计算,以及平稳队长和逗留时间分布各阶矩的数值计算及渐近分析.其中T-SPH表示可数状态吸收生灭链吸收时间的分布.在分布PGF和LST的基础上,首先给出了计算平稳队长分布,平稳队长以及逗留时间分布各阶矩的数值结果的递推公式.其次还讨论了平稳队长及平稳逗留时间分布各阶矩的尾部渐近...     

Tail behavior of conditional sojourn times in Processor-Sharing queues

We investigate the tail behavior of the sojourn-time distribution for a request of a given length in an M/G/1 Processor-Sharing (PS) queue. An exponential asymptote is proven for general service times in two special cases: when the traffic load is sufficiently high and when the request length is sufficiently small. Furthermore, using the branching process technique we derive exact asymptotics of exponential type for the sojourn time in the M/M/1 queue. We obtain an equation for the asymptotic decay rate and an exact expression for the asymptotic constant. The decay rate is studied in detail and is compared to other service disciplines. Finally, using numerical methods, we investigate the accuracy of the exponential asymptote. AMS 2000 Subject Classifications Primary:60K25,Secondary: 60F10,68M20,90B22     

基于特征根方法的M/G_N/1个性化服务排队顾客逗留时间分布函数的数值计算

以多语种便民服务热线为实际应用背景,研究个性化服务M/G_N/1排队系统中顾客逗留时间分布函数的数值计算方法.首先,利用嵌入Markov链技术和Pollaczek-Khintchine变换公式给出顾客逗留时间的Laplace-Stieltjes(LS)变换.其次,根据个性化服务时间分布函数的具体类型,给出上述LS变换的有理函数表达形式.通过求解有理函数分母之具有负实部的零点,即所谓的特征根,最终使用部分分式分解方法和复分析中的留数理论给出顾客逗留时间的概率分布函数.     

具有多类顾客的单服务台流体逼近的收敛速度

本文研究了—个具有多类顾客到达的单服务台排队系统．在流体变换下,我们知道排队模型以概率1在紧集上一致收敛到相应的流体模型．在一致收敛拓扑下,如果到达过程,服务过程在流体变换下以指数速度收敛到相应的流体过程,我们证明了在流体变换下的排队系统中的各个参量以指数速度收敛到流体模型中相应的参量,这些参量包括队长过程,负荷过程,逗留时间过程,离去过程,闲期过程等．     

The equivalence between processor sharing and service in random order

In this note we explore a useful equivalence relation for the delay distribution in the G/M/1 queue under two different service disciplines: (i) processor sharing (PS); and (ii) random order of service (ROS). We provide a direct probabilistic argument to show that the sojourn time under PS is equal (in distribution) to the waiting time under ROS of a customer arriving to a non-empty system. We thus conclude that the sojourn time distribution for PS is related to the waiting-time distribution for ROS through a simple multiplicative factor, which corresponds to the probability of a non-empty system at an arrival instant. We verify that previously derived expressions for the sojourn time distribution in the M/M/1 PS queue and the waiting-time distribution in the M/M/1 ROS queue are indeed identical, up to a multiplicative constant. The probabilistic nature of the argument enables us to extend the equivalence result to more general models, such as the M/M/1/K queue and ·/M/1 nodes in product-form networks.     

对一类等待空间有限的抢占优先权排队的分析

讨论M/M/1抢占优先权排队模型, 且假设低优先权顾客的等待空间有限. 该模型可以用有限位相拟生灭过程来描述. 由矩阵解析方法, 对该拟生灭过程进行了分析, 并得到排队模型平稳队长的计算公式, 最后还用数值 结果说明了方法的有效性.     

Sojourn time asymptotics in the M/G/1 processor sharing queue

We show for the M/G/1 processor sharing queue that the service time distribution is regularly varying of index -ν, ν non-integer, iff the sojourn time distribution is regularly varying of index -ν. This result is derived from a new expression for the Laplace–Stieltjes transform of the sojourn time distribution. That expression also leads to other new properties for the sojourn time distribution. We show how the moments of the sojourn time can be calculated recursively and prove that the kth moment of the sojourn time is finite iff the kth moment of the service time is finite. In addition, we give a short proof of a heavy traffic theorem for the sojourn time distribution, prove a heavy traffic theorem for the moments of the sojourn time, and study the properties of the heavy traffic limiting sojourn time distribution when the service time distribution is regularly varying. Explicit formulas and multiterm expansions are provided for the case that the service time has a Pareto distribution. This revised version was published online in June 2006 with corrections to the Cover Date.     

Palm calculus for a process with a stationary random measure and its applications to fluid queues

We consider a process associated with a stationary random measure, which may have infinitely many jumps in a finite interval. Such a process is a generalization of a process with a stationary embedded point process, and is applicable to fluid queues. Here, fluid queue means that customers are modeled as a continuous flow. Such models naturally arise in the study of high speed digital communication networks. We first derive the rate conservation law (RCL) for them, and then introduce a process indexed by the level of the accumulated input. This indexed process can be viewed as a continuous version of a customer characteristic of an ordinary queue, e.g., of the sojourn time. It is shown that the indexed process is stationary under a certain kind of Palm probability measure, called detailed Palm. By using this result, we consider the sojourn time processes in fluid queues. We derive the continuous version of Little's formula in our framework. We give a distributional relationship between the buffer content and the sojourn time in a fluid queue with a constant release rate.