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.     

Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse

Certain diffusion processes known as semimartingale reflecting Brownian motions (SRBMs) have been shown to approximate many single class and some multiclass open queueing networks under conditions of heavy traffic. While it is known that not all multiclass networks with feedback can be approximated in heavy traffic by SRBMs, one of the outstanding challenges in contemporary research on queueing networks is to identify broad categories of networks that can be so approximated and to prove a heavy traffic limit theorem justifying the approximation. In this paper, general sufficient conditions are given under which a heavy traffic limit theorem holds for open multiclass queueing networks with head-of-the-line (HL) service disciplines, which, in particular, require that service within each class is on a first-in-first-out (FIFO) basis. The two main conditions that need to be verified are that (a) the reflection matrix for the SRBM is well defined and completely- S, and (b) a form of state space collapse holds. A result of Dai and Harrison shows that condition (a) holds for FIFO networks of Kelly type and their proof is extended here to cover networks with the HLPPS (head-of-the-line proportional processor sharing) service discipline. In a companion work, Bramson shows that a multiplicative form of state space collapse holds for these two families of networks. These results, when combined with the main theorem of this paper, yield new heavy traffic limit theorems for FIFO networks of Kelly type and networks with the HLPPS service discipline. This revised version was published online in June 2006 with corrections to the Cover Date.     

Some consequences of estimating parameters for the M/M/1 queue

An important interface between stochastic models and actual systems comes in estimating values for model parameters using “real world” data. This interface between models and systems is studied for one of the most elementary stochastic systems, the M/M/1 queue. Estimating arrival rates and service rates results in a notable discrepancy between the state distribution for the model (estimated parameters) and the state distribution for the actual system (known parameters). Also, the expected number of customers in the model is infinite regardless of the (unknown) value of the actual traffic intensity. The truth of this assertion is obvious if one allows estimated traffic intensities to equal or exceed one. However, it is shown that the mean for the model is infinite even if the estimated traffic intensity is restricted to be strictly less than one.     

Stability of Earliest-Due-Date,First-Served Queueing Networks

We study multiclass queueing networks with the earliest-due-date, first-served (EDDFS) discipline. For these networks, the service priority of a customer is determined, upon its arrival in the network, by an assigned random due date. First-in-system, first-out queueing networks, where a customer's priority is given by its arrival time in the network, are a special case. Using fluid models, we show that EDDFS queueing networks, without preemption, are stable whenever the traffic intensity satisfies _j <1 for each station j.     

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.     

Sensitivity Analysis Based Method for Optimal Road Network Pricing

Road pricing is an important economic measure for optimal management of transportation networks. The optimization objectives can be the total travel time or total cost incurred by all the travelers, or some other environmental objective such as minimum emission of dioxide, an so on. Suppose a certain toll is posed on some link on the network, this will give an impact on flows over the whole network and brings about a new equilibrium state. An equilibrium state is a state of traffic network at which no traveler could decrease the perceived travel cost by unilaterally changing the route. The aim of the toll setting is to achieve such an equilibrium state that a certain objective function is optimized. The problem can be formulated as a mathematical program with equilibrium constraints (MPEC). A key step for solving such a MPEC problem is the sensitivity analysis of traffic flows with respect to the change of link characteristics such as the toll prices. In this paper a sensitivity analysis based method is proposed for solving optimal road pricing problems.     

Effective bandwidths: Call admission,traffic policing and filtering for ATM networks

In this paper we review and extend the effective bandwidth results of Kelly [28], and Kesidis, Walrand and Chang [29, 6]. These results provide a framework for call admission schemes which are sensitive to constraints on the mean delay or the tail distribution of the workload in buffered queues. We present results which are valid for a wide variety of traffic streams and discuss their applicability for traffic management in ATM networks. We discuss the impact of traffic policing schemes, such as thresholding and filtering, on the effective bandwidth of sources. Finally we discuss effective bandwidth results for Brownian traffic models for which explicit results reveal the interaction arising in finite buffers.     

More about empirical evaluation of formal theory†

The purpose of this discussion is to transform the implicit equilibrium assumption endemic to network analysis into an explicit instrument for such analysis. I propose a formal model that brings together Coleman's restriction of Walras’ general equilibrium model and recent developments in describing the “social topology” of a multiple network system of actors such that a class of relational equilibria is defined. The specific equilibrium expected in a system is a function of the previously existing stratification of actors in the system. Corresponding to multiple observed networks, the model generates multiple equilibrium networks. The structural analysis of the observed networks can therefore be repeated on the equilibrium networks so as to assess the extent to which the analysis would differ if the observed relations were actually in an equilibrium state. Numerical illustration is provided by an analysis of alternative relational equilibria in the system of elite experts in methodological and mathematical sociology as such a system existed in 1975.     

Networks of probabilistic events in discrete time

The usual methods of applying Bayesian networks to the modeling of temporal processes, such as Dean and Kanazawa’s dynamic Bayesian networks (DBNs), consist in discretizing time and creating an instance of each random variable for each point in time. We present a new approach called network of probabilistic events in discrete time (NPEDT), for temporal reasoning with uncertainty in domains involving probabilistic events. Under this approach, time is discretized and each value of a variable represents the instant at which a certain event may occur. This is the main difference with respect to DBNs, in which the value of a variable V_i represents the state of a real-world property at time t_i. Therefore, our method is more appropriate for temporal fault diagnosis, because only one variable is necessary for representing the occurrence of a fault and, as a consequence, the networks involved are much simpler than those obtained by using DBNs. In contrast, DBNs are more appropriate for monitoring tasks, since they explicitly represent the state of the system at each moment. We also introduce in this paper several types of temporal noisy gates, which facilitate the acquisition and representation of uncertain temporal knowledge. They constitute a generalization of traditional canonical models of multicausal interactions, such as the noisy OR-gate, which have been usually applied to static domains. We illustrate the approach with the example domain of modeling the evolution of traffic jams produced on the outskirts of a city, after the occurrence of an event that obliges traffic to stop indefinitely.     

On the Existence of Invariant Measures for Networks with String Transitions

Recently a new class of Markov network processes was introduced, characterized by so-called string transitions. These are continuous-time Markov processes on a discrete state space. It is known that they possess an invariant measure of a special form, called a product-form, provided that a certain system of so-called traffic equations possesses a solution. Little is known about the existence of solutions of the traffic equations. The present paper deals with this question, focussing on the most important special case of unit vector string transitions. It is shown for open networks with unit vector string transitions of bounded lengths that the traffic equations possess a solution. Furthermore, it is shown for a prominent example of a network featuring signals and batch services that the traffic equations possess a solution.     

Joint Distributions for Interacting Fluid Queues

Motivated by recent traffic control models in ATM systems, we analyse three closely related systems of fluid queues, each consisting of two consecutive reservoirs, in which the first reservoir is fed by a two-state (on and off) Markov source. The first system is an ordinary two-node fluid tandem queue. Hence the output of the first reservoir forms the input to the second one. The second system is dual to the first one, in the sense that the second reservoir accumulates fluid when the first reservoir is empty, and releases fluid otherwise. In these models both reservoirs have infinite capacities. The third model is similar to the second one, however the second reservoir is now finite. Furthermore, a feedback mechanism is active, such that the rates at which the first reservoir fills or depletes depend on the state (empty or nonempty) of the second reservoir.The models are analysed by means of Markov processes and regenerative processes in combination with truncation, level crossing and other techniques. The extensive calculations were facilitated by the use of computer algebra. This approach leads to closed-form solutions to the steady-state joint distribution of the content of the two reservoirs in each of the models.     

Multiclass batch arrival retrial queues analyzed as branching processes with immigration

TheM/G/1 batch arrival retrial queue is studied by means of branching processes with immigration. We shall investigate this queue when traffic intensity is less than one, tends to one or is greater than one.     

Stability of Fluid Networks with Proportional Routing

In this paper we investigate the stability of a class of two-station multiclass fluid networks with proportional routing. We obtain explicit necessary and sufficient conditions for the global stability of such networks. By virtue of a stability theorem of Dai [14], these results also give sufficient conditions for the stability of a class of related multiclass queueing networks. Our study extends the results of Dai and VandeVate [19], who provided a similar analysis for fluid models without proportional routing, which arise from queueing networks with deterministic routing. The models we investigate include fluid models which arise from a large class of two-station queueing networks with probabilistic routing. The stability conditions derived turn out to have an appealing intuitive interpretation in terms of virtual stations and push-starts which were introduced in earlier work on multiclass networks.     

Log-weight scheduling in switched networks

We consider switched queueing networks in which there are constraints on which queues may be served simultaneously. The scheduling policy for such a network specifies which queues to serve at any point in time. We introduce and study a variant of the popular maximum weight or backpressure policy which chooses the collection of queues to serve that has maximum weight. Unlike the maximum weight policies studied in the literature, the weight of a queue depends on logarithm of its queue-size in this paper. For any multihop switched network operating under such maximum log-weighted policy, we establish that the network Markov process is positive recurrent as long as it is underloaded. As the main result of this paper, a meaningful fluid model is established as the formal functional law of large numbers approximation. The fluid model is shown to be work-conserving. That is, work (or total queue-size) is nonincreasing as long as the network is underloaded or critically loaded. We identify invariant states or fixed points of the fluid model. When underloaded, null state is the unique invariant state. For a critically loaded fluid model, the space of invariant states is characterized as the solution space of an optimization problem whose objective is lexicographic ordering of total queue-size and the negative entropy of the queue state. An important contribution of this work is in overcoming the challenge presented by the log-weight function in establishing meaningful fluid model. Specifically, the known approaches in the literature primarily relied on the “scale invariance” property of the weight function that log-function does not possess.     

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.      

On the departure process of a leaky bucket system with long-range dependent input traffic

Due to the strong experimental evidence that the traffic to be offered to future broadband networks will display long-range dependence, it is important to study the possible implications that such traffic may have for the design and performance of these networks. In particular, an important question is whether the offered traffic preserves its long-range dependent nature after passing through a policing mechanism at the interface of the network. One of the proposed solutions for flow control in the context of the emerging ATM standard is the so-called leaky bucket scheme. In this paper we consider a leaky bucket system with long-range dependent input traffic. We adopt the following popular model for long-range dependent traffic: Time is discrete. At each unit time a random number of sessions is initiated, having the distribution of a Poisson random variable with mean λ. Each of these sessions has a random duration τ, where the integer random variable τ has finite mean, infinite variance, and a regularly varying tail, i.e., P(τ >К) ~ К^-Lα L(К), where 1 < α < 2 L(·) is a slowly varying function. Once a session is initiated, it generates one cell at each unit of time until its termination. We examine the departure process of the leaky bucket policing mechanism driven by such an arrival process, and show that it too is long-range dependent for any token buffer size and any - finite or infinite - cell buffer size. Moreover, upper and lower bounds for the covariance sequence of the output process are established. The above results demonstrate that long-range dependence cannot be removed by the kinds of flow control schemes that are currently being envisioned for broadband networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

Stationary Analysis of a Fluid Queue Driven by Some Countable State Space Markov Chain

Motivated by queueing systems playing a key role in the performance evaluation of telecommunication networks, we analyze in this paper the stationary behavior of a fluid queue, when the instantaneous input rate is driven by a continuous-time Markov chain with finite or infinite state space. In the case of an infinite state space and for particular classes of Markov chains with a countable state space, such as quasi birth and death processes or Markov chains of the G/M/1 type, we develop an algorithm to compute the stationary probability distribution function of the buffer level in the fluid queue. This algorithm relies on simple recurrence relations satisfied by key characteristics of an auxiliary queueing system with normalized input rates.      

Brownian models of multiclass queueing networks: Current status and open problems

This paper is concerned with Brownian system models that arise as heavy traffic approximations for open queueing networks. The focus is on model formulation, and more specifically, on the formulation of Brownian models for networks with complex routing. We survey the current state of knowledge in this dynamic area of research, including important open problems. Brownian approximations culminate in estimates of complete distributions; we present numerical examples for which complete sojourn time distributions are estimated, and those estimates are compared against simulation.     

A feedback fluid queue with two congestion control thresholds

Feedback fluid queues play an important role in modeling congestion control mechanisms for packet networks. In this paper we present and analyze a fluid queue with a feedback-based traffic rate adaptation scheme which uses two thresholds. The higher threshold B ₁ is used to signal the beginning of congestion while the lower threshold B ₂ signals the end of congestion. These two parameters together allow to make the trade-off between maximizing throughput performance and minimizing delay. The difference between the two thresholds helps to control the amount of feedback signals sent to the traffic source. In our model the input source can behave like either of two Markov fluid processes. The first applies as long as the upper threshold B ₁ has not been hit from below. As soon as that happens, the traffic source adapts and switches to the second process, until B ₂ (smaller than B ₁) is hit from above. We analyze the model by setting up the Kolmogorov forward equations, then solving the corresponding balance equations using a spectral expansion, and finally identifying sufficient constraints to solve for the unknowns in the solution. In particular, our analysis yields expressions for the stationary distribution of the buffer occupancy, the buffer delay distribution, and the throughput.