Performance Evaluation by Simulation and Analysis with Applications to Computer Networks

An engineer by training, Ken Chen is a professor at the University Paris 13 and professor at Telecom ParisTech.

• LIST OF TABLES xvLIST OF FIGURES xviiLIST OF LISTINGS xxiPREFACE xxiiiCHAPTER 1. PERFORMANCE EVALUATION 11.1. Performance evaluation 11.2. Performance versus resources provisioning 31.2.1. Performance indicators 31.2.2. Resources provisioning 41.3. Methods of performance evaluation 41.3.1. Direct study 41.3.2. Modeling 51.4. Modeling 61.4.1. Shortcomings 61.4.2. Advantages 71.4.3. Cost of modeling 71.5. Types of modeling 81.6. Analytical modeling versus simulation 8PART 1. SIMULATION 11CHAPTER 2. INTRODUCTION TO SIMULATION 132.1. Presentation 132.2. Principle of discrete event simulation 152.2.1. Evolution of a event-driven system 152.2.2. Model programming 162.3. Relationship with mathematical modeling 18CHAPTER 3. MODELING OF STOCHASTIC BEHAVIORS 213.1. Introduction 213.2. Identification of stochastic behavior 233.3. Generation of random variables 243.4. Generation of U(0, 1) r.v. 253.4.1. Importance of U(0, 1) r.v. 253.4.2. Von Neumann’s generator 263.4.3. The LCG generators 283.4.4. Advanced generators 313.4.5. Precaution and practice 333.5. Generation of a given distribution 353.5.1. Inverse transformation method 353.5.2. Acceptance–rejection method 363.5.3. Generation of discrete r.v. 383.5.4. Particular case 393.6. Some commonly used distributions and their generation 403.6.1. Uniform distribution 413.6.2. Triangular distribution 413.6.3. Exponential distribution 423.6.4. Pareto distribution 433.6.5. Normal distribution 443.6.6. Log-normal distribution 453.6.7. Bernoulli distribution 453.6.8. Binomial distribution 463.6.9. Geometric distribution 473.6.10. Poisson distribution 483.7. Applications to computer networks 48CHAPTER 4. SIMULATION LANGUAGES 534.1. Simulation languages 534.1.1. Presentation 534.1.2. Main programming features 544.1.3. Choice of a simulation language 544.2. Scheduler 564.3. Generators of random variables 574.4. Data collection and statistics 584.5. Object-oriented programming 584.6. Description language and control language 594.7. Validation 594.7.1. Generality 594.7.2. Verification of predictions 604.7.3. Some specific and typical errors 614.7.4. Various tests 62CHAPTER 5. SIMULATION RUNNING AND DATA ANALYSIS 635.1. Introduction 635.2. Outputs of a simulation 645.2.1. Nature of the data produced by a simulation 645.2.2. Stationarity 655.2.3. Example 665.2.4. Transient period 685.2.5. Duration of a simulation 695.3. Mean value estimation 705.3.1. Mean value of discrete variables 715.3.2. Mean value of continuous variables 725.3.3. Estimation of a proportion 725.3.4. Confidence interval 735.4. Running simulations 735.4.1. Replication method 735.4.2. Batch-means method 755.4.3. Regenerative method 765.5. Variance reduction 775.5.1. Common random numbers 785.5.2. Antithetic variates 795.6. Conclusion 80CHAPTER 6. OMNET++ 816.1. A summary presentation 816.2. Installation 826.2.1. Preparation 826.2.2. Installation 836.3. Architecture of OMNeT++ 836.3.1. Simple module 846.3.2. Channel 856.3.3. Compound module 856.3.4. Simulation model (network) 856.4. The NED langage 856.5. The IDE of OMNeT++ 866.6. The project 866.6.1. Workspace and projects 876.6.2. Creation of a project 876.6.3. Opening and closing of a project 876.6.4. Import of a project 886.7. A first example 886.7.1. Creation of the modules 886.7.2. Compilation 926.7.3. Initialization 926.7.4. Launching of the simulation 936.8. Data collection and statistics 936.8.1. The Signal mechanism 946.8.2. The collectors 956.8.3. Extension of the model with statistics 956.8.4. Data analysis 986.9. A FIFO queue 986.9.1. Construction of the queue 986.9.2. Extension of MySource 1016.9.3. Configuration 1036.10. An elementary distributed system 1056.10.1. Presentation 1056.10.2. Coding 1076.10.3. Modular construction of a larger system 1146.10.4. The system 1156.10.5. Configuration of the simulation and its scenarios 1156.11. Building large systems: an example with INET 1176.11.1. The system 1176.11.2. Ethernet card with LLC 1196.11.3. The new entity MyApp 1216.11.4. Simulation 1256.11.5. Conclusion 126PART 2. QUEUEING THEORY 129CHAPTER 7. INTRODUCTION TO THE QUEUEING THEORY 1317.1. Presentation 1317.2. Modeling of the computer networks 1337.3. Description of a queue 1337.4. Main parameters 1357.5. Performance indicators 1367.5.1. Usual parameters 1367.5.2. Performance in steady state 1367.6. The Little’s law 1377.6.1. Presentation 1377.6.2. Applications 138CHAPTER 8. POISSON PROCESS 1418.1. Definition 1418.1.1. Definition 1418.1.2. Distribution of a Poisson process 1428.2. Interarrival interval 1438.2.1. Definition 1438.2.2. Distribution of the interarrival interval Δ 1448.2.3. Relation between N(t) and Δ 1458.3. Erlang distribution 1458.4. Superposition of independent Poisson processes 1468.5. Decomposition of a Poisson process 1478.6. Distribution of arrival instants over a given interval 1508.7. The PASTA property 151CHAPTER 9. MARKOV QUEUEING SYSTEMS 1539.1. Birth-and-death process 1539.1.1. Definition 1539.1.2. Differential equations 1549.1.3. Steady-state solution 1569.2. The M/M/1 queues 1589.3. The M/M/∞ queues 1609.4. The M/M/m queues 1619.5. The M/M/1/K queues 1639.6. The M/M/m/m queues 1649.7. Examples 1659.7.1. Two identical servers with different activation thresholds 1659.7.2. A cybercafe 167CHAPTER 10. THE M/G/1 QUEUES 16910.1. Introduction 16910.2. Embedded Markov chain 17010.3. Length of the queue 17110.3.1. Number of arrivals during a service period 17210.3.2. Pollaczek–Khinchin formula 17310.3.3. Examples 17510.4. Sojourn time 17810.5. Busy period 17910.6. Pollaczek–Khinchin mean value formula 18110.7. M/G/1 queue with server vacation 18310.8. Priority queueing systems 185CHAPTER 11. QUEUEING NETWORKS 18911.1. Generality 18911.2. Jackson network 19211.3. Closed network 197PART 3. PROBABILITY AND STATISTICS 201CHAPTER 12. AN INTRODUCTION TO THE THEORY OF PROBABILITY 20312.1. Axiomatic base 20312.1.1. Introduction 20312.1.2. Probability space 20412.1.3. Set language versus probability language 20612.2. Conditional probability 20612.2.1. Definition 20612.2.2. Law of total probability 20712.3. Independence 20712.4. Random variables 20812.4.1. Definition 20812.4.2. Cumulative distribution function 20812.4.3. Discrete random variables 20912.4.4. Continuous random variables 21012.4.5. Characteristic function 21212.5. Some common distributions 21212.5.1. Bernoulli distribution 21212.5.2. Binomial distribution 21312.5.3. Poisson distribution 21312.5.4. Geometric distribution 21412.5.5. Uniform distribution 21512.5.6. Triangular distribution 21512.5.7. Exponential distribution 21612.5.8. Normal distribution 21712.5.9. Log-normal distribution 21912.5.10. Pareto distribution 21912.6. Joint probability distribution of multiple random variables 22012.6.1. Definition 22012.6.2. Independence and covariance 22112.6.3. Mathematical expectation 22112.7. Some interesting inequalities 22212.7.1. Markov’s inequality 22212.7.2. Chebyshev’s inequality 22212.7.3. Cantelli’s inequality 22312.8. Convergences 22312.8.1. Types of convergence 22412.8.2. Law of large numbers 22612.8.3. Central limit theorem 227CHAPTER 13. AN INTRODUCTION TO STATISTICS 22913.1. Introduction 22913.2. Description of a sample 23013.2.1. Graphic representation 23013.2.2. Mean and variance of a given sample 23113.2.3. Median 23113.2.4. Extremities and quartiles 23213.2.5. Mode and symmetry 23213.2.6. Empirical cumulative distribution function and histogram 23313.3. Parameters estimation 23613.3.1. Position of the problem 23613.3.2. Estimators 23613.3.3. Sample mean and sample variance 23713.3.4. Maximum-likelihood estimation 23713.3.5. Method of moments 23913.3.6. Confidence interval 24013.4. Hypothesis testing 24113.4.1. Introduction 24113.4.2. Chi-square (χ2) test 24113.4.3. Kolmogorov–Smirnov test 24413.4.4. Comparison between the χ2 test and the K-S test 246CHAPTER 14. MARKOV PROCESS 24714.1. Stochastic process 24714.2. Discrete-time Markov chains 24814.2.1. Definitions 24814.2.2. Properties 25114.2.3. Transition diagram 25314.2.4. Classification of states 25414.2.5. Stationarity 25514.2.6. Applications 25714.3. Continuous-time Markov chain 26014.3.1. Definitions 26014.3.2. Properties 26214.3.3. Structure of a Markov process 26314.3.4. Generators 26614.3.5. Stationarity 26714.3.6. Transition diagram 27014.3.7. Applications 272BIBLIOGRAPHY 273INDEX 277