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.     

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     

TheM/G/1 queue with processor sharing and its relation to a feedback queue

The central model of this paper is anM/M/1 queue with a general probabilistic feedback mechanism. When a customer completes his ith service, he departs from the system with probability 1–p(i) and he cycles back with probabilityp(i). The mean service time of each customer is the same for each cycle. We determine the joint distribution of the successive sojourn times of a tagged customer at his loops through the system. Subsequently we let the mean service time at each loop shrink to zero and the feedback probabilities approach one in such a way that the mean total required service time remains constant. The behaviour of the feedback queue then approaches that of anM/G/1 processor sharing queue, different choices of the feedback probabilities leading to different service time distributions in the processor sharing model. This is exploited to analyse the sojourn time distribution in theM/G/1 queue with processor sharing.Some variants are also considered, viz., anM/M/1 feedback queue with additional customers who are always present, and anM/G/1 processor sharing queue with feedback.     

Two-stage queueing network models for quality control and testing

We study sojourn times in a two-node open queueing network with a processor sharing node and a delay node, with Poisson arrivals at the PS node. Motivated by quality control and blood testing applications, we consider a feedback mechanism in which customers may either leave the system after service at the PS node or move to the delay node; from the delay node, they always return to the PS node for new quality controls or blood tests. We propose various approximations for the distribution of the total sojourn time in the network; each of these approximations yields the exact mean sojourn time, and very accurate results for the variance. The best of the three approximations is used to tackle an optimization problem that is mainly inspired by a blood testing application.     

Analysis of the M/M/1 Queue with Processor Sharing via Spectral Theory

We show in this paper that the computation of the distribution of the sojourn time of an arbitrary customer in a M/M/1 with the processor sharing discipline (abbreviated to M/M/1 PS queue) can be formulated as a spectral problem for a self-adjoint operator. This approach allows us to improve the existing results for this queue in two directions. First, the orthogonal structure underlying the M/M/1 PS queue is revealed. Second, an integral representation of the distribution of the sojourn time of a customer entering the system while there are n customers in service is obtained.     

Sojourn times in a processor sharing queue with service interruptions

We study the sojourn times of customers in an M/M/1 queue with the processor sharing service discipline and a server that is subject to breakdowns. The lengths of the breakdowns have a general distribution, whereas the on-periods are exponentially distributed. A branching process approach leads to a decomposition of the sojourn time, in which the components are independent of each other and can be investigated separately. We derive the Laplace–Stieltjes transform of the sojourn-time distribution in steady state, and show that the expected sojourn time is not proportional to the service requirement. In the heavy-traffic limit, the sojourn time conditioned on the service requirement and scaled by the traffic load is shown to be exponentially distributed. The results can be used for the performance analysis of elastic traffic in communication networks, in particular, the ABR service class in ATM networks, and best-effort services in IP networks.     

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.     

Waiting times for M/M systems under state-dependent processor sharing

We consider a system where the arrivals form a Poisson process and the required service times of the requests are exponentially distributed. The requests are served according to the state-dependent (Cohen’s generalized) processor sharing discipline, where each request in the system receives a service capacity which depends on the actual number of requests in the system. For this system we derive systems of ordinary differential equations for the LST and for the moments of the conditional waiting time of a request with given required service time as well as a stable and fast recursive algorithm for the LST of the second moment of the conditional waiting time, which in particular yields the second moment of the unconditional waiting time. Moreover, asymptotically tight upper bounds for the moments of the conditional waiting time are given. The presented numerical results for the first two moments of the sojourn times in M/M/m?PS systems show that the proposed algorithms work well.     

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.     

Sojourn times in a processor sharing queue with multiple vacations

We study an M/G/1 processor sharing queue with multiple vacations. The server only takes a vacation when the system has become empty. If he finds the system still empty upon return, he takes another vacation, and so on. Successive vacations are identically distributed, with a general distribution. When the service requirements are exponentially distributed we determine the sojourn time distribution of an arbitrary customer. We also show how the same approach can be used to determine the sojourn time distribution in an M/M/1-PS queue of a polling model, under the following constraints: the service discipline at that queue is exhaustive service, the service discipline at each of the other queues satisfies a so-called branching property, and the arrival processes at the various queues are independent Poisson processes. For a general service requirement distribution we investigate both the vacation queue and the polling model, restricting ourselves to the mean sojourn time.     

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.     

Insensitivity of multiclass systems with general dynamic preemptive resume queueing disciplines

We are concerned with the insensitivity of the stationary distributions of the system states inM/G/s/m queues with multiclass customers and with LIFO preemptive resume service disciplines. We introduce general entrance and exit rules into and from waiting positions, respectively, for the behaviour of waiting customers whose service is interrupted. These rules may, roughly speaking, depend on the number of customers in the system. It is shown that the stationary distribution of the system state is insensitive not only with respect to the service time distributions but also with respect to the general entrance and exit rules. As well as the insensitivity of the service scheme, our results are obtained for a special form of state and customer type dependent arrival and service rates. Some further results are concluded related to insensitivity like the formula for the conditional mean sojourn time and the property of transformation of a Poisson input into a Poisson output by the systems.     

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.     

On Stochastic Bounds for Monotonic Processor Sharing Networks

We consider a network of processor sharing nodes with independent Poisson arrival processes. Nodes are coupled through their service capacity in that the speed of each node depends on the number of customers present at this and any other node. We assume the network is monotonic in the sense that removing a customer from any node increases the service rate of all customers. Under this assumption, we give stochastic bounds on the number of customers present at any node. We also identify limiting regimes that allow to test the tightness of these bounds. The bounds and the limiting regimes are insensitive to the service time distribution. We apply these results to a number of practically interesting systems, including the discriminatory processor sharing queue, the generalized processor sharing queue, and data networks whose resources are shared according to max–min fairness.     

Performance Analysis of the GI/M/1 Queue with Single Working Vacation and Vacations

In this paper, we consider a new class of the GI/M/1 queue with single working vacation and vacations. When the system become empty at the end of each regular service period, the server first enters a working vacation during which the server continues to serve the possible arriving customers with a slower rate, after that, the server may resume to the regular service rate if there are customers left in the system, or enter a vacation during which the server stops the service completely if the system is empty. Using matrix geometric solution method, we derive the stationary distribution of the system size at arrival epochs. The stochastic decompositions of system size and conditional system size given that the server is in the regular service period are also obtained. Moreover, using the method of semi-Markov process (SMP), we gain the stationary distribution of system size at arbitrary epochs. We acquire the waiting time and sojourn time of an arbitrary customer by the first-passage time analysis. Furthermore, we analyze the busy period by the theory of limiting theorem of alternative renewal process. Finally, some numerical results are presented.     

Explicit formulas for the variance of conditioned sojourn times in M/D/1-PS

For the M/D/1 processor sharing queue, explicit formulas for the coefficient of variation of the sojourn time conditioned on the service time and on the residual service times of the tasks found on arrival are derived via branching representations.     

On the Two-Class M/M/1 System under Preemptive Resume and Impatience of the Prioritized Customers

The paper deals with the two-class priority M/M/1 system, where the prioritized class-1 customers are served under FCFS preemptive resume discipline and may become impatient during their waiting for service with generally distributed maximal waiting times. The class-2 customers have no impatience. The required mean service times may depend on the class of the customer. As the dynamics of class-1 customers are related to the well analyzed M/M/1+GI system, our aim is to derive characteristics for class-2 customers and for the whole system. The solution of the balance equations for the partial probability generating functions of the detailed system state process is given in terms of the weak solution of a family of boundary value problems for ordinary differential equations, where the latter can be solved explicitly only for particular distributions of the maximal waiting times. By means of this solution formulae for the joint occupancy distribution and for the sojourn and waiting times of class-2 customers are derived generalizing corresponding results recently obtained by Choi et al. in case of deterministic maximal waiting times. The latter case is dealt as an example in our paper.     

A discrete-time queueing system with optional LCFS discipline

We consider a discrete-time queueing system in which the arriving customers decide with a certain probability to be served under a LCFS-PR discipline and with complementary probability to join the queue. The arrivals are assumed to be geometrical and the service times are arbitrarily distributed. The service times of the expelled customers are independent of their previous ones. We carry out an extensive analysis of the system developing recursive formulae and generating functions for the steady-state distribution of the number of customers in the system and obtaining also recursive formulae and generating functions for the stationary distribution of the busy period and sojourn time as well as some performance measures.     

Asymptotic Analysis of Spectral Properties of Finite Capacity Processor Shared Queues

We consider sojourn (or response) times in processor‐shared queues that have a finite customer capacity. Computing the response time of a tagged customer involves solving a finite system of linear ODEs. Writing the system in matrix form, we study the eigenvectors and eigenvalues in the limit as the size of the matrix becomes large. This corresponds to finite capacity models where the system can only hold a large number K of customers. Using asymptotic methods we reduce the eigenvalue problem to that of a standard differential equation, such as the Airy equation. The dominant eigenvalue leads to the tail of a customer's sojourn time distribution. Some numerical results are given to assess the accuracy of the asymptotic results.