Approximations of open queueing networks by reflection mappings

This paper presents a three-step procedure which allows to approximate the queue-length and the busy-time processes associated with open queueing networks. These three approximations are based on reflection mappings and are introduced with explicit estimates of their accuracy. The third one may be treated as approximation by accompanying reflection Brownian motions with rates of convergence. This revised version was published online in June 2006 with corrections to the Cover Date.     

Computing the Stationary Distribution of an SRBM in an Orthant with Applications to Queueing Networks

In [15], a BNAfm (Brownian network analyzer with finite element method) algorithm was developed for computing the stationary distribution of a semimartingale reflecting Brownian motion (SRBM) in a hypercube. In this companion paper, that BNAfm algorithm is extended to computing the stationary distribution of an SRBM in an orthant, which is achieved by constructing a converging sequence of SRBMs in hypercubes. The SRBM in the orthant serves as an approximation model of queueing networks with infinite buffers. We show that the constructed sequence of SRBMs in the hypercubes converges weakly to the SRBM in the orthant as the hypercubes approach the orthant. Under the conjecture that the set of the stationary distributions of the SRBMs in the hypercubes is relatively compact, we prove that the sequence of the stationary distributions of the SRBMs in the hypercubes converges weakly to the stationary distribution of the SRBM in the orthant. A three-machine job shop example is presented to illustrate the effectiveness of the SRBM approximation model and our BNAfm algorithm. The BNAfm algorithm is shown to produce good estimates for stationary probabilities of queueing networks.     

The Finite Element Method for Computing the Stationary Distribution of an SRBM in a Hypercube with Applications to Finite Buffer Queueing Networks

This paper proposes an algorithm, referred to as BNAfm (Brownian network analyzer with finite element method), for computing the stationary distribution of a semimartingale reflecting Brownian motion (SRBM) in a hypercube. The SRBM serves as an approximate model of queueing networks with finite buffers. Our BNAfm algorithm is based on the finite element method and an extension of a generic algorithm developed by Dai and Harrison [14]. It uses piecewise polynomials to form an approximate subspace of an infinite-dimensional functional space. The BNAfm algorithm is shown to produce good estimates for stationary probabilities, in addition to stationary moments. This is in contrast to the BNAsm algorithm (Brownian network analyzer with spectral method) of Dai and Harrison [14], which uses global polynomials to form the approximate subspace and which sometimes fails to produce meaningful estimates of these stationary probabilities. Extensive computational experiences from our implementation are reported, which may be useful for future numerical research on SRBMs. A three-station tandem network with finite buffers is presented to illustrate the effectiveness of the Brownian approximation model and our BNAfm algorithm.     

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

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

Nonexistence of Brownian models for certain multiclass queueing networks

We present two multiclass queueing networks where the Brownian models proposed by Harrison and Nguyen [3,4] do not exist. If self-feedback is allowed, we can construct such an example with a two-station network. For a three-station network, we can construct such an example without self-feedback.Research supported in part by Texas Instruments Corporation Grant 90456-034.     

Heavy traffic analysis of a storage model with long range dependent On/Off sources

We consider a fluid queueing system with infinite storage capacity and constant output rate offered a superposition ofN identical On/Off sources, where the ratio of input to output rate is small. The On and/or Off periods have heavy tailed distributions with infinite variance, giving rise to Long Range Dependence in the arrival process. In the limit of a large number of sources and high load, it is shown that the tail of the stationary queue content distribution is Weibullian, implying much larger queue contents than in the classical case of exponential tails. Noting that similar results were recently found by I. Norros for a storage system input by a Fractional Brownian Motion, we then show how the two models are related, thus providing a further physical motivation for the Fractional Brownian Motion model.     

Dynamic routing in open queueing networks: Brownian models,cut constraints and resource pooling

We present an introductory review of recent work on the control of open queueing networks. We assume that customers of different types arrive at a network and pass through the system via one of several possible routes; the set of routes available to a customer depends on its type. A route through the network is an ordered set of service stations: a customer queues for service at each station on its route and then leaves the system. The two methods of control we consider are the routing of customers through the network, and the sequencing of service at the stations, and our aim is to minimize the number of customers in the system. We concentrate especially on the insights which can be obtained from heavy traffic analysis, and in particular from Harrison's Brownian network models. Our main conclusion is that in many respects dynamic routingsimplifies the behaviour of networks, and that under good control policies it may well be possible to model the aggregate behaviour of a network quite straightforwardly.Supported by SERC grant GR/F 94194.     

An invariance principle for semimartingale reflecting Brownian motions in an orthant

Semimartingale reflecting Brownian motions in an orthant (SRBMs) are of interest in applied probability because of their role as heavy traffic approximations for open queueing networks. It is shown in this paper that a process which satisfies the definition of an SRBM, except that small random perturbations in the defining conditions are allowed, is close in distribution to an SRBM. This perturbation result is called an invariance principle by analogy with the invariance principle of Stroock and Varadhan for diffusions with boundary conditions. A crucial ingredient in the proof of this result is an oscillation inequality for solutions of a perturbed Skorokhod problem. In a subsequent paper, the invariance principle is used to give general conditions under which a heavy traffic limit theorem holds for open multiclass queueing networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

抢占型优先服务机制下多类排队网络的扩散逼近

证明一个满负荷交通极限定理以证实在抢占型优先服务机制下多类排队网络的扩散逼近,进而为该系统提供有效的随机动力学模型．所研究的排队网络典型地出现在现代通讯系统中高速集成服务分组数据网络,其中包含分组数据包的若干交通类型,每个类型涉及若干工作处理类（步骤）,并且属于同一交通类型的工作在可能接受服务的每一个网站被赋予相同的优先权等级,更进一步地,在整个网络中,属于不同交通类型的分组数据包之间无交互路由．     

Packet Models Revisited: Tandem and Priority Systems

We examine two extensions of traditional single-node packet-scale queueing models: tandem networks and (strict) priority systems. Two generic input processes are considered: periodic and Poisson arrivals. For the two-node tandem, an exact expression is derived for the joint distribution of the total queue length, and the queue length of the first queue, implicitly determining the distribution of the second queue. Similarly we derive the distribution of the low-priority queue in a two-class priority system. We also provide explicit approximations based on the Brownian bridge.     

Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse

Certain diffusion processes known as semimartingale reflecting Brownian motions (SRBMs) have been shown to approximate many single class and some multiclass open queueing networks under conditions of heavy traffic. While it is known that not all multiclass networks with feedback can be approximated in heavy traffic by SRBMs, one of the outstanding challenges in contemporary research on queueing networks is to identify broad categories of networks that can be so approximated and to prove a heavy traffic limit theorem justifying the approximation. In this paper, general sufficient conditions are given under which a heavy traffic limit theorem holds for open multiclass queueing networks with head-of-the-line (HL) service disciplines, which, in particular, require that service within each class is on a first-in-first-out (FIFO) basis. The two main conditions that need to be verified are that (a) the reflection matrix for the SRBM is well defined and completely- S, and (b) a form of state space collapse holds. A result of Dai and Harrison shows that condition (a) holds for FIFO networks of Kelly type and their proof is extended here to cover networks with the HLPPS (head-of-the-line proportional processor sharing) service discipline. In a companion work, Bramson shows that a multiplicative form of state space collapse holds for these two families of networks. These results, when combined with the main theorem of this paper, yield new heavy traffic limit theorems for FIFO networks of Kelly type and networks with the HLPPS service discipline. This revised version was published online in June 2006 with corrections to the Cover Date.     

Harnack inequalities for SDEs driven by subordinate Brownian motions

By using regularization approximations of the underlying subordinator and a gradient estimate approach, the dimension-independent Harnack inequalities are established for the inhomogeneous semigroup associated with a class of SDEs with Lévy noise containing a subordinate Brownian motion. Our estimates in Harnack type inequalities improve the corresponding ones in the recent paper by Wang and Wang (2014) [10].     

On Double Stratonovich Fractional Integrals and Some Strong and Weak Approximations

Abstract

Double Stratonovich integrals with respect to the odd part and even part of the fractional Brownian motion are constructed. The first and the second moments of such integrals are explicitly identified. As application of double Stratonovich integrals a strong law of large numbers for efBm and ofBm is derived.

Riemann–Stieltjes integral approximations to double Stratonovich fractional integrals are also considered. The strong convergence (almost surely and mean square) is obtained for approximations based on explicit series expansions of the fractional Brownian processes. The weak convergence is derived for approximations by processes with absolutely continuous paths which converge weakly to the considered fractional Brownian processes. The above-mentioned convergences are obtained for deterministic integrands which are given by bimeasures.     

Diffusion approximations for re-entrant lines with a first-buffer-first-served priority discipline

The diffusion approximation is proved for a class of queueing networks, known as re-entrant lines, under a first-buffer-first-served (FBFS) service discipline. The diffusion limit for the workload process is a semi-martingale reflecting Brownian motion on a nonnegative orthant. This approximation has recently been used by Dai, Yeh and Zhou [21] in estimating the performance measures of the re-entrant lines with a FBFS discipline.Supported in part by a grant from NSERC (Canada).Supported in part by a grant from NSERC (Canada); the research was done while the author was visiting the Faculty of Commerce and Business Administration, UBC, Canada.     

Heavy traffic resource pooling in parallel‐server systems

We consider a queueing system with r non‐identical servers working in parallel, exogenous arrivals into m different job classes, and linear holding costs for each class. Each arrival requires a single service, which may be provided by any of several different servers in our general formulation; the service time distribution depends on both the job class being processed and the server selected. The system manager seeks to minimize holding costs by dynamically scheduling waiting jobs onto available servers. A linear program involving only first‐moment data (average arrival rates and mean service times) is used to define heavy traffic for a system of this form, and also to articulate a condition of overlapping server capabilities which leads to resource pooling in the heavy traffic limit. Assuming that the latter condition holds, we rescale time and state space in standard fashion, then identify a Brownian control problem that is the formal heavy traffic limit of our rescaled scheduling problem. Because of the assumed overlap in server capabilities, the limiting Brownian control problem is effectively one‐dimensional, and it admits a pathwise optimal solution. That is, in the limiting Brownian control problem the multiple servers of our original model merge to form a single pool of service capacity, and there exists a dynamic control policy which minimizes cumulative cost incurred up to any time t with probability one. Interpreted in our original problem context, the Brownian solution suggests the following: virtually all backlogged work should be held in one particular job class, and all servers can and should be productively employed except when the total backlog is small. It is conjectured that such ideal system behavior can be approached using a family of relatively simple scheduling policies related to the cμ rule. This revised version was published online in June 2006 with corrections to the Cover Date.     

时间序列中参数变点的检测(英文)

The paper considers the problem of testing for a change point in the parameters of AR（p） models.It is shown that the asymptotically limiting distribution of the residual CUSUM of squares test（RCUSQ） is still the sup of a standard Brownian bridge under null hypothesis.We also show via simulations that our asymptotic results provide good approximations in finite samples.     

Critical Thresholds for Dynamic Routing in Queueing Networks

This paper studies dynamic routing in a parallel server queueing network with a single Poisson arrival process and two servers with exponential processing times of different rates. Each customer must be routed at the time of arrival to one of the two queues in the network. We establish that this system operating under a threshold policy can be well approximated by a one-dimensional reflected Brownian motion when the arrival rate to the network is close to the processing capacity of the two servers. As the heavy traffic limit is approached, thresholds which grow at a logarithmic rate are critical in determining the behavior of the limiting system. We provide necessary and sufficient conditions on the growth rate of the threshold for (i) approximation of the network by a reflected Brownian motion (ii) positive recurrence of the limiting Brownian diffusion and (iii) asymptotic optimality of the threshold policy.     

Periodic load balancing

Multiprocessor load balancing aims to improve performance by moving jobs from highly loaded processors to more lightly loaded processors. Some schemes allow only migration of new jobs upon arrival, while other schemes allow migration of jobs in progress. A difficulty with all these schemes, however, is that they require continuously maintaining detailed state information. In this paper we consider the alternative of periodic load balancing, in which the loads are balanced only at each T time units for some appropriate T. With periodic load balancing, state information is only needed at the balancing times. Moreover, it is often possible to use slightly stale information collected during the interval between balancing times. In this paper we study the performance of periodic load balancing. We consider multiple queues in parallel with unlimited waiting space to which jobs come either in separate independent streams or by assignment (either random or cyclic) from a single stream. Resource sharing is achieved by periodically redistributing the jobs or the work in the system among the queues. The performance of these systems of queues coupled by periodic load balancing depends on the transient behavior of a single queue. We focus on useful approximations obtained by considering a large number of homogeneous queues and a heavy load. When the number of queues is sufficiently large, the number of jobs or quantity of work at each queue immediately after redistribution tends to evolve deterministically, by the law of large numbers. The steady-state (limiting) value of this deterministic sequence is obtained as the solution of a fixed point equation, where the initial value is equal to the expected transient value over the interval between successive redistributions conditional on the initial value. A refined approximation based on the central limit theorem is a normal distribution, where the mean and variance are obtained by solving a pair of fixed-point equations. With higher loads, which is natural to consider when load balancing is performed, a heavy-traffic limit theorem shows that one-dimensional reflected Brownian motion can be used to approximately describe system performance, even with general arrival and service processes. With these approximations, we show how performance depends on the assumed arrival pattern of jobs and the model parameters. We do numerical calculations and conduct simulation experiments to show the accuracy of the approximations. This revised version was published online in June 2006 with corrections to the Cover Date.     

Two Workload Properties for Brownian Networks

As one approach to dynamic scheduling problems for open stochastic processing networks, J.M. Harrison has proposed the use of formal heavy traffic approximations known as Brownian networks. A key step in this approach is a reduction in dimension of a Brownian network, due to Harrison and Van Mieghem [21], in which the queue length process is replaced by a workload process. In this paper, we establish two properties of these workload processes. Firstly, we derive a formula for the dimension of such processes. For a given Brownian network, this dimension is unique. However, there are infinitely many possible choices for the workload process. Harrison [16] has proposed a canonical choice, which reduces the possibilities to a finite number. Our second result provides sufficient conditions for this canonical choice to be valid and for it to yield a non-negative workload process. The assumptions and proofs for our results involve only first-order model parameters.     

Optimal Bounds for Cauchy Approximations for the Winding Distribution of Planar Brownian Motion

Optimal nonuniform bounds are given for the remainder terms in Spitzer's theorem, which gives some final answer to the question of Cauchy approximations for the winding distribution of planar Brownian motion. As a corollary, a large deviation result is presented. Optimal nonuniform bounds for the approximations of the density are also derived.