Performance Analysis of Communication Systems Modeling with Non-Markovian Stochastic Petri Nets

by German, Reinhard

• ISBN13: 9780471492580
• ISBN10: 0471492582
• Edition: 1st
• Format: Hardcover
• Copyright: 2000-06-08
• Publisher: WILEY

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

Author Biography

Reinhard German is the author of Performance Analysis of Communication Systems : Modeling with Non-Markovian Stochastic Petri Nets, published by Wiley.

Table of Contents

Foreword	xi
Preface	xv
Contents Outline	xvi
Acknowledgments	xvi
I Modeling with Stochastic Petri Nets	1	(34)
Introduction	5	(4)
Stochastic Petri Nets	5	(1)
Technical Approach	5	(1)
Application to Communication Systems	6	(1)
Related Work	7	(1)
Organization of the Text	8	(1)
Stochastic Petri Nets	9	(20)
Definition of Petri Nets	9	(5)
An Example: OCDR Connection Management	14	(1)
Petri Net Extensions	15	(4)
Definition of Stochastic Petri Nets	19	(5)
The Example Continued	24	(3)
Bibliographical Notes	27	(2)
Tool Support	29	(6)
A Brief Review of Tools	29	(2)
TimeNET	31	(3)
SPNica: A Prototype Tool	34	(1)
II Analytical Methodology	35	(266)
Preliminaries	39	(14)
Firing Time Distributions	39	(4)
A Characterization of Distributions	39	(3)
Expolynomial Distributions	42	(1)
Stochastic Processes	43	(2)
Quantitative Measures	45	(6)
Firing Frequencies of Transitions	45	(2)
Reward-Based Measure Definitions	47	(4)
Bibliographical Notes	51	(2)
Markovian Stochastic Petri Nets	53	(24)
Discrete Time	53	(8)
Geometric Firing Time Distributions	53	(2)
Discrete-Time Markov Chains	55	(3)
Example: The Geo/Geo/1/K System	58	(3)
Continuous Time	61	(11)
Exponential Firing Time Distributions	61	(2)
Continuous-Time Markov Chains	63	(3)
Example: The M/M/1/K System	66	(1)
Uniformization	67	(5)
Relationship of Continuous and Discrete Time	72	(3)
First Moment Matching	72	(1)
Equidistant Embedding	72	(1)
Uniformized Markov Chain	73	(1)
Embedded Markov Chain	74	(1)
Bibliographical Notes	75	(2)
The Method of Supplementary Variables	77	(32)
Analysis of the M/G/1 System	78	(12)
Definitions and Notation	78	(2)
Derivation of State Equations	80	(6)
Transform Domain Analysis	86	(4)
Analysis of the M/G/1/K System	90	(14)
Additional Definitions and Notation	90	(1)
Derivation of State Equations	91	(2)
Time-Domain Analysis	93	(2)
Example: Deterministic Service	95	(2)
Introduction of Vector and Matrix Notation	97	(5)
Example: The M/D/1/K System in Matrix Notation	102	(2)
Alternative Use of Supplementary Variables	104	(2)
Bibliographical Notes	106	(3)
General State Equations	109	(20)
Definitions and Notation	109	(11)
Example: OCDR Connection Management	115	(3)
Example: The M/D/1/K System with Preemptions	118	(2)
Derivation of the State Equations	120	(7)
Example: OCDR Connection Management	123	(4)
Simplifications for Deterministic Timing	127	(1)
Bibliographical Notes	127	(2)
Stationary Analysis	129	(32)
General Solution Algorithm	129	(11)
Description of the Solution Algorithm	129	(1)
Derivation of the Solution Formulas	130	(4)
Example: OCDR Connection Management	134	(4)
Example: The M/D/1/K System with Preemptions	138	(2)
Computation of the Integrals	140	(20)
Problem Definition	141	(1)
Uniformization for the Cumulative Transient Analysis	142	(4)
Uniformization for Random Times	146	(7)
Alpha-Factors for Expolynomial Distributions	153	(6)
Alpha-Factors for the Pareto Distribution	159	(1)
Example: Alpha-Factors for the OCDR Model	159	(1)
Bibliographical Notes	160	(1)
Transient Analysis	161	(40)
Solution of the Partial Differential Equations	161	(1)
Solution of the Remaining State Equations	162	(8)
Discretization of the Equations	163	(2)
General Solution Algorithm	165	(2)
Simplifications in the Deterministic Case	167	(3)
Complexity Analysis	170	(1)
Refinement of the Solution Algorithm	170	(10)
Dealing with Discontinuities Explicitly	171	(3)
Separation of Discrete and Continuous Parts	174	(2)
Formulation of a Refined Algorithm	176	(4)
Periodic DSPNs	180	(4)
Simplified State Equations	180	(1)
Simplified Transient Analysis	181	(2)
Complexity Analysis	183	(1)
Experimental Evaluation	184	(14)
A GSPN	185	(1)
A Periodic DSPN	186	(3)
A Non-periodic DSPN	189	(3)
The Refined Algorithm	192	(6)
Bibliographical Notes	198	(3)
General Execution Policies	201	(30)
Definitions and Notation	202	(3)
Preemption Policies	205	(10)
Derivation of State Equations	205	(2)
Stationary Analysis	207	(3)
The M/G/1/K System with Failures and Repairs	210	(5)
Enabling-Dependent Firing Time Distributions	215	(6)
Derivation of State Equations	216	(1)
Stationary Analysis	216	(2)
An M/G/1/K System with Degradable Service	218	(3)
Scaling Factors	221	(5)
Defining the Type of Marking Dependence	221	(1)
Derivation of State Equations	222	(1)
Stationary Analysis	223	(1)
An M/G/1/K System with Degradable Service	224	(2)
PRS Policy and Marking Dependence	226	(2)
PRS Policy and Enabling Dependence	226	(1)
PRS Policy and Scaling Factors	226	(2)
Unified Algorithm	228	(1)
Bibliographical Notes	229	(2)
Reducible Structures	231	(18)
Reducible Markov Chains	231	(6)
Analysis	231	(3)
An Example	234	(3)
Reducible Non-Markovian Processes	237	(10)
Analysis	237	(5)
An Example	242	(5)
Bibliographical Notes	247	(2)
Markov Renewal Theory	249	(34)
Main Concepts of Markov Renewal Theory	249	(6)
Regeneration and Embedding	250	(2)
Transient State Equations	252	(2)
Stationary State Equations	254	(1)
Derivation of the Kernel Matrices	255	(4)
The Markovian Case	255	(1)
The Non-Markovian Case	256	(3)
Examples	259	(4)
The M/G/1/K System	259	(1)
The OCDR System	260	(1)
The M/D/1/K System with Service Preemptions	261	(2)
Relationship to Supplementary Variables	263	(11)
Formal Relationship in the Transient Case	263	(4)
Experimental Comparison	267	(4)
Formal Relationship in the Stationary Case	271	(1)
Consequences of the Relationship	272	(2)
Solution of Large Models	274	(7)
Iterative Solution Algorithm	275	(3)
Complexity Analysis	278	(3)
Bibliographical Notes	281	(2)
Concurrent Deterministic Transitions	283	(18)
Cascaded Embedding	284	(1)
Definition of Cascaded DSPNs	285	(1)
Analysis of Cascaded DSPNs	286	(4)
An Example	290	(6)
Potential Extensions of Cascaded Embedding	296	(1)
Alternative Approaches and Bibliographical Notes	297	(4)
III Application to the Performance Analysis of Communication Systems	301	(78)
Introduction to Communication Systems	305	(10)
Topics in Communications	305	(3)
Traffic Source Modeling	308	(5)
Studies of Communication Systems Based on SPNs	313	(2)
Medium Access Control	315	(30)
Issues in Medium Access Control	315	(2)
Wireless LANs	317	(13)
IEEE 802.11 Wireless LANs	317	(4)
A Detailed SPN Model	321	(5)
A Compact SPN Model	326	(2)
Numerical Results	328	(2)
Fast Ethernet	330	(6)
Packet Reservation Multiple Access	336	(4)
The Knockout Switch	340	(5)
Error Control for Noisy Channels	345	(16)
Issues in Logical Link Control	345	(3)
Stop and Wait	348	(2)
Selective Repeat	350	(5)
Go-Back-N	355	(6)
Miscellaneous Topics	361	(16)
Congestion Control in TCP	362	(2)
Usage Parameter Control in ATM	364	(4)
WWW Server Performance	368	(3)
Preventive Maintenance	371	(6)
Concluding Remarks	377	(2)
Appendix: SPNica Manual	379	(28)
A.1 A Short Tour of SPNica	379	(6)
A.1.1 Tool Architecture	379	(1)
A.1.2 SPN Specification	380	(2)
A.1.3 Reduced Reachability Graph	382	(1)
A.1.4 Stochastic Process and Its Analysis	383	(1)
A.1.5 Presentation of Results	384	(1)
A.1.6 Installation	384	(1)
A.2 Analysis of Discrete-Time Markov Chains	385	(1)
A.3 Analysis of GSPN Models	386	(3)
A.4 Stationary Analysis of Non-Markovian SPNs	389	(12)
A.4.1 Firing Time Distributions	389	(1)
A.4.2 Extraction of the Stochastic Process	390	(2)
A.4.3 The General Solution Algorithm	392	(2)
A.4.4 Uniformization	394	(2)
A.4.5 The Iterative Solution Algorithm	396	(2)
A.4.6 General Execution Policies	398	(3)
A.5 Transient Analysis of DSPNs	401	(6)
A.5.1 Solution Algorithm for Periodic DSPNs	401	(2)
A.5.2 Solution Algorithm for Non-periodic DSPNs	403	(4)
List of Abbreviations	407	(4)
Glossary of Notation	411	(8)
References	419	(14)
Index	433