Performance analysis of communication systems : modeling with non-Markovian stochastic Petri nets / Reinhard German.

Format:

Book

Author/Creator:

German, Reinhard.

Series:

Wiley-Interscience series in systems and optimization

Language:

English

Subjects (All):

Computer networks--Evaluation.

Computer networks.

Numerical analysis.

Petri nets.

Stochastic processes.

Physical Description:

xvii, 438 pages : illustrations ; 24 cm.

Edition:

First edition.

Place of Publication:

Chichester ; New York : Wiley, [2000]

Summary:

The Mathematica routines used for implementing the algorithms are available for downloading on the following Wiley ftp site: ftp: //ftp.wiley.co.uk/pub/books/german

Contents:

I Modeling with Stochastic Petri Nets 1

1.1 Stochastic Petri Nets 5

1.2 Technical Approach 5

1.3 Application to Communication Systems 6

1.4 Related Work 7

2 Stochastic Petri Nets 9

2.1 Definition of Petri Nets 9

2.2 An Example: OCDR Connection Management 14

2.3 Petri Net Extensions 15

2.4 Definition of Stochastic Petri Nets 19

2.5 The Example Continued 24

3 Tool Support 29

3.1 A Brief Review of Tools 29

3.2 TimeNET 31

3.3 SPNica: A Prototype Tool 34

II Analytical Methodology 35

4.1 Firing Time Distributions 39

4.1.1 A Characterization of Distributions 39

4.1.2 Expolynomial Distributions 42

4.2 Stochastic Processes 43

4.3 Quantitative Measures 45

4.3.1 Firing Frequencies of Transitions 45

4.3.2 Reward-Based Measure Definitions 47

5 Markovian Stochastic Petri Nets 53

5.1 Discrete Time 53

5.1.1 Geometric Firing Time Distributions 53

5.1.2 Discrete-Time Markov Chains 55

5.1.3 Example: The Geo/Geo/1/K System 58

5.2 Continuous Time 61

5.2.1 Exponential Firing Time Distributions 61

5.2.2 Continuous-Time Markov Chains 63

5.2.3 Example: The M/M/1/K System 66

5.2.4 Uniformization 67

5.3 Relationship of Continuous and Discrete Time 72

5.3.1 First Moment Matching 72

5.3.2 Equidistant Embedding 72

5.3.3 Uniformized Markov Chain 73

5.3.4 Embedded Markov Chain 74

6 The Method of Supplementary Variables 77

6.1 Analysis of the M/G/1 System 78

6.1.2 Derivation of State Equations 80

6.1.3 Transform Domain Analysis 86

6.2 Analysis of the M/G/1/K System 90

6.2.1 Additional Definitions and Notation 90

6.2.2 Derivation of State Equations 91

6.2.3 Time-Domain Analysis 93

6.2.4 Example: Deterministic Service 95

6.2.5 Introduction of Vector and Matrix Notation 97

6.2.6 Example: The M/D/1/K System in Matrix Notation 102

6.3 Alternative Use of Supplementary Variables 104

7 General State Equations 109

7.1.1 Example: OCDR Connection Management 115

7.1.2 Example: The M/D/1/K System with Preemptions 118

7.2 Derivation of the State Equations 120

7.2.1 Example: OCDR Connection Management 123

7.2.2 Simplifications for Deterministic Timing 127

8 Stationary Analysis 129

8.1 General Solution Algorithm 129

8.1.1 Description of the Solution Algorithm 129

8.1.2 Derivation of the Solution Formulas 130

8.1.3 Example: OCDR Connection Management 134

8.1.4 Example: The M/D/1/K System with Preemptions 138

8.2 Computation of the Integrals 140

8.2.1 Problem Definition 141

8.2.2 Uniformization for the Cumulative Transient Analysis 142

8.2.3 Uniformization for Random Times 146

8.2.4 Alpha-Factors for Expolynomial Distributions 153

8.2.5 Alpha-Factors for the Pareto Distribution 159

8.2.6 Example: Alpha-Factors for the OCDR Model 159

9 Transient Analysis 161

9.1 Solution of the Partial Differential Equations 161

9.2 Solution of the Remaining State Equations 162

9.2.1 Discretization of the Equations 163

9.2.2 General Solution Algorithm 165

9.2.3 Simplifications in the Deterministic Case 167

9.2.4 Complexity Analysis 170

9.3 Refinement of the Solution Algorithm 170

9.3.1 Dealing with Discontinuities Explicitly 171

9.3.2 Separation of Discrete and Continuous Parts 174

9.3.3 Formulation of a Refined Algorithm 176

9.4 Periodic DSPNs 180

9.4.1 Simplified State Equations 180

9.4.2 Simplified Transient Analysis 181

9.4.3 Complexity Analysis 183

9.5 Experimental Evaluation 184

9.5.1 Case 1: A GSPN 185

9.5.2 Case 2: A Periodic DSPN 186

9.5.3 Case 3: A Non-periodic DSPN 189

9.5.4 The Refined Algorithm 192

10 General Execution Policies 201

10.2 Preemption Policies 205

10.2.1 Derivation of State Equations 205

10.2.2 Stationary Analysis 207

10.2.3 The M/G/1/K System with Failures and Repairs 210

10.3 Enabling-Dependent Firing Time Distributions 215

10.3.1 Derivation of State Equations 216

10.3.2 Stationary Analysis 216

10.3.3 An M/G/1/K System with Degradable Service 218

10.4 Scaling Factors 221

10.4.1 Defining the Type of Marking Dependence 221

10.4.2 Derivation of State Equations 222

10.4.3 Stationary Analysis 223

10.4.4 An M/G/1/K System with Degradable Service 224

10.5 PRS Policy and Marking Dependence 226

10.5.1 PRS Policy and Enabling Dependence 226

10.5.2 PRS Policy and Scaling Factors 226

10.6 Unified Algorithm 228

11 Reducible Structures 231

11.1 Reducible Markov Chains 231

11.1.1 Analysis 231

11.2 Reducible Non-Markovian Processes 237

11.2.1 Analysis 237

12 Markov Renewal Theory 249

12.1 Main Concepts of Markov Renewal Theory 249

12.1.1 Regeneration and Embedding 250

12.1.2 Transient State Equations 252

12.1.3 Stationary State Equations 254

12.2 Derivation of the Kernel Matrices 255

12.2.1 The Markovian Case 255

12.2.2 The Non-Markovian Case 256

12.3.1 The M/G/1/K System 259

12.3.2 The OCDR System 260

12.3.3 The M/D/1/K System with Service Preemptions 261

12.4 Relationship to Supplementary Variables 263

12.4.1 Formal Relationship in the Transient Case 263

12.4.2 Experimental Comparison 267

12.4.3 Formal Relationship in the Stationary Case 271

12.4.4 Consequences of the Relationship 272

12.5 Solution of Large Models 274

12.5.1 Iterative Solution Algorithm 275

12.5.2 Complexity Analysis 278

13 Concurrent Deterministic Transitions 283

13.1 Cascaded Embedding 284

13.2 Definition of Cascaded DSPNs 285

13.3 Analysis of Cascaded DSPNs 286

13.5 Potential Extensions of Cascaded Embedding 296

13.6 Alternative Approaches and Bibliographical Notes 297

III Application to the Performance Analysis of Communication Systems 301

14 Introduction to Communication Systems 305

14.1 Topics in Communications 305

14.2 Traffic Source Modeling 308

14.3 Studies of Communication Systems Based on SPNs 313

15 Medium Access Control 315

15.1 Issues in Medium Access Control 315

15.2 Wireless LANs 317

15.2.1 IEEE 802.11 Wireless LANs 317

15.2.2 A Detailed SPN Model 321

15.2.3 A Compact SPN Model 326

15.2.4 Numerical Results 328

15.3 Fast Ethernet 330

15.4 Packet Reservation Multiple Access 336

15.5 The Knockout Switch 340

16 Error Control for Noisy Channels 345

16.1 Issues in Logical Link Control 345

16.2 Stop and Wait 348

16.3 Selective Repeat 350

16.4 Go-Back-N 355

17.1 Congestion Control in TCP 362

17.2 Usage Parameter Control in ATM 364

17.3 WWW Server Performance 368

17.4 Preventive Maintenance 371

Appendix SPNica Manual 379

A.1 A Short Tour of SPNica 379

A.1.1 Tool Architecture 379

A.1.2 SPN Specification 380

A.1.3 Reduced Reachability Graph 382

A.1.4 Stochastic Process and Its Analysis 383

A.1.5 Presentation of Results 384

A.1.6 Installation 384

A.2 Analysis of Discrete-Time Markov Chains 385

A.3 Analysis of GSPN Models 386

A.4 Stationary Analysis of Non-Markovian SPNs 389

A.4.1 Firing Time Distributions 389

A.4.2 Extraction of the Stochastic Process 390

A.4.3 The General Solution Algorithm 392

A.4.4 Uniformization 394

A.4.5 The Iterative Solution Algorithm 396

A.4.6 General Execution Policies 398

A.5 Transient Analysis of DSPNs 401

A.5.1 Solution Algorithm for Periodic DSPNs 401

A.5.2 Solution Algorithm for Non-periodic DSPNs 403.

Notes:

Includes bibliographical references (pages [419]-432) and index.

ISBN:

0471492582

OCLC:

43323785