Search

We consider a system of $N$ identical server pools and a single dispatcher where tasks arrive as a Poisson process of rate $\lambda(N)$. Arriving tasks cannot be queued, and must immediately be assigned to one of the server pools to start execution, or discarded. The execution times are assumed to be exponentially distributed with unit mean, and do not depend on the number of other tasks receiving service. However, the experienced performance (e.g. in terms of received throughput) does degrade with an increasing number of concurrent tasks at the same server pool. The dispatcher therefore aims to evenly distribute the tasks across the various server pools. Specifically, when a task arrives, the dispatcher assigns it to the server pool with the minimum number of tasks among $d(N)$ randomly selected server pools. This assignment strategy is called the JSQ$(d(N))$ scheme, as it resembles the power-of-$d$ version of the Join-the-Shortest-Queue (JSQ) policy, and will also be referred to as such in the special case $d(N) = N$. We construct a stochastic coupling to bound the difference in the system occupancy processes between the JSQ policy and a scheme with an arbitrary value of $d(N)$. We use the coupling to derive the fluid limit in case $d(N) \to \infty$ and $\lambda(N)/N \to \lambda$ as $N \to \infty$, along with the associated fixed point. The fluid limit turns out to be insensitive to the exact growth rate of $d(N)$, and coincides with that for the JSQ policy. We further leverage the coupling to establish that the diffusion limit corresponds to that for the JSQ policy as well, as long as $d(N)/\sqrt{N} \log(N) \to \infty$, and characterize the common limiting diffusion process. These results indicate that the JSQ optimality can be preserved at the fluid-level and diffusion-level while reducing the overhead by nearly a factor O($N$) and O($\sqrt{N}/\log(N)$), respectively., Comment: 48 pages, 3 figures, companion paper of arXiv:1612.00723

We analyze a tractable model of a limit order book on short time scales, where the dynamics are driven by stochastic fluctuations between supply and demand. We establish the existence of a limiting distribution for the highest bid, and for the lowest ask, where the limiting distributions are confined between two thresholds. We make extensive use of fluid limits in order to establish recurrence properties of the model. We use the model to analyze various high-frequency trading strategies, and comment on the Nash equilibria that emerge between high-frequency traders when a market in continuous time is replaced by frequent batch auctions., Revision of the submitted version: correcting an error (caught by Jan Swart) in the statement of Proposition 4.1 (1), propagating to Theorem 2.1 (1)

A single queueing station serving K input streams with renewal arrivals and generally distributed independent and identically distributed service times is considered. Customers are served by the Shortest Remaining Processing Time policy. In the case of a tie, the first-in, first-out policy is utilized. We analyze a fluid model for the evolution of a measure-valued state descriptor of this system, with particular emphasis on its limiting behavior in the critical case as time gets large. We also prove a fluid limit theorem justifying our fluid model as the first-order approximation of the queueing system under consideration. Along the way, we establish fluid limits for the corresponding state-dependent response times.

A single-server queueing model is considered with customers that have deadlines. If a customer’s deadline elapses before service is offered, the customer abandons the system (customers do not abandon while being served). When the server becomes available, it offers service to the customer having the earliest deadline among those that are in the queue. We obtain a fluid limit of the queue length and abandonment processes and for the occupation measure of deadlines, in the form of measure-valued processes. We characterize the limit by means of a Skorohod problem in a time-varying domain that has an explicit solution. The fluid limits also describe a certain process called the frontier that is well known to play a key role in systems operating under this scheduling policy.

Bandwidth-sharing networks as considered by Roberts and Massoulié [28] (Roberts JW, Massoulié L (1998) Bandwidth sharing and admission control for elastic traffic. Proc. ITC Specialist Seminar, Yokohama, Japan) provide a natural modeling framework for describing the dynamic flow-level interaction among elastic data transfers. Under mild assumptions, it has been established that a wide family of so-called α-fair bandwidth-sharing strategies achieve stability in such networks provided that no individual link is overloaded. In the present paper we focus on bandwidth-sharing networks where the load on one or several of the links exceeds the capacity. To characterize the overload behavior, we examine the fluid limit, which emerges when the flow dynamics are scaled in both space and time. We derive a functional equation characterizing the fluid limit, and show that any strictly positive solution must be unique, which in particular implies the convergence of the scaled number of flows to the fluid limit for nonzero initial states when the load is sufficiently high. For the case of a zero initial state and a zero-degree homogeneous rate allocation function, we show that there exists a linear solution to the fluid-limit equation, and obtain a fixed-point equation for the corresponding asymptotic growth rates. It is proved that a fixed-point solution is also a solution to a related strictly concave optimization problem, and hence exists and is unique. In addition, we establish uniqueness of fluid-model solutions for monotone rate-preserving networks (in particular tree networks).

We prove a many-server heavy-traffic fluid limit for an overloaded Markovian queueing system having two customer classes and two service pools, known in the call-center literature as the X model. The system uses the fixed-queue-ratio-with-thresholds (FQR-T) control, which we proposed in a recent paper as a way for one service system to help another in face of an unexpected overload. Under FQR-T, customers are served by their own service pool until a threshold is exceeded. Then, one-way sharing is activated with customers from one class allowed to be served in both pools. After the control is activated, it aims to keep the two queues at a prespecified fixed ratio. For large systems that fixed ratio is achieved approximately. For the fluid limit, or FWLLN (functional weak law of large numbers), we consider a sequence of properly scaled X models in overload operating under FQR-T. Our proof of the FWLLN follows the compactness approach, i.e., we show that the sequence of scaled processes is tight and then show that all converging subsequences have the specified limit. The characterization step is complicated because the queue-difference processes, which determine the customer-server assignments, need to be considered without spatial scaling. Asymptotically, these queue-difference processes operate on a faster time scale than the fluid-scaled processes. In the limit, because of a separation of time scales, the driving processes converge to a time-dependent steady state (or local average) of a time-varying fast-time-scale process (FTSP). This averaging principle allows us to replace the driving processes with the long-run average behavior of the FTSP.

We consider a canonical revenue management problem in a network setting where the goal is to find a customer admission policy to maximize the total expected revenue over a fixed finite horizon. There is a set of resources, each of which has a fixed capacity. There are several customer classes, each with an associated arrival process, price, and resource consumption vector. If a customer is accepted, it effectively removes the resources that it consumes from the system. The exact solution cannot be obtained for reasonable-sized problems due to the curse of dimensionality. Several (approximate) solution techniques have been proposed in the literature. One way to analytically compare policies is via an asymptotic analysis where both resource sizes and arrival rates grow large. Many of the proposed policies are asymptotically optimal on the fluid scale. However, as we demonstrate in this paper, these policies may fail to be optimal on the more sensitive diffusion scale even for quite simple problem instances. We develop a new policy that achieves diffusion-scale optimality. The policy starts with a probabilistic admission rule derived from the optimization of the fluid model, embeds a trigger function that tracks the difference between the actual and expected customer acceptance, and sets threshold values for the trigger function, the violation of which invokes the reoptimization of the admission rule. We show that re-solving the fluid model, which needs to be performed at most once, is required for extending the asymptotic optimality from the fluid scale to the diffusion scale. We demonstrate the implementation of the policy by numerical examples.

This paper primarily concerns strictly supercritical fluid models, which arise as functional law of large numbers approximations for overloaded processor sharing queues. Analogous results for critical fluid models associated with heavily loaded processor sharing queues are contained in Gromoll et al. (2002) and Puha and Williams (2004). An important distinction between critical and strictly supercritical fluid models is that the total mass for a solution that starts from zero grows with time for the latter, but it is identically equal to zero for the former. For strictly supercritical fluid models, this paper contains descriptions of each of the following: the distribution of the mass as it builds up from zero, the set of stationary solutions, and the limiting behavior of an arbitrary solution as time tends to infinity. In addition, a fluid limit result is proved that justifies strictly supercritical fluid models as first order approximations to overloaded processor sharing queues.

We investigate stability of scheduling policies in queueing systems. To this day no algorithmic characterization exists for checking stability of a given policy in a given queueing system. In this paper we introduce a certain generalized priority policy and prove that the stability of this policy is algorithmically undecidable. We also prove that stability of a homogeneous random walk in 𝒵d+ is undecidable. Finally, we show that the problem of computing a fluid limit of a queueing system or of a constrained homogeneous random walk is undecidable. To the best of our knowledge these are the first undecidability results in the area of stability of queueing systems and random walks in 𝒵d+. We conjecture that stability of common policies like First-In-First-Out and priority policy is also an undecidable problem.

In this paper, we first formally identify a FIFO fluid network that corresponds to the queueing network under a first-in first-out (FIFO) service discipline, thus complementing the result of Dai (Dai, J. G. 1995a. On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models. Ann. Appl. Probab. 5 49–77.) for the use of the fluid model for the stability of a multiclass queueing network under a FIFO service discipline. Then we establish two sufficient conditions for the stability of a multiclass FIFO queueing network. The results extend the previous work on the single class network, the single station network and a network studied by Rybko and Stolyar (Rybko, A. N., A. L. Stolyar. 1992. Ergodicity of stochastic processes describing the operations of open queueing networks. Problemy Peredachi Informatsii 28 2–26.). Finally we establish a fluid approximation theorem for the queueing network under FIFO service discipline.