Fractional Brownian Heavy Traffic Approximations of Multiclass Feedforward Queueing Networks

We consider multiclass feedforward queueing networks under first in first out and priority service disciplines driven by long-range dependent arrival and service time processes. We show that in critical loading the normalized workload, queue length and sojourn time processes can converge to a multi-dimensional reflected fractional Brownian motion. This weak heavy traffic approximation is deduced from a deterministic pathwise approximation of the network behavior close to constant critical load in terms of the solution of a Skorokhod problem. Since we model the doubly infinite time interval, our results directly cover the stationary case.AMS subject classification: primary 90B15, secondary 60K25, 68M20     

A stochastic network with mobile users in heavy traffic

We consider a stochastic network with mobile users in a heavy traffic regime. We derive the scaling limit of the multidimensional queue length process and prove a form of spatial state space collapse. The proof exploits a recent result by Lambert and Simatos (preprint, 2012), which provides a general principle to establish scaling limits of regenerative processes based on the convergence of their excursions. We also prove weak convergence of the sequences of stationary joint queue length distributions and stationary sojourn times.     

������̨�����Ŷ�ϵͳ�Ķ���ʱ���ǿ�ƽ�

??We obtain the strong approximation of the sojourn time progress for a two-stage tandem queue in heavy traffic, that is, the traffic intensity $\rho_1=\rho_2=1$. The sojourn time is the period from a customer's arrival to her departure, and the strong approximation is a function of Brownian motion.     

Heavy traffic approximation for the stationary distribution of stochastic fluid networks

It has recently been shown that in the heavy traffic limit, the stationary distribution of the scaled queue length process of a Generalized Jackson Network converges to the stationary distribution of its corresponding Reflected Brownian Motion limit. In this paper, we show that this “interchange of limits” is valid for Stochastic Fluid Networks with Lévy inputs. Furthermore, under additional assumptions, we extend the result to show that the interchange is valid for moments of the stationary distribution and for state-dependent routing. The results are obtained using monotonicity and sample-path arguments.     

An overview of Brownian and non-Brownian FCLTs for the single-server queue

We review functional central limit theorems (FCLTs) for the queue-content process in a single-server queue with finite waiting room and the first-come first-served service discipline. We emphasize alternatives to the familiar heavy-traffic FCLTs with reflected Brownian motion (RBM) limit process that arise with heavy-tailed probability distributions and strong dependence. Just as for the familiar convergence to RBM, the alternative FCLTs are obtained by applying the continuous mapping theorem with the reflection map to previously established FCLTs for partial sums. We consider a discrete-time model and first assume that the cumulative net-input process has stationary and independent increments, with jumps up allowed to have infinite variance or even infinite mean. For essentially a single model, the queue must be in heavy traffic and the limit is a reflected stable process, whose steady-state distribution can be calculated by numerically inverting its Laplace transform. For a sequence of models, the queue need not be in heavy traffic, and the limit can be a general reflected Lévy process. When the Lévy process representing the net input has no negative jumps, the steady-state distribution of the reflected Lévy process again can be calculated by numerically inverting its Laplace transform. We also establish FCLTs for the queue-content process when the input process is a superposition of many independent component arrival processes, each of which may exhibit complex dependence. Then the limiting input process is a Gaussian process. When the limiting net-input process is also a Gaussian process and there is unlimited waiting room, the steady-state distribution of the limiting reflected Gaussian process can be conveniently approximated. This revised version was published online in June 2006 with corrections to the Cover Date.     

Heavy-traffic limits for stationary network flows

This paper studies stationary customer flows in an open queueing network. The flows are the processes counting customers flowing from one queue to another or out of the network. We establish the existence of unique stationary flows in generalized Jackson networks and convergence to the stationary flows as time increases. We establish heavy-traffic limits for the stationary flows, allowing an arbitrary subset of the queues to be critically loaded. The heavy-traffic limit with a single bottleneck queue is especially tractable because it yields limit processes involving one-dimensional reflected Brownian motion. That limit plays an important role in our new nonparametric decomposition approximation of the steady-state performance using indices of dispersion and robust optimization.

     

高负荷下非强占优先排队网络系统中队长过程的扩散逼近

本文是在高负荷下非强占优先排除网络系统中给出了队长过程的扩散逼近 .证明了其队长过程的扩散极限是半鞅反射的布朗运动 .     

Heavy traffic approximations of large deviations of feedforward queueing networks

We consider a multi-class feedforward queueing network with first come first serve queueing discipline and deterministic services and routing. The large deviation asymptotics of tail probabilities of the distribution of the workload vector can be characterized by convex path space minimization problems with non-linear constraints. So far there exists no numerical algorithm which could solve such minimization problems in a general way. When the queueing network is heavily loaded it can be approximated by a reflected Brownian motion. The large deviation asymptotics of tail probabilities of the distribution of this heavy traffic limit can again be characterized by convex path space minimization problems with non-linear constraints. However, due to their less complicated structure there exist algorithms to solve such minimization problems. In this paper we show that, as the network tends to a heavy traffic limit, the solution of the large deviation minimization problems of the network approaches the solution of the corresponding minimization problems of a reflected Brownian motion. Stated otherwise, we show that large deviation and heavy traffic asymptotics can be interchanged. We prove this result in the case when the network is initially empty. Without proof we state the corresponding result in the stationary case. We present an illuminating example with two queues. This revised version was published online in June 2006 with corrections to the Cover Date.     

Heavy-traffic analysis of the sojourn time in a three node Jackson network with overtaking

We consider a Jackson network consisting of three first-in-first-out (FIFO)M/M/1 queues. When customers leave the first queue they can be routed to either the second or third queue. Thus, a customer that traverses the network by going from the first to the second to the third queue, can be overtaken by another customer that is routed from the first queue directly to the third. We study the distribution of the sojourn time of a customer through the three node network, in the heavy traffic limit. A three term heavy traffic asymptotic approximation to the sojourn time density is derived. The leading term shows that the nodes decouple in the heavy traffic limit. The next two terms, however, do show the dependence of the sojourn times at the individual nodes and give quantitative measures of the effects of overtaking.     

Brownian models of multiclass queueing networks: Current status and open problems

This paper is concerned with Brownian system models that arise as heavy traffic approximations for open queueing networks. The focus is on model formulation, and more specifically, on the formulation of Brownian models for networks with complex routing. We survey the current state of knowledge in this dynamic area of research, including important open problems. Brownian approximations culminate in estimates of complete distributions; we present numerical examples for which complete sojourn time distributions are estimated, and those estimates are compared against simulation.     

Distributional Form of Little's Law for FIFO Queues with Multiple Markovian Arrival Streams and Its Application to Queues with Vacations

This paper considers stationary queues with multiple arrival streams governed by an irreducible Markov chain. In a very general setting, we first show an invariance relationship between the time-average joint queue length distribution and the customer-average joint queue length distribution at departures. Based on this invariance relationship, we provide a distributional form of Little's law for FIFO queues with simple arrivals (i.e., the superposed arrival process has the orderliness property). Note that this law relates the time-average joint queue length distribution with the stationary sojourn time distributions of customers from respective arrival streams. As an application of the law, we consider two variants of FIFO queues with vacations, where the service time distribution of customers from each arrival stream is assumed to be general and service time distributions of customers may be different for different arrival streams. For each queue, the stationary waiting time distribution of customers from each arrival stream is first examined, and then applying the Little's law, we obtain an equation which the probability generating function of the joint queue length distribution satisfies. Further, based on this equation, we provide a way to construct a numerically feasible recursion to compute the joint queue length distribution.     

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.     

About the Sojourn Time Process in Multiphase Queueing Systems

Multiphase queueing systems (MQS) (tandem queues, queues in series) are of special interest both in theory and in practical applications (packet switch structures, cellular mobile networks, message switching systems, retransmission of video images, asembly lines, etc.). In this paper, we deal with approximations of MQS and present a heavy traffic limit theorems for the sojourn time of a customer in MQS. Functional limit theorems are proved for the customer sojourn time – an important probability characteristic of the queueing system under conditions of heavy traffic.      

M/T-SPH/1排队平稳指标分布的尾部衰减特征

讨论M/T-SPH/1排队平稳队长分布和平稳逗留时间分布的尾部衰减特征,其中T-SPH表示可数状态吸收生灭过程吸收时间的分布。在分布PGF和LST的基础上,给出了两个平稳分布衰减规律的完整分析.结果表明,当参数取不同值时,平稳队长与平稳逗留时间的尾部具有三种不同类型的衰减特征.     

Stability and performance analysis of rate-based feedback flow controlled ATM networks

Motivated by ABR class of service in ATM networks, we study a continuous time queueing system with a feedback control of the arrival rate of some of the sources. The feedback about the queue length or the total workload is provided at regular intervals (variations on it, especially the traffic management specification TM 4.0, are also considered). The propagation delays can be nonnegligible. For a general class of feedback algorithms, we obtain the stability of the system in the presence of one or more bottleneck nodes in the virtual circuit. Our system is general enough that it can be useful to study feedback control in other network protocols. We also obtain rates of convergence to the stationary distributions and finiteness of moments. For the single botterneck case, we provide algorithms to compute the stationary distributions and the moments of the sojourn times in different sets of states. We also show analytically (by showing continuity of stationary distributions and moments) that for small propagation delays, we can provide feedback algorithms which have higher mean throughput, lower probability of overflow and lower delay jitter than any open loop policy. Finally these results are supplemented by some computational results. This revised version was published online in June 2006 with corrections to the Cover Date.     

Insensitive bounds for the moments of the sojourn time distribution in the M/G/1 processor-sharing queue

This paper studies the M/G/1 processor-sharing (PS) queue, in particular the sojourn time distribution conditioned on the initial job size. Although several expressions for the Laplace-Stieltjes transform (LST) are known, these expressions are not suitable for computational purposes. This paper derives readily applicable insensitive bounds for all moments of the conditional sojourn time distribution. The instantaneous sojourn time, i.e., the sojourn time of an infinitesimally small job, leads to insensitive upper bounds requiring only knowledge of the traffic intensity and the initial job size. Interestingly, the upper bounds involve polynomials with so-called Eulerian numbers as coefficients. In addition, stochastic ordering and moment ordering results for the sojourn time distribution are obtained. AMS Subject Classification: 60K25, 60E15 This work has been partially funded by the Dutch Ministry of Economic Affairs under the program ‘Technologische Samenwerking ICT-doorbraakprojecten’, project TSIT1025 BEYOND 3G.     

Numerical Computation and Tail Asymptotic for Stationary Indices of a Discrete-Time Vacation Queue

In this paper we study a Geo/Geo/1 queue with T-IPH vacations, where T-IPH denotes the discrete-time phase type distribution defined on a birth and death process with countably many states. Both the multiple and single vacation strategies are considered. For each case, based on the system of stationary equations and using complex analysis method, we firstly give the probability generating functions (PGFs) of stationary distributions for queue length and sojourn time. Moreover, by analysis the PGFs, recursive and asymptotic formulas for additional queue length and additional delay are also given. Finally, we further give some numerical examples to show the effectiveness of the method.     

对M/T-SPH/1排队平稳指标的进一步研究—数值计算与渐近分析

讨论M/T-SPH/1排队平稳队长分布的数值计算,以及平稳队长和逗留时间分布各阶矩的数值计算及渐近分析.其中T-SPH表示可数状态吸收生灭链吸收时间的分布.在分布PGF和LST的基础上,首先给出了计算平稳队长分布,平稳队长以及逗留时间分布各阶矩的数值结果的递推公式.其次还讨论了平稳队长及平稳逗留时间分布各阶矩的尾部渐近...     

State-space collapse in stationarity and its application to a multiclass single-server queue in heavy traffic

Recently Gamarnik and Zeevi (Ann. Appl. Probab. 16:56–90, 2006) and Budhiraja and Lee (Math. Oper. Res. 34:45–56, 2009) established that, under suitable conditions, a sequence of the stationary scaled queue lengths in a generalized Jackson queueing network converges to the stationary distribution of multidimensional reflected Brownian motion in the heavy-traffic regime. In this work we study the corresponding problem in multiclass queueing networks (MQNs).     

Heavy traffic limits associated with >M/G/∞ input processes

We study the heavy traffic regime of a discrete-time queue driven by correlated inputs, namely the M/G/ input processes of Cox. We distinguish between M/G/ processes with short- and long-range dependence, identifying in each case the appropriate heavy traffic scaling that results in a nondegenerate limit. As expected, the limits we obtain for short-range dependent inputs involve the standard Brownian motion. Of particular interest are the conclusions for the long-range dependent case: the normalized queue length can be expressed as a function not of a fractional Brownian motion, but of an -stable, 1/ self-similar independent increment Lévy process. The resulting buffer content distribution in heavy traffic is expressed through a Mittag–Leffler special function and displays a hyperbolic decay of power 1-. Thus, M/G/ processes already demonstrate that under long-range dependence, fractional Brownian motion does not necessarily assume the ubiquitous role that standard Brownian motion plays in the short-range dependence setup.