Sample path analysis of level crossings for the workload process

We examine level crossings of sample paths of queueing processes and investigate the conditions under which the limiting empirical distribution for the workload process exists and is absolutely continuous. The connection between the density of the workload distribution and the rate of downcrossings is established as a sample path result that does not depend on any stochastic assumptions. As a corollary, we obtain the sample path version of the Takács formula connecting the time and customer stationary distributions in a queue. Defective limiting empirical distributions are considered and an expression for the mass at infinity is derived.This research has been supported in part by NSF Grants ECS-8811003 and DDM-8905638.     

Infinite Server Queues with Synchronized Departures Driven by a Single Point Process

We analyze an infinite-server queueing model with synchronized arrivals and departures driven by the point process {T _n } according to the following rules. At time T _n , a single customer (or a batch of size β _n ) arrives to the system. The service requirement of the ith customer in the nth batch is σ _i,n . All customers enter service immediately upon arrival but each customer leaves the system at the first epoch of the point process {T _n } which occurs after his service requirement has been satisfied. For this system the queue length process and the statistics of the departing batches of customers are investigated under various assumptions for the statistics of the point process {T _n }, the incoming batch sequence {β _n }, and the service sequence {σ _i,n }. Results for the asymptotic distribution of the departing batches when the service times are long compared to the interarrival times are also derived.     

Perturbation analysis of theGI/GI/1 queue

We examine a family ofGI/GI/1 queueing processes generated by a parametric family of service time distributions,F(x,), and we show that under suitable conditions the corresponding customer stationary expectation of the system time is twice continuously differentiable with respect to. Expressions for the derivatives are given which are suitable for single run derivative estimation. These results are extended to parameters of the interarrival time distribution and expressions for the corresponding second derivatives (as well as partial second derivatives involving both interarrivai and service time parameters) are also obtained. Finally, we present perturbation analysis algorithms based on these expressions along with simulation results demonstrating their performance.     

The distribution of age-of-information performance measures for message processing systems

Queueing Systems - The idea behind the recently introduced “age-of-information” performance measure of a network message processing system is that it indicates our knowledge regarding...     

A fully stochastic approach to limit theorems for iterates of Bernstein operators

This paper presents a stochastic approach to theorems concerning the behavior of iterations of the Bernstein operator $B_n$ taking a continuous function $f\in C[0,1]$ to a degree-$n$ polynomial when the number of iterations $k$ tends to infinity and $n$ is kept fixed or when $n$ tends to infinity as well. In the first instance, the underlying stochastic process is the so-called Wright–Fisher model, whereas, in the second instance, the underlying stochastic process is the Wright–Fisher diffusion. Both processes are probably the most basic ones in mathematical genetics. By using Markov chain theory and stochastic compositions, we explain probabilistically a theorem due to Kelisky and Rivlin, and by using stochastic calculus we compute a formula for the application of $B_n$ a number of times $k=k\left(n\right)$ to a polynomial $f$ when $k\left(n\right)∕n$ tends to a constant.     

Formulas and representations for cyclic Markovian networks via Palm calculus

We present an extension of the arrival theorem for the output process from a node in closed Markovian networks which we use to obtain simple representations and explicit expressions for the throughput, the distribution of the cycle time, and the joint distribution of interoutput times from a node in single class closed networks with exponential servers. Our approach uses tools from Palm calculus to obtain a recursion on the number of customers in the system. The analysis relies on a non-overtake condition and thus many of the results obtained here apply only to cyclic, single server networks. One of the surprising conclusions of our analysis is that the interoutput times that comprise the cycle time of a customer are (finitely) exchangeable, i.e., that their joint distribution is invariant under permutations. This revised version was published online in June 2006 with corrections to the Cover Date.     

Cycle times in single server cyclic Jackson networks

Using the arrival theorem together with elementary facts regarding integrated tail distributions and length-biased sampling we obtain closed form expressions for the inter-output time and the cycle time distribution in cyclic, single-class Jackson networks. Corresponding expressions for the normalization constant and the throughput are also obtained.     

Consistency of perturbation analysis for a queue with finite buffer space and loss policy

The subject of discrete-event dynamical systems has taken on a new direction with the advent of perturbation analysis (PA), an efficient method for estimating the gradients of a steady-state performance measure, by analyzing data obtained from a single-simulation experiment in the time domain. A crucial issue is whether PA gives strongly consistent estimates, namely, whether average time-domain-based gradients converge, over infinite horizon, to the steady-state gradients. In this paper, we investigate this issue for a queue with a finite buffer capacity and a loss policy. The performance measure in question is the average amount of lost customers, as a function of the buffer's capacity, which is assumed to be continuous in our work. It is shown that PA gives strongly consistent estimates. The analysis uses a new technique, based on busy period-dependent inequalities. This technique may have possible extensions to analyses of consistency of PA for more general queueing systems.     

A sample path analysis of M/GI/1 queues with workload restrictions

A simple random time change is used to analyze M/GI/1 queues with workload restrictions. The types of restrictions considered include workload bounds and rejection of jobs whose waiting times exceed a (possibly random) threshold. Load dependent service rates and vacations are also allowed and in each case the steady state distribution of the workload process for the system with workload restrictions is obtained in terms of that of the corresponding M/ GI/1 queue without restrictions. The novel sample path arguments used simplify and generalize previous results.