Blick ins Buch

Queueing Networks (eBook)

A Fundamental Approach

Richard J. Boucherie, Nico M. van Dijk (Herausgeber)

eBook Download: PDF

2010 | 2011
XXIV, 800 Seiten
Springer US (Verlag)
978-1-4419-6472-4 (ISBN)

Lese- und Medienproben

Ebook-Leseprobe (PDF)

<body>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.</body>

<body>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 theanalysis 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.</body>

Preface 6
Part 1. Exact analytical results, chapters 1–7 7
Part 2. Monotonicity and comparison results, chapters 8–9 7
Part 3. Diffusion and fluid results, chapters 10–12 8
Part 4. Computational and approximate results, chapters 13–15 8
Part 5. Selected applications, chapters 16–18 9
Acknowledgments 9
Contents 10
List of Contributors 22
Chapter 1 On Practical Product Form Characterizations 26
A: Product Forms: Single Station Hierarchy 27
1.1 Introduction 27
1.2 Product Forms: Three Balances 29
1.2.1 Station Balance: B-D or Erlang-Engset systems 29
1.2.2 Class balance: Coordinate convex property (CCP) 31
1.2.2.1 Two class coordinate convex case 31
1.2.2.2 Class Balance and Product Form 35
1.2.2.3 More examples 37
1.2.3 Job Local Balance: Necessity 40
1.2.3.1 Introduction: single server system 40
1.2.3.2 Instructive FCFS case 41
1.2.3.3 LCFS-pre case 43
1.2.4 LCFS-pre case: Nonexponential 44
1.2.5 Symmetric Disciplines and Job-Local-balance (JLB) 47
1.3 Invariant Disciplines and JLB 50
1.3.1 Invariance Condition 50
1.3.2 Service invariant examples 53
1.3.3 A generalized symmetric insensitivity result 57
1.4 An application, literature discussion and hierarchy review 60
1.4.1 An M|G|c|c+m application 60
1.4.2 Literature discussion 62
1.4.3 A hierarchy review 64
B: Product Forms: Tandem and Cluster Structures 66
1.5 Tandem Queues 66
1.5.1 Introduction 66
1.5.2 Product Form Tandem Queues 70
1.5.3 Service examples 74
1.5.4 Blocking examples 76
1.5.5 Mixed examples 79
1.6 Jacksonian clusters 81
1.6.1 A Jackson cluster 81
1.6.2 A restricted Jackson cluster 83
1.6.3 A conservative product form protocol 85
1.7 Product form bounds for networks of restricted clusters 87
1.7.1 Instructive tandem extension 88
1.7.2 A Jackson Tandem 91
1.7.3 A nested case 93
1.7.4 Further illustrative examples 94
1.7.4.1 A ClusterWith Parallel Stations 95
1.7.4.2 An Overflow Example 96
1.7.4.3 A breakdownModel 96
1.7.5 An Optimal Design Application 98
1.8 A hospital application 98
1.8.1 Motivation 98
1.8.2 Model formulation 99
1.8.3 Bounds and application 101
1.9 Evaluation 102
1.9.1 Literature 102
1.9.2 Review Part B 104
1.9.3 Some remaining questions 105
Acknowledgements 105
References 106
Chapter 2 Order Independent Queues 109
2.1 Introduction 109
2.2 The OI Queue 111
2.2.1 The Definition of an OI Queue 112
2.2.2 The Implications of the OI Conditions 112
2.2.3 The Stationary Distribution 113
2.2.4 Models Covered by the OI Class 116
2.2.4.1 BCMP Models in the OI Class 116
2.2.4.2 The MSCCC and MSHCC Queues 117
2.3 Numerical Techniques for the OI Queue 119
2.3.1 Aggregating the State Space 119
2.3.2 The Performance Measures: the MSCCC Queue 120
2.3.2.1 InvariantMeasures over Special Sets 120
2.3.2.2 The Expected Queue Length 123
2.4 The OI Loss Queue 126
2.4.1 The Stationary Distribution 127
2.4.2 The Performance Measures: the MSCCC Loss Queue 129
2.4.2.1 InvariantMeasures over Special Sets 129
2.4.2.2 The Expected Queue Length 132
2.4.3 OI Loss Networks 133
2.5 OI Applications 134
2.5.1 Multiported Memory 134
2.5.2 A Messaging Card 134
2.5.3 Multilayer Window Flow Control 135
2.5.4 Machine Scheduling Model 135
2.5.5 Blocked Calls Cleared 135
2.5.6 Blocked Calls Queued 136
2.5.7 Blocked Calls Queued with Source Rejection 137
2.5.8 Local and Long Distance Calls 137
2.5.9 Local and Transit Calls 138
2.5.10 Hierarchical Tree Networks 139
2.5.11 Local and External Networks 139
2.5.12 Transit Calls among Networks 140
2.6 An Algorithm to Compute the Performance Measures of the MSCCC 142
References 143
Chapter 3 Insensitivity in Stochastic Models 145
3.1 Introduction 145
3.2 The Erlang Loss System as a Symmetric Queue 150
3.3 The Erlang Loss System as a GSMP 153
3.4 Insensitive Queueing Networks 156
3.5 Non-Standard Insensitive Models 160
3.6 Conclusion 161
Acknowledgement 162
References 162
Chapter 4 Palm Calculus, Reallocatable GSMP and Insensitivity Structure 165
4.1 Introduction 165
4.2 Shift operator group 166
4.3 Point processes 170
4.4 Palm distribution 173
4.5 Inversion formula 177
4.6 Detailed Palm distribution 181
4.7 Time and event averages 183
4.8 Rate conservation law 187
4.9 PASTA: a proof by the rate conservation law 191
4.10 Relationship among the queueing length processes observed at different points in time 194
4.11 An extension of the rate conservation law 197
4.12 Piece-wise deterministic Markov process (PDMP) 200
4.13 Exponentially distributed lifetime 206
4.14 GSMP and RGSMP 209
4.15 Exponential and non-exponential clocks in RGSMP 213
4.16 Product form decomposability 217
4.17 Applications to queues and their networks 225
4.18 Further insensitivity structure in RGSMP 229
4.19 Bibliographic notes 237
References 238
Chapter 5 Networks with Customers, Signals, and Product Form Solutions 240
5.1 Introduction 240
5.2 Quasi-Reversibility of Queues 242
5.3 Quasi-Reversibility of Queues with Triggered Departures 247
5.4 Networks of Quasi-Reversible Nodes 249
5.5 Networks with Signals and Triggered Movements 258
5.6 Networks with Positive and Negative Signals 264
5.6.1 Single Class of Positive and Negative Signals 265
5.6.2 Multiple Classes of Positive and Negative Signals 269
5.7 Necessary and Sufficient Conditions for Product Form 273
5.8 Quasi-Reversibility Revisited 279
5.9 Networks with Random Customer Shuffling 283
5.10 Conclusion 287
References 288
Chapter 6 Discrete Time Networks with Product Form Steady States 291
6.1 Introduction 291
6.2 Bernoulli Servers with Different Customer Types and state-dependent arrivals 293
6.3 Closed Cycles of Bernoulli Servers 297
6.3.1 Steady State Behaviour and Arrival Theorem 297
6.3.2 Delay Times for Customers in a Closed Cycle 301
6.3.3 Computational Algorithms for Closed Cycles of State Independent Bernoulli Servers 303
6.3.4 Large Cycles of State Dependent Bernoulli Servers 304
6.4 Open Tandems of Bernoulli Servers with State Dependent Arrivals 306
6.4.1 Steady State and Arrival Theorem 306
6.4.2 Delay Times for Customers in an Open Tandem 309
6.4.3 Open Tandems of Unreliable Bernoulli Servers 310
6.5 Networks with Doubly Stochastic and Geometrical Servers 311
6.5.1 Common Properties of Doubly Stochastic and Geometrical Server 312
6.5.2 The Doubly Stochastic Server 312
6.5.3 The Geometrical Server 317
6.5.4 Networks of Doubly Stochastic and Geometrical Nodes 318
6.6 Batch Service and Movements Networks 322
6.6.1 The General Network Model 322
6.6.2 Walrand’s S–Queues and Networks 326
6.6.3 Closed Networks of Unreliable S–Queues 327
6.6.4 Networks with Triggered Batch Movements 329
References 330
Chapter 7 Decomposition and Aggregation in Queueing Networks 335
7.1 Introduction 335
Decomposition 336
Aggregation 337
Examples and outline 339
7.2 Model 339
7.2.1 The nodes 339
7.2.2 Interaction between the nodes 342
7.2.3 The network 344
7.3 Decomposition 346
7.4 Aggregation 352
7.5 Examples 357
7.5.1 Quasi-reversible nodes linked via state-dependent routing 357
7.5.2 Biased local balance 359
7.5.3 A pull network 361
7.5.4 An assembly network 362
References 365
Chapter 8 Stochastic Comparison of Queueing Networks 367
8.1 Introduction 367
8.1.1 Jackson networks 371
8.1.2 Gordon-Newell networks 372
8.1.3 Ergodicity of classical networks 372
8.2 Stochastic monotonicity and related properties for classical networks 374
8.2.1 Stochastic orders and monotonicity 374
8.2.1.1 Discrete time 377
8.2.1.2 Continuous time 377
8.2.2 Stochastic monotonicity and networks 378
8.2.3 Bounds in transient state 379
8.2.4 Bounds in stationary state 379
8.2.5 Sojourn times in networks 381
8.2.5.1 Dependence properties for sojourn times 381
8.2.5.2 Sojourn times in closed networks 382
8.3 Properties of throughput in classical networks 383
8.3.1 Uniform conditional variability ordering, a relation between closed and open networks 383
8.3.2 Effect of enlarging service rates in closed networks 384
8.3.3 Majorization, arrangement and proportional service rates 385
8.3.4 Throughput and number of jobs 387
8.4 Routing and correlations 387
8.4.1 Correlation inequalities via generators 389
8.4.2 Doubly stochastic routing 395
8.4.3 Robin-Hood transforms 396
8.4.4 Dependence orderings and monotonicity 398
8.5 Jackson networks with breakdowns 403
8.5.1 Product formula 403
8.5.2 Bounds via dependence ordering for networks with breakdowns 405
8.5.2.1 Dependence ordering of Jackson networks with breakdowns 405
8.6 General networks 406
8.6.1 Dependence and variability in input 409
8.6.2 Comparison of workloads 409
8.6.2.1 Workload in parallel queues 410
8.6.2.2 Workload in batch queues 411
8.6.3 Throughput in general networks 412
References 413
Chapter 9 Error Bounds and Comparison Results: The Markov Reward Approach For Queueing Networks 418
A: General results 419
9.1 Motivation 419
9.1.1 A first example 419
9.1.1.1 Applications and solvability 419
9.1.1.2 Instructive breakdown example 420
9.1.1.3 Two questions 422
9.1.2 Two more examples 423
9.1.2.1 Finite Tandem Queues 423
9.1.2.2 Finite Jackson Networks 424
9.1.3 Objectives 426
9.1.4 Approach 426
9.1.5 Outline 427
9.2 Stochastic Comparison. 428
9.2.1 Preliminaries 428
9.2.2 Stochastic comparison 429
9.2.3 Stochastic comparison failure 432
9.3 Markov reward approach 434
9.3.1 Preliminaries 434
9.3.2 Comparison Result 435
9.3.3 Error bound Result 437
9.3.4 Truncation Error Bound 441
9.3.5 Comparison of MRA and SC 442
B: Applications 446
9.4 Application 1: Instructive Breakdown Example 446
9.4.1 Analytic bounds for the bias-terms 446
9.4.2 Comparison Result 450
9.4.3 Error Bounds 452
9.5 Application 2: Finite Tandem Queue 454
9.5.1 Problem Motivation 454
9.5.2 Comparison Result (Bounds) 456
9.5.3 Technical verification of Bias-Terms 457
9.6 Application 3: Truncation of Finite Jackson Network 461
9.6.1 Description and motivation. 462
9.6.2 Truncation 463
9.6.3 Analytic Error bound 468
9.6.4 Application: Cellular Mobile Network Application 471
9.7 Evaluation 472
9.7.1 Extensions 473
9.7.2 Further Research 474
9.7.3 Other applications. 475
Acknowledgements 477
References 477
Chapter 10 Stability of Join-the-Shortest-Queue networks: Analysis by Fluid Limits 481
10.1 Join-the-shortest-queue networks 481
10.2 The network process and the fluid model 484
10.3 JSQ networks with two stations 489
10.4 Two examples with three stations 494
10.5 JSQ networks with homogeneous feedback 502
10.6 Further study 506
References 506
Chapter 11 Methods in Diffusion Approximation for Multi-Server Systems: Sandwich, Uniform Attraction and State-Space Collapse 508
11.1 Introduction 508
11.2 Preliminaries 511
11.3 Multi-Server Queue: Sandwich Method 513
11.4 A Multi-Class Queue under FIFO Service Discipline: Uniform Attraction and State-Space Collapse 517
11.4.1 Fluid Approximation and Uniform Attraction 519
11.4.2 Diffusion Approximation 522
11.4.2.1 From Uniform Attraction to State-Space Collapse 524
11.5 Multi-Channel Queues under JSQ Routing Control 528
11.5.1 Fluid Approximation and Uniform Attraction 530
11.5.2 Diffusion Approximation 533
11.5.2.1 Complementarity and State-Space Collapse 536
11.6 Notes 537
11.7 Appendix 538
11.7.1 Proof of Lemma 11.5.2 538
11.7.2 Proof of Proposition 11.5.3 540
11.7.3 Proof of Lemma 11.5.6 542
References 548
Chapter 12 Queueing Networks with Gaussian Inputs 550
12.1 Introduction 550
12.2 Preliminaries on Gaussian processes 552
12.2.1 Gaussian sources 552
12.2.2 Classifications 553
12.2.3 Schilder’s theorem 555
12.3 Single queues 558
12.3.1 Steady-state queue length 558
12.3.2 Logarithmic asymptotics 559
12.3.3 The shape of the loss curve 560
12.3.4 The buffer-bandwidth curve is convex 564
12.4 Tandem networks 566
12.4.1 Alternative formulation 566
12.4.2 Lower bound 569
12.4.3 Tightness two regimes
12.4.4 Approximation 573
12.5 Priority queues 574
12.5.1 Lower bound 575
12.5.2 Tightness two regimes
12.5.3 Approximation 577
12.6 Concluding remarks 578
References 578
Chapter 13 Mean Values Techniques 580
13.1 Introduction 580
13.2 PASTA property and Little’s law 581
13.3 MVA for single-station systems 582
13.3.1 M|M|1 582
13.3.2 M|G|1 583
13.3.3 M|G|1 with priorities 583
13.3.4 M|G|1 with least attained service 584
13.3.5 Server vacations 586
13.3.6 M|M|c 586
13.3.7 M|M|c with priorities 587
13.3.8 Retrials 588
13.3.9 Polling 588
13.4 AMVA for single-station systems 590
13.4.1 M|G|c 590
13.4.2 M|G|c with priorities 591
13.5 ASTA property in PF networks 591
13.5.1 Open single-class PF networks 591
13.5.2 Open multi-class PF networks 592
13.5.3 Closed multi-class PF networks 593
13.6 MVA for open PF networks 595
13.7 MVA for closed single-class PF networks 595
Single class, single servers 595
Single class, multi servers 596
Single class, queue-dependent servers 597
13.8 MVA for closed multi-class PF networks 598
13.9 AMVA for open networks 599
13.10 AMVA for closed single-server networks 599
13.10.1 Class-dependent general service times 600
13.10.2 Priorities 601
13.10.3 Multiple visits to a station 601
13.11 AMVA for closed multi-server networks 602
13.12 The Schweitzer-Bard approximation 602
Acknowledgement 604
References 604
Chapter 14 Response Time Distributions in Networks of Queues 606
14.1 Introduction 606
14.2 Closed Markovian networks 608
14.2.1 Tagged customer approach 609
14.2.2 Example: Central server model 609
14.3 Open Markovian networks of M/M/c/b = 8 queues 613
14.3.1 Response time blocks 614
14.3.1.1 M/M/1 614
14.3.1.2 M/M/8 614
14.3.1.3 M/M/c 615
14.3.1.4 M/M/c/b 616
14.3.1.5 M/M/1/b 617
14.3.2 Building the Markov chain from a queuing network 617
14.3.3 Examples 620
14.3.3.1 Computer system 620
14.3.3.2 Distributed system 623
14.3.3.3 Distribution of the response time sample mean 626
14.4 Open Markovian networks of queues with general PH service time distributions 630
14.4.1 Building blocks with general PH service time distributions 630
14.4.2 Building the Markov chain 631
14.4.3 Example: CPU and disk queuing system 633
14.5 Non-Markovian networks 634
14.5.1 Approximating non-PH distributions 635
14.5.1.1 The response time distribution at an M/G/1 priority queue 635
14.5.1.2 The CTMC approach 638
14.5.1.3 Moment matching 638
14.5.1.4 Function fitting of the LST 640
14.5.1.5 Example: Transaction processing system 641
14.5.2 Modeling response time distributions using semi-Markov processes 643
14.5.2.1 Deriving parameters of arrival processes 646
14.5.2.2 Response time distribution at a PH/G/1 queue 648
14.5.2.3 Transient solution of a semi-Markov process 649
14.5.2.4 Building the semi-Markov chain from the queuing network 651
14.5.2.5 Example: Distributed system 652
14.5.2.6 End-to-end delay in a virtual circuit 653
14.6 Conclusions 656
References 658
Chapter 15 Decomposition-Based Queueing Network Analysis with FiFiQueues 661
15.1 Introduction 661
15.2 The decomposition approach 663
Sketch of the idea 663
Open questions 664
The analysis of complex networks 664
The analysis of individual stations 665
15.3 Whitt’s Queueing Network Analyzer 666
15.3.1 Model class 667
15.3.2 Traffic descriptors 667
15.3.3 Superposition of traffic streams 667
15.3.4 Splitting traffic streams 668
15.3.5 Servicing jobs 669
15.3.6 Node performance 669
15.3.7 Network-wide performance 670
15.3.8 Complexity 670
15.4 FiFiQueues 671
15.4.1 Model class 671
15.4.2 Traffic descriptor 672
15.4.3 Superposition of traffic streams 672
15.4.4 Splitting traffic streams 673
15.4.5 Servicing jobs 673
15.4.5.1 Phase-type representation of the arrival processes 673
15.4.5.2 Analysis of PH|PH|1|K queues 674
15.4.5.3 Analysis of PH|PH|1 queues 676
15.4.6 Node performance 677
15.4.6.1 Node performance of PH|PH|1|K queues 677
15.4.6.2 Node performance of PH|PH|1 queues 678
15.4.7 Network-wide performance 678
15.4.8 Complexity 679
15.4.8.1 Traffic computation 679
15.4.8.2 Node performance and network performance computation 680
15.4.9 The FiFiQueues network designer 680
15.4.9.1 The graphical user interface 680
15.4.9.2 The numerical analysis module 682
15.4.9.3 The simulation module 682
15.5 Performance of FiFiQueues 682
15.5.1 Evaluation of FiFiQueues 683
15.5.1.1 Single queues 683
15.5.1.2 Queueing networks with feedback 683
15.5.2 Performance evaluation of a web server 686
15.5.2.1 Description of the test system 687
15.5.2.2 Web server without disk access 687
15.5.2.3 Web server with disk access 688
15.5.2.4 Group of servers 690
15.5.3 Summary 694
15.6 Summary and conclusions 694
15.7 Appendix: Jackson queueing networks 695
15.7.1 Model class 695
15.7.2 Traffic descriptor 695
15.7.3 Superposition of traffic streams 696
15.7.4 Splitting traffic streams 696
15.7.5 Servicing jobs 696
15.7.6 Node performance 696
15.7.7 Network-wide performance 697
15.7.8 Complexity 697
15.8 Appendix: MAPs, PH-distributions and QBDs 698
15.8.1 Markovian Arrival Processes (MAPs) 699
15.8.1.1 Definition and notation 699
15.8.1.2 Characteristics 699
15.8.1.3 Superposition and Markovian splitting 700
15.8.1.4 Markov-Modulated Poisson Processes (MMPPs) 701
15.8.2 Phase-type (PH) renewal processes 701
15.8.2.1 Definition and notation 701
15.8.2.2 Inter-event time characteristics 701
15.8.2.3 Superposition and Markovian splitting 702
15.8.3 Infinite QBDs 702
15.8.3.1 Definition 702
15.8.3.2 Steady-state solution 703
15.8.3.3 Matrix-geometric solution methods 704
15.8.3.4 Transform methods 704
15.8.4 Finite QBDs 704
15.8.4.1 Definition 704
15.8.4.2 Steady-state solution 705
15.9 Appendix: Existence of the fixed point 706
15.9.1 Notation and Brouwer’s theorem 706
15.9.2 Properties of D 706
15.9.3 Continuity of H 707
15.9.4 Continuity for c²a= 1 708
15.9.4.1 Case c²a= 1 708
15.9.4.2 Case c²a/1 709
15.9.4.3 Case c²a / 1 710
15.9.5 Continuity for c²a= 1/m, m {2, . . . ,10} 711
References 715
Chapter 16 Loss Networks 718
16.1 Introduction 718
16.2 Uncontrolled loss networks: stationary behaviour 722
16.2.1 The stationary distribution 722
16.2.2 The single resource case 723
16.2.3 The Kaufman-Dziong-Roberts (KDR) recursion 724
16.2.4 Approximations for large networks 725
A simple approximation 725
A refined approximation 727
16.3 Controlled loss networks: stationary behaviour 728
16.3.1 Single resource networks 728
16.3.2 Multiple resource models 730
16.4 Dynamical behaviour and stability 732
16.4.1 Fluid limits for large capacity networks 732
16.4.2 Single resource networks 734
16.4.3 Multi-resource networks: the uncontrolled case 735
16.4.4 Multi-resource networks: the general case 736
16.4.5 The diverse routing limit 740
16.5 Further developments and open questions 741
References 743
Chapter 17 A Queueing Analysis of Data Networks 746
17.1 Introduction 746
17.2 Capacity region 747
Wireline networks 748
Traffic splitting 749
Wireless networks 750
Ad-hoc networks 752
Flow rate limits 753
17.3 Traffic characteristics 754
Markovian setting 754
Flow size distribution 754
Session structure 754
17.4 Stability issues 755
Necessary condition 755
Sufficient condition 755
17.5 Flow throughput 756
Mean flow duration 756
Mean instantaneous rate 756
Other throughput metrics 757
17.6 Queueing analysis 757
A queueing network 757
Balance property 757
Stationary distribution 758
17.7 Resource allocation 759
Max-min fairness 759
Proportional fairness 760
Balanced fairness 760
17.8 Insensitivity results 762
Flow size distribution 762
Sessions 764
17.9 A single link 764
No flow rate limit 765
A common flow rate limit 765
Multiple rate limits 766
Probability of saturation 766
Flow throughput 767
17.10 Performance bounds 768
Flows with a single capacity constraint 769
Lower bound 770
Upper bound 770
17.11 Examples 773
Wireline networks 773
Traffic splitting 774
Wireless networks 775
Ad-hoc networks 777
Flow rate limits 777
17.12 Open issues 779
17.13 Bibliographical notes 779
Appendix 780
References 781
Chapter 18 Modeling a Hospital Queueing Network 783
18.1 Introduction 783
18.2 Problem Description 785
Re-entry of patients and stochastic routings 786
Service sessions for consultation and surgery 787
Capacity related issues 787
Modeling of absences, disturbances and interruptions 787
18.3 A hospital queueing system 787
18.3.1 Modeling arrival rate and natural service times 789
18.3.2 Variability from preemptive and nonpreemptive outages 793
18.3.2.1 Outages, classification and impact 794
18.3.2.2 Nonpreemptive outages 795
18.3.2.3 Preemptive outages 796
18.3.2.4 Combining preemptive and nonpreemptive outages 799
18.3.2.5 Including the time availability of workstations 800
18.3.2.6 Squared coefficient of variation of the aggregate arrival process 801
18.4 Applications 802
18.4.1 Numerical example 802
18.4.2 The impact of interrupts 804
18.4.3 The impact of pooling 805
18.4.4 Finding the optimal number of patients in a service session 807
18.5 Conclusion 812
References 812

Erscheint lt. Verlag	25.11.2010
Reihe/Serie	International Series in Operations Research & Management Science
Reihe/Serie	International Series in Operations Research & Management Science
Zusatzinfo	XXIV, 800 p.
Verlagsort	New York
Sprache	englisch
Themenwelt	Mathematik / Informatik ► Informatik
	Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
	Mathematik / Informatik ► Mathematik ► Finanz- / Wirtschaftsmathematik
	Mathematik / Informatik ► Mathematik ► Statistik
	Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik
	Studium ► 1. Studienabschnitt (Vorklinik) ► Biochemie / Molekularbiologie
	Technik
	Wirtschaft ► Betriebswirtschaft / Management ► Planung / Organisation
ISBN-10	1-4419-6472-X / 144196472X
ISBN-13	978-1-4419-6472-4 / 9781441964724

Haben Sie eine Frage zum Produkt?

PDF (Wasserzeichen)
Größe: 7,4 MB

DRM: Digitales Wasserzeichen
Dieses eBook enthält ein digitales Wasserzeichen und ist damit für Sie personalisiert. Bei einer missbräuchlichen Weitergabe des eBooks an Dritte ist eine Rückverfolgung an die Quelle möglich.

Dateiformat: PDF (Portable Document Format)
Mit einem festen Seitenlayout eignet sich die PDF besonders für Fachbücher mit Spalten, Tabellen und Abbildungen. Eine PDF kann auf fast allen Geräten angezeigt werden, ist aber für kleine Displays (Smartphone, eReader) nur eingeschränkt geeignet.

Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen dafür einen PDF-Viewer - z.B. den Adobe Reader oder Adobe Digital Editions.
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen dafür einen PDF-Viewer - z.B. die kostenlose Adobe Digital Editions-App.

Zusätzliches Feature: Online Lesen
Dieses eBook können Sie zusätzlich zum Download auch online im Webbrowser lesen.

Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.