Tai Lieu Chat Luong Optimal Design of Queueing Systems Shaler Stidham, Jr. University of North Carolina Chapel Hill, North Carolina, U. Chapman & Hall/CRC Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487‑2742 © 2009 by Taylor & Francis Group, LLC Chapman & Hall/CRC is an imprint of Taylor & Francis Group, an Informa business No claim to original U. Government works Printed in the United States of America on acid‑free paper 10 9 8 7 6 5 4 3 2 1 International Standard Book Number‑13: 978‑1‑58488‑076‑9 (Hardcover) This book contains information obtained from authentic and highly regarded sources.
Reasonable efforts have been made to publish reliable data and information, but the author and publisher can‑ not assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.
Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.com (http://www.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978‑750‑8400. CCC is a not‑for‑profit organization that pro‑ vides licenses and registration for a variety of users.
For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Library of Congress Cataloging‑in‑Publication Data Stidham, Shaler. Optimal design for queueing systems / Shaler Stidham Jr.” Includes bibliographical references and index.8’2‑‑dc22 2009003648 Visit the Taylor & Francis Web site at http://www.com and the CRC Press Web site at http://www.com Contents List of Figures v Preface ix 1 Introduction to Design Models 1 1.1 Optimal Service Rate 3 1.2 Optimal Arrival Rate 6 1.3 Optimal Arrival Rate and Service Rate 13 1.4 Optimal Arrival Rates for a Two-Class System 16 1.5 Optimal Arrival Rates for Parallel Queues 21 1.6 Endnotes 26 2 Optimal Arrival Rates in a Single-Class Queue 29 2.1 A Model with General Utility and Cost Functions 29 2.2 Generalizations of Basic Model 42 2.3 GI/GI/1 Queue with Probabilistic Joining Rule 45 2.4 Uniform Value Distribution: Stability 68 2.6 Bidding for Priorities 77 2.7 Endnotes 80 3 Dynamic Adaptive Algorithms: Stability and Chaos 83 3.2 Discrete-Time Dynamic Adaptive Model 85 3.3 Discrete-Time Dynamic Algorithms: Variants 98 3.4 Continuous-Time Dynamic Adaptive Algorithms 101 3.5 Continuous-Time Dynamic Algorithm: Variants 106 3.6 Endnotes 107 4 Optimal Arrival Rates in a Multiclass Queue 109 4.1 General Multiclass Model: Formulation 109 4.2 General Multiclass Model: Optimal Solutions 113 4.3 General Multiclass Model: Dynamic Algorithms 124 4.4 Waiting Costs Dependent on Total Arrival Rate 129 4.5 Linear Utility Functions: Class Dominance 134 4.6 Examples with Different Utility Functions 153 iii iv CONTENTS 4.7 Multiclass Queue with Priorities 158 4.9 Figures for FIFO Examples 172 5 Optimal Service Rates in a Single-Class Queue 177 5.1 The Basic Model 178 5.2 Models with Fixed Toll and Fixed Arrival Rate 182 5.3 Models with Variable Toll and Fixed Arrival Rate 184 5.4 Models with Fixed Toll and Variable Arrival Rate 185 5.5 Models with Variable Toll and Variable Arrival Rate 199 5.6 Endnotes 215 6 Multi-Facility Queueing Systems: Parallel Queues 217 6.1 Optimal Arrival Rates 217 6.2 Optimal Service Rates 255 6.3 Optimal Arrival Rates and Service Rates 258 6.4 Endnotes 277 7 Single-Class Networks of Queues 279 7.2 Individually Optimal Arrival Rates and Routes 280 7.3 Socially Optimal Arrival Rates and Routes 282 7.
and Toll-Free I.5 Facility Optimal Arrival Rates and Routes 307 7.6 Endnotes 314 8 Multiclass Networks of Queues 317 8.2 Fixed Routes: Optimal Solutions 330 8.3 Fixed Routes: Dynamic Adaptive Algorithms 334 8.4 Fixed Routes: Homogeneous Waiting Costs 338 8.5 Variable Routes: Homogeneous Waiting Costs 339 8.6 Endnotes 342 A Scheduling a Single-Server Queue 343 A.1 Strong Conservation Laws 343 A.2 Work-Conserving Scheduling Systems 344 A.3 GI/GI/1 WCSS with Nonpreemptive Scheduling Rules 351 A.4 GI/GI/1 Queue: Preemptive-Resume Scheduling Rules 355 A.5 Endnotes 357 References 359 Index 369 List of Figures 1.1 Total Cost as a Function of Service Rate 4 1.2 Optimal Arrival Rate, Case 1: r ≤ h/µ 8 1.3 Optimal Arrival Rate, Case 2: r > h/µ 8 1.4 Net Benefit: Contour Plot 20 1.5 Net Benefit: Response Surface 21 1.6 Arrival Control to Parallel Queues: Parametric Socially Optimal Solution 23 1.7 Arrival Control to Parallel Queues: Explicit Socially Optimal Solution 24 1.8 Arrival Control to Parallel Queues: Parametric Individually Optimal Solution 25 1.9 Arrival Control to Parallel Queues: Explicit Individually Optimal Solution 26 1.10 Arrival Control to Parallel Queues: Comparison of Socially and Individually Optimal Solutions 27 2.1 Characterization of Equilibrium Arrival Rate 33 2.2 Graph of the Function U 0 (λ) 40 2.3 Graph of the Function λU 0 (λ) 41 2.4 Graph of the Objective Function: λU 0 (λ) − λG(λ) 41 2.5 Graph of the Function U 0 (λ) 43 2.6 Equilibrium Arrival Rate.7 Equilibrium Arrival Rate.8 Graphical Interpretation of U (λ) as an Integral: Case 1 50 2.9 Graphical Interpretation of U (λ) as an Integral: Case 2 51 2.14 U (λ) for Three-Class Example 60 2.15 U 0 (λ) for Three-Class Example 61 2.16 λU 0 (λ) for Three-Class Example 63 2.18 Ũ(λ) for Three-Class Example (Case 2) 64 v vi LIST OF FIGURES 2.19 Ui (λ), i = 1, 2, 3, for Three-Class Example 65 2.22 Supply and Demand Curves: Uniform Value Distribution 69 2.23 An Unstable Equilibrium 70 2.24 Convergence to a Stable Equilibrium 71 2.25 Graphical Illustration of Power Maximization 74 2.26 Graph of Equilibrium Bid Distribution 81 3.1 Period-Doubling Bifurcations 95 3.3 Arrival Rate Distribution 97 4.1 Class Dominance Regions for Individual and Social Optimization 153 4.2 Linear Utility Functions: U(λ1 , λ2 ) = 16λ1 − 4λ1 /(1 − λ1 − λ2 ) + 9λ2 − λ2 /(1 − λ1 − λ2 ) 156 4.3 Linear Utility Functions: U(λ1 , λ2 ) = 16λ1 − 4λ1 /(1 − λ1 − λ2 ) + 9λ2 − λ2 /(1 − λ1 − λ2 ) 156 4.4 Linear Utility Functions: U(λ1 , λ2 ) = 64λ1 − 9λ1 /(1 − λ1 − λ2 ) + 12λ2 157 4.5 Linear Utility Functions: U(λ1 , λ2 ) = 16λ1 − 4λ1 /(1 − λ1 ) + 9λ2 − λ2 /((1 − λ1 )(1 − λ1 − λ2 )) 169 4.6 Linear Utility Functions: U(λ1 , λ2 ) = 4λ1 − .7 Square-Root Utility Functions: U(λ1 , λ2 ) = 64λ1 + 8 λ1 − 9λ1 /(1 − λ1 − λ2 ) + 15λ2 √ 172 4.8 Square-Root Utility Functions: U(λ1 , λ2 ) = 24λ1 + 8 λ1 − 9λ1 /(1 − λ1 − λ2 ) + 9λ2 √ 172 4.9 Square-Root Utility Functions: U(λ1 , λ2 ) = 24λ1 + 8 λ1 − 9λ1 /(1 − λ1 − λ2 ) + 9λ2 − 0.10 Square-Root Utility Functions:√ U(λ 1 , λ2 ) = 16λ1 + 16 λ1 − 4λ1 /(1 − λ1 − λ2 ) + 9λ2 + 9 λ2 − λ2 /(1 − λ1 − λ2 ) 173 4.11 Logarithmic Utility Functions: U(λ1 , λ2 ) = 16 log(1 + λ1 ) − 4λ1 /(1 − λ1 − λ2 ) + 3λ2 174 4.12 Logarithmic Utility Functions: U(λ1 , λ2 ) = 16 log(1 + λ1 ) − 4λ1 /(1 − λ1 − λ2 ) + 4 log(1 + λ2 ) − 0.13 Logarithmic Utility Functions: U(λ1 , λ2 ) = 16 log(1 + λ1 ) − 4λ1 /(1 − λ1 − λ2 ) + 9 log(1 + λ2 ) − 0.14 Logarithmic Utility Functions: U(λ1 , λ2 ) = 16 log(1 + λ1 ) − 2λ1 /(1 − λ1 − λ2 ) + 9 log(1 + λ2 ) − 0.15 Quadratic Utility Functions: U(λ1 , λ2 ) = 75λ1 − λ21 − 4λ1 /(1 − λ1 − λ2 ) + 14λ2 − 0.1 M/M/1 Queue: Graph of H(λ, µ) (h = 1) 180 5.2 M/M/1 Queue: Graph of ψ(µ) 190 LIST OF FIGURES vii 5.3 Example with Convex Objective Function, µ > µ0 194 5.4 Long-Run Demand and Supply Curves 203 5.5 Uniform [d, a] Value Distribution Long-Run Demand and Supply Curves, Case 1 205 5.6 Uniform [d, a] Value Distribution Long-Run Demand and Supply Curves, Case 2 205 5.7 Long-Run Demand and Supply Curves; Uniform [0, a] Value Distribution 207 5.8 Convergence of Iterative Algorithm for Case of Uniform [0, a] Demand 208 6. Supply-Demand Curves for Variable λ 239 6.2 Nash Equilibrium for Two Competitive M/M/1 Facilities 246 6.3 Waiting-Cost Function for M/M/1 Queue 251 6.4 Illustration of Sequential Discrete-Time Algorithm 254 6.5 Facility Dominance as a Function of λ 266 6.6 Graphs of U 0 (λ) and C 0 (λ) for Parallel-Facility Example 269 7.1 First Example Network for Braess’s Paradox 286 7.2 Second Example Network for Braess’s Paradox 288 7.3 Example Network with α(λ) < π(λ) 293 7.4 Illustration of Theorem 7.5 Illustration of Derivation of Upper Bound for Affine Waiting- Cost Function 302 7.7 Table: Values of σ = φ(ρe ) and (1 − σ)−1 304 A.1 Graph of V (t): Work in System 345 Preface What began a long time ago as a comprehensive book on optimization of queueing systems has evolved into two books: this one on optimal design and a subsequent book (still in the works) on optimal control of queueing systems. In this setting, “design” refers to setting the parameters of a queueing sys- tem (such as arrival rates and service rates) before putting it into operation. By contrast, in “control” problems the parameters are control variables in the sense that they can be varied dynamically in response to changes in the state of the system.
The distinction between design and control, admittedly, can be somewhat artificial. But the available material had outgrown the confines of a single book and I decided that this was as good a way as any of making a division. Why look at design models? In principle, of course, one can always do better by allowing the values of the decision variables to depend on the state of the system, but in practice this is frequently an unattainable goal. For example, in modern communication networks, real-time information about the buffer contents at the various nodes (routers/switches) of the network would, in principle, help us to make good real-time decisions about the routing of messages or packets.
But such information is rarely available to a centralized controller in time to make decisions that are useful for the network as a whole. Even if it were available, the combinatorial complexity of the decision problem makes it impossible to solve even approximately in the time available. (The essential difficulty with such systems is that the time scale on which the system state is evolving is comparable to, or shorter than, the time scale on which information can be obtained and calculations of optimal policies can be made.) For these and other reasons, those in the business of analyzing, designing, and operating communication networks have turned their attention more and more to flow control, in which quantities such as arrival (e., packet-generation) rates and service (e., transmission) rates are computed as time averages over periods during which they may be reasonably expected to be constant (e., peak and off-peak hours) and models are used to suggest how these rates can be controlled to achieve certain objectives.