nach oben

2001 | Buch

Kapitel lesen Erstes Kapitel lesen

Fundamentals of Queueing Networks

Performance, Asymptotics, and Optimization

verfasst von: Hong Chen, David D. Yao

Verlag: Springer New York

Buchreihe : Stochastic Modelling and Applied Probability

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten

Über dieses Buch

The objective of this book is to collect in a single volume the essentials of stochastic networks, from the classical product-form theory to the more re cent developments such as diffusion and fluid limits, stochastic comparisons, stability, control (dynamic scheduling) and optimization. The selection of materials inevitably is a reflection upon our bias and preference, but it is also driven to a large extent by our desire to provide a graduate-level text that is well balanced in breadth and depth, suitable for the classroom. Given the wide-ranging applications of stochastic networks in recent years, from supply chains to telecommunications, it is also our hope that the book will serve as a useful reference for researchers and students alike in these diverse fields. The book consists of three parts. The first part, Chapters 1 through 4, covers (continuous-time) Markov-chain models, including the classical Jackson and Kelly networks, the notion of quasi-reversible queues, and stochastic comparisons. The second part, Chapters 5 through 10, focuses on Brownian models, including limit theorems for generalized Jackson net works and multiclass feedforward networks, an in-depth examination of stability in a Kumar-Seidman network, and Brownian approximations for general multiclass networks with a mixture of priority and first-in-first-out disciplines. The third part, Chapters 11 and 12, discusses scheduling in both queueing (stochastic) and fluid (deterministic) networks, along with topics such as conservation laws, polymatroid optimization, and linear pro gramming.

Inhaltsverzeichnis

Frontmatter

1. Birth-Death Queues

Abstract

This chapter introduces three preliminary topics that will serve as the basis for much of the first part of this book (the first four chapters), which focuses on continuous-time Markov chain models. The three topics are (a) the birth—death process and related queueing models in Section 1.1, (b) the notion of time reversibility of a Markov chain in Section 1.2, and (c) likelihood ratio ordering and stochastic ordering in Section 1.3.

Hong Chen, David D. Yao

2. Jackson Networks

Abstract

A Jackson network consists of J nodes (or stations), each with one or several servers. The processing times of jobs at each node are i.i.d., following an exponential distribution with unit mean. The service rate, i.e., the rate by which work is depleted, at each node i can be both node-dependent and state-dependent. Specifically, whenever there are x _i jobs at node i, the processing rate is μ _i(x _i),where μ _i(·)is a function Z ₊ ↦ ℜ₊, with μ _i(0)= 0 and μ _i (x) > 0 for all x > 0. Jobs travel among the nodes following a routing matrix P:= (p _ij), where, for i, j = 1,..., J,p _ijis the probability that a job leaving node i will go to node j.

Hong Chen, David D. Yao

3. Stochastic Comparisons

Abstract

We continue our study of Jackson networks, but shift to focusing on their structural properties: those that describe the qualitative behavior of the network. We want to demonstrate that the Jackson network has the capability to capture the essential qualitative behavior of the system, to make it precise, and to bring out explicitly the role played by different resources and control parameters.

Hong Chen, David D. Yao

4. Kelly Networks

Abstract

The central approach used in this chapter, just as in Section 2.6, is to examine a stationary Markov chain together with its time-reversal: another Markov chain defined through reversing the time index of the original chain. Applying this technique to the Jackson network in Section 2.6, we not only recovered the product-form distributions derived earlier in Chapter 2 but also established the Poisson property of the exit processes from the network. In particular, we showed that in equilibrium the Jackson network preserves the Poisson property of the input processes to the network, such that the exit processes are also Poisson. This “Poisson-in-Poisson-out” property is the main motivation here for defining and studying a class of so-called quasi-reversible queues. This class is an extension of the basic M/M(n)/1 queues, which constitute the nodes in a Jackson network, to allow multiclass jobs and more general arrival and service disciplines, while still preserving the Poisson-in-Poisson-out property. It turns out that a general multiclass network, known as a Kelly network, which connects a set of quasi-reversible queues through some very general routing schemes, still enjoys the basic properties of the Jackson network, namely, the product-form equilibrium distribution and the Poisson-in-Poisson-out property.

Hong Chen, David D. Yao

5. Technical Desiderata

Abstract

This chapter collects background materials for the many limit theorems in queues and queueing networks that will appear in later chapters. We start with presenting some preliminaries in basic probability theory, such as almost sure convergence and weak convergence, Donsker’s theorem and Brownian motion, in Sections 5.1–5.3. Then in Sections 5.4–5.6, we focus on a pair of fundamental processes: the partial sum of i.i.d. random variables and the associated renewal counting process. The pair serves as a building block for modeling many queueing systems. We show that under different time—space scaling the pair converges differently, leading to functional versions of the strong law of large numbers and the central limit theorem. Furthermore, with additional moment conditions (on the i.i.d. random variables), we can refine these limits via functional versions of the law of iterated logarithms and strong approximations. When the generating function of the i.i.d. random variables exist, we can further characterize the convergence rate via exponential bounds.

Hong Chen, David D. Yao

6. Single-Station Queues

Abstract

The main subject of this chapter is limit theorems for the queue-length and the workload processes in the G/G/1 queue. The limit theorems include the functional strong law of large numbers (FSLLN), the functional law of the iterated logarithm (FLIL), the functional central limit theorem (FCLT) and the strong approximation. In addition, we also establish an exponential rate of convergence result for the fluid approximation. The limit of the FSLLN and the FLIL is a single station fluid model. Because of this, the FSLLN is often known as the fluid approximation. Similarly, the limit of the FCLT and the strong approximation takes the form of a one-dimensional reflected Brownian motion. Since this limit is a diffusion process, the FCLT has been conventionally known as diffusion approximation. Throughout this and the following chapters we shall follow the convention to use the terms “fluid approximation” and “diffusion approximation” interchangeably with their underlying limit theorems. (In contrast, in Chapter 10, where the proposed approximations are not necessarily supported by limit theorems, we shall use the term “Brownian approximation,” in keeping with the Brownian network models in the research literature as approximations for queueing networks.)

Hong Chen, David D. Yao

7. Generalized Jackson Networks

Abstract

In this chapter we consider a queueing network that generalizes the Jackson network studied in Chapter 2, by allowing renewal arrival processes that need not be Poisson and i.i.d. service times that need not follow exponential distributions. (However, we do not allow the service times of the network to be state-dependent; in this regard, the network is more restrictive than the Jackson network. Nevertheless, this network has been conventionally referred to as the generalized Jackson network.) Unlike the Jackson network, the stationary distribution of a generalized Jackson network usually does not have an explicit analytical form. Therefore, approximations and limit theorems that support such approximations are usually sought for the generalized Jackson networks.

Hong Chen, David D. Yao

8. A Two-Station Multiclass Network

Abstract

Most of this chapter focuses on a two-station queueing network. We spell out details of the model in the next section, followed by Section 8.2-Section 8.5, where we study, respectively, a corresponding fluid network, the stability of the queueing network via the fluid network, the fluid limit, and the diffusion limit. Finally, in Section 8.6 we present additional network examples that appear to be counterintuitive to what we know from single-class networks. This last section is technically independent of the earlier sections; however, it provides further motivation as to why stability is an important and interesting issue in multiclass networks.

Hong Chen, David D. Yao

9. Multiclass Feedforward Networks

Abstract

In a feedforward network, jobs after service completion at a station can be routed only to a downstream station. Other than this restriction on routing, the network has more features than the generalized Jackson network studied in Chapter 7. In particular, jobs at each station come from different classes, with different service time distributions, and upon service completion will follow different routing sequences. In addition, job classes are partitioned into priority groups. Within the same group, jobs are served in the order of arrivals, i.e., following a first-in-first-out (FIFO) discipline. Among different groups, jobs are served under a preassigned preemptive priority discipline. Therefore, the model includes a network with a pure FIFO service discipline or a pure priority service discipline as a special case.

Hong Chen, David D. Yao

10. Brownian Approximations

Abstract

The purpose of this chapter is to develop a general approach to approximating a multiclass queueing network by a semimartingale reflected Brownian motion, (SRBM), which is a generalization of the RBM studied earlier. Our focus is not on proving limit theorems so as to justify why the network in question can be approximated by an SRBM (as we did in several previous chapters). Rather our intention is to illustrate how to approximate the network by an SRBM. We make no claim that the proposed approximation can always be justified by some limit theorems. To the contrary, through both analysis and numerical results, we identify cases where the SRBM may not exist, or may work poorly. (A complete characterization of when the proposed approximation works is a challenging and active research topic; refer to Section 10.7 for a survey on the recent advances in this research area.)

Hong Chen, David D. Yao

11. Conservation Laws

Abstract

Conservation laws belong to the most fundamental principles that govern the dynamics, or law of motion, of a wide range of stochastic systems. Under conservation laws, the performance space of the system becomes a polymatroid, that is, a polytope with a matroid-like structure, with all the vertices corresponding to the performance under priority rules, and all the vertices are easily identified. Consequently, the optimal control problem can be translated into an optimization problem. When the objective is a linear function of the performance measure, the optimization problem becomes a special linear program, for which the optimal solution is a vertex that is directly determined by the relative order of the cost coefficients in the linear objective. This implies that the optimal control is a priority rule that assigns priorities according to exactly the order of the cost coefficients.

Hong Chen, David D. Yao

12. Scheduling of Fluid Networks

Abstract

Here we study the optimal scheduling of a multiclass fluid network. We start with model formulation in Section 12.1, followed by developing a solution procedure based on linear programming in Section 12.2, and establishing several key properties of the procedure in Section 12.3. In particular, we show that the procedure involves up to 2^K iterations (K being the total number of types), and that the so-called global optimality, i.e., optimality of the objective function over every time point, is not guaranteed. In this sense, the solution procedure is termed “myopic” (or greedy). On the other hand, we show that the procedure is guaranteed to lead to the stability of the fluid network. In addition, we derive the minimum “clearing time” as the time it takes to drive all fluid levels down to zero.

Hong Chen, David D. Yao

Backmatter

Titel: Fundamentals of Queueing Networks
verfasst von: Hong Chen
David D. Yao
Verlag: Springer New York
Electronic ISBN: 978-1-4757-5301-1
Print ISBN: 978-1-4419-2896-2
DOI: https://doi.org/10.1007/978-1-4757-5301-1

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

1. Birth-Death Queues

2. Jackson Networks

3. Stochastic Comparisons

4. Kelly Networks

5. Technical Desiderata

6. Single-Station Queues

7. Generalized Jackson Networks

8. A Two-Station Multiclass Network

9. Multiclass Feedforward Networks

10. Brownian Approximations

11. Conservation Laws

12. Scheduling of Fluid Networks

Backmatter