Boucherie / Dijk Queueing Networks

A Fundamental Approach
1. Auflage 2010
ISBN: 978-1-4419-6472-4
Verlag: Springer US
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 154, 800 Seiten

Reihe: International Series in Operations Research & Management Science

This handbook aims to highlight fundamental, methodological and computational aspects of networks of queues to provide insights and to unify results that can be applied in a more general manner.  The handbook is organized into five parts:

Part 1 considers exact analytical results such as of product form type. Topics include characterization of product forms by physical balance concepts and simple traffic flow equations, classes of service and queue disciplines that allow a product form, a unified description of product forms for discrete time queueing networks, insights for insensitivity, and aggregation and decomposition results that allow sub networks to be aggregated into single nodes to reduce computational burden.

Part 2 looks at monotonicity and comparison results such as for computational simplification by either of two approaches: stochastic monotonicity and ordering results based on the ordering of the process generators, and comparison results and explicit error bounds based on an underlying Markov reward structure leading to ordering of expectations of performance measures.

Part 3 presents diffusion and fluid results. It specifically looks at  the fluid regime and the diffusion regime. Both of these are illustrated through fluid limits for the analysis of system stability, diffusion approximations for multi-server systems, and a system fed by Gaussian traffic.

Part 4 illustrates computational and approximate results through the classical MVA (mean value analysis) and QNA (queueing network analyzer) for computing mean and variance of performance measures such as queue lengths and sojourn times; numerical approximation of response time distributions; and approximate decomposition results for large open queueing networks.

Part 5 enlightens selected applications as loss networks originating from circuit switched telecommunications applications, capacity sharing originating from packet switching in data networks, and a hospital application that is of growing present day interest.

The book shows that the intertwined progress of theory and practice  will remain to be most intriguing and will continue to be the basis of further developments in queueing networks.

Autoren/Hrsg.

Boucherie, Richard J.

Dijk, Nico M. van

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