Stewart - Probability, Markov Chains, Queues, and Simulation: The Mathematical Basis of Performance Modeling

PROBABILITY, MARKOV CHAINS,
QUEUES, AND SIMULATION

PROBABILITY, MARKOV CHAINS,
QUEUES, AND SIMULATION

The Mathematical Basis of
Performance Modeling

William J. Stewart

Copyright 2009 by Princeton University Press

Published by Princeton University Press, 41 William street, Princeton, New Jersey 08540

In the United Kingdom: Princeton University Press, 6 Oxford Street,

Woodstock, Oxfordshire OX20 1TW

All Rights Reserved

Library of Congress Cataloging-in-Publication Data

Stewart, William J., 1946

Probability, Markov chains, queues and simulation: the mathematical basis of

performance modeling/William J. Stewart. 1st ed.

p. cm.

ISBN 978-0-691-14062-9 (cloth : alk. paper) 1. ProbabilityComputer simulation.

2. Markov processes. 3. Queueing theory. I. Title.

QA273.S7532 2009

519.20113dc22 2008041122

British Library Cataloging-in-Publication Data is available

This book has been composed in Times

Printed on acid-free paper.

press.princeton.edu

MATLAB is a registered trademark of The MathWorks, Inc.

Typeset by S R Nova Pvt Ltd, Bangalore, India

Printed in the United States of America

10 9 8 7 6 5 4 3 2 1

This book is dedicated to all those
whom I love, especially

My dear wife, Kathie,
and my wonderful children
Nicola, Stephanie, Kathryn, and William

My father, William J. Stewart and
the memory of my mother, Mary (Marshall) Stewart

This book has been written to provide a complete, yet elementary and pedagogic, treatment of the mathematical basis of systems performance modeling. Performance modeling is of fundamental importance to many branches of the mathematical sciences and engineering as well as to the social and economic sciences. Advances in methodology and technology have now provided the wherewithal to build and solve sophisticated models. The purpose of this book is to provide the student and teacher with a modern approach for building and solving probability based models with confidence.

The book is divided into four major parts, namely, Probability, Markov Chains, Queueing Models, and Simulation. The eight chapters of is devoted to bounds and limit theorems, including the laws of large numbers and the central limit theorem.

deals with numerical solutions, from Gaussian elimination and basic iterative-type methods for stationary solutions to ordinary differential equation solvers for transient solutions. Block methods and iterative aggregation-disaggregation methods for nearly completely decomposable Markov chains are considered. A section is devoted to matrix geometric and matrix analytic methods for structured Markov chains. Algorithms and computational considerations are stressed throughout this chapter.

Queueing models are presented in the five chapters that constitute , treats queueing networks. Open networks are introduced via Burkes theorem and Jacksons extensions to this theorem. Closed queueing networks are treated using both the convolution algorithm and the mean value approach. The flow-equivalent server approach is also treated and its potential as an approximate solution procedure for more complex networks is explored. The chapter terminates with a discussion of product form in queueing networks and the BCMP theorem for open, closed, and mixed networks.

The final part of the text, is the final chapter in the book. It concerns simulation measurement and accuracy and is based on sampling theory. Special attention is paid to the generation of confidence intervals and to variance reduction techniques, an important means of keeping the computational costs of simulation to a manageable level.

The text also includes two appendixes; the first is just a simple list of the letters of the Greek alphabet and their spellings; the second is a succinct, yet complete, overview of the linear algebra used throughout the book.

This book saw its origins in two first-year graduate level courses that I teach, and have taught for quite some time now, at North Carolina State University. The first is entitled An Introduction to Performance Evaluation; it is offered by the Computer Science Department and the Department of Electrical and Computer Engineering. This course is required for our networking degrees. The second is a course entitled Queues and Stochastic Service Systems and is offered by the Operations Research Program and the Industrial and Systems Engineering Department. It follows then that this book has been designed for students from a variety of academic disciplines in which stochastic processes constitute a fundamental concept, disciplines that include not only computer science and engineering, industrial engineering, and operations research, but also mathematics, statistics, economics, and business, the social sciencesin fact all disciplines in which stochastic performance modeling plays a primary role. A calculus-based probability course is a prerequisite for both these courses so it is expected that students taking these classes are already familiar with probability theory. However, many of the students who sign up for these courses are returning students, and it is often the case that it has been several years and in some cases a decade or more, since they last studied probability. A quick review of probability is hardly sufficient to bring them can then be used as a reference source as and when needed.

The entire text has been written at a level that is suitable for upper-level undergraduate students or first-year graduate students and is completely self-contained. The entirety of the text can be covered in a two-semester sequence, such as the stochastic processes sequence offered by the Industrial Engineering (IE) Department and the Operations Research (OR) Program at North Carolina State University. A two-semester sequence is appropriate for classes in which students have limited (or no) exposure to probability theory. In such cases it is recommended that the first semester be devoted to the , which concern elementary queueing theory. With this background clearly understood, the student should have no difficulty in covering the remaining topics of the text in the second semester.

The complete content of could also be eliminated: for example, an instructor might include only the first three sections of this chapter. In my own case, when teaching the OR/IE course, I concentrate on covering all of the Markov chain and queueing theory chapters. These students often take simulation as an individual course later on. When teaching the computer science and engineering course, I omit some of the material on the numerical solution of Markov chains so as to leave enough time to cover simulation.

Numerous examples with detailed explanations are provided throughout the text. These examples are designed to help the student more clearly understand the theoretical and computational aspects of the material and to be in a position to apply the acquired knowledge to his/her own areas of interest. A solution manual is available for teachers who adopt this text for their courses. This manual contains detailed explanations of the solution of all the exercises.

Where appropriate, the text contains program modules written in Matlab or in the Java programming language. These programs are not meant to be robust production code, but are presented so that the student may experiment with the mathematical concepts that are discussed. To free the student from the hassle of copying these code segments from the book, a listing of all of the code used can be freely downloaded from the web page: