Convergence to equilibria for fluid models of head-of-the-line proportional processor sharing queueing networks

Fluid models have recently become an important tool for the study of open multiclass queueing networks. We are interested in a family of such models, which we refer to as head-of-the-line proportional processor sharing (HLPPS) fluid models. Here, the fraction of time spent serving a class present at a station is proportional to the quantity of the class there, with all of the service going into the first customer of each class. To study such models, we employ an entropy function associated with the state of the system. The corresponding estimates show that if the traffic intensity function is at most 1, then such fluid models converge exponentially fast to equilibria. When the traffic intensity function is strictly less than 1, the limit is always the empty state and occurs after a finite time. A consequence is that generalized HLPPS networks with traffic intensity strictly less than 1 are positive Harris recurrent. Related results for FIFO fluid models of Kelly type were obtained in Bramson [4].Partially supported by NSF Grants DMS-93-00612 and DMS-93-04580. The paper was written while the author was in residence at the Institute for Advanced Study.     

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.     

A Simple proof for the stability of global FIFO queueing networks

We study the stability of multiclass queueing networks under the global FIFO （first in first out） service discipline, which was established by Bramson in 2001. For these networks, the service priority of a customer is determined by his entrance time. Using fluid models, we describe the entrance time of the most senior customer in the networks at time t, which is the key to simplify the proof for the stability of the global FIFO queueing networks.     

Stability of two families of queueing networks and a discussion of fluid limits

We investigate the stability of two families of queueing networks. The first family consists of a general class of networks, where service is allotted to the lead customer at each buffer. The other generalizes networks considered by Humes [18], and is related to the insertion of “leaky buckets” into the system. The arguments for the stability of the networks in each case rely on the corresponding behavior for the associated fluid models. This connection is employed using the framework established by Dai [10], with some modifications. It is discussed here in a somewhat more general setting, with future applications in mind. This revised version was published online in June 2006 with corrections to the Cover Date.     

Instability of FIFO in a simple queueing system with arbitrarily low loads

We show, using a simple example, that the First-In-First-Out (FIFO) policy can be unstable in a system with arbitrarily low load. Our proof is based on the observation that the special structure of the example we use allows us to establish stability using a much simpler queueing system.     

On the reversibility of queueing networks

This paper relates the reversibility of certain discrete state Markovian queueing networks — the class of quasi-reversible networks — to the reversibility of the underlying switching process. Quasi-reversible networks are characterized by a product form equilibrium state distribution.When the state can be represented by customer totals at each node, the reversibility of the state process is equivalent to the reversibility of the switching process. More complicated quasi-reversible networks require additional conditions, to ensure the reversibility of the network state process.     

Asymptotic analysis for closed multiclass queueing networks in critical usage

We consider a class of closed multiclass queueing networks containing First-Come-First-Serve (FCFS) and Infinite Server (IS) stations. These networks have a productform solution for their equilibrium probabilities. We study these networks in an asymptotic regime for which the number of customers and the service rates at the FCFS stations go to infinity with the same order. We assume that the regime is in critical usage, whereby the utilizations of the FCFS servers slowly approach one. The asymptotic distribution of the normalized queue lengths is shown to be in many cases a truncated multivariate normal distribution. Traffic conditions for which the normalized queue lengths arealmost asymptotically independent are determined. Asymptotic expansions of utilizations and expected queue lengths are presented. We show through an example how to obtain asymptotic expansions of performance measures when the networks are in mixed usage and how to apply the results to networks with finite data.Supported partially by NSF grant NCR93-04601.     

Calculating the normalization constants in queueing networks

Many queueing network models have a product-form solution for their steady-state probability distributions. However, the calculation of the normalization constants involved in the solutions is nontrivial. Recently, Gordon proposed a method to derive the closed form formula for normalization constants for certain closed networks. In this paper, we describe a simpler method using Z-transform. In the cases of networks of multiple server queues or of single server queues with equal traffic intensities, the computation involved in proposed approach is much simpler than that in Gordon's paper. For multichain closed networks, we propose to use FFT (Fast-Fourier-Transform) to calculate the normalization constants.     

Limit non-stationary behavior of large closed queueing networks with bottlenecks

In this paper martingales methods are applied for analyzing limit non-stationary behavior of the queue length processes in closed Jackson queueing networks with a single class consisting of a large number of customers, a single infinite server queue, and a fixed number of single server queues with large state independent service rates. It is assumed that one of the single server nodes forms a bottleneck. For the non-bottleneck nodes we show that the queue length distribution at timet converges in generalized sense to the stationary distribution of the M/M/1 queue whose parameters explicitly depend ont. For the bottleneck node a diffusion approximation with reflection is proved in the moderate usage regime while fluid and Gaussian diffusion approximations are established for the heavy usage regime.     

Deadlock properties of queueing networks with finite capacities and multiple routing chains

Blocking in queueing network models with finite capacities can lead to deadlock situations. In this paper, deadlock properties are investigated in queueing networks with multiple routing chains. The necessary and sufficient conditions for deadlockfree queueing networks with blocking are provided. An optimization algorithm is presented for finding deadlock-free capacity assignments with the least total capacity. The optimization algorithm maps the queueing network into a directed graph and obtains the deadlock freedom conditions from a specified subset of cycles in the directed graph. In certain network topologies, the number of deadlock freedom conditions can be large, thus, making any optimization computationally expensive. For a special class of topologies, so-calledtandem networks, it is shown that a minimal capacity assignment can be directly obtained without running an optimization algorithm. Here, the solution to the minimal capacity assignment takes advantage of the regular topology of tandem networks.This work was supported by the National Science Foundation under Grant No. CCR-90-11981.     

Nash equilibria in all-optical networks

We consider the problem of routing a number of communication requests in WDM (wavelength division multiplexing) all-optical networks from the standpoint of game theory. If we view each routing request (pair of source-target nodes) as a player, then a strategy consists of a path from the source to the target and a frequency (color). To reflect the restriction that two requests must not use the same frequency on the same edge, conflicting strategies are assigned a prohibitively high cost.Under this formulation, we consider several natural cost functions, each one reflecting a different aspect of restriction in the available bandwidth. For each cost function we examine the problem of the existence of pure Nash equilibria, the complexity of recognizing and computing them and finally, the problem in which we are given a Nash equilibrium and we are asked to find a better one in the sense that the total bandwidth used is less. As it turns out some of these problems are tractable and others are NP-hard.     

Open queueing networks in discrete time-some limit theorems

A finite number of nodes, each with a single server and infinite buffers, is considered in discrete time. The service may be FIFO and the service times are constant. The external arrivals and the routing decision variables form a general stationary sequence. Stability of the system is proved under these assumptions. Extension to multiple servers at a node and general stationary distributions holds. If the external input is i.i.d. and the routing is Markovian then stochastic ordering, continuity of stationary distributions, rates of convergence, a functional CLT and a functional LIL and various other limit theorems for the queue length process are also proved. Generalizations to multiple servers at nodes, customers with priority, multiple customer classes, general service length and Markov modulated external arrival cases are discussed.     

Approximate analysis of arbitrary configurations of open queueing networks with blocking

An algorithm for analyzing approximately open exponential queueing networks with blocking is presented. The algorithm decomposes a queueing network with blocking into individual queues with revised capacity, and revised arrival and service processes. These individual queues are then analyzed in isolation. Numerical experience with this algorithm is reported for three-node and four-node queueing networks. The approximate results obtained were compared against exact numerical data, and they seem to have an acceptable error level.Supported in part by a grant from CAIP Center, Rutgers University.Supported in part by the National Science Foundation under Grant DCR-85-02540.     

Fleet-sizing and service availability for a vehicle rental system via closed queueing networks

In this paper, we address the problem of determining the optimal fleet size for a vehicle rental company and derive analytical results for its relationship to vehicle availability at each rental station in the company’s network of locations. This work is motivated by the recent surge in interest for bicycle and electric car sharing systems, one example being the French program Vélib (2010). We first formulate a closed queueing network model of the system, obtained by viewing the system from the vehicle’s perspective. Using this framework, we are able to derive the asymptotic behavior of vehicle availability at an arbitrary rental station with respect to fleet size. These results allow us to analyze imbalances in the system and propose some basic principles for the design of system balancing methods. We then develop a profit-maximizing optimization problem for determining optimal fleet size. The large-scale nature of real-world systems results in computational difficulties in obtaining this exact solution, and so we provide an approximate formulation that is easier to solve and which becomes exact as the fleet size becomes large. To illustrate our findings and validate our solution methods, we provide numerical results on some sample networks.     

Dynamic scheduling in multiclass queueing networks: Stability under discrete-review policies

This paper describes a family of discrete-review policies for scheduling open multiclass queueing networks. Each of the policies in the family is derived from what we call a dynamic reward function: such a function associates with each queue length vector q and each job class k a positive value r _k (q), which is treated as a reward rate for time devoted to processing class k jobs. Assuming that each station has a traffic intensity parameter less than one, all policies in the family considered are shown to be stable. In such a policy, system status is reviewed at discrete points in time, and at each such point the controller formulates a processing plan for the next review period, based on the queue length vector observed. Stability is proved by combining elementary large deviations theory with an analysis of an associated fluid control problem. These results are extended to systems with class dependent setup times as well as systems with alternate routing and admission control capabilities. This revised version was published online in June 2006 with corrections to the Cover Date.     

Analysis of cyclic queueing networks with parallelism and vacation

The aim of this paper is to improve the machine interference model with vacation to deal with more recent problems of the communication area. To this scope the model is extended to include parallelism in the vacation station. The underlying Markov process is analyzed and a state arrangement is found that yields an efficient matrix-analytic technique that substantially lowers down the time- and space-complexity of standard methods. A numerical example of the method effectiveness is presented, and an example of resource allocation is introduced that finds applications in the QoS management of wireless networks. The author is thankful to the anonymous referees for the improvements their comments have earned to the quality of the presentation and to the completeness of the paper. The author is thankful to Giuseppe Iazeolla, whose careful reading of the original draft of this paper led to significant improvements in its overall quality. This work was partially supported by funds from the FIRB project “Performance Evaluation of Complex Systems: Techniques Methodologies and Tools” and by the University of Roma TorVergata project on High Performance ICT Platforms.     

Approximate queueing models for capacitated multi-stage inventory systems under base-stock control

A queueing analysis is presented for base-stock controlled multi-stage production-inventory systems with capacity constraints. The exact queueing model is approximated by replacing some state-dependent conditional probabilities (that are used to express the transition rates) by constants. Two recursive algorithms (each with several variants) are developed for analysis of the steady-state performance. It is analytically shown that one of these algorithms is equivalent to the existing approximations given in the literature. The system studied here is more general than the systems studied in the literature. The numerical investigation for three-stage systems shows that the proposed approximations work well to estimate the relevant performance measures.     

Design of manufacturing systems using queueing models

Design issues in various types of manufacturing systems such as flow lines, automatic transfer lines, job shops, flexible machining systems, flexible assembly systems and multiple cell systems are addressed in this paper. Approaches to resolving these design issues of these systems using queueing models are reviewed. In particular, we show how the structural properties that are recently derived for single and multiple stage queueing systems can be used effectively in the solution of certain design optimization problems.Supported in part by the Natural Sciences and Engineering Research Council of Canada via Operating and Strategic Grants on Modeling and Analyses of Production Systems and Modeling and Implementation of Just-in-Time Cells.Supported in part by the NSF Grants ECS-8811234 and DDM-9113008 and by Sloan Foundation Grants for the Consortium for Competitiveness and Cooperation and for the study on Competitive Semiconductor Manufacturing.     

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.     

Two-stage queueing network models for quality control and testing

We study sojourn times in a two-node open queueing network with a processor sharing node and a delay node, with Poisson arrivals at the PS node. Motivated by quality control and blood testing applications, we consider a feedback mechanism in which customers may either leave the system after service at the PS node or move to the delay node; from the delay node, they always return to the PS node for new quality controls or blood tests. We propose various approximations for the distribution of the total sojourn time in the network; each of these approximations yields the exact mean sojourn time, and very accurate results for the variance. The best of the three approximations is used to tackle an optimization problem that is mainly inspired by a blood testing application.