Performance Evaluation by Simulation and Analysis with Applications to Computer Networks

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 DELTA 144    8.2.3. Relation between N(t) and DELTA 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 (chi2) test 241    13.4.3. Kolmogorov-Smirnov test 244    13.4.4. Comparison between the chi2 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