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→∞.     

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.     

An invariance property of sojourn times in cyclic networks

We investigate a customer's roundtrip behaviour in a cycle of exponential single server nodes. The conditional joint sojourn time distribution, given the cycle time, is independent of the number of circulating customers. We compare the consequences of this invariance property with previous results on passage time behaviour in case of bottlenecks.     

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.     

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     

A note on comparing response times in the M/GI/1/FB and M/GI/1/PS queues

We compare the overall mean response time (a.k.a. sojourn time) of the processor sharing (PS) and feedback (FB) queues under an M/GI/1 system. We show that FB outperforms PS under service distributions having decreasing failure rates; whereas PS outperforms FB under service distributions having increasing failure rates.     

Asymptotic expansions for the sojourn time distribution in the M/G/1-PS queue

We consider the M/G/1 queue with a processor sharing server. We study the conditional sojourn time distribution, conditioned on the customer’s service requirement, as well as the unconditional distribution, in various asymptotic limits. These include large time and/or large service request, and heavy traffic, where the arrival rate is only slightly less than the service rate. Our results demonstrate the possible tail behaviors of the unconditional distribution, which was previously known in the cases G = M and G = D (where it is purely exponential). We assume that the service density decays at least exponentially fast. We use various methods for the asymptotic expansion of integrals, such as the Laplace and saddle point methods.     

Asymptotic expansions for the conditional sojourn time distribution in the <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/1-PS queue

We consider the M/M/1 queue with processor sharing. We study the conditional sojourn time distribution, conditioned on the customer’s service requirement, in various asymptotic limits. These include large time and/or large service request, and heavy traffic, where the arrival rate is only slightly less than the service rate. The asymptotic formulas relate to, and extend, some results of Morrison (SIAM J. Appl. Math. 45:152–167, [1985]) and Flatto (Ann. Appl. Probab. 7:382–409, [1997]). This work was partly supported by NSF grant DMS 05-03745.     

A sample path relation for the sojourn times in G/G/1−PS systems and its applications

For the single server system under processor sharing (PS) a sample path result for the sojourn times in a busy period is proved, which yields a sample path relation between the sojourn times under PS and FCFS discipline. This relation provides a corresponding one between the mean stationary sojourn times in G/G/1 under PS and FCFS. In particular, the mean stationary sojourn time in G/D/1 under PS is given in terms of the mean stationary sojourn time under FCFS, generalizing known results for GI/M/1 and M/GI/1. Extensions of these results suggest an approximation of the mean stationary sojourn time in G/GI/1 under PS in terms of the mean stationary sojourn time under FCFS. Mathematics Subject Classification (MSC 2000) 60K25· 68M20· 60G17· 60G10 This work was supported by a grant from the Siemens AG.     

On the rate of convergence for central limit theorems of sojourn times of Gaussian fields

The aim of this paper is to control the rate of convergence for central limit theorems of sojourn times of Gaussian fields in both cases: the fixed and the moving level. Our main tools are the Malliavin calculus and the Stein method, developed by Nualart, Peccati and Nourdin. We also extend some results of Berman to the multidimensional case.     

Geo/G/1 queues with disasters and general repair times

This paper discusses discrete-time single server Geo/G/1 queues that are subject to failure due to a disaster arrival. Upon a disaster arrival, all present customers leave the system. At a failure epoch, the server is turned off and the repair period immediately begins. The repair times are commonly distributed random variables. We derive the probability generating functions of the queue length distribution and the FCFS sojourn time distribution. Finally, some numerical examples are given.     

A direct approach to sojourn times in a busy period of an M/M/1 queue

In this paper we present a direct approach to obtaining joint distributions of various quantities of interest in a busy period in an M/M/1 queue. These quantities are: the sojourn times and waiting times of all the customers in the busy period, the busy period length and the number of customers served in a busy period. Since the evolution of the total workload process between two successive customer arrivals is deterministic, this work gives statistic of the complete evolution of the workload process within a busy period. This work was done when the author was post doctoral fellow with the MAESTRO group at INRIA, Sophia Antipolis, France, and was supported by project no. 2900-IT-1 from the Centre Franco-Indien pour la Promotion de la Recherche Avancee (CEFIPRA).     

An M/G/1 queue with cyclic service times

In this paper we consider a single server queue with Poisson arrivals and general service distributions in which the service distributions are changed cyclically according to customer sequence number. This model extends a previous study that used cyclic exponential service times to the treatment of general service distributions. First, the stationary probability generating function and the average number of customers in the system are found. Then, a single vacation queueing system with aN-limited service policy, in which the server goes on vacation after servingN consecutive customers is analyzed as a particular case of our model. Also, to increase the flexibility of using theM/G/1 model with cyclic service times in optimization problems, an approximation approach is introduced in order to obtain the average number of customers in the system. Finally, using this approximation, the optimalN-limited service policy for a single vacation queueing system is obtained.On leave from the Department of Industrial Engineering, Iran University of Science and Technology, Narmak, Tehran 16844, Iran.     

On the average sojourn time under M/M/1/SRPT

We study an M/M/1 queueing system under the shortest remaining processing time (SRPT) policy. We show that the average sojourn time varies as , where ρ is the system load. Thus, SRPT offers a Θ(ln(e/(1−ρ))) factor improvement over policies that ignore knowledge of job sizes while scheduling.     

On the sojourn times for many-queue head-of-the-line Processor-sharing systems with permanent customers

We consider a single server system consisting of e queues with different types of customers (Poisson streams) andk permanent customers. The permanent customers and those at the head of the queues are served in processor-sharing by the service facility (head-of-the-line processor-sharing). The stability condition and a pseudo work conservation law will be given for arbitrary service time distributions; for exponential service times a pseudo conservation law for the mean sojourn tunes can be derived. In case of two queues and exponential service times, the generating function of the stationary occupancy distribution satisfies a functional equation being a Riemann-Hilbert problem which can be reduced to a Dirichlet problem for a circle. The solution yields the mean sojourn times as an elliptic integral, which can be computed numerically very efficiently. In case ofn 2 a numerical algorithm for computing the performance measures is presented, which is efficient forn 3. Since forn 4 an exact analytical or/and numerical treatment is too complex a heuristic approximation for the mean sojourn times of the different types of customers is given, which in case of a (completely) symmetric system is exact. The numerical and simulation results show that, over a wide range of parameters, the approximation works well.This work was supported by a grant from the Siemens AG.     

A central limit theorem for the sojourn times of strongly ergodic Markov chains

Let X_n be an irreducible aperiodic recurrent Markov chain with countable state space I and with the mean recurrence times having second moments. There is proved a global central limit theorem for the properly normalized sojourn times. More precisely, if $\text{t}{}^{\mathrm{(n}}\text{)}{}_{\mathrm{i}}\text{=Σ}{}^{\mathrm{n}}{}_{\mathrm{k=1}}\text{i}\text{?}{}_{\mathrm{i}}\text{(X}{}_{\mathrm{k}}\text{)}$, then the probability measures induced by {t⁽ⁿ⁾_i/√n?√nπ_i}_i?I(π_i being the ergotic distribution) on the Hilbert-space of square summable I-sequences converge weakly in this space to a Gaussian measure determined by a certain weak potential operator.     

M/G/1/K queues withN-policy and setup times

A steady-state analysis is given for M/G/1/K queues with combinedN-policy and setup times before service periods. The queue length distributions and the mean waiting times are obtained for the exhaustive service system, the gated service system, the E-limited service system, and the G-limited service system. Numerical examples are also provided.     

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.     

AnM/M/1 retrial queue with control policy and general retrial times

We consider anM/M/1 retrial queueing system in which the retrial time has a general distribution and only the customer at the head of the queue is allowed to retry for service. We find a necessary and sufficient condition for ergodicity and, when this is satisfied, the generating function of the distribution of the number of customers in the queue and the Laplace transform of the waiting time distribution under steady-state conditions. The results agree with known results for special cases.Supported by KOSEF 90-08-00-02.     

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.