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     

Steady state approximations of limited processor sharing queues in heavy traffic

We investigate steady state properties of limited processor sharing queues in heavy traffic. Our analysis builds on previously obtained process limit theorems, and requires the interchange of steady state and heavy traffic limits, which are established by a coupling argument. The limit theorems yield explicit approximations of the steady state queue length and response time distribution in heavy traffic, of which the quality is supported by simulation experiments.     

Mean sojourn times for phase-type discriminatory processor sharing systems

In a discriminatory processor sharing (DPS) queueing model, each job (or customer) belongs to one out of finitely many classes. The arrival processes are Poisson. Classes differ with respect to arrival rates and service time distributions. Moreover, classes have different priority levels. All jobs present are served simultaneously but the fraction of the server’s capacity allocated to each one of them is proportional to their class priority parameter (while the total capacity is of course fixed).     

Large deviations analysis of the generalized processor sharing policy

In this paper we consider a stochastic server (modeling a multiclass communication switch) fed by a set of parallel buffers. The dynamics of the system evolve in discrete-time and the generalized processor sharing (GPS) scheduling policy of [25] is implemented. The arrival process in each buffer is an arbitrary, and possibly autocorrelated, stochastic process. We obtain a large deviations asymptotic for the buffer overflow probability at each buffer. In the standard large deviations methodology, we provide a lower and a matching (up to first degree in the exponent) upper bound on the buffer overflow probabilities. We view the problem of finding a most likely sample path that leads to an overflow as an optimal control problem. Using ideas from convex optimization we analytically solve the control problem to obtain both the asymptotic exponent of the overflow probability and a characterization of most likely modes of overflow. These results have important implications for traffic management of high-speed networks. They extend the deterministic, worst-case analysis of [25] to the case where a detailed statistical model of the input traffic is available and can be used as a basis for an admission control mechanism. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

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.     

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.     

Asymptotic behavior of generalized processor sharing queues under subexponential assumptions

We analyze the behavior of Generalized Processor Sharing (GPS) queues with heavy-tailed service times. We compute the exact tail asymptotics of the stationary workload of an individual class and give new conditions for reduced-load equivalence and induced burstiness to hold. We also show that both phenomena can occur simultaneously. Our proofs rely on the single big event theorem and new fluid limits obtained for the GPS system that can be of interest by themselves.     

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.     

Dynamic interactive stabilization of systems of flow with processor sharing

An interactive protocol for the control for a switched system of flow with process sharing is proposed. It is shown that the protocol suggested generates the required periodic process as a global attractor.     

Performance of miniload systems with two-class storage

To increase throughput, the higher turnover items are often stored near the input/output point of a miniload system. We analyze the performance of such a miniload with a square-in-time rack containing two storage zones: high turnover and low turnover. First, we derive the distribution of the dual command travel time. System performance measures such as the throughput depend upon the distribution of the dual command travel time and the distribution of pick times. We work out the details and obtain closed-form expressions for throughput for two important families of pick time distributions: deterministic and exponential. Finally, we investigate how the size of the high turnover region affects throughput.     

Additive functionals with application to sojourn times in infinite-server and processor sharing systems

We deal with additive functionals of stationary processes. It is shown that under some assumptions a stationary model of the time-changed process exists. Further, bounds for the expectation of functions of additive functionals are derived. As an application we analyze virtual sojourn times in an infinite-server system where the service speed is governed by a stationary process. It turns out that the sojourn time of some kind of virtual requests equals in distribution an additive functional of a stationary time-changed process, which provides bounds for the expectation of functions of virtual sojourn times, in particular bounds for fractional moments and the distribution function. Interpreting the GI(n)/GI(n)/∞ system or equivalently the GI(n)/GI system under state-dependent processor sharing as an infinite-server system where the service speed is governed by the number n of requests in the system provides results for sojourn times of virtual requests. In the case of M(n)/GI(n)/∞, the sojourn times of arriving and added requests equal in distribution sojourn times of virtual requests in modified systems, which yields several results for the sojourn times of arriving and added requests. In case of positive integer moments, the bounds generalize earlier results for M/GI(n)/∞. In particular, the mean sojourn times of arriving and added requests in M(n)/GI(n)/∞ are proportional to the required service time, generalizing Cohen’s famous result for M/GI(n)/∞.     

A survey on discriminatory processor sharing

The Discriminatory Processor Sharing (DPS) model is a multi-class generalization of the egalitarian Processor Sharing model. In the DPS model all jobs present in the system are served simultaneously at rates controlled by a vector of weights {g_k > 0; k = 1,..., K }. If there are N_k jobs of class k present in the system, k = 1,..., K, each class-k job is served at rate . The present article provides an overview of the analytical results for the DPS model. In particular, we focus on response times and numbers of jobs in the system. This work is part of a French-Dutch Van Gogh research project funded by NWO (The Netherlands Organization for Scientific Research) and EGIDE under grant VGP 61-520. We also acknowledge the support of EuroNGI Network of Excellence. This work was done while U. Ayesta was an ERCIM Postdoc fellow at CWI.     

Scheduling for a processor sharing system with linear slowdown

We consider the problem of scheduling arrivals to a congestion system with a finite number of users having identical deterministic demand sizes. The congestion is of the processor sharing type in the sense that all users in the system at any given time are served simultaneously. However, in contrast to classical processor sharing congestion models, the processing slowdown is proportional to the number of users in the system at any time. That is, the rate of service experienced by all users is linearly decreasing with the number of users. For each user there is an ideal departure time (due date). A centralized scheduling goal is then to select arrival times so as to minimize the total penalty due to deviations from ideal times weighted with sojourn times. Each deviation penalty is assumed quadratic, or more generally convex. But due to the dynamics of the system, the scheduling objective function is non-convex. Specifically, the system objective function is a non-smooth piecewise convex function. Nevertheless, we are able to leverage the structure of the problem to derive an algorithm that finds the global optimum in a (large but) finite number of steps, each involving the solution of a constrained convex program. Further, we put forward several heuristics. The first is the traversal of neighbouring constrained convex programming problems, that is guaranteed to reach a local minimum of the centralized problem. This is a form of a “local search”, where we use the problem structure in a novel manner. The second is a one-coordinate “global search”, used in coordinate pivot iteration. We then merge these two heuristics into a unified “local–global” heuristic, and numerically illustrate the effectiveness of this heuristic.     

Convergence of series with respect to generalized Haar systems

. . . . , L _p[0, l], 1 >p <, .     

Batch processor sharing with hyper-exponential service time

We study the Processor Sharing queueing model with a hyper-exponential service time distribution and Poisson batch arrival process. In the case of the hyper-exponential service time distribution we find an analytical expression for the expected conditional response time function and obtain an alternative proof of its concavity with respect to the service time.     

On Markovian approximations for virtual-build-to-order systems

The Virtual Build-to-Order (VBTO) approach strives to allow a producer to fulfil customers with the specific product variants they seek more efficiently than a conventional order fulfilment system. It does so by opening the planning pipeline. Here the feasibility of modelling the VBTO system as a Markov process is investigated. Two system configurations are considered—a random pipeline feed policy that assumes only knowledge of the overall demand pattern and an informed policy that ensures a mix of different variants in the system. First-order Markov models, which assume stationarity requirements are satisfied, are developed for small VBTO systems. The model for the informed feed policy has excellent agreement with simulation results and confirms the superiority of this policy over the random policy. The model for the random policy is more accurate at high variety than at low variety levels. Accuracy is improved with a second-order Markov model. Although impractical for modelling large scale VBTO systems for either configuration, the Markov approach is valuable in providing insights, theoretical foundations and validation for simulation models. It aids the interpretation of observations from simulations of large scale systems and explains the mechanism by which an unrepresentative stock mix develops over time for the random policy.