Performance Evaluation by Simulation and Analysis with Applications to Computer Networks
1st Edition
Published on 6. February 2015
Book
Hardback
316 pages
978-1-84821-747-8 (ISBN)
Description
This book is devoted to the most used methodologies for performance evaluation: simulation using specialized software and mathematical modeling. An important part is dedicated to the simulation, particularly in its theoretical framework and the precautions to be taken in the implementation of the experimental procedure. These principles are illustrated by concrete examples achieved through operational simulation languages ??(OMNeT ++, OPNET). Presented under the complementary approach, the mathematical method is essential for the simulation. Both methodologies based largely on the theory of probability and statistics in general and particularly Markov processes, a reminder of the basic results is also available.
More details
Language
English
Place of publication
London
United Kingdom
Target group
Professional and scholarly
Product notice
sewn/stitched
Cloth over boards
Dimensions
Height: 240 mm
Width: 161 mm
Thickness: 22 mm
Weight
642 gr
ISBN-13
978-1-84821-747-8 (9781848217478)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Other editions
Additional editions
E-Book
02/2015
Wiley-ISTE
€139.99
Available for download
E-Book
02/2015
Wiley-ISTE
€139.99
Available for download
Person
An engineer by training, Ken Chen is a professor at the University Paris 13 and professor at Telecom ParisTech.
Content
LIST OF TABLES xv
LIST OF FIGURES xvii
LIST OF LISTINGS xxi
PREFACE xxiii
CHAPTER 1. PERFORMANCE EVALUATION 1
1.1. Performance evaluation 1
1.2. Performance versus resources provisioning 3
1.2.1. Performance indicators 3
1.2.2. Resources provisioning 4
1.3. Methods of performance evaluation 4
1.3.1. Direct study 4
1.3.2. Modeling 5
1.4. Modeling 6
1.4.1. Shortcomings 6
1.4.2. Advantages 7
1.4.3. Cost of modeling 7
1.5. Types of modeling 8
1.6. Analytical modeling versus simulation 8
PART 1. SIMULATION 11
CHAPTER 2. INTRODUCTION TO SIMULATION 13
2.1. Presentation 13
2.2. Principle of discrete event simulation 15
2.2.1. Evolution of a event-driven system 15
2.2.2. Model programming 16
2.3. Relationship with mathematical modeling 18
CHAPTER 3. MODELING OF STOCHASTIC BEHAVIORS 21
3.1. Introduction 21
3.2. Identification of stochastic behavior 23
3.3. Generation of random variables 24
3.4. Generation of U(0, 1) r.v. 25
3.4.1. Importance of U(0, 1) r.v. 25
3.4.2. Von Neumann's generator 26
3.4.3. The LCG generators 28
3.4.4. Advanced generators 31
3.4.5. Precaution and practice 33
3.5. Generation of a given distribution 35
3.5.1. Inverse transformation method 35
3.5.2. Acceptance-rejection method 36
3.5.3. Generation of discrete r.v. 38
3.5.4. Particular case 39
3.6. Some commonly used distributions and their generation 40
3.6.1. Uniform distribution 41
3.6.2. Triangular distribution 41
3.6.3. Exponential distribution 42
3.6.4. Pareto distribution 43
3.6.5. Normal distribution 44
3.6.6. Log-normal distribution 45
3.6.7. Bernoulli distribution 45
3.6.8. Binomial distribution 46
3.6.9. Geometric distribution 47
3.6.10. Poisson distribution 48
3.7. Applications to computer networks 48
CHAPTER 4. SIMULATION LANGUAGES 53
4.1. Simulation languages 53
4.1.1. Presentation 53
4.1.2. Main programming features 54
4.1.3. Choice of a simulation language 54
4.2. Scheduler 56
4.3. Generators of random variables 57
4.4. Data collection and statistics 58
4.5. Object-oriented programming 58
4.6. Description language and control language 59
4.7. Validation 59
4.7.1. Generality 59
4.7.2. Verification of predictions 60
4.7.3. Some specific and typical errors 61
4.7.4. Various tests 62
CHAPTER 5. SIMULATION RUNNING AND DATA ANALYSIS 63
5.1. Introduction 63
5.2. Outputs of a simulation 64
5.2.1. Nature of the data produced by a simulation 64
5.2.2. Stationarity 65
5.2.3. Example 66
5.2.4. Transient period 68
5.2.5. Duration of a simulation 69
5.3. Mean value estimation 70
5.3.1. Mean value of discrete variables 71
5.3.2. Mean value of continuous variables 72
5.3.3. Estimation of a proportion 72
5.3.4. Confidence interval 73
5.4. Running simulations 73
5.4.1. Replication method 73
5.4.2. Batch-means method 75
5.4.3. Regenerative method 76
5.5. Variance reduction 77
5.5.1. Common random numbers 78
5.5.2. Antithetic variates 79
5.6. Conclusion 80
CHAPTER 6. OMNET++ 81
6.1. A summary presentation 81
6.2. Installation 82
6.2.1. Preparation 82
6.2.2. Installation 83
6.3. Architecture of OMNeT++ 83
6.3.1. Simple module 84
6.3.2. Channel 85
6.3.3. Compound module 85
6.3.4. Simulation model (network) 85
6.4. The NED langage 85
6.5. The IDE of OMNeT++ 86
6.6. The project 86
6.6.1. Workspace and projects 87
6.6.2. Creation of a project 87
6.6.3. Opening and closing of a project 87
6.6.4. Import of a project 88
6.7. A first example 88
6.7.1. Creation of the modules 88
6.7.2. Compilation 92
6.7.3. Initialization 92
6.7.4. Launching of the simulation 93
6.8. Data collection and statistics 93
6.8.1. The Signal mechanism 94
6.8.2. The collectors 95
6.8.3. Extension of the model with statistics 95
6.8.4. Data analysis 98
6.9. A FIFO queue 98
6.9.1. Construction of the queue 98
6.9.2. Extension of MySource 101
6.9.3. Configuration 103
6.10. An elementary distributed system 105
6.10.1. Presentation 105
6.10.2. Coding 107
6.10.3. Modular construction of a larger system 114
6.10.4. The system 115
6.10.5. Configuration of the simulation and its scenarios 115
6.11. Building large systems: an example with INET 117
6.11.1. The system 117
6.11.2. Ethernet card with LLC 119
6.11.3. The new entity MyApp 121
6.11.4. Simulation 125
6.11.5. Conclusion 126
PART 2. QUEUEING THEORY 129
CHAPTER 7. INTRODUCTION TO THE QUEUEING THEORY 131
7.1. Presentation 131
7.2. Modeling of the computer networks 133
7.3. Description of a queue 133
7.4. Main parameters 135
7.5. Performance indicators 136
7.5.1. Usual parameters 136
7.5.2. Performance in steady state 136
7.6. The Little's law 137
7.6.1. Presentation 137
7.6.2. Applications 138
CHAPTER 8. POISSON PROCESS 141
8.1. Definition 141
8.1.1. Definition 141
8.1.2. Distribution of a Poisson process 142
8.2. Interarrival interval 143
8.2.1. Definition 143
8.2.2. Distribution of the interarrival interval ? 144
8.2.3. Relation between N(t) and ? 145
8.3. Erlang distribution 145
8.4. Superposition of independent Poisson processes 146
8.5. Decomposition of a Poisson process 147
8.6. Distribution of arrival instants over a given interval 150
8.7. The PASTA property 151
CHAPTER 9. MARKOV QUEUEING SYSTEMS 153
9.1. Birth-and-death process 153
9.1.1. Definition 153
9.1.2. Differential equations 154
9.1.3. Steady-state solution 156
9.2. The M/M/1 queues 158
9.3. The M/M/? queues 160
9.4. The M/M/m queues 161
9.5. The M/M/1/K queues 163
9.6. The M/M/m/m queues 164
9.7. Examples 165
9.7.1. Two identical servers with different activation thresholds 165
9.7.2. A cybercafe 167
CHAPTER 10. THE M/G/1 QUEUES 169
10.1. Introduction 169
10.2. Embedded Markov chain 170
10.3. Length of the queue 171
10.3.1. Number of arrivals during a service period 172
10.3.2. Pollaczek-Khinchin formula 173
10.3.3. Examples 175
10.4. Sojourn time 178
10.5. Busy period 179
10.6. Pollaczek-Khinchin mean value formula 181
10.7. M/G/1 queue with server vacation 183
10.8. Priority queueing systems 185
CHAPTER 11. QUEUEING NETWORKS 189
11.1. Generality 189
11.2. Jackson network 192
11.3. Closed network 197
PART 3. PROBABILITY AND STATISTICS 201
CHAPTER 12. AN INTRODUCTION TO THE THEORY OF PROBABILITY 203
12.1. Axiomatic base 203
12.1.1. Introduction 203
12.1.2. Probability space 204
12.1.3. Set language versus probability language 206
12.2. Conditional probability 206
12.2.1. Definition 206
12.2.2. Law of total probability 207
12.3. Independence 207
12.4. Random variables 208
12.4.1. Definition 208
12.4.2. Cumulative distribution function 208
12.4.3. Discrete random variables 209
12.4.4. Continuous random variables 210
12.4.5. Characteristic function 212
12.5. Some common distributions 212
12.5.1. Bernoulli distribution 212
12.5.2. Binomial distribution 213
12.5.3. Poisson distribution 213
12.5.4. Geometric distribution 214
12.5.5. Uniform distribution 215
12.5.6. Triangular distribution 215
12.5.7. Exponential distribution 216
12.5.8. Normal distribution 217
12.5.9. Log-normal distribution 219
12.5.10. Pareto distribution 219
12.6. Joint probability distribution of multiple random variables 220
12.6.1. Definition 220
12.6.2. Independence and covariance 221
12.6.3. Mathematical expectation 221
12.7. Some interesting inequalities 222
12.7.1. Markov's inequality 222
12.7.2. Chebyshev's inequality 222
12.7.3. Cantelli's inequality 223
12.8. Convergences 223
12.8.1. Types of convergence 224
12.8.2. Law of large numbers 226
12.8.3. Central limit theorem 227
CHAPTER 13. AN INTRODUCTION TO STATISTICS 229
13.1. Introduction 229
13.2. Description of a sample 230
13.2.1. Graphic representation 230
13.2.2. Mean and variance of a given sample 231
13.2.3. Median 231
13.2.4. Extremities and quartiles 232
13.2.5. Mode and symmetry 232
13.2.6. Empirical cumulative distribution function and histogram 233
13.3. Parameters estimation 236
13.3.1. Position of the problem 236
13.3.2. Estimators 236
13.3.3. Sample mean and sample variance 237
13.3.4. Maximum-likelihood estimation 237
13.3.5. Method of moments 239
13.3.6. Confidence interval 240
13.4. Hypothesis testing 241
13.4.1. Introduction 241
13.4.2. Chi-square (?2) test 241
13.4.3. Kolmogorov-Smirnov test 244
13.4.4. Comparison between the ?2 test and the K-S test 246
CHAPTER 14. MARKOV PROCESS 247
14.1. Stochastic process 247
14.2. Discrete-time Markov chains 248
14.2.1. Definitions 248
14.2.2. Properties 251
14.2.3. Transition diagram 253
14.2.4. Classification of states 254
14.2.5. Stationarity 255
14.2.6. Applications 257
14.3. Continuous-time Markov chain 260
14.3.1. Definitions 260
14.3.2. Properties 262
14.3.3. Structure of a Markov process 263
14.3.4. Generators 266
14.3.5. Stationarity 267
14.3.6. Transition diagram 270
14.3.7. Applications 272
BIBLIOGRAPHY 273
INDEX 277
LIST OF FIGURES xvii
LIST OF LISTINGS xxi
PREFACE xxiii
CHAPTER 1. PERFORMANCE EVALUATION 1
1.1. Performance evaluation 1
1.2. Performance versus resources provisioning 3
1.2.1. Performance indicators 3
1.2.2. Resources provisioning 4
1.3. Methods of performance evaluation 4
1.3.1. Direct study 4
1.3.2. Modeling 5
1.4. Modeling 6
1.4.1. Shortcomings 6
1.4.2. Advantages 7
1.4.3. Cost of modeling 7
1.5. Types of modeling 8
1.6. Analytical modeling versus simulation 8
PART 1. SIMULATION 11
CHAPTER 2. INTRODUCTION TO SIMULATION 13
2.1. Presentation 13
2.2. Principle of discrete event simulation 15
2.2.1. Evolution of a event-driven system 15
2.2.2. Model programming 16
2.3. Relationship with mathematical modeling 18
CHAPTER 3. MODELING OF STOCHASTIC BEHAVIORS 21
3.1. Introduction 21
3.2. Identification of stochastic behavior 23
3.3. Generation of random variables 24
3.4. Generation of U(0, 1) r.v. 25
3.4.1. Importance of U(0, 1) r.v. 25
3.4.2. Von Neumann's generator 26
3.4.3. The LCG generators 28
3.4.4. Advanced generators 31
3.4.5. Precaution and practice 33
3.5. Generation of a given distribution 35
3.5.1. Inverse transformation method 35
3.5.2. Acceptance-rejection method 36
3.5.3. Generation of discrete r.v. 38
3.5.4. Particular case 39
3.6. Some commonly used distributions and their generation 40
3.6.1. Uniform distribution 41
3.6.2. Triangular distribution 41
3.6.3. Exponential distribution 42
3.6.4. Pareto distribution 43
3.6.5. Normal distribution 44
3.6.6. Log-normal distribution 45
3.6.7. Bernoulli distribution 45
3.6.8. Binomial distribution 46
3.6.9. Geometric distribution 47
3.6.10. Poisson distribution 48
3.7. Applications to computer networks 48
CHAPTER 4. SIMULATION LANGUAGES 53
4.1. Simulation languages 53
4.1.1. Presentation 53
4.1.2. Main programming features 54
4.1.3. Choice of a simulation language 54
4.2. Scheduler 56
4.3. Generators of random variables 57
4.4. Data collection and statistics 58
4.5. Object-oriented programming 58
4.6. Description language and control language 59
4.7. Validation 59
4.7.1. Generality 59
4.7.2. Verification of predictions 60
4.7.3. Some specific and typical errors 61
4.7.4. Various tests 62
CHAPTER 5. SIMULATION RUNNING AND DATA ANALYSIS 63
5.1. Introduction 63
5.2. Outputs of a simulation 64
5.2.1. Nature of the data produced by a simulation 64
5.2.2. Stationarity 65
5.2.3. Example 66
5.2.4. Transient period 68
5.2.5. Duration of a simulation 69
5.3. Mean value estimation 70
5.3.1. Mean value of discrete variables 71
5.3.2. Mean value of continuous variables 72
5.3.3. Estimation of a proportion 72
5.3.4. Confidence interval 73
5.4. Running simulations 73
5.4.1. Replication method 73
5.4.2. Batch-means method 75
5.4.3. Regenerative method 76
5.5. Variance reduction 77
5.5.1. Common random numbers 78
5.5.2. Antithetic variates 79
5.6. Conclusion 80
CHAPTER 6. OMNET++ 81
6.1. A summary presentation 81
6.2. Installation 82
6.2.1. Preparation 82
6.2.2. Installation 83
6.3. Architecture of OMNeT++ 83
6.3.1. Simple module 84
6.3.2. Channel 85
6.3.3. Compound module 85
6.3.4. Simulation model (network) 85
6.4. The NED langage 85
6.5. The IDE of OMNeT++ 86
6.6. The project 86
6.6.1. Workspace and projects 87
6.6.2. Creation of a project 87
6.6.3. Opening and closing of a project 87
6.6.4. Import of a project 88
6.7. A first example 88
6.7.1. Creation of the modules 88
6.7.2. Compilation 92
6.7.3. Initialization 92
6.7.4. Launching of the simulation 93
6.8. Data collection and statistics 93
6.8.1. The Signal mechanism 94
6.8.2. The collectors 95
6.8.3. Extension of the model with statistics 95
6.8.4. Data analysis 98
6.9. A FIFO queue 98
6.9.1. Construction of the queue 98
6.9.2. Extension of MySource 101
6.9.3. Configuration 103
6.10. An elementary distributed system 105
6.10.1. Presentation 105
6.10.2. Coding 107
6.10.3. Modular construction of a larger system 114
6.10.4. The system 115
6.10.5. Configuration of the simulation and its scenarios 115
6.11. Building large systems: an example with INET 117
6.11.1. The system 117
6.11.2. Ethernet card with LLC 119
6.11.3. The new entity MyApp 121
6.11.4. Simulation 125
6.11.5. Conclusion 126
PART 2. QUEUEING THEORY 129
CHAPTER 7. INTRODUCTION TO THE QUEUEING THEORY 131
7.1. Presentation 131
7.2. Modeling of the computer networks 133
7.3. Description of a queue 133
7.4. Main parameters 135
7.5. Performance indicators 136
7.5.1. Usual parameters 136
7.5.2. Performance in steady state 136
7.6. The Little's law 137
7.6.1. Presentation 137
7.6.2. Applications 138
CHAPTER 8. POISSON PROCESS 141
8.1. Definition 141
8.1.1. Definition 141
8.1.2. Distribution of a Poisson process 142
8.2. Interarrival interval 143
8.2.1. Definition 143
8.2.2. Distribution of the interarrival interval ? 144
8.2.3. Relation between N(t) and ? 145
8.3. Erlang distribution 145
8.4. Superposition of independent Poisson processes 146
8.5. Decomposition of a Poisson process 147
8.6. Distribution of arrival instants over a given interval 150
8.7. The PASTA property 151
CHAPTER 9. MARKOV QUEUEING SYSTEMS 153
9.1. Birth-and-death process 153
9.1.1. Definition 153
9.1.2. Differential equations 154
9.1.3. Steady-state solution 156
9.2. The M/M/1 queues 158
9.3. The M/M/? queues 160
9.4. The M/M/m queues 161
9.5. The M/M/1/K queues 163
9.6. The M/M/m/m queues 164
9.7. Examples 165
9.7.1. Two identical servers with different activation thresholds 165
9.7.2. A cybercafe 167
CHAPTER 10. THE M/G/1 QUEUES 169
10.1. Introduction 169
10.2. Embedded Markov chain 170
10.3. Length of the queue 171
10.3.1. Number of arrivals during a service period 172
10.3.2. Pollaczek-Khinchin formula 173
10.3.3. Examples 175
10.4. Sojourn time 178
10.5. Busy period 179
10.6. Pollaczek-Khinchin mean value formula 181
10.7. M/G/1 queue with server vacation 183
10.8. Priority queueing systems 185
CHAPTER 11. QUEUEING NETWORKS 189
11.1. Generality 189
11.2. Jackson network 192
11.3. Closed network 197
PART 3. PROBABILITY AND STATISTICS 201
CHAPTER 12. AN INTRODUCTION TO THE THEORY OF PROBABILITY 203
12.1. Axiomatic base 203
12.1.1. Introduction 203
12.1.2. Probability space 204
12.1.3. Set language versus probability language 206
12.2. Conditional probability 206
12.2.1. Definition 206
12.2.2. Law of total probability 207
12.3. Independence 207
12.4. Random variables 208
12.4.1. Definition 208
12.4.2. Cumulative distribution function 208
12.4.3. Discrete random variables 209
12.4.4. Continuous random variables 210
12.4.5. Characteristic function 212
12.5. Some common distributions 212
12.5.1. Bernoulli distribution 212
12.5.2. Binomial distribution 213
12.5.3. Poisson distribution 213
12.5.4. Geometric distribution 214
12.5.5. Uniform distribution 215
12.5.6. Triangular distribution 215
12.5.7. Exponential distribution 216
12.5.8. Normal distribution 217
12.5.9. Log-normal distribution 219
12.5.10. Pareto distribution 219
12.6. Joint probability distribution of multiple random variables 220
12.6.1. Definition 220
12.6.2. Independence and covariance 221
12.6.3. Mathematical expectation 221
12.7. Some interesting inequalities 222
12.7.1. Markov's inequality 222
12.7.2. Chebyshev's inequality 222
12.7.3. Cantelli's inequality 223
12.8. Convergences 223
12.8.1. Types of convergence 224
12.8.2. Law of large numbers 226
12.8.3. Central limit theorem 227
CHAPTER 13. AN INTRODUCTION TO STATISTICS 229
13.1. Introduction 229
13.2. Description of a sample 230
13.2.1. Graphic representation 230
13.2.2. Mean and variance of a given sample 231
13.2.3. Median 231
13.2.4. Extremities and quartiles 232
13.2.5. Mode and symmetry 232
13.2.6. Empirical cumulative distribution function and histogram 233
13.3. Parameters estimation 236
13.3.1. Position of the problem 236
13.3.2. Estimators 236
13.3.3. Sample mean and sample variance 237
13.3.4. Maximum-likelihood estimation 237
13.3.5. Method of moments 239
13.3.6. Confidence interval 240
13.4. Hypothesis testing 241
13.4.1. Introduction 241
13.4.2. Chi-square (?2) test 241
13.4.3. Kolmogorov-Smirnov test 244
13.4.4. Comparison between the ?2 test and the K-S test 246
CHAPTER 14. MARKOV PROCESS 247
14.1. Stochastic process 247
14.2. Discrete-time Markov chains 248
14.2.1. Definitions 248
14.2.2. Properties 251
14.2.3. Transition diagram 253
14.2.4. Classification of states 254
14.2.5. Stationarity 255
14.2.6. Applications 257
14.3. Continuous-time Markov chain 260
14.3.1. Definitions 260
14.3.2. Properties 262
14.3.3. Structure of a Markov process 263
14.3.4. Generators 266
14.3.5. Stationarity 267
14.3.6. Transition diagram 270
14.3.7. Applications 272
BIBLIOGRAPHY 273
INDEX 277