Heavily loaded queue coupled to two underloaded queues

We consider a system of three parallel queues with Poisson arrivals and exponentially distributed service requirements. The service rate for the heavily loaded queue depends on which of the two underloaded queues are empty. We derive the lowest-order asymptotic approximation to the joint stationary distribution of the queue lengths, in terms of a small parameter measuring the closeness of the heavily loaded queue to instability. To this order the queue lengths are independent, and the underloaded queues and the heavily loaded queue have geometrically and, after suitable scaling, exponentially distributed lengths, respectively. The expression for the exponential decay rate for the heavily loaded queue involves the solution to an inhomogeneous linear functional equation. Explicit results are obtained for this decay rate when the two underloaded queues have vastly different arrival and service rates.     

Processor sharing for two queues with vastly different rates

We consider a 2-class queueing system, operating under a generalized processor-sharing discipline, in an asymptotic regime where the arrival and service rates of the two classes are vastly different. We use regular and singular perturbation analyses in a small parameter measuring this difference in rates. It is assumed that the system is stable, and not close to instability. Three different regimes are analyzed, corresponding to an underloaded, an overloaded and a critically loaded fast queue, respectively. In the first two regimes the lowest order approximation to the joint stationary distribution of the queue lengths is derived. For a critically loaded fast queue only the mean queue lengths are investigated, and the asymptotic matching, to lowest order, with the results for an underloaded and an overloaded fast queue is established.      

A spectral theory approach for extreme value analysis in a tandem of fluid queues

We consider a model to evaluate performance of streaming media over an unreliable network. Our model consists of a tandem of two fluid queues. The first fluid queue is a Markov modulated fluid queue that models the network congestion, and the second queue represents the play-out buffer. For this model the distribution of the total amount of fluid in the congestion and play-out buffer corresponds to the distribution of the maximum attained level of the first buffer. We show that, under proper scaling and when we let time go to infinity, the distribution of the total amount of fluid converges to a Gumbel extreme value distribution. From this result, we derive a simple closed-form expression for the initial play-out buffer level that provides a probabilistic guarantee for undisturbed play-out.     

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.

     

Fluid models for many-server Markovian queues in a changing environment

Motivated by service systems with time-varying customer arrivals, we consider a fluid model as a macroscopic approximation for many-server Markovian queues alternating between underloaded and overloaded intervals. Our main result is a refinement of the piecewise stationary approximation (PSA) for the stationary distribution of the fluid model. The form of the refined approximation suggests simple metrics for assessing the accuracy of PSA for underloaded and overloaded intervals respectively.     

A simple policy for multiple queues with size-independent service times

We consider a service system with two Poisson arrival queues. A server chooses which queue to serve at each moment. Once a queue is served, all the customers will be served within a fixed amount of time. This model is useful in studying airport shuttling or certain online computing systems. We propose a simple yet optimal state-independent policy for this problem which is not only easy to implement, but also performs very well.     

Marginal queue length approximations for a two-layered network with correlated queues

We consider an extension of the classical machine-repair model, where we assume that the machines, apart from receiving service from the repairman, also serve queues of products. The extended model can be viewed as a layered queueing network, where the first layer consists of the queues of products and the second layer is the ordinary machine-repair model. As the repair time of one machine may affect the time the other machine is not able to process products, the downtimes of the machines are correlated. This correlation leads to dependence between the queues of products in the first layer. Analysis of these queue length distributions is hard, as the exact dependence structure for the downtimes, or the queue lengths, is not known. Therefore, we obtain an approximation for the complete marginal queue length distribution of any queue in the first layer, by viewing such a queue as a single server queue with correlated server downtimes. Under an explicit assumption on the form of the downtime dependence, we obtain exact results for the queue length distribution for that single server queue. We use these exact results to approximate the machine-repair model. We do so by computing the downtime correlation for the latter model and by subsequently using this information to fine-tune the parameters we introduced to the single server queue. As a result, we immediately obtain an approximation for the queue length distributions of products in the machine-repair model, which we show to be highly accurate by extensive numerical experiments.     

Networks of infinite-server queues with nonstationary Poisson input

In this paper we focus on networks of infinite-server queues with nonhomogeneous Poisson arrival processes. We start by introducing a more general Poisson-arrival-location model (PALM) in which arrivals move independently through a general state space according to a location stochastic process after arriving according to a nonhomogeneous Poisson process. The usual open network of infinite-server queues, which is also known as a linear population process or a linear stochastic compartmental model, arises in the special case of a finite state space. The mathematical foundation is a Poisson-random-measure representation, which can be obtained by stochastic integration. It implies a time-dependent product-form result: For appropriate initial conditions, the queue lengths (numbers of customers in disjoint subsets of the state space) at any time are independent Poisson random variables. Even though there is no dependence among the queue lengths at each time, there is important dependence among the queue lengths at different times. We show that the joint distribution is multivariate Poisson, and calculate the covariances. A unified framework for constructing stochastic processes of interest is provided by stochastically integrating various functionals of the location process with respect to the Poisson arrival process. We use this approach to study the flows in the queueing network; e.g., we show that the aggregate arrival and departure processes at a given queue (to and from other queues as well as outside the network) are generalized Poisson processes (without necessarily having a rate or unit jumps) if and only if no customer can visit that queue more than once. We also characterize the aggregate arrival and departure processes when customers can visit the queues more frequently. In addition to obtaining structural results, we use the stochastic integrals to obtain explicit expressions for time-dependent means and covariances. We do this in two ways. First, we decompose the entire network into a superposition of independent networks with fixed deterministic routes. Second, we make Markov assumptions, initially for the evolution of the routes and finally for the entire location process. For Markov routing among the queues, the aggregate arrival rates are obtained as the solution to a system of input equations, which have a unique solution under appropriate qualifications, but not in general. Linear ordinary differential equations characterize the time-dependent means and covariances in the totally Markovian case.     

Explicit Solution for a Network Control Problem in the Large Deviation Regime

We consider optimal control of a stochastic network, where service is controlled to prevent buffer overflow. We use a risk-sensitive escape time criterion, which in comparison to the ordinary escape time criteria heavily penalizes exits which occur on short time intervals. A limit as the buffer sizes tend to infinity is considered. In [2] we showed that, for a large class of networks, the limit of the normalized cost agrees with the value function of a differential game. In this game, one player controls the service discipline (who to serve and whether to serve), and the other player chooses arrival and service rates in the network. The game's value is characterized in [2] as the unique solution to a Hamilton–Jacobi–Bellman Partial Differential Equation (PDE). In the current paper we apply this general theory to the important case of a network of queues in tandem. Our main results are: (i) the construction of an explicit solution to the corresponding PDE, and (ii) drawing out the implications for optimal risk-sensitive and robust regulation of the network. In particular, the following general principle can be extracted. To avoid buffer overflow there is a natural competition between two tendencies. One may choose to serve a particular queue, since that will help prevent its own buffer from overflowing, or one may prefer to stop service, with the goal of preventing overflow of buffers further down the line. The solution to the PDE indicates the optimal choice between these two, specifying the parts of the state space where each queue must be served (so as not to lose optimality), and where it can idle. Referring to those queues which must be served as bottlenecks, one can use the solution to the PDE to explicitly calculate the bottleneck queues as a function of the system's state, in terms of a simple set of equations.     

Analysis of a dynamic assignment of impatient customers to parallel queues

Consider a number of parallel queues, each with an arbitrary capacity and multiple identical exponential servers. The service discipline in each queue is first-come-first-served (FCFS). Customers arrive according to a state-dependent Poisson process. Upon arrival, a customer joins a queue according to a state-dependent policy or leaves the system immediately if it is full. No jockeying among queues is allowed. An incoming customer to a parallel queue has a general patience time dependent on that queue after which he/she must depart from the system immediately. Parallel queues are of two types: type 1, wherein the impatience mechanism acts on the waiting time; or type 2, a single server queue wherein the impatience acts on the sojourn time. We prove a key result, namely, that the state process of the system in the long run converges in distribution to a well-defined Markov process. Closed-form solutions for the probability density function of the virtual waiting time of a queue of type 1 or the offered sojourn time of a queue of type 2 in a given state are derived which are, interestingly, found to depend only on the local state of the queue. The efficacy of the approach is illustrated by some numerical examples.     

On a generic class of two-node queueing systems

This paper analyzes a generic class of two-node queueing systems. A first queue is fed by an on–off Markov fluid source; the input of a second queue is a function of the state of the Markov fluid source as well, but now also of the first queue being empty or not. This model covers the classical two-node tandem queue and the two-class priority queue as special cases. Relying predominantly on probabilistic argumentation, the steady-state buffer content of both queues is determined (in terms of its Laplace transform). Interpreting the buffer content of the second queue in terms of busy periods of the first queue, the (exact) tail asymptotics of the distribution of the second queue are found. Two regimes can be distinguished: a first in which the state of the first queue (that is, being empty or not) hardly plays a role, and a second in which it explicitly does. This dichotomy can be understood by using large-deviations heuristics. This work has been carried out partly in the Dutch BSIK/BRICKS project.     

An analytic finite capacity queueing network model capturing the propagation of congestion and blocking

Analytic queueing network models often assume infinite capacity queues due to the difficulty of grasping the between-queue correlation. This correlation can help to explain the propagation of congestion. We present an analytic queueing network model which preserves the finite capacity of the queues and uses structural parameters to grasp the between-queue correlation. Unlike pre-existing models it maintains the network topology and the queue capacities exogenous. Additionally, congestion is directly modeled via a novel formulation of the state space of the queues which explicitly captures the blocking phase. The model can therefore describe the sources and effects of congestion.     

Monotonicity properties of user equilibrium policies for parallel batch systems

We study a simple network with two parallel batch-service queues, where service at a queue commences when the batch is full and each queue is served by infinitely many servers. A stream of general arrivals observe the current state of the system on arrival and choose which queue to join to minimize their own expected transit time. We show that for each set of parameter values there exists a unique user equilibrium policy and that it possesses various monotonicity properties. User equilibrium policies for probabilistic routing are also discussed and compared with the state-dependent setting.     

Optimal assignment policy of a single server attended by two queues

A single server attends to two separate queues. Each queue has Poisson arrivals and exponential service. There is a switching cost whenever the server switches from one queue to another. The objective is to minimize the discounted or average holding and switching costs over a finite or an infinite horizon. We show numerically that the optimal assignment policy is characterized by a switching curve. We also show that the optimal policy is monotonic in the following senses: If it is optimal to switch from queue one to queue two, then it is optimal to continue serve queue two whenever the number of customers in queue one or in queue two decreases or increases, respectively.     

Models for queue length in clocked queueing networks

We analyze a discrete-time network of queues. The unit element of the network is the 2 × 2 buffered switch, which we regard as a system of two queues working in parallel. We show how to transform transition probability information from the output of one switch, or network stage, to the input of the next one. This is used to carry out a Markov time series input model to predict mean queue length at every stage of the system. Another model considered is a renewal process time series model, which we use to find the mean queue length of the second stage of the network. Numerical simulations fall within the narrow band spanned by the two models.     

Near optimal control of queueing networks over a finite time horizon

We propose a method for the control of multi-class queueing networks over a finite time horizon. We approximate the multi-class queueing network by a fluid network and formulate a fluid optimization problem which we solve as a separated continuous linear program. The optimal fluid solution partitions the time horizon to intervals in which constant fluid flow rates are maintained. We then use a policy by which the queueing network tracks the fluid solution. To that end we model the deviations between the queuing and the fluid network in each of the intervals by a multi-class queueing network with some infinite virtual queues. We then keep these deviations stable by an adaptation of a maximum pressure policy. We show that this method is asymptotically optimal when the number of items that is processed and the processing speed increase. We illustrate these results through a simple example of a three stage re-entrant line. Research supported in part by Israel Science Foundation Grant 249/02 and 454/05 and by European Network of Excellence Euro-NGI.     

On Kelly networks with shuffling

We consider Kelly networks with shuffling of customers within each queue. Specifically, each arrival, departure or movement of a customer from one queue to another triggers a shuffle of the other customers at each queue. The shuffle distribution may depend on the network state and on the customer that triggers the shuffle. We prove that the stationary distribution of the network state remains the same as without shuffling. In particular, Kelly networks with shuffling have the product form. Moreover, the insensitivity property is preserved for symmetric queues.      

Geometric equilibrium distributions for queues with interactive batch departures

Gelenbe et al. [1, 2] consider single server Jackson networks of queues which contain both positive and negative customers. A negative customer arriving to a nonempty queue causes the number of customers in that queue to decrease by one, and has no effect on an empty queue, whereas a positive customer arriving at a queue will always increase the queue length by one. Gelenbe et al. show that a geometric product form equilibrium distribution prevails for this network. Applications for these types of networks can be found in systems incorporating resource allocations and in the modelling of decision making algorithms, neural networks and communications protocols.In this paper we extend the results of [1, 2] by allowing customer arrivals to the network, or the transfer between queues of a single positive customer in the network to trigger the creation of a batch of negative customers at the destination queue. This causes the length of the queue to decrease by the size of the created batch or the size of the queue, whichever is the smallest. The probability of creating a batch of negative customers of a particular size due to the transfer of a positive customer can depend on both the source and destination queue.We give a criterion for the validity of a geometric product form equilibrium distribution for these extended networks. When such a distribution holds it satisfies partial balance equations which are enforced by the boundaries of the state space. Furthermore it will be shown that these partial balance equations relate to traffic equations for the throughputs of the individual queues.     

An Application of Little's Result to the G/G/1 (LCFS/P) Queue

This paper considers a quite general single-server queueing system, under a last-come-first-served queue discipline, with pre-emption and arbitrary restarting policy. Expressions are given for the queue-size limiting distribution when the system is considered at arrival (or departure) epochs and in continuous time, by using very simple arguments.     

User equilibria for a parallel queueing system with state dependent routing

Consider a system of two queues in parallel, one of which is a ⋅|M|1 single-server infinite capacity queue, and the other a ⋅|G ^(N)|∞ batch service queue. A stream of general arrivals choose which queue to join, after observing the current state of the system, and so as to minimize their own expected delay. We show that a unique user equilibrium (user optimal policy) exists and that it possesses various monotonicity properties, using sample path and coupling arguments. This is a very simplified model of a transportation network with a choice of private and public modes of transport. Under probabilistic routing (which is equivalent to the assumption that users have knowledge only of the mean delays on routes), the network may exhibit the Downs–Thomson paradox observed in transportation networks with expected delay increasing as the capacity of the ⋅|M|1 queue (private transport) is increased. We give examples where state-dependent routing mitigates the Downs–Thomson effect observed under probabilistic routing, and providing additional information on the state of the system to users reduces delay considerably.