We extend the measure-valued fluid model, which tracks residuals of patience and service times, to allow for time-varying arrivals. The fluid model can be characterized by a one-dimensional convolution equation involving both the patience and service
time distributions. We also make an interesting connection to the measure-valued fluid model tracking the elapsed waiting and service times. Our analysis shows that the two fluid models are actually characterized by the same one-dimensional convolution equation.
Motivated by a web-server model, we present a queueing network consisting of two layers. The first layer incorporates the arrival of customers at a network of two single-server nodes. We assume that the inter-arrival and the service times have genera
l distributions. Customers are served according to their arrival order at each node and after finishing their service they can re-enter at nodes several times (as new customers) for new services. At the second layer, active servers act as jobs which are served by a single server working at speed one in a Processor-Sharing fashion. We further assume that the degree of resource sharing is limited by choice, leading to a Limited Processor-Sharing discipline. Our main result is a diffusion approximation for the process describing the number of customers in the system. Assuming a single bottleneck node and studying the system as it approaches heavy traffic, we prove a state-space collapse property. The key to derive this property is to study the model at the second layer and to prove a diffusion limit theorem, which yields an explicit approximation for the customers in the system.
Consider a storage system where the content is driven by a Brownian motion absent control. At any time, one may increase or decrease the content at a cost proportional to the amount of adjustment. A decrease of the content takes effect immediately, w
hile an increase is realized after a fixed lead time $lt$. Holding costs are incurred continuously over time and are a convex function of the content. The objective is to find a control policy that minimizes the expected present value of the total costs. Due to the positive lead time for upward adjustments, one needs to keep track of all the outstanding upward adjustments as well as the actual content at time $t$ as there may also be downward adjustments during $[t,t+lt)$, i.e., the state of the system is a function on $[0,ell]$. To the best of our knowledge, this is the first paper to study instantaneous control of stochastic systems in such a functional setting. We first extend the concept of $L^ atural$-convexity to function spaces and establish the $L^ atural$-convexity of the optimal cost function. We then derive various properties of the cost function and identify the structure of the optimal policy as a state-dependent two-sided reflection mapping making the minimum amount of adjustment necessary to keep the system states within a certain region.
Proportional fairness is a popular service allocation mechanism to describe and analyze the performance of data networks at flow level. Recently, several authors have shown that the invariant distribution of such networks admits a product form distri
bution under critical loading. Assuming exponential job size distributions, they leave the case of general job size distributions as an open question. In this paper we show the conjecture holds for a dense class of distributions. This yields a key example of a stochastic network in which the heavy traffic limit has an invariant distribution that does not depend on second moments. Our analysis relies on a uniform convergence result for a fluid model which may be of independent interest.
The paper studies approximations and control of a processor sharing (PS) server where the service rate depends on the number of jobs occupying the server. The control of such a system is implemented by imposing a limit on the number of jobs that can
share the server concurrently, with the rest of the jobs waiting in a first-in-first-out (FIFO) buffer. A desirable control scheme should strike the right balance between efficiency (operating at a high service rate) and parallelism (preventing small jobs from getting stuck behind large ones). We employ the framework of heavy-traffic diffusion analysis to devise near optimal control heuristics for such a queueing system. However, while the literature on diffusion control of state-dependent queueing systems begins with a sequence of systems and an exogenously defined drift function, we begin with a finite discrete PS server and propose an axiomatic recipe to explicitly construct a sequence of state-dependent PS servers which then yields a drift function. We establish diffusion approximations and use them to obtain insightful and closed-form approximations for the original system under a static concurrency limit control policy. We extend our study to control policies that dynamically adjust the concurrency limit. We provide two novel numerical algorithms to solve the associated diffusion control problem. Our algorithms can be viewed as average cost iteration: The first algorithm uses binary-search on the average cost and can find an $epsilon$-optimal policy in time $Oleft( log^2 frac{1}{epsilon} right)$; the second algorithm uses the Newton-Raphson method for root-finding and requires $Oleft( log frac{1}{epsilon} loglog frac{1}{epsilon}right)$ time. Numerical experiments demonstrate the accuracy of our approximation for choosing optimal or near-optimal static and dynamic concurrency control heuristics.
We investigate a computer network consisting of two layers occurring in, for example, application servers. The first layer incorporates the arrival of jobs at a network of multi-server nodes, which we model as a many-server Jackson network. At the se
cond layer, active servers at these nodes act now as customers who are served by a common CPU. Our main result shows a separation of time scales in heavy traffic: the main source of randomness occurs at the (aggregate) CPU layer; the interactions between different types of nodes at the other layer is shown to converge to a fixed point at a faster time scale; this also yields a state-space collapse property. Apart from these fundamental insights, we also obtain an explicit approximation for the joint law of the number of jobs in the system, which is provably accurate for heavily loaded systems and performs numerically well for moderately loaded systems. The obtained results for the model under consideration can be applied to thread-pool dimensioning in application servers, while the technique seems applicable to other layered systems too.
Fluid models have become an important tool for the study of many-server queues with general service and patience time distributions. The equilibrium state of a fluid model has been revealed by Whitt (2006) and shown to yield reasonable approximations
to the steady state of the original stochastic systems. However, it remains an open question whether the solution to a fluid model converges to the equilibrium state and under what condition. We show in this paper that the convergence holds under a mild condition. Our method builds on the framework of measure-valued processes developed in Zhang (2013), which keeps track of the remaining patience and service times.
We propose a unified approach to establishing diffusion approximations for queues with impatient customers within a general framework of scaling customer patience time. The approach consists of two steps. The first step is to show that the diffusion-
scaled abandonment process is asymptotically close to a function of the diffusion-scaled queue length process under appropriate conditions. The second step is to construct a continuous mapping not only to characterize the system dynamics using the system primitives, but also to help verify the conditions needed in the first step. The diffusion approximations can then be obtained by applying the continuous mapping theorem. The approach has two advantages: (i) it provides a unified procedure to establish the diffusion approximations regardless of the structure of the queueing model or the type of patience-time scaling; (ii) and it makes the diffusion analysis of queues with customer abandonment essentially the same as the diffusion analysis of queues without customer abandonment. We demonstrate the application of this approach via the single server system with Markov-modulated service speeds in the traditional heavy-traffic regime and the many-server system in the Halfin-Whitt regime and the non-degenerate slowdown regime.
We consider a processor sharing queue where the number of jobs served at any time is limited to $K$, with the excess jobs waiting in a buffer. We use random counting measures on the positive axis to model this system. The limit of this measure-valued
process is obtained under diffusion scaling and heavy traffic conditions. As a consequence, the limit of the system size process is proved to be a piece-wise reflected Brownian motion.
We study many-server queues with abandonment in which customers have general service and patience time distributions. The dynamics of the system are modeled using measure- valued processes, to keep track of the residual service and patience times of
each customer. Deterministic fluid models are established to provide first-order approximation for this model. The fluid model solution, which is proved to uniquely exists, serves as the fluid limit of the many-server queue, as the number of servers becomes large. Based on the fluid model solution, first-order approximations for various performance quantities are proposed.
