Performance Evaluation by Simulation and Analysis with Applications to Computer Networks
Description
More details
Other editions
Additional editions
Person
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/8 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
1
Performance Evaluation
In this chapter we introduce the performance evaluation jointly with the resource provisioning. We then give a survey on the general aspects of modeling before focusing on simulation and analytical modeling.
1.1. Performance evaluation
Recent developments in telecommunications are characterized by a double diversity: diversity of applications and diversity of infrastructures. New applications and services appear day by day. The amount of data to be transported is constantly increasing, of which multimedia data are taking an increasingly important part. These data are characterized by their tight time constraints, high flow rates and abrupt variations in time. We are witnessing the advent of the so-called ambient intelligence, i.e. computers and data are everywhere, they can be produced everywhere (cloud, body-area sensor, your smart phone, etc.) and consumed everywhere else (your laptop, your smart phone, a remote monitoring facility, etc.). This ubiquitous/pervasive computing environment is supported by various networking infrastructures, including Digital Subscriber Line (DSL) connections, 3G/4G cellular networks, wireless Local Area Network (LAN), optical networks, etc.
One important issue is the so-called Quality of Service (QoS) of the data transmission. Roughly speaking, the QoS required by an application is the set of parameters (throughput, delay, jitter, reliability, etc.) on which the application relies. For example, for a videoconferencing, the nominal end-to-end delay is about 150 ms. If the actual delay is too variable, such that the delay is frequently higher than 150 ms, we simply cannot perform decent videoconferencing.
It is a fundamental matter to guarantee QoS for different applications. One of the key issues is the performance evaluation, and, in a dual manner, the resource provisioning. Performance evaluation aims to quantitatively assess various parameters of a system running most often in a stochastic environment.
A computer network is a complex system which is constituted of various components organized in layers, according to the standard International Organization for Standardization/Open System Interconnection (ISO/OSI) seven-layers model. Here are examples of performance indicators:
- at the Physical layer: bit error rate of a wireless link; - at the Link/Medium Access Control (MAC) layer: collision probability in a common medium (e.g. wireless fidelity (WiFi)) and point-to-point delay; - at the network layer: rejection rate in a router and sojourn time in a router; - at the transport layer: number of Transmission Control Protocol (TCP) connections that can be simultaneously opened; - at the application layer: response delay to a HyperText Transfer Protocol (HTTP) request.The control of the performance of a network is achieved through the control of each of its components.
Before a user makes a decision on their choice of telecommunication facility (e.g. MultiProtocol Label Switching (MPLS) connection or WiFi local network), it is normal for them to want to know the parameters characterizing the transmission quality (delay, loss ratio, etc.) offered by this facility, in order to know whether this facility truly matches their needs. In other words, one must know the performance of this facility.
In case it is the user who has full responsibility for the telecommunications facility (typically a LAN), it is then up to them to assess the performance of the system.
When a user is dealing with a service provider, there will be a contractual relation, which is called in generic terms service-level agreement (SLA), between the QoS that the provider has to offer and the traffic that a user can submit. For instance, a delay less than 100 ms for traffic not exceeding 50 Mbps in average and 100 Mbps in peak rate.
1.2. Performance versus resources provisioning
The performance of a system depends strongly on the available resources. For example, a video broadcast of 2 Mbps cannot be achieved if the available bandwidth is only 1 Mbps. The performance of a system and the resource provisioning are two faces of the same problem, which is the matching between the requirement of an application and the resources that have to be committed. For instance, a video traffic with a sustainable rate of 5 Mbps and peak rate of 10 Mbps can certainly be supported by a dedicated bandwidth of 10 Mbps, the QoS will be perfectly guaranteed with zero loss ratio and no waiting delay. However, the dedicated 10 Mbps resource has to be paid. An extremely economic solution is to provide only 5 Mbps (the mean rate), with a buffer absorbing traffic submitted at higher instantaneous rates. The committed resources (5 Mbps and some random access memory (RAM) for buffering) should be less expensive than the dedicated bandwidth of 10 Mbps, but the QoS will be less good, with probable long delay and high packet loss ratio. An intermediary solution would be a bandwidth of B ? (5, 10) Mbps with an adequate amount (L) of buffer. Performance evaluation aims to find a good couple of (B, L) for a given requirement (delay, loss ratio).
1.2.1. Performance indicators
The choice of relevant performance indicators intrinsically depends on the application. For example, a file transfer can allow a relatively large transmission delay, but claims lossless quality, whereas for videoconferencing, the standard end-to-end delay is 150 ms but it is tolerant to a limited amount of losses.
The performance of a computer network, or more generally the one of a network-based computer system, is characterized by a set of parameters:
- throughput; - delay (end-to-end delay, delay at an intermediary node, etc.); - load (utilization ratio); - number of packets in the node (router, switch, etc.); - loss ratio on a wireless link, rejection ratio in a router.1.2.2. Resources provisioning
The resources involved in networking systems fall mainly in one of the following three categories:
- processing: it is usually the central processing unit (CPU) power, with impacts on the performance indicators such as number of packets routed by a router, number of HTTP requests processed by a Web server, etc.; - storage: this can include both a volatile storage (RAM) or permanent storage (disk, flash memory). These resources act often as a buffer to absorb the random variations of the submitted work. Their provisioning affects indicators such as loss ratio in a router; - transmission: from a modeling point of view, this resource plays a similar role to that of the processing capacity, with the particularity that, here, the "processing" consists of messages transmission (Internet Protocol (IP) packet, Ethernet frame, etc.). It affects indicators such as delay or loss ratio (considered jointly with the storage resource).1.3. Methods of performance evaluation
Two classes of methods are generally used to assess the performance of a system: studies done directly on the system itself versus studies carried out through a model.
1.3.1. Direct study
This approach requires the availability of the physical system to be studied, or, at least, that of a conform copy. The advantage of a study conducted directly on the system itself (or a copy of it) is its intrinsic faithfulness to the reality. There is no distortion by the modeling process (see below) which, by definition, cannot be an exact copy. However, this method is very expensive and often impossible:
- it is, for example, very difficult to stop an operational network to turn it into a test bed. The only reasonably feasible operations are measurements gathering; - this study is by definition infeasible when conceiving a new system (which does not exist yet). We may note that it is precisely at this phase that there is a need to compare multiple design options for various possible scenarios.There are indeed very few cases where we can carry out studies directly on physical systems, for reasons of availability, safety, etc. Therefore, in many cases, we have no choice but to try modeling. This book only considers approaches based on modeling.
1.3.2. Modeling
Failing to work directly on the system itself, it is necessary to work on a model. There are two main approaches:
- physical modeling in which we build a scale model (reduced model) of the system. This approach is often rather expensive. We will not deal with these kind of models and focus instead on abstract modeling, by using mathematical formalism and/or computer technology; - abstract modeling: this modeling can be done in two ways: - mathematical model (analytical model) that is carried out using mathematical frameworks such as the Queueing theory (or graph theory, etc.); - computer-based model that is achieved by using appropriate programming language. In practice, we often use specialized software, for instance the OMNeT++ simulation environment.Model building requires an abstraction of the real system and often has to abandon some details that are...
