Details

Performance Evaluation by Simulation and Analysis with Applications to Computer Networks

1. Aufl.

von: Ken Chen
139,99 €
Verlag:	Wiley
Format:	PDF
Veröffentl.:	02.02.2015
ISBN/EAN:	9781119006213
Sprache:	englisch
Anzahl Seiten:	316

In den Warenkorb

Als Gutschein

DRM-geschütztes eBook, Sie benötigen z.B. Adobe Digital Editions und eine Adobe ID zum Lesen.

Beschreibungen

Titelbeschreibung

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.

Inhaltsverzeichnis

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