Title Details

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