Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Performance of computer communication systems - a model-based approach
Nội dung xem thử
Mô tả chi tiết
PERFO~CI~ 0E;
CoMPUTER
COMMUNICA~ON
SYSTEMS
Performance of Computer Communication Systems: A Model-Based Approach.
Boudewijn R. Haverkort
Copyright © 1998 John Wiley & Sons, Ltd
Print ISBN 0-471-197228-2 Electronic ISBN 0-470-84192-3
PERFORMAN~E~F
COMPUTER
COMMUNICATION
SYSTEMS
A Model-Based Approach
BOUDEWIJN R. HAVERKORT
Rheinisch- Westfalische Technische
Hochschule Aachen, Germany
John Wiley & Sons, Ltd
Chichester l New York l Weinheim l Brisbane l Singapore l Toronto
Copyright 0 1998 by John Wiley & Sons Ltd,
Baffins Lane, Chichester,
West Sussex PO 19 1 UD, England
National 0 1243 779777
International (+44) 1243 779777
e-mail (for orders and customer service enquiries): [email protected]
Visit our Home Page on http://www.wiley.co.uk or http://www.wiley.com
Reprinted June 1999
All Rights Reserved. No part of this publication may be reproduced, stored in a retrieval system, or
transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or
otherwise, except under the terms of the Copyright, Designs and Patents Act 1988 or under the terms of a
licence issued by the Copyright Licensing Agency, 90 Tottenham Court Road, London W 1P 9HE, UK,
without the permission in writing of the Publisher.
Neither the author nor John Wiley & Sons Ltd accept any responsibility or liability for loss or damage
occasioned to any person or property through using the material, instructions, methods or ideas contained
herein, or acting or refraining from acting as a result of such use. The author and Publisher expressly
disclaim all implied warranties, including merchantability or fitness for any particular purpose. There will
be no duty on the author or Publisher to correct any errors or defects in the software.
Designations used by companies to distinguish their products are often claimed as trademarks. In all
instances where John Wiley & Sons is aware of a claim, the product names appear in initial capital or all
capital letters. Readers, however, should contact the appropriate companies for more complete information
regarding trademarks and registration.
Other Wiley Editorial Oflees
New York l Weinheim l Brisbane l Singapore l Toronto
Library of Congress Cataloguing in Publication Data
Haverkort, Boudewijn R.
Performance of computer communication systems : a model-based
approach / Boudewijn R. Haverkort.
p. cm.
Includes bibliographical references and index.
ISBN O-471-97228-2 (alk. paper)
1. Computer networks-Evaluation. 2. Electronic digital
computers-Evaluation. 3. Queuing theory. 4. Telecommunication
systems-Evaluation, 5. Stochastic processes. I. Title.
TK5 105.5.H375 1998
004.6-dc2 1 98-27222
CIP
British Library Cataloguing in Publication Data
A catalogue record for this book is available from the British Library
ISBN 0 471 97228 2
Produced from Postcript files supplied by the author.
Printed and bound in Great Britain by Biddles Ltd, Guildford and King’s Lynn.
This book is printed on acid-free paper responsibly manufactured from sustainable
forestry, in which at least two trees are planted for each one used in paper production.
In memory of my father
Johannes Hermannus Hendrikus Haverkort
Contents
Preface xvii
I Performance modelling with stochastic processes
1 Introduction
1.1 Performance evaluation: aim and approach ..................
1.2 Model solution techniques ...........................
1.3 Stochastic models ................................
1.4 Queueing models ................................
1.4.1 The principle of queueing .......................
1.4.2 Single queues: the Kendall notation ..................
1.5 Tool support. ..................................
1.5.1 Model construction ...........................
1.5.2 Model solution .............................
1.6 Further reading .................................
1.7 Exercises .....................................
2 Little’s law and the MIMI1 queue
2.1 Little’s law ...................................
2.1.1 Understanding Little’s law .......................
2.1.2 Proof of Little’s law ...........................
2.2 The simplest queueing model: the MI M 11 queue ...............
2.3 Further reading .................................
2.4 Exercises .....................................
3 Stochastic processes
3.1 Overview of stochastic processes . . . . . . . . . . . . . . . . . . . . . . . .
1
3
3
8
9
11
11
13
15
15
18
19
19
21
21
21
24
25
28
28
31
31
. . . Vlll Contents
3.2
3.3
3.4
3.5
3.6
3.7
3.8
3.9
Renewal processes ................................ 34
Discrete-time Markov chains .......................... 37
Convergence properties of Markov chains ................... 41
Continuous-time Markov chains ........................ 43
3.5.1 From DTMC to CTMC ........................ 43
3.5.2 Evaluating the steady-state and transient behaviour ......... 45
Semi-Markov chains ............................... 51
The birth-death process ............................ 53
The Poisson process. .............................. 53
Renewal processes as arrival processes ..................... 54
3.9.1 Phase-type distributions ........................ 55
3.9.2 Phase-type renewal processes ..................... 58
3.10 Summary of Markov chains .......................... 62
3.11 Further reading ................................. 63
3.12 Exercises. .................................... 63
II Single-server queueing models 67
4 MIMI1 queueing models 69
4.1 General solution of the MIMI1 queue ..................... 70
4.2 The MIMI1 queue with constant rates ..................... 73
4.3 The PASTA property .............................. 74
4.4 Response time distribution in the MIMI1 queue ............... 76
4.5 The MIMI m multi-server queue ........................ 77
4.6 The MIMI 00 infinite-server queue ....................... 79
4.7 Job allocation in heterogeneous multi-processors ............... 80
4.8 The MIMI11 m single-server queue with bounded buffer ........... 83
4.9 The MIMI m m I multi-server queue without buffer ............... 85
4.10 The MIM(l((K queue or the terminal model ................. 86
4.11 Mean values for the terminal model ...................... 88
4.12 Further reading ................................. 92
4.13 Exercises. .................................... 92
5 MIGjl-FCFS queueing models 95
5.1 The M/Gil result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.2 An intuitive proof of the M/G/l result . . . . . . . . . . . . . . . . . . . . . 99
Contents iX
5.2.1 Residual lifetime ............................ 100
5.2,2 Intuitive proof .............................. 103
5.3 A formal proof of the MlGll result ...................... 104
5.4 The MlGll model with batch arrivals ..................... 107
5.5 MI G/ 1 queueing systems with server breakdowns ............... 109
5.5.1 Single arrivals .............................. 110
5.5.2 Batch arrivals .............................. 111
5.6 Further reading ................................. 112
5.7 Exercises ..................................... 112
6 M/G/ 1 queueing models with various scheduling disciplines 115
6.1 Non-preemptive priority scheduling ...................... 115
6.2 Preemptive priority scheduling ......................... 121
6.3 Shortest job next scheduling .......................... 123
6.4 Round robin scheduling ............................. 126
6.5 Processor sharing scheduling .......................... 128
6.6 Scheduling based on elapsed processing time ................. 129
6.7 Further reading ................................. 131
6.8 Exercises ..................................... 131
7 G)Mll-FCFS and GIGIl-FCFS queueing models 133
7.1 The GlMll queue ................................ 133
7.2 The GIG11 queue ................................ 139
7.3 Approximate results for the G(GI 1 queue ................... 143
7.4 Further reading ................................. 143
7.5 Exercises ..................................... 144
8 PHIPHIl queueing models 145
8.1 The MIMI1 queue ................................ 145
8.2 The PHIPHIl queue .............................. 148
8.2.1 A structured description of the CTMC ................ 148
8.2.2 Matrix-geometric solution ....................... 152
8.2.3 Stability issues ............................. 153
8.2.4 Performance measures ......................... 154
8.3 Numerical aspects ................................ 155
8.3.1 Solving the boundary equations .................... 155
X Contents
8.3.2 A successive substitution algorithm .................. 156
8.3.3 The logarithmic reduction algorithm ................. 158
8.4 A few special cases ............................... 162
8.4.1 The M/PHI1 q ueue: an explicit expression for R ........... 162
8.4.2 The PHlMlm queue ........................... 163
8.5 The caudal curve ................................ 164
8.6 Other models with matrix-geometric solution ................. 167
8.7 Further reading ................................. 169
8.8 Exercises ..................................... 169
9 Polling models 173
9.1 Characterisation of polling models ....................... 173
9.1.1 Basic terminology ............................ 174
9.1.2 The visit order ............................. 174
9.1.3 The scheduling strategy ........................ 176
9.2 Cyclic polling: cycle time and conservation law ............... 177
9.3 Count-based symmetric cyclic polling models ................. 180
9.4 Count-based asymmetric cyclic polling models ................ 183
9.4.1 Exhaustive service: exact analysis ................... 183
9.4.2 Some approximate results ....................... 184
9.5 Performance evaluation of the IBM token ring ................ 186
9.5.1 Timed-token access mechanisms .................... 186
9.5.2 Approximating the timed-token access mechanism .......... 187
9.5.3 The influence of the token holding timer ............... 189
9.6 Local and global time-based polling models .................. 191
9.7 Further reading ................................. 194
9.8 Exercises ..................................... 194
III Queueing network models 197
10 Open queueing networks 199
10.1 Basic terminology ................................ 200
10.2 Feed-forward queueing networks ........................ 200
10.2.1 The MIMI1 queue ............................ 200
10.2.2 Series of MIMI1 queues ......................... 201
10.2.3 Feed-forward queueing networks .................... 204
Contents xi
10.3 Jackson queueing networks ........................... 205
10.4 The QNA method ................................ 207
10.4.1 The QNA queueing network class ................... 208
10.4.2 The QNA method ............................ 209
10.4.3 Summary of approximations ...................... 219
10.5 Telecommunication network modelling .................... 220
10.5.1 System description ........................... 220
10.5.2 Evaluation using Jackson queueing networks ............. 223
10.5.3 Evaluation using networks of M 1 G 11 queues ............. 224
10.5.4 Evaluation using QNA ......................... 225
10.6 Further reading ................................. 226
10.7 Exercises ..................................... 226
11 Closed queueing networks 229
11.1 Gordon-Newell queueing networks ....................... 229
11.2 The convolution algorithm ........................... 235
11.3 Mean-value analysis ............................... 241
11.4 Mean-value analysis-based approximations .................. 245
11.4.1 Asymptotic bounds ........................... 245
11.4.2 The Bard-Schweitzer approximation .................. 247
11.4.3 Balanced networks ........................... 248
11.5 An approximate solution method ....................... 251
11.5.1 Queueing network definition ...................... 252
11.5.2 Basic approach ............................. 252
11.5.3 Numerical solution ........................... 254
11.5.4 Extension to other queueing stations ................. 256
11.6 Application study 258 ..... / . ....
11.6.1 System description and basic model ....................................... 258
11.6.2 Evaluation with MVA and other techniques ............. 259
11.6.3 Suggestions for performance improvements .............. 261
11.7 Further reading ................................. 261
11.8 Exercises ..................................... 263
12 Hierarchical queueing networks 265
12.1 Load-dependent servers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
12.2 The convolution algorithm . , . . . . . . . . . . . . . . . . . . . . . . . . . 269
xii Contents
12.3 Special cases of the convolution algorithm .................. 272
12.3.1 Convolution with multi-server queueing stations ........... 272
12.3.2 Convolution with an infinite-server station .............. 273
12.4 Mean-value analysis ............................... 274
12.5 Exact hierarchical decomposition ....................... 277
12.5.1 Informal description of the decomposition method .......... 277
12.5.2 Formal derivation of the decomposition method ........... 279
12.6 Approximate hierarchical decomposition ................... 283
12.6.1 Multiprogrammed computer system models ............. 283
12.6.2 Studying paging effects ......................... 286
12.7 Further reading ................................. 290
12.8 Exercises ..................................... 291
13 BCMP queueing networks 293
13.1 Queueing network class and solution ..................... 293
13.1.1 Model class ............................... 293
13.1.2 Steady-state customer probability distribution ............ 295
13.2 Computational algorithms ........................... 298
13.2.1 The convolution algorithm ....................... 298
13.2.2 Mean-value analysis ........................... 299
13.3 Further reading ................................. 300
13.4 Exercises ..................................... 301
IV Stochastic Petri net models 303
14 Stochastic Petri nets 305
14.1 Definition .................................... 305
14.1.1 Static SPN properties ......................... 306
14.1.2 Dynamic SPN properties ........................ 307
14.1.3 SPN extensions ............................. 311
14.2 Structural properties .............................. 312
14.3 Measures to obtain from SPNs ......................... 316
14.4 Mapping SPNs to CTMCs ........................... 318
14.5 Further reading ................................. 323
14.6 Exercises ..................................... 325
Contents . . . x111
15 Numerical solution of Markov chains 329
15.1 Computing steady-state probabilities ..................... 329
15.1.1 Gaussian elimination .......................... 330
15.1.2 LU decomposition ............................ 334
15.1.3 Power, Jacobi, Gauss-Seidel and SOR iterative methods. ...... 337
15.2 Transient behaviour ............................... 343
15.2.1 Introduction ............................... 343
15.2.2 Runge-Kutta methods ......................... 346
15.2.3 Uniformisation ............................. 347
15.2.4 Cumulative measures .......................... 352
15.3 Further reading ................................. 353
15.4 Exercises ..................................... 354
16 Stochastic Petri net applications 357
16.1 Multiprogramming systems ........................... 357
16.1.1 Multiprogramming computer systems ................. 358
16.1.2 The SPN model ............................. 358
16.1.3 Some numerical results ......................... 360
16.2 Polling models .................................. 363
16.2.1 Count-based, cyclic polling models .................. 365
16.2.2 Local time-based, cyclic polling models ................ 367
16.2.3 Approximating large models ...................... 371
16.2.4 Polling with load-dependent visit ordering .............. 373
16.3 An SPN availability model ........................... 376
16.4 Resource reservation systems .......................... 378
16.5 Further reading ................................. 381
16.6 Exercises ..................................... 382
17 Infinite-state SPNs 383
17.1 Introduction ................................... 383
17.2 Definitions .................................... 385
17.2.1 Preliminaries .............................. 385
17.2.2 Requirements: formal definition .................... 385
17.2.3 Requirements: discussion ........................ 386
17.3 Matrix-geometric solution ........................... 387
17.4 iSPN specification and measure computation ................. 390
xiv Contents
17.4.1 From iSPN to the underlying QBD ..................
17.4.2 Efficient computation of reward-based measures ...........
17.5 Application studies ...............................
17.5.1 A queueing model with delayed service ................
17.5.2 Connection management in communication systems .........
17.5.3 A queueing system with checkpointing and recovery .........
17.6 Further reading .................................
17.7 Exercises .....................................
390
391
393
393
395
399
405
405
V Simulation 407
18 Simulation: methodology and statistics 409
18.1 The idea of simulation ............................. 409
18.2 Classifying simulations ............................. 411
18.3 Implementation of discrete-event simulations ................. 412
18.3.1 Terminology ............................... 412
18.3.2 Time-based simulation ......................... 413
18.3.3 Event-based simulation ......................... 415
18.3.4 Implementation strategies ....................... 418
18.4 Random number generation .......................... 419
18.4.1 Generating pseudo-random numbers ................. 420
18.4.2 Testing pseudo-uniformly distributed random numbers ....... 422
18.4.3 Generation of non-uniformly distributed random numbers ...... 424
18.5 Statistical evaluation of simulation results .................. 427
18.5.1 Obtaining measurements ........................ 428
18.5.2 Mean values and confidence intervals ................. 430
18.6 Further reading ................................. 434
18.7 Exercises ..................................... 435
VI Appendices 439
A Applied probability for performance analysts 441
A.1 Probability measures .............................. 441
A.2 Discrete random variables ........................... 443
A.3 Some important discrete distributions ..................... 444
Contents XV
A.4 Continuous random variables ......................... 445
A.5 Some important continuous distributions ................... 447
A.6 Moments of random variables ......................... 450
A.7 Moments of discrete random variables ..................... 451
A.8 Moments of continuous random variables ................... 452
B Some useful techniques in applied probability
B.l Laplace transforms . . . . . . . . . . . . . . . .
B.2 Geometric series . . . . . . . . . . . . . . . . . .
B.3 Tensor sums and products . . . . . . . . . . . .
C Abbreviations
Bibliography
Index
455
. . . . * . . . . . . . . . 455
. . . . . . . . . . . . . . 457
. . . . . . . . . . . . . . 458
461
465
489
Preface
W HEN I began lecturing a course on the performance of communication systems in
the electrical engineering department of the University of Twente in the fall of
1990, I had difficulty in finding a suitable textbook for this course. Many books were too
much mathematically oriented, others used only a very limited set of evaluation techniques,
e.g.,only the MlGll q ueue. I therefore decided to use a collection of book chapters, recent
survey articles and some research papers, thereby focusing on the performance evaluation
of network access mechanisms. During the semester, however, I began to realise that using
material from different sources is not the most adequate. To overcome this inadequacy, I
started to develop my own course material in the years that followed.
In 1993 I also started lecturing a course on the performance evaluation of computer
systems in the computer science department of the University of Twente, traditionally focused on scheduling techniques, queueing networks and multiprogramming models. Trying
to organise my teaching more efficiently, I decided to extend my course notes so that they
could be used for both classes: an introductory part on stochastic processes and singleserver queues, followed by specialisations towards communication networks and computer
systems. By mid 1995, the course notes had evolved into a booklet of some 200 pages.
After having moved to the RWTH-Aachen in the fall of 1995, I started two new courses
for computer science students, dealing with a superset of the themes I already addressed
at the University of Twente. The evolving course notes for these two courses resulted in
the book you are now reading.
Prerequisites
Many performance evaluation textbooks require a rather strong mathematical background
of the readers, e.g., by the extensive use of Laplace transforms. In this book, the use
of Laplace and x-transforms is completely avoided (except for two non-critical issues in
Part II) ; however, it is assumed that the readers are familiar with the basic principles of