On finite capacity queues with time dependent arrival rates

We consider the finite capacity M/M/1−K$M/M/1-K$ queue with a time dependent arrival rate λ(t)$\lambda \left(t\right)$. Assuming that the capacity K$K$ is large and that the arrival rate varies slowly with time (as t/K$t/K$), we construct asymptotic approximations to the probability of finding n$n$ customers in the system at time t$t$, as well as the mean number. We consider various time ranges, where the system is nearly empty, nearly full, or is filled to a fraction of its capacity. Extensive numerical studies are used to back up the asymptotic analysis.     

Large deviations of sojourn times in processor sharing queues

This paper presents a large deviation analysis of the steady-state sojourn time distribution in the GI/G/1 PS queue. Logarithmic estimates are obtained under the assumption of the service time distribution having a light tail, thus supplementing recent results for the heavy-tailed setting. Our proof gives insight into the way a large sojourn time occurs, enabling the construction of an (asymptotically efficient) importance sampling algorithm. Finally our results for PS are compared to a number of other service disciplines, such as FCFS, LCFS, and SRPT. 2000 mathematics subject classification: 60K25.     

The customer response times in the processor sharing queue are associated

The customer response times in the egalitarian processor sharing queue are shown to be associated random variables under renewal inputs and general independent service times assumptions.The work by this author was supported in part by the National Science Foundation under grant ASC 88-8802764 and by the Office of Naval Research under grant ONR N00014-87-K-0796.     

Large buffer asymptotics for generalized processor sharing queues with Gaussian inputs

In this paper we derive large-buffer asymptotics for a two-class Generalized Processor Sharing (GPS) model. We assume both classes to have Gaussian characteristics. We distinguish three cases depending on whether the GPS weights are above or below the average rate at which traffic is sent. First, we calculate exact asymptotic upper and lower bounds, then we calculate the logarithmic asymptotics, and finally we show that the decay rates of the upper and lower bound match. We apply our results to two special Gaussian models: the integrated Gaussian process and the fractional Brownian motion. Finally we derive the logarithmic large-buffer asymptotics for the case where a Gaussian flow interacts with an on-off flow. AMS Subject Classification Primary—60K25; Secondary—68M20, 60G15     

Asymptotic analysis of a large closed queueing network with discriminatory processor sharing

In this paper the steady-state behavior of a closed queueing network with multiple classes and large populations is investigated. One of the two nodes of the network simply introduces random delays and the discipline in the other node is discriminatory processor sharing. The network is not product-form, so not even the steady-state behavior is known. We assume that the usage is moderately heavy, and obtain two-term asymptotic approximations to the mean number of jobs, and the mean sojourn time, of each class of jobs in the processor node. We also obtain the leading term in the asymptotic approximation to the joint distribution of the number of jobs in the processor node, which is a zero-mean multivariate Gaussian distribution around a line through the origin.     

Processor sharing for two queues with vastly different rates

We consider a 2-class queueing system, operating under a generalized processor-sharing discipline, in an asymptotic regime where the arrival and service rates of the two classes are vastly different. We use regular and singular perturbation analyses in a small parameter measuring this difference in rates. It is assumed that the system is stable, and not close to instability. Three different regimes are analyzed, corresponding to an underloaded, an overloaded and a critically loaded fast queue, respectively. In the first two regimes the lowest order approximation to the joint stationary distribution of the queue lengths is derived. For a critically loaded fast queue only the mean queue lengths are investigated, and the asymptotic matching, to lowest order, with the results for an underloaded and an overloaded fast queue is established.      

Waiting time distributions for closed M/M/N processor sharing queues

We consider a multiple server processor sharing model with a finite number of terminals (customers). Each terminal can submit at most one job for service at any time. The think times of the terminals and the service time demands are independently exponentially distributed. We focus our attention on the exact detailed analysis of the waiting time distribution of a tagged job. We give the Laplace-Stieltjes transform of the waiting time distribution conditioned on the job's service time demand and the state of the other terminals and show that these transforms can be efficiently evaluated and inverted. Further results include the representation of conditioned waiting times as mixtures of a constant and several exponentially distributed components. The numerical precision of our results is being compared with results from a discrete approximation of the waiting time distributions.The main part of this research was carried out at the Institut für Mathematische Stochastik of the Technische UniversitÄt Braunschweig.     

On sojourn times in the finite capacity queue with processor sharing

We consider a processor shared M/M/1 queue that can accommodate at most a finite number K of customers. We give an exact expression for the sojourn time distribution in this finite capacity model, in terms of a Laplace transform. We then give the tail behavior, for the limit K→∞.     

Fluid and diffusion limits for transient sojourn times of processor sharing queues with time varying rates

We provide an approximate analysis of the transient sojourn time for a processor sharing queue with time varying arrival and service rates, where the load can vary over time, including periods of overload. Using the same asymptotic technique as uniform acceleration as demonstrated in [12] and [13], we obtain fluid and diffusion limits for the sojourn time of the M_t/M_t/1 processor-sharing queue. Our analysis is enabled by the introduction of a “virtual customer” which differs from the notion of a “tagged customer” in that the former has no effect on the processing time of the other customers in the system. Our analysis generalizes to non-exponential service and interarrival times, when the fluid and diffusion limits for the queueing process are known.     

A note on large-buffer asymptotics for generalized processor sharing with Gaussian inputs

In a previous study by Dębicki and van Uitert (Queueing Syst. 54, 111–120, 2006) logarithmic large-buffer asymptotics were derived for a two-class generalized processor sharing system with Gaussian inputs, for three of the four possible scenarios. In this note we show how the large-buffer asymptotics for the remaining fourth regime follow from a recently derived result for tandem systems. We also provide a heuristic interpretation of the result. M.M. is also affiliated to CWI, P.O. Box 94079, 1090 GB Amsterdam, the Netherlands, and EURANDOM, Eindhoven, the Netherlands.     

Some algorithms for discrete time queues with finite capacity

We consider a discrete time queue with finite capacity and i.i.d. and Markov modulated arrivals. Efficient algorithms are developed to calculate the moments and the distributions of the first time to overflow and the regeneration length. Results are extended to the multiserver queue. Some illustrative numerical examples are provided. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Nonstationary analysis of the loss queue and of queueing networks of loss queues

We present an iterative scheme based on the fixed-point approximation method, for the numerical calculation of the time-dependent mean number of customers and blocking probability functions in a nonstationary queueing network with multi-rate loss queues. We first show how the proposed method can be used to analyze a single-class, multi-class, and multi-rate nonstationary loss queue. Subsequently, the proposed method is extended to the analysis of a nonstationary queueing network of multi-rate loss queues. Comparisons with exact and simulation results showed that the results are consistently close to the exact results and they are always within simulation confidence intervals.     

On the transient behavior of the processor sharing queue

We analyze the transient behavior of the single server queue under the processor sharing discipline. Under fairly general assumptions, we give the rate of growth of the number of customers in the queue as well as the asymptotic behavior of the residual service times described in terms of a renormalized point process.     

Large deviations and the generalized processor sharing scheduling for a multiple-queue system

We establish asymptotic upper and lower bounds on the asymptotic decay rate of per-session queue length tail distributions for a multiple-queue system where a single constant rate server services the queues using the generalized processor sharing (GPS) scheduling discipline. In the special case where there are only two queues, the upper and lower bounds match, yielding the optimal bound proved in [15]. The dynamics of bandwidth sharing of a multiple-queue GPS system is captured using the notion of partial feasible sets, and the bounds are obtained using the sample-path large deviation principle. The results have implications in call admission control for high-speed communication networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

Large deviations and the generalized processor sharing scheduling for a two-queue system

We establish the optimal asymptotic decay rate of per-session queue length tail distributions for a two-queue system where a single constant rate server serves the two queues using the Generalized Processor Sharing (GPS) scheduling discipline. The result is obtained using the sample-path large deviation principle and has implications in call admission control for high-speed communication networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

Asymptotics for transient and stationary probabilities for finite and infinite buffer discrete time queues

Consider a discrete time queue with i.i.d. arrivals (see the generalisation below) and a single server with a buffer length m. Let τm be the first time an overflow occurs. We obtain asymptotic rate of growth of moments and distributions of τm as m → ∞. We also show that under general conditions, the overflow epochs converge to a compound Poisson process. Furthermore, we show that the results for the overflow epochs are qualitatively as well as quantitatively different from the excursion process of an infinite buffer queue studied in continuous time in the literature. Asymptotic results for several other characteristics of the loss process are also studied, e.g., exponential decay of the probability of no loss (for a fixed buffer length) in time [0,η], η → ∞, total number of packets lost in [0, η, maximum run of loss states in [0, η]. We also study tails of stationary distributions. All results extend to the multiserver case and most to a Markov modulated arrival process. This revised version was published online in June 2006 with corrections to the Cover Date.     

A heavy-traffic comparison of shared and segregated buffer schemes for queues with the head-of-line processor-sharing discipline

As network speeds increase and the data traffic becomes more diverse, the need arises for service disciplines that offer fair treatment to diverse applications, while efficiently using resources at high speeds. Disciplines that approximate round-robin or processor-sharing service per channel are well suited for data networks because, over a wide range of time scales, they allocate bandwidth fairly among channels without needing to distinguish between different types of applications. This study is among the few to address head-of-line processor sharing. In most previous models of processor-sharing disciplines, the system immediately serves any arriving message at a rate depending only on the number of messages in the system regardless of how these messages are distributed among the channels. This model is commonly called pure processor sharing. In our model, the server completes the work from a given channel at a rate depending on the number of other channels with work in the system. That is, the service rate depends on how messages are distributed among the channels, and only indirectly on the total number of messages in the system. In this paper, we contrast the buffer requirements of shared and non-shared buffer schemes, when both types of schemes provide head-of-the-line processor-sharing service among channels. We formulate the problem as a system of functions representing the cumulative input and cumulative lost (potential) output to parts of the queueing system and model the vector of input functions as a multi-dimensional Brownian motion. The resulting heavy-traffic approximations predict much larger benefits from sharing buffers than those predicted by pure processor sharing.     

一类比例保险模型的破产概率问题

研究了比例再保险的破产概率问题,推广了Gramer-Lundberg经典模型的有关结果,并证明了基于比例模型合保问题最低保费的一个结果。     

����˿͹����Ŷ�ϵͳ����Ϣ����

The discriminatory processor sharing queues with multiple classes of customers (abbreviated as DPS queues) are an important but difficult research direction in queueing theory, and it has many important practical applications in the fields of, such as, computer networks, manufacturing systems, transportation networks, and so forth. Recently, researchers have carried out some key work for the DPS queues. They gave the generating function of the steady-state joint queue lengths, which leads to the first two moments of the steady-state joint queue lengths. However, using the generating function to provide explicit expressions for the steady-state joint queue lengths has been a difficult and challenging problem for many years. Based on this, this paper applies the maximum entropy principle in the information theory to providing an approximate expression with high precision, and this approximate expression can have the same first three moments as those of its exact expression. On the other hand, this paper gives efficiently numerical computation by means of this approximate expression, and analyzes how the key variables of this approximate expression depend on the original parameters of this queueing system in terms of some numerical experiments. Therefore, this approximate expression has important theoretical significance to promote practical applications of the DPS queues. At the same time, not only do the methodology and results given in this paper provide a new line in the study of DPS queues, but they also provide the theoretical basis and technical support for how to apply the information theory to the study of queueing systems, queueing networks and more generally, stochastic models.