Transition time asymptotics of queue-based activation protocols in random-access networks

We consider networks where each node represents a server with a queue. An active node deactivates at unit rate. An inactive node activates at a rate that depends on its queue length, provided none of its neighbors is active.For complete bipartite networks, in the limit as the queues become large, we compute the average transition time between the two states where one half of the network is active and the other half is inactive. We show that the law of the transition time divided by its mean exhibits a trichotomy, depending on the activation rate functions.     

Functional continuity and large deviations for the behavior of single-class queueing networks

We consider a single-class queueing network in which the functional network primitives describe the cumulative exogenous arrivals, service times and routing decisions of the queues. The behavior of the network consisting of the cumulative total arrival, cumulative idle time, and queue length developments for each node is specified by conditions which relate the network primitives to the network behavior. For a broad class of network primitives, including discrete customer and fluid models, a network behavior exists, but need not be unique. Nevertheless, the mapping from network primitives to the set of associated network behavior is upper semicontinuous at network primitives with continuous routing. As an application we consider a sequence of random network primitives satisfying a sample path large deviation principle. We take advantage of the partial functional set-valued upper semicontinuity in order to derive a large deviation principle for the sequence of associated random queue length processes and to identify the rate function. This extends the results of Puhalskii (Markov Process. Relat. Fields 13(1), 99–136, 2007) about large deviations for the tail probabilities of generalized Jackson networks. Since the analysis is carried out on the doubly-infinite time axis ?, we can directly treat stationary situations.     

Large deviations and importance sampling for a tandem network with slow-down

We consider a variant of the two-node tandem Jackson network where the upstream server reduces its service rate when the downstream queue exceeds some prespecified threshold. The rare event of interest is the overflow of the downstream queue. Based on a game/subsolution approach, we rigorously identify the exponential decay rate of the rare event probabilities and construct asymptotically optimal importance sampling schemes. Research of P. Dupuis supported in part by the National Science Foundation (NSF-DMS-0404806 and NSF-DMS-0706003) and the Army Research Office (W911NF-05-1-0289). Research of K. Leder supported in part by the National Science Foundation (NSF-DMS-0404806 and NSF-DMS-0706003). Research of H. Wang supported in part by the National Science Foundation (NSF-DMS-0404806 and NSF-DMS-0706003).     

Jitter analysis of an MMPP-2 tagged stream in the presence of an MMPP-2 background stream

We first consider a single-server queue that serves a tagged MMPP-2 stream and a background MMPP-2 stream in a FIFO manner. The service time is exponentially distributed. For this queueing system, we obtain the CDF of the tagged inter-departure time, from which we can calculate the jitter, defined as a percentile of the inter-departure time. The formulation is exact, but the solution is obtained numerically, which introduces an error that has been found to be negligible. Subsequently, we consider a tandem queueing network consisting of N tandem queues, which is traversed by the MMPP-2 tagged stream, and where each queue also serves a local MMPP-2 background stream. For this queueing network, we obtain an upper bound on the CDF of the inter-departure time from the Nth queue using a heavy traffic approximation, and we verify it by simulation.     

Fluid polling systems

We study N-queues single-server fluid polling systems, where a fluid is continuously flowing into the queues at queue-dependent rates. When visiting and serving a queue, the server reduces the amount of fluid in the queue at a queue-dependent rate. Switching from queue i to queue j requires two random-duration steps: (i) departing queue i, and (ii) reaching queue j. The length of time the server resides in a queue depends on the service regime. We consider three main regimes: Exhaustive, Gated, and Globally-Gated. Two polling procedures are analyzed: (i) cyclic and (ii) probabilistic. Under steady-state, we derive the Laplace–Stieltjes transform (LST), mean, and second moment of the amount of flow at each queue at polling instants, as well as at an arbitrary moment. We further calculate the LST and mean of the “waiting time” of a drop at each queue and derive expressions for the mean total load in the system for the various service regimes. Finally, we explore optimal switching procedures.     

Queues with Service Rate Controlled by a Delayed Feedback

We consider a single queue with a Markov modulated Poisson arrival process. Its service rate is controlled by a scheduler. The scheduler receives the workload information from the queue after a delay. This queue models the buffer in an earth station in a satellite network where the scheduler resides in the satellite. We obtain the conditions for stability, rates of convergence to the stationary distribution and the finiteness of the stationary moments. Next we extend these results to the system where the scheduler schedules the service rate among several competing queues based on delayed information about the workloads in the different queues.     

Mean queue size in a queue with discrete autoregressive arrivals of order <Emphasis Type="Italic">p</Emphasis>

We consider a discrete time single server queueing system where the arrival process is governed by a discrete autoregressive process of order p (DAR(p)), and the service time of a customer is one slot. For this queueing system, we give an expression for the mean queue size, which yields upper and lower bounds for the mean queue size. Further we propose two approximation methods for the mean queue size. One is based on the matrix analytic method and the other is based on simulation. We show, by illustrations, that the proposed approximations are very accurate and computationally efficient.     

Models for queue length in clocked queueing networks

We analyze a discrete-time network of queues. The unit element of the network is the 2 × 2 buffered switch, which we regard as a system of two queues working in parallel. We show how to transform transition probability information from the output of one switch, or network stage, to the input of the next one. This is used to carry out a Markov time series input model to predict mean queue length at every stage of the system. Another model considered is a renewal process time series model, which we use to find the mean queue length of the second stage of the network. Numerical simulations fall within the narrow band spanned by the two models.     

A Markov-modulated M/G/1 queue II: Busy period and time for buffer overflow

We consider an M/G/1 queue where the arrival and service processes are modulated by a two state Markov chain. We assume that the arrival rate, service time density and the rates at which the Markov chain switches its state, are functions of the total unfinished work (buffer content) in the queue. We compute asymptotic approximations to performance measures such as the mean residual busy period, mean length of a busy period, and the mean time to reach capacity.This research was supported in part by NSF Grants DMS-84-06110, DMS-85-01535 and DMS-86-20267, and grants from the U.S. Israel Binational Science Foundation and the Israel Academy of Sciences.     

Infinite-server systems with Coxian arrivals

We consider a network of infinite-server queues where the input process is a Cox process of the following form: The arrival rate is a vector-valued linear transform of a multivariate generalized (i.e., being driven by a subordinator rather than a compound Poisson process) shot-noise process. We first derive some distributional properties of the multivariate generalized shot-noise process. Then these are exploited to obtain the joint transform of the numbers of customers, at various time epochs, in a single infinite-server queue fed by the above-mentioned Cox process. We also obtain transforms pertaining to the joint stationary arrival rate and queue length processes (thus facilitating the analysis of the corresponding departure process), as well as their means and covariance structure. Finally, we extend to the setting of a network of infinite-server queues.

     

Sample path large deviations for a family of long-range dependent traffic and associated queue length processes

We consider the long-range dependent cumulative traffic generated by the superposition of constant rate fluid sources having exponentially distributed inter start times and Pareto distributed durations with finite mean and infinite variance. We prove a sample path large deviation principle when the session start time intensity is increased and the processes are centered and scaled appropriately. Properties of the rate function are investigated. We derive a sample path large deviation principle for a related family of stationary queue length processes. The large deviation approximation of the steady-state queue length distribution is compared with the corresponding empirical distribution obtained by a computer simulation. MSC 2000 Classifications: Primary 60F10; Secondary 60K25, 68M20, 90B22     

Path Space Large Deviations of a Large Buffer with Gaussian Input Traffic

We consider a queue fed by Gaussian traffic and give conditions on the input process under which the path space large deviations of the queue are governed by the rate function of the fractional Brownian motion. As an example we consider input traffic that is composed of of independent streams, each of which is a fractional Brownian motion, having different Hurst indices.     

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.     

Marginal queue length approximations for a two-layered network with correlated queues

We consider an extension of the classical machine-repair model, where we assume that the machines, apart from receiving service from the repairman, also serve queues of products. The extended model can be viewed as a layered queueing network, where the first layer consists of the queues of products and the second layer is the ordinary machine-repair model. As the repair time of one machine may affect the time the other machine is not able to process products, the downtimes of the machines are correlated. This correlation leads to dependence between the queues of products in the first layer. Analysis of these queue length distributions is hard, as the exact dependence structure for the downtimes, or the queue lengths, is not known. Therefore, we obtain an approximation for the complete marginal queue length distribution of any queue in the first layer, by viewing such a queue as a single server queue with correlated server downtimes. Under an explicit assumption on the form of the downtime dependence, we obtain exact results for the queue length distribution for that single server queue. We use these exact results to approximate the machine-repair model. We do so by computing the downtime correlation for the latter model and by subsequently using this information to fine-tune the parameters we introduced to the single server queue. As a result, we immediately obtain an approximation for the queue length distributions of products in the machine-repair model, which we show to be highly accurate by extensive numerical experiments.     

On Queues with Markov Modulated Service Rates

In this paper, we consider a queue whose service speed changes according to an external environment that is governed by a Markov process. It is possible that the server changes its service speed many times while serving a customer. We derive first and second moments of the service time of customers in system using first step analysis to obtain an insight on the service process. In fact, we obtain an intriguing result in that the moments of service time actually depend on the arrival process! We also show that the mean service rate is not the reciprocal of the mean service time. Further, since it is not possible to obtain a closed form expression for the queue length distribution, we use matrix geometric methods to compute performance measures such as average queue length and waiting time. We apply the method of large deviations to obtain tail distributions of the workload in the queue using the concept of effective bandwidth. We present two applications in computer systems: (1) Web server with multi-class requests and (2) CPU with multiple processes. We illustrate the analysis and various methods discussed with the help of numerical examples for the above two applications. AMS subject classification: 90B22, 68M20     

Queue length distributions in a markov model of a multistage clocked queueing network

In [4], we treated the problem of passage through a discrete-time clock-regulated multistage queueing network by modeling the input time series {a_n} to each queue as a Markov chain. We showed how to transform probability transition information from the input of one queue to the input of the next in order to predict mean queue length at each stage. The Markov approximation is very good for p = E(a_n) ≦ ½, which is in fact the range of practical utility. Here we carry out a Markov time series input analysis to predict the stage to stage change in the probability distribution of queue length. The main reason for estimating the queue length distribution at each stage is to locate “hot spots”, loci where unrestricted queue length would exceed queue capacity, and a quite simple expression is obtained for this purpose.     

Competitive queue policies for differentiated services

We consider the setting of a network providing differentiated services. As is often the case in differentiated services, we assume that the packets are tagged as either being a high priority packet or a low priority packet. Outgoing links in the network are serviced by a single FIFO queue.Our model gives a benefit of α1 to each high priority packet and a benefit of 1 to each low priority packet. A queue policy controls which of the arriving packets are dropped and which enter the queue. Once a packet enters the queue it is eventually sent. The aim of a queue policy is to maximize the sum of the benefits of all the packets it sends.We analyze and compare different queue policies for this problem using the competitive analysis approach, where the benefit of the online policy is compared to the benefit of an optimal offline policy. We derive both upper and lower bounds for the policies we consider. We believe that competitive analysis gives important insight to the performance of these queuing policies.     

Parallel cleaning of a network with brushes

We consider the process of cleaning a network where at each time step, all vertices that have at least as many brushes as incident, contaminated edges, send brushes down these edges and remove them from the network. An added condition is that, because of the contamination model used, the final configuration must be the initial configuration of another cleaning of the network. We find the minimum number of brushes required for trees, cycles, complete bipartite networks; and for all networks when all edges must be cleaned on each step. Finally, we give bounds on the number of brushes required for complete networks.     

Impact of Bursty Traffic on Queues

The impact of bursty traffic on queues is investigated in this paper. We consider a discrete-time single server queue with an infinite storage room, that releases customers at the constant rate of c customers/slot. The queue is fed by an M/G/∞ process. The M/G/∞ process can be seen as a process resulting from the superposition of infinitely many ‘sessions’: sessions become active according to a Poisson process; a station stays active for a random time, with probability distribution G, after which it becomes inactive. The number of customers entering the queue in the time-interval [t, t + 1) is then defined as the number of active sessions at time t (t = 0,1, ...) or, equivalently, as the number of busy servers at time t in an M/G/∞ queue, thereby explaining the terminology. The M/G/∞ process enjoys several attractive features: First, it can display various forms of dependencies, the extent of which being governed by the service time distribution G. The heavier the tail of G, the more bursty the M/G/∞ process. Second, this process arises naturally in teletraffic as the limiting case for the aggregation of on/off sources [27]. Third, it has been shown to be a good model for various types of network traffic, including telnet/ftp connections [37] and variable-bit-rate (VBR) video traffic [24]. Last but not least, it is amenable to queueing analysis due to its very strong structural properties. In this paper, we compute an asymptotic lower bound for the tail distribution of the queue length. This bound suggests that the queueing delays will dramatically increase as the burstiness of the M/G/∞ input process increases. More specifically, if the tail of G is heavy, implying a bursty input process, then the tail of the queue length will also be heavy. This result is in sharp contrast with the exponential decay rate of the tail distribution of the queue length in presence of ‘non-bursty’ traffic (e.g. Poisson-like traffic). This revised version was published online in August 2006 with corrections to the Cover Date.     

Stochastic cyclic flow lines: non-blocking,Markovian models

In this paper we consider stochastic cyclic flow lines where identical sets of jobs are repeatedly produced in the same loading and processing sequence. Each machine has an input buffer with enough capacity. Processing times are stochastic. We model the shop as a stochastic event graph, a class of Petri nets. We characterise the ergodicity condition and the cycle time. For the case where processing times are exponentially distributed, we present a way of computing queue length distributions. For two-machine cases, by the matrix geometric method, we compute the exact queue length distributions. For general cases, we present two methods for approximately decomposing the line model into two-machine submodels, one based on starvation propagation and the other based on transition enabling probability propagation. We experiment our approximate methods for various stochastic cyclic flow lines and discuss performance characteristics as well as accuracy of the approximate methods. Finally, we discuss the effects of job processing sequences of stochastic cyclic flow lines.