Queueing Networks

A Fundamental Approach
1. Auflage 2010
ISBN: 978-1-4419-6472-4
Verlag: Springer-Verlag
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 800 Seiten

Autoren/Hrsg.

Inhaltsverzeichnis

1;Preface;6
1.1;Part 1. Exact analytical results, chapters 1–7;7
1.2;Part 2. Monotonicity and comparison results, chapters 8–9;7
1.3;Part 3. Diffusion and fluid results, chapters 10–12;8
1.4;Part 4. Computational and approximate results, chapters 13–15;8
1.5;Part 5. Selected applications, chapters 16–18;9
1.6;Acknowledgments;9
2;Contents;10
3;List of Contributors;22
4;Chapter 1 On Practical Product Form Characterizations;26
4.1;A: Product Forms: Single Station Hierarchy;27
4.1.1;1.1 Introduction;27
4.1.2;1.2 Product Forms: Three Balances;29
4.1.2.1;1.2.1 Station Balance: B-D or Erlang-Engset systems;29
4.1.2.2;1.2.2 Class balance: Coordinate convex property (CCP);31
4.1.2.2.1;1.2.2.1 Two class coordinate convex case;31
4.1.2.2.2;1.2.2.2 Class Balance and Product Form;35
4.1.2.2.3;1.2.2.3 More examples;37
4.1.2.3;1.2.3 Job Local Balance: Necessity;40
4.1.2.3.1;1.2.3.1 Introduction: single server system;40
4.1.2.3.2;1.2.3.2 Instructive FCFS case;41
4.1.2.3.3;1.2.3.3 LCFS-pre case;43
4.1.2.4;1.2.4 LCFS-pre case: Nonexponential;44
4.1.2.5;1.2.5 Symmetric Disciplines and Job-Local-balance (JLB);47
4.1.3;1.3 Invariant Disciplines and JLB;50
4.1.3.1;1.3.1 Invariance Condition;50
4.1.3.2;1.3.2 Service invariant examples;53
4.1.3.3;1.3.3 A generalized symmetric insensitivity result;57
4.1.4;1.4 An application, literature discussion and hierarchy review;60
4.1.4.1;1.4.1 An M|G|c|c+m application;60
4.1.4.2;1.4.2 Literature discussion;62
4.1.4.3;1.4.3 A hierarchy review;64
4.2;B: Product Forms: Tandem and Cluster Structures;66
4.2.1;1.5 Tandem Queues;66
4.2.1.1;1.5.1 Introduction;66
4.2.1.2;1.5.2 Product Form Tandem Queues;70
4.2.1.3;1.5.3 Service examples;74
4.2.1.4;1.5.4 Blocking examples;76
4.2.1.5;1.5.5 Mixed examples;79
4.2.2;1.6 Jacksonian clusters;81
4.2.2.1;1.6.1 A Jackson cluster;81
4.2.2.2;1.6.2 A restricted Jackson cluster;83
4.2.2.3;1.6.3 A conservative product form protocol;85
4.2.3;1.7 Product form bounds for networks of restricted clusters;87
4.2.3.1;1.7.1 Instructive tandem extension;88
4.2.3.2;1.7.2 A Jackson Tandem;91
4.2.3.3;1.7.3 A nested case;93
4.2.3.4;1.7.4 Further illustrative examples;94
4.2.3.4.1;1.7.4.1 A ClusterWith Parallel Stations;95
4.2.3.4.2;1.7.4.2 An Overflow Example;96
4.2.3.4.3;1.7.4.3 A breakdownModel;96
4.2.3.5;1.7.5 An Optimal Design Application;98
4.2.4;1.8 A hospital application;98
4.2.4.1;1.8.1 Motivation;98
4.2.4.2;1.8.2 Model formulation;99
4.2.4.3;1.8.3 Bounds and application;101
4.2.5;1.9 Evaluation;102
4.2.5.1;1.9.1 Literature;102
4.2.5.2;1.9.2 Review Part B;104
4.2.5.3;1.9.3 Some remaining questions;105
4.3;Acknowledgements;105
4.4;References;106
5;Chapter 2 Order Independent Queues;109
5.1;2.1 Introduction;109
5.2;2.2 The OI Queue;111
5.2.1;2.2.1 The Definition of an OI Queue;112
5.2.2;2.2.2 The Implications of the OI Conditions;112
5.2.3;2.2.3 The Stationary Distribution;113
5.2.4;2.2.4 Models Covered by the OI Class;116
5.2.4.1;2.2.4.1 BCMP Models in the OI Class;116
5.2.4.2;2.2.4.2 The MSCCC and MSHCC Queues;117
5.3;2.3 Numerical Techniques for the OI Queue;119
5.3.1;2.3.1 Aggregating the State Space;119
5.3.2;2.3.2 The Performance Measures: the MSCCC Queue;120
5.3.2.1;2.3.2.1 InvariantMeasures over Special Sets;120
5.3.2.2;2.3.2.2 The Expected Queue Length;123
5.4;2.4 The OI Loss Queue;126
5.4.1;2.4.1 The Stationary Distribution;127
5.4.2;2.4.2 The Performance Measures: the MSCCC Loss Queue;129
5.4.2.1;2.4.2.1 InvariantMeasures over Special Sets;129
5.4.2.2;2.4.2.2 The Expected Queue Length;132
5.4.3;2.4.3 OI Loss Networks;133
5.5;2.5 OI Applications;134
5.5.1;2.5.1 Multiported Memory;134
5.5.2;2.5.2 A Messaging Card;134
5.5.3;2.5.3 Multilayer Window Flow Control;135
5.5.4;2.5.4 Machine Scheduling Model;135
5.5.5;2.5.5 Blocked Calls Cleared;135
5.5.6;2.5.6 Blocked Calls Queued;136
5.5.7;2.5.7 Blocked Calls Queued with Source Rejection;137
5.5.8;2.5.8 Local and Long Distance Calls;137
5.5.9;2.5.9 Local and Transit Calls;138
5.5.10;2.5.10 Hierarchical Tree Networks;139
5.5.11;2.5.11 Local and External Networks;139
5.5.12;2.5.12 Transit Calls among Networks;140
5.6;2.6 An Algorithm to Compute the Performance Measures of the MSCCC;142
5.7;References;143
6;Chapter 3 Insensitivity in Stochastic Models;145
6.1;3.1 Introduction;145
6.2;3.2 The Erlang Loss System as a Symmetric Queue;150
6.3;3.3 The Erlang Loss System as a GSMP;153
6.4;3.4 Insensitive Queueing Networks;156
6.5;3.5 Non-Standard Insensitive Models;160
6.6;3.6 Conclusion;161
6.7;Acknowledgement;162
6.8;References;162
7;Chapter 4 Palm Calculus, Reallocatable GSMP and Insensitivity Structure;165
7.1;4.1 Introduction;165
7.2;4.2 Shift operator group;166
7.3;4.3 Point processes;170
7.4;4.4 Palm distribution;173
7.5;4.5 Inversion formula;177
7.6;4.6 Detailed Palm distribution;181
7.7;4.7 Time and event averages;183
7.8;4.8 Rate conservation law;187
7.9;4.9 PASTA: a proof by the rate conservation law;191
7.10;4.10 Relationship among the queueing length processes observed at different points in time;194
7.11;4.11 An extension of the rate conservation law;197
7.12;4.12 Piece-wise deterministic Markov process (PDMP);200
7.13;4.13 Exponentially distributed lifetime;206
7.14;4.14 GSMP and RGSMP;209
7.15;4.15 Exponential and non-exponential clocks in RGSMP;213
7.16;4.16 Product form decomposability;217
7.17;4.17 Applications to queues and their networks;225
7.18;4.18 Further insensitivity structure in RGSMP;229
7.19;4.19 Bibliographic notes;237
7.20;References;238
8;Chapter 5 Networks with Customers, Signals, and Product Form Solutions;240
8.1;5.1 Introduction;240
8.2;5.2 Quasi-Reversibility of Queues;242
8.3;5.3 Quasi-Reversibility of Queues with Triggered Departures;247
8.4;5.4 Networks of Quasi-Reversible Nodes;249
8.5;5.5 Networks with Signals and Triggered Movements;258
8.6;5.6 Networks with Positive and Negative Signals;264
8.6.1;5.6.1 Single Class of Positive and Negative Signals;265
8.6.2;5.6.2 Multiple Classes of Positive and Negative Signals;269
8.7;5.7 Necessary and Sufficient Conditions for Product Form;273
8.8;5.8 Quasi-Reversibility Revisited;279
8.9;5.9 Networks with Random Customer Shuffling;283
8.10;5.10 Conclusion;287
8.11;References;288
9;Chapter 6 Discrete Time Networks with Product Form Steady States;291
9.1;6.1 Introduction;291
9.2;6.2 Bernoulli Servers with Different Customer Types and state-dependent arrivals;293
9.3;6.3 Closed Cycles of Bernoulli Servers;297
9.3.1;6.3.1 Steady State Behaviour and Arrival Theorem;297
9.3.2;6.3.2 Delay Times for Customers in a Closed Cycle;301
9.3.3;6.3.3 Computational Algorithms for Closed Cycles of State Independent Bernoulli Servers;303
9.3.4;6.3.4 Large Cycles of State Dependent Bernoulli Servers;304
9.4;6.4 Open Tandems of Bernoulli Servers with State Dependent Arrivals;306
9.4.1;6.4.1 Steady State and Arrival Theorem;306
9.4.2;6.4.2 Delay Times for Customers in an Open Tandem;309
9.4.3;6.4.3 Open Tandems of Unreliable Bernoulli Servers;310
9.5;6.5 Networks with Doubly Stochastic and Geometrical Servers;311
9.5.1;6.5.1 Common Properties of Doubly Stochastic and Geometrical Server;312
9.5.2;6.5.2 The Doubly Stochastic Server;312
9.5.3;6.5.3 The Geometrical Server;317
9.5.4;6.5.4 Networks of Doubly Stochastic and Geometrical Nodes;318
9.6;6.6 Batch Service and Movements Networks;322
9.6.1;6.6.1 The General Network Model;322
9.6.2;6.6.2 Walrand’s S–Queues and Networks;326
9.6.3;6.6.3 Closed Networks of Unreliable S–Queues;327
9.6.4;6.6.4 Networks with Triggered Batch Movements;329
9.7;References;330
10;Chapter 7 Decomposition and Aggregation in Queueing Networks;335
10.1;7.1 Introduction;335
10.1.1;Decomposition;336
10.1.2;Aggregation;337
10.1.3;Examples and outline;339
10.2;7.2 Model;339
10.2.1;7.2.1 The nodes;339
10.2.2;7.2.2 Interaction between the nodes;342
10.2.3;7.2.3 The network;344
10.3;7.3 Decomposition;346
10.4;7.4 Aggregation;352
10.5;7.5 Examples;357
10.5.1;7.5.1 Quasi-reversible nodes linked via state-dependent routing;357
10.5.2;7.5.2 Biased local balance;359
10.5.3;7.5.3 A pull network;361
10.5.4;7.5.4 An assembly network;362
10.6;References;365
11;Chapter 8 Stochastic Comparison of Queueing Networks;367
11.1;8.1 Introduction;367
11.1.1;8.1.1 Jackson networks;371
11.1.2;8.1.2 Gordon-Newell networks;372
11.1.3;8.1.3 Ergodicity of classical networks;372
11.2;8.2 Stochastic monotonicity and related properties for classical networks;374
11.2.1;8.2.1 Stochastic orders and monotonicity;374
11.2.1.1;8.2.1.1 Discrete time;377
11.2.1.2;8.2.1.2 Continuous time;377
11.2.2;8.2.2 Stochastic monotonicity and networks;378
11.2.3;8.2.3 Bounds in transient state;379
11.2.4;8.2.4 Bounds in stationary state;379
11.2.5;8.2.5 Sojourn times in networks;381
11.2.5.1;8.2.5.1 Dependence properties for sojourn times;381
11.2.5.2;8.2.5.2 Sojourn times in closed networks;382
11.3;8.3 Properties of throughput in classical networks;383
11.3.1;8.3.1 Uniform conditional variability ordering, a relation between closed and open networks;383
11.3.2;8.3.2 Effect of enlarging service rates in closed networks;384
11.3.3;8.3.3 Majorization, arrangement and proportional service rates;385
11.3.4;8.3.4 Throughput and number of jobs;387
11.4;8.4 Routing and correlations;387
11.4.1;8.4.1 Correlation inequalities via generators;389
11.4.2;8.4.2 Doubly stochastic routing;395
11.4.3;8.4.3 Robin-Hood transforms;396
11.4.4;8.4.4 Dependence orderings and monotonicity;398
11.5;8.5 Jackson networks with breakdowns;403
11.5.1;8.5.1 Product formula;403
11.5.2;8.5.2 Bounds via dependence ordering for networks with breakdowns;405
11.5.2.1;8.5.2.1 Dependence ordering of Jackson networks with breakdowns;405
11.6;8.6 General networks;406
11.6.1;8.6.1 Dependence and variability in input;409
11.6.2;8.6.2 Comparison of workloads;409
11.6.2.1;8.6.2.1 Workload in parallel queues;410
11.6.2.2;8.6.2.2 Workload in batch queues;411
11.6.3;8.6.3 Throughput in general networks;412
11.7;References;413
12;Chapter 9 Error Bounds and Comparison Results: The Markov Reward Approach For Queueing Networks;418
12.1;A: General results;419
12.1.1;9.1 Motivation;419
12.1.1.1;9.1.1 A first example;419
12.1.1.1.1;9.1.1.1 Applications and solvability;419
12.1.1.1.2;9.1.1.2 Instructive breakdown example;420
12.1.1.1.3;9.1.1.3 Two questions;422
12.1.1.2;9.1.2 Two more examples;423
12.1.1.2.1;9.1.2.1 Finite Tandem Queues;423
12.1.1.2.2;9.1.2.2 Finite Jackson Networks;424
12.1.1.3;9.1.3 Objectives;426
12.1.1.4;9.1.4 Approach;426
12.1.1.5;9.1.5 Outline;427
12.1.2;9.2 Stochastic Comparison.;428
12.1.2.1;9.2.1 Preliminaries;428
12.1.2.2;9.2.2 Stochastic comparison;429
12.1.2.3;9.2.3 Stochastic comparison failure;432
12.1.3;9.3 Markov reward approach;434
12.1.3.1;9.3.1 Preliminaries;434
12.1.3.2;9.3.2 Comparison Result;435
12.1.3.3;9.3.3 Error bound Result;437
12.1.3.4;9.3.4 Truncation Error Bound;441
12.1.3.5;9.3.5 Comparison of MRA and SC;442
12.2;B: Applications;446
12.2.1;9.4 Application 1: Instructive Breakdown Example;446
12.2.1.1;9.4.1 Analytic bounds for the bias-terms;446
12.2.1.2;9.4.2 Comparison Result;450
12.2.1.3;9.4.3 Error Bounds;452
12.2.2;9.5 Application 2: Finite Tandem Queue;454
12.2.2.1;9.5.1 Problem Motivation;454
12.2.2.2;9.5.2 Comparison Result (Bounds);456
12.2.2.3;9.5.3 Technical verification of Bias-Terms;457
12.2.3;9.6 Application 3: Truncation of Finite Jackson Network;461
12.2.3.1;9.6.1 Description and motivation.;462
12.2.3.2;9.6.2 Truncation;463
12.2.3.3;9.6.3 Analytic Error bound;468
12.2.3.4;9.6.4 Application: Cellular Mobile Network Application;471
12.2.4;9.7 Evaluation;472
12.2.4.1;9.7.1 Extensions;473
12.2.4.2;9.7.2 Further Research;474
12.2.4.3;9.7.3 Other applications.;475
12.3;Acknowledgements;477
12.4;References;477
13;Chapter 10 Stability of Join-the-Shortest-Queue networks: Analysis by Fluid Limits;481
13.1;10.1 Join-the-shortest-queue networks;481
13.2;10.2 The network process and the fluid model;484
13.3;10.3 JSQ networks with two stations;489
13.4;10.4 Two examples with three stations;494
13.5;10.5 JSQ networks with homogeneous feedback;502
13.6;10.6 Further study;506
13.7;References;506
14;Chapter 11 Methods in Diffusion Approximation for Multi-Server Systems: Sandwich, Uniform Attraction and State-Space Collapse;508
14.1;11.1 Introduction;508
14.2;11.2 Preliminaries;511
14.3;11.3 Multi-Server Queue: Sandwich Method;513
14.4;11.4 A Multi-Class Queue under FIFO Service Discipline: Uniform Attraction and State-Space Collapse;517
14.4.1;11.4.1 Fluid Approximation and Uniform Attraction;519
14.4.2;11.4.2 Diffusion Approximation;522
14.4.2.1;11.4.2.1 From Uniform Attraction to State-Space Collapse;524
14.5;11.5 Multi-Channel Queues under JSQ Routing Control;528
14.5.1;11.5.1 Fluid Approximation and Uniform Attraction;530
14.5.2;11.5.2 Diffusion Approximation;533
14.5.2.1;11.5.2.1 Complementarity and State-Space Collapse;536
14.6;11.6 Notes;537
14.7;11.7 Appendix;538
14.7.1;11.7.1 Proof of Lemma 11.5.2;538
14.7.2;11.7.2 Proof of Proposition 11.5.3;540
14.7.3;11.7.3 Proof of Lemma 11.5.6;542
14.8;References;548
15;Chapter 12 Queueing Networks with Gaussian Inputs;550
15.1;12.1 Introduction;550
15.2;12.2 Preliminaries on Gaussian processes;552
15.2.1;12.2.1 Gaussian sources;552
15.2.2;12.2.2 Classifications;553
15.2.3;12.2.3 Schilder’s theorem;555
15.3;12.3 Single queues;558
15.3.1;12.3.1 Steady-state queue length;558
15.3.2;12.3.2 Logarithmic asymptotics;559
15.3.3;12.3.3 The shape of the loss curve;560
15.3.4;12.3.4 The buffer-bandwidth curve is convex;564
15.4;12.4 Tandem networks;566
15.4.1;12.4.1 Alternative formulation;566
15.4.2;12.4.2 Lower bound;569
15.4.3;12.4.3 Tightness; two regimes;572
15.4.4;12.4.4 Approximation;573
15.5;12.5 Priority queues;574
15.5.1;12.5.1 Lower bound;575
15.5.2;12.5.2 Tightness; two regimes;576
15.5.3;12.5.3 Approximation;577
15.6;12.6 Concluding remarks;578
15.7;References;578
16;Chapter 13 Mean Values Techniques;580
16.1;13.1 Introduction;580
16.2;13.2 PASTA property and Little’s law;581
16.3;13.3 MVA for single-station systems;582
16.3.1;13.3.1 M|M|1;582
16.3.2;13.3.2 M|G|1;583
16.3.3;13.3.3 M|G|1 with priorities;583
16.3.4;13.3.4 M|G|1 with least attained service;584
16.3.5;13.3.5 Server vacations;586
16.3.6;13.3.6 M|M|c;586
16.3.7;13.3.7 M|M|c with priorities;587
16.3.8;13.3.8 Retrials;588
16.3.9;13.3.9 Polling;588
16.4;13.4 AMVA for single-station systems;590
16.4.1;13.4.1 M|G|c;590
16.4.2;13.4.2 M|G|c with priorities;591
16.5;13.5 ASTA property in PF networks;591
16.5.1;13.5.1 Open single-class PF networks;591
16.5.2;13.5.2 Open multi-class PF networks;592
16.5.3;13.5.3 Closed multi-class PF networks;593
16.6;13.6 MVA for open PF networks;595
16.7;13.7 MVA for closed single-class PF networks;595
16.7.1;Single class, single servers;595
16.7.2;Single class, multi servers;596
16.7.3;Single class, queue-dependent servers;597
16.8;13.8 MVA for closed multi-class PF networks;598
16.9;13.9 AMVA for open networks;599
16.10;13.10 AMVA for closed single-server networks;599
16.10.1;13.10.1 Class-dependent general service times;600
16.10.2;13.10.2 Priorities;601
16.10.3;13.10.3 Multiple visits to a station;601
16.11;13.11 AMVA for closed multi-server networks;602
16.12;13.12 The Schweitzer-Bard approximation;602
16.13;Acknowledgement;604
16.14;References;604
17;Chapter 14 Response Time Distributions in Networks of Queues;606
17.1;14.1 Introduction;606
17.2;14.2 Closed Markovian networks;608
17.2.1;14.2.1 Tagged customer approach;609
17.2.2;14.2.2 Example: Central server model;609
17.3;14.3 Open Markovian networks of M/M/c/b = 8 queues;613
17.3.1;14.3.1 Response time blocks;614
17.3.1.1;14.3.1.1 M/M/1;614
17.3.1.2;14.3.1.2 M/M/8;614
17.3.1.3;14.3.1.3 M/M/c;615
17.3.1.4;14.3.1.4 M/M/c/b;616
17.3.1.5;14.3.1.5 M/M/1/b;617
17.3.2;14.3.2 Building the Markov chain from a queuing network;617
17.3.3;14.3.3 Examples;620
17.3.3.1;14.3.3.1 Computer system;620
17.3.3.2;14.3.3.2 Distributed system;623
17.3.3.3;14.3.3.3 Distribution of the response time sample mean;626
17.4;14.4 Open Markovian networks of queues with general PH service time distributions;630
17.4.1;14.4.1 Building blocks with general PH service time distributions;630
17.4.2;14.4.2 Building the Markov chain;631
17.4.3;14.4.3 Example: CPU and disk queuing system;633
17.5;14.5 Non-Markovian networks;634
17.5.1;14.5.1 Approximating non-PH distributions;635
17.5.1.1;14.5.1.1 The response time distribution at an M/G/1 priority queue;635
17.5.1.2;14.5.1.2 The CTMC approach;638
17.5.1.3;14.5.1.3 Moment matching;638
17.5.1.4;14.5.1.4 Function fitting of the LST;640
17.5.1.5;14.5.1.5 Example: Transaction processing system;641
17.5.2;14.5.2 Modeling response time distributions using semi-Markov processes;643
17.5.2.1;14.5.2.1 Deriving parameters of arrival processes;646
17.5.2.2;14.5.2.2 Response time distribution at a PH/G/1 queue;648
17.5.2.3;14.5.2.3 Transient solution of a semi-Markov process;649
17.5.2.4;14.5.2.4 Building the semi-Markov chain from the queuing network;651
17.5.2.5;14.5.2.5 Example: Distributed system;652
17.5.2.6;14.5.2.6 End-to-end delay in a virtual circuit;653
17.6;14.6 Conclusions;656
17.7;References;658
18;Chapter 15 Decomposition-Based Queueing Network Analysis with FiFiQueues;661
18.1;15.1 Introduction;661
18.2;15.2 The decomposition approach;663
18.2.1;Sketch of the idea;663
18.2.2;Open questions;664
18.2.3;The analysis of complex networks;664
18.2.4;The analysis of individual stations;665
18.3;15.3 Whitt’s Queueing Network Analyzer;666
18.3.1;15.3.1 Model class;667
18.3.2;15.3.2 Traffic descriptors;667
18.3.3;15.3.3 Superposition of traffic streams;667
18.3.4;15.3.4 Splitting traffic streams;668
18.3.5;15.3.5 Servicing jobs;669
18.3.6;15.3.6 Node performance;669
18.3.7;15.3.7 Network-wide performance;670
18.3.8;15.3.8 Complexity;670
18.4;15.4 FiFiQueues;671
18.4.1;15.4.1 Model class;671
18.4.2;15.4.2 Traffic descriptor;672
18.4.3;15.4.3 Superposition of traffic streams;672
18.4.4;15.4.4 Splitting traffic streams;673
18.4.5;15.4.5 Servicing jobs;673
18.4.5.1;15.4.5.1 Phase-type representation of the arrival processes;673
18.4.5.2;15.4.5.2 Analysis of PH|PH|1|K queues;674
18.4.5.3;15.4.5.3 Analysis of PH|PH|1 queues;676
18.4.6;15.4.6 Node performance;677
18.4.6.1;15.4.6.1 Node performance of PH|PH|1|K queues;677
18.4.6.2;15.4.6.2 Node performance of PH|PH|1 queues;678
18.4.7;15.4.7 Network-wide performance;678
18.4.8;15.4.8 Complexity;679
18.4.8.1;15.4.8.1 Traffic computation;679
18.4.8.2;15.4.8.2 Node performance and network performance computation;680
18.4.9;15.4.9 The FiFiQueues network designer;680
18.4.9.1;15.4.9.1 The graphical user interface;680
18.4.9.2;15.4.9.2 The numerical analysis module;682
18.4.9.3;15.4.9.3 The simulation module;682
18.5;15.5 Performance of FiFiQueues;682
18.5.1;15.5.1 Evaluation of FiFiQueues;683
18.5.1.1;15.5.1.1 Single queues;683
18.5.1.2;15.5.1.2 Queueing networks with feedback;683
18.5.2;15.5.2 Performance evaluation of a web server;686
18.5.2.1;15.5.2.1 Description of the test system;687
18.5.2.2;15.5.2.2 Web server without disk access;687
18.5.2.3;15.5.2.3 Web server with disk access;688
18.5.2.4;15.5.2.4 Group of servers;690
18.5.3;15.5.3 Summary;694
18.6;15.6 Summary and conclusions;694
18.7;15.7 Appendix: Jackson queueing networks;695
18.7.1;15.7.1 Model class;695
18.7.2;15.7.2 Traffic descriptor;695
18.7.3;15.7.3 Superposition of traffic streams;696
18.7.4;15.7.4 Splitting traffic streams;696
18.7.5;15.7.5 Servicing jobs;696
18.7.6;15.7.6 Node performance;696
18.7.7;15.7.7 Network-wide performance;697
18.7.8;15.7.8 Complexity;697
18.8;15.8 Appendix: MAPs, PH-distributions and QBDs;698
18.8.1;15.8.1 Markovian Arrival Processes (MAPs);699
18.8.1.1;15.8.1.1 Definition and notation;699
18.8.1.2;15.8.1.2 Characteristics;699
18.8.1.3;15.8.1.3 Superposition and Markovian splitting;700
18.8.1.4;15.8.1.4 Markov-Modulated Poisson Processes (MMPPs);701
18.8.2;15.8.2 Phase-type (PH) renewal processes;701
18.8.2.1;15.8.2.1 Definition and notation;701
18.8.2.2;15.8.2.2 Inter-event time characteristics;701
18.8.2.3;15.8.2.3 Superposition and Markovian splitting;702
18.8.3;15.8.3 Infinite QBDs;702
18.8.3.1;15.8.3.1 Definition;702
18.8.3.2;15.8.3.2 Steady-state solution;703
18.8.3.3;15.8.3.3 Matrix-geometric solution methods;704
18.8.3.4;15.8.3.4 Transform methods;704
18.8.4;15.8.4 Finite QBDs;704
18.8.4.1;15.8.4.1 Definition;704
18.8.4.2;15.8.4.2 Steady-state solution;705
18.9;15.9 Appendix: Existence of the fixed point;706
18.9.1;15.9.1 Notation and Brouwer’s theorem;706
18.9.2;15.9.2 Properties of D;706
18.9.3;15.9.3 Continuity of H;707
18.9.4;15.9.4 Continuity for c²a= 1;708
18.9.4.1;15.9.4.1 Case c²a= 1;708
18.9.4.2;15.9.4.2 Case c²a\1;709
18.9.4.3;15.9.4.3 Case c²a / 1;710
18.9.5;15.9.5 Continuity for c²a= 1/m, m {2, . . . ,10};711
18.10;References;715
19;Chapter 16 Loss Networks;718
19.1;16.1 Introduction;718
19.2;16.2 Uncontrolled loss networks: stationary behaviour;722
19.2.1;16.2.1 The stationary distribution;722
19.2.2;16.2.2 The single resource case;723
19.2.3;16.2.3 The Kaufman-Dziong-Roberts (KDR) recursion;724
19.2.4;16.2.4 Approximations for large networks;725
19.2.4.1;A simple approximation;725
19.2.4.2;A refined approximation;727
19.3;16.3 Controlled loss networks: stationary behaviour;728
19.3.1;16.3.1 Single resource networks;728
19.3.2;16.3.2 Multiple resource models;730
19.4;16.4 Dynamical behaviour and stability;732
19.4.1;16.4.1 Fluid limits for large capacity networks;732
19.4.2;16.4.2 Single resource networks;734
19.4.3;16.4.3 Multi-resource networks: the uncontrolled case;735
19.4.4;16.4.4 Multi-resource networks: the general case;736
19.4.5;16.4.5 The diverse routing limit;740
19.5;16.5 Further developments and open questions;741
19.6;References;743
20;Chapter 17 A Queueing Analysis of Data Networks;746
20.1;17.1 Introduction;746
20.2;17.2 Capacity region;747
20.2.1;Wireline networks;748
20.2.2;Traffic splitting;749
20.2.3;Wireless networks;750
20.2.4;Ad-hoc networks;752
20.2.5;Flow rate limits;753
20.3;17.3 Traffic characteristics;754
20.3.1;Markovian setting;754
20.3.2;Flow size distribution;754
20.3.3;Session structure;754
20.4;17.4 Stability issues;755
20.4.1;Necessary condition;755
20.4.2;Sufficient condition;755
20.5;17.5 Flow throughput;756
20.5.1;Mean flow duration;756
20.5.2;Mean instantaneous rate;756
20.5.3;Other throughput metrics;757
20.6;17.6 Queueing analysis;757
20.6.1;A queueing network;757
20.6.2;Balance property;757
20.6.3;Stationary distribution;758
20.7;17.7 Resource allocation;759
20.7.1;Max-min fairness;759
20.7.2;Proportional fairness;760
20.7.3;Balanced fairness;760
20.8;17.8 Insensitivity results;762
20.8.1;Flow size distribution;762
20.8.2;Sessions;764
20.9;17.9 A single link;764
20.9.1;No flow rate limit;765
20.9.2;A common flow rate limit;765
20.9.3;Multiple rate limits;766
20.9.4;Probability of saturation;766
20.9.5;Flow throughput;767
20.10;17.10 Performance bounds;768
20.10.1;Flows with a single capacity constraint;769
20.10.2;Lower bound;770
20.10.3;Upper bound;770
20.11;17.11 Examples;773
20.11.1;Wireline networks;773
20.11.2;Traffic splitting;774
20.11.3;Wireless networks;775
20.11.4;Ad-hoc networks;777
20.11.5;Flow rate limits;777
20.12;17.12 Open issues;779
20.13;17.13 Bibliographical notes;779
20.14;Appendix;780
20.15;References;781
21;Chapter 18 Modeling a Hospital Queueing Network;783
21.1;18.1 Introduction;783
21.2;18.2 Problem Description;785
21.2.1;Re-entry of patients and stochastic routings;786
21.2.2;Service sessions for consultation and surgery;787
21.2.3;Capacity related issues;787
21.2.4;Modeling of absences, disturbances and interruptions;787
21.3;18.3 A hospital queueing system;787
21.3.1;18.3.1 Modeling arrival rate and natural service times;789
21.3.2;18.3.2 Variability from preemptive and nonpreemptive outages;793
21.3.2.1;18.3.2.1 Outages, classification and impact;794
21.3.2.2;18.3.2.2 Nonpreemptive outages;795
21.3.2.3;18.3.2.3 Preemptive outages;796
21.3.2.4;18.3.2.4 Combining preemptive and nonpreemptive outages;799
21.3.2.5;18.3.2.5 Including the time availability of workstations;800
21.3.2.6;18.3.2.6 Squared coefficient of variation of the aggregate arrival process;801
21.4;18.4 Applications;802
21.4.1;18.4.1 Numerical example;802
21.4.2;18.4.2 The impact of interrupts;804
21.4.3;18.4.3 The impact of pooling;805
21.4.4;18.4.4 Finding the optimal number of patients in a service session;807
21.5;18.5 Conclusion;812
21.6;References;812