Large deviations of the steady-state distribution of reflected processes with applications to queueing systems

We consider a Skorohod map which takes paths in to paths which stay in the positive orthant . We let be the domain of definition of . A convex and lower semi-continuous function and a set are given. We are concerned with the calculation of the infimum of the value for t ⩾ 0 and absolutely continuous subject to the conditions and . We show that such minimization problems characterize large deviation asymptotics of tail probabilities of the steady-state distribution of certain reflected processes. We approximate the infimum by a sequence of finite-dimensional minimization problems. This approximation allows to formulate an algorithm for the calculation of the infimum and to derive analytical bounds for its value. Several applications are discussed including large deviations of generalized processor sharing and large deviations of heavily loaded queueing networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

A note on the delay distribution in GPS

In this note a two-class generalized processor sharing (GPS) system is considered. We analyze the probability that the virtual delay of a particular class exceeds some threshold. We apply Schilder's theorem to calculate the logarithmic many-sources asymptotics of this probability in the important case of Gaussian inputs.     

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.     

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.     

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.     

Some Asymptotic Results for the Number of Generalized Records

In this paper, we study asymptotic properties (large deviations and functional central limit theorem) of generalized record processes built on a triangular array of continuous and exchangeable random variables. As an application of these results, the links with the Kendall's rank correlation statistic are studied and testing exchangeability is discussed. AMS 2000 Subject Classification Primary—60F10 Secondary—60F17, 62G10     

A Skorokhod Problem formulation and large deviation analysis of a processor sharing model

Generalized processor sharing has been proposed as a policy for distributing processing in a fair manner between different data classes in high-speed networks. In this paper we show how recent results on the Skorokhod Problem can be used to construct and analyze the mapping that takes the input processes into the buffer content. More precisely, we show how to represent the map in terms of a Skorokhod Problem, and from this infer that the mapping is well defined (existence and uniqueness) and well behaved (Lipschitz continuity). As an elementary application we present some large deviation estimates for a many data source model. This revised version was published online in June 2006 with corrections to the Cover Date.     

State space collapse with application to heavy traffic limits for multiclass queueing networks

Heavy traffic limits for multiclass queueing networks are a topic of continuing interest. Presently, the class of networks for which these limits have been rigorously derived is restricted. An important ingredient in such work is the demonstration of state space collapse. Here, we demonstrate state space collapse for two families of networks, first-in first-out (FIFO) queueing networks of Kelly type and head-of-the-line proportional processor sharing (HLPPS) queueing networks. We then apply our techniques to more general networks. To demonstrate state space collapse for FIFO networks of Kelly type and HLPPS networks, we employ law of large number estimates to show a form of compactness for appropriately scaled solutions. The limits of these solutions are next shown to satisfy fluid model equations corresponding to the above queueing networks. Results from Bramson [4,5] on the asymptotic behavior of these limits then imply state space collapse. The desired heavy traffic limits for FIFO networks of Kelly type and HLPPS networks follow from this and the general criteria set forth in the companion paper Williams [41]. State space collapse and the ensuing heavy traffic limits also hold for more general queueing networks, provided the solutions of their fluid model equations converge. Partial results are given for such networks, which include the static priority disciplines. This revised version was published online in June 2006 with corrections to the Cover Date.     

广义凸函数的特征性质

提出广义凸集、广义凸函数、中间点广义凸函数、端点广义凸函数四个定义,通过定义条件P1,研究条件P1所蕴含的等式关系,进而得到一个基础性定理一稠密性定理和一个相对条件较弱的推论,最后将结果应用于若干不同类型的广义凸函数类,尤其是s-凸函数、几何凸函数、rp-凸函数,得到它们所共有的一个特征性质,即满足稠密性定理．     

Large deviations for generalized compound Poisson risk models and its bankruptcy moments

We extend the classical compound Poisson risk model to the case where the premium income process, based on a Poisson process, is no longer a linear function. For this more realistic risk model, Lundberg type limiting results on the finite time ruin probabilities are derived. Asymptotic behaviour of the tail probabilities of the claim surplus process is also investigated.     

Performance analysis of a constrained resource sharing system

We consider a queueing system where the servers are arranged in a circle, and each arriving customer requires a pair of resources that is shared by its server with the respective neighbors on either side. If either resource is being used, the customer is denied service. Customers arrive at each server according to independent Poisson processes, and lengths of service times at each server have an exponential distribution. We derive a closed-form formula for the expected fraction of busy servers at any time in terms of the number of servers and the utilization factor (defined as the arrival rate times the mean service-time duration). This allows us to evaluate system performance when these parameters are varied, and to determine whether denying service to arrivals at alternate servers improves performance. We relate the system to Dijkstra's dining philosophers problem, which is an abstraction for resource sharing in an operating system. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Reduced-Load Equivalence for Generalised Processor Sharing Networks with Long-Tailed Input Flows

We consider networks where traffic is served according to the Generalised Processor Sharing (GPS) principle. GPS-based scheduling algorithms are considered important for providing differentiated quality of service in integrated-services networks. We are interested in the workload of a particular flow i at the bottleneck node on its path. Flow i is assumed to have long-tailed traffic characteristics. We distinguish between two traffic scenarios, (i) flow i generates instantaneous traffic bursts and (ii) flow i generates traffic according to an on/off process. In addition, we consider two configurations of feed-forward networks. First we focus on the situation where other flows join the path of flow i. Then we extend the model by adding flows which can branch off at any node, with cross traffic as a special case. We prove that under certain conditions the tail behaviour of the workload distribution of flow i is equivalent to that in a two-node tandem network where flow i is served in isolation at constant rates. These rates only depend on the traffic characteristics of the other flows through their average rates. This means that the results do not rely on any specific assumptions regarding the traffic processes of the other flows. In particular, flow i is not affected by excessive activity of flows with heavier-tailed traffic characteristics. This confirms that GPS has the potential to protect individual flows against extreme behaviour of other flows, while obtaining substantial multiplexing gains.     

Stochastic programming approaches to stochastic scheduling

Practical scheduling problems typically require decisions without full information about the outcomes of those decisions. Yields, resource availability, performance, demand, costs, and revenues may all vary. Incorporating these quantities into stochastic scheduling models often produces diffculties in analysis that may be addressed in a variety of ways. In this paper, we present results based on stochastic programming approaches to the hierarchy of decisions in typical stochastic scheduling situations. Our unifying framework allows us to treat all aspects of a decision in a similar framework. We show how views from different levels enable approximations that can overcome nonconvexities and duality gaps that appear in deterministic formulations. In particular, we show that the stochastic program structure leads to a vanishing Lagrangian duality gap in stochastic integer programs as the number of scenarios increases.This author's work was supported in part by the National Science Foundation under Grants ECS 88-15101, ECS 92-16819, and SES 92-11937.This author's work was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant A-5489 and by the UK Engineering and Physical Sciences Research Council under Grants J90855 and K17897.     

The asymptotic behavior of fragmentation processes

The fragmentation processes considered in this work are self-similar Markov processes which are meant to describe the evolution of a mass that falls apart randomly as time passes. We investigate their pathwise asymptotic behavior as t. In the so-called homogeneous case, we first point at a law of large numbers and a central limit theorem for (a modified version of) the empirical distribution of the fragments at time t. These results are reminiscent of those of Asmussen and Kaplan [3] and Biggins [12] for branching random walks. Next, in the same vein as Biggins [10], we also investigate some natural martingales, which open the way to an almost sure large deviation principle by an application of the Gärtner-Ellis theorem. Finally, some asymptotic results in the general self-similar case are derived by time-change from the previous ones. Properties of size-biased picked fragments provide key tools for the study. Mathematics Subject Classification (2000) 60J25, 60G09     

The Janson inequalities for general up‐sets

Janson and Janson, ?uczak and Ruciński proved several inequalities for the lower tail of the distribution of the number of events that hold, when all the events are up‐sets (increasing events) of a special form—each event is the intersection of some subset of a single set of independent events (i.e., a principal up‐set). We show that these inequalities in fact hold for arbitrary up‐sets, by modifying existing proofs to use only positive correlation, avoiding the need to assume positive correlation conditioned on one of the events. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 391–395, 2015     

广义重心坐标与凸多胞形的性质

提出n维欧氏空间中广义重心坐标的概念,建立了广义重心坐标下两点间的距离公式,并利用于研究凸多胞形的若干性质,将欧氏平面上凸多边形的一些定值与极值性质推广到n维空间.     

Brown运动连续模在Holder范数下的收敛速率

应用Brown运动在Holder范数下的大偏差和小偏差得到了Brown运动连续模在Holder范数下的泛函极限的收敛速率.     

一般非均匀凸介质的迁移算子广义本征函数系统的完整性

该文讨论一般非均匀凸介质所确定的迁移算子的广义本征函数系统的完整性问题，利用我们探索的相对收敛方法，完整地刻划了一般非均匀凸介质中迁移问题的广义本征函数系统的完整性问题，我们证明了，对迁移半群E（t），当0∈Pσ（E（t）），迁移算子广义本征函数系统不完整，当0∈Pσ（E（t））时，仅当满足相对收敛条件时，迁移算子的广义本征函数系统完整．     

The BCD queue and its ramifications

We introduce a process similar to the birth-death process and use it as a starting point for defining queueing models much in the same way as the birth-death process can be used for this purpose. Steady-state distributions for this process and the corresponding queues are derived. Generalizations allowing nonexponential service times are also studied.