目录 Contents 1 Introduction to IP Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 TCP/IP Architecture Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 Physical Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Data Link Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.3 Network Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.4 Transport Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.5 Application Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2 Aspects of IP Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.1 Levels of Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.2 Traffic Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2.3 Asymmetry in IP Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.2.4 Temporal Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.2.5 Network Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3 Quality of Service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.3.1 Best Effort Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.3.2 Time Sensitive Data Traffic . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.3.3 Overprovisioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.3.4 Prioritization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.4 Why Traditional Models Fail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2 Classical Traffic Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.1 Introduction to Traffic Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.1.1 Basic Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.1.2 Basic Processes and Kendall Notation . . . . . . . . . . . . . . . . 32 2.1.3 Basic Properties of Exponential Distributions . . . . . . . . . 33 2.2 Kolmogorov Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2.1 State Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.2.2 Stationary State Equation . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.3 Transition Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.4 Pure Markov Systems M/M/n . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.4.1 Loss Systems M/M/n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.4.2 Queueing Systems M/M/n . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.4.3 Application to Teletraffic . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.5 Special Traffic Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.5.1 Loss Systems M/M/∞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.5.2 Queueing Systems of Engset . . . . . . . . . . . . . . . . . . . . . . . . 58 2.5.3 Queueing Loss Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.6 Renewal Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.6.1 Definitions and Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.6.2 Bounds for the Renewal Function . . . . . . . . . . . . . . . . . . . . 65 2.6.3 Recurrence Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 2.6.4 Asymptotic Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2.6.5 Stationary Renewal Processes . . . . . . . . . . . . . . . . . . . . . . . 71 2.6.6 Random Sum Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 2.7 General Poisson Arrival and Serving Systems M/G/n . . . . . . . . 73 2.7.1 Markov Chains and Embedded Systems . . . . . . . . . . . . . . 73 2.7.2 General Loss Systems M/G/n . . . . . . . . . . . . . . . . . . . . . . . 74 2.7.3 Queueing Systems M/G/n . . . . . . . . . . . . . . . . . . . . . . . . . . 74 2.7.4 Heavy-Tail Serving Time Distribution . . . . . . . . . . . . . . . . 81 2.7.5 Application of M/G/1 Models to IP Traffic . . . . . . . . . . . 95 2.7.6 Markov Serving Times Models GI/M/1 . . . . . . . . . . . . . . 102 2.8 General Serving Systems GI/G/n. . . . . . . . . . . . . . . . . . . . . . . . . . 107 2.8.1 Loss Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 2.8.2 The Time-Discrete Queueing System GI/G/1 . . . . . . . . . 109 2.8.3 GI/G/1 Time Discrete Queueing System with Limitation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 2.9 Network Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 2.9.1 Jackson’s Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 2.9.2 Systems with Priorities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 2.9.3 Systems with Impatient Demands . . . . . . . . . . . . . . . . . . . 131 2.9.4 Conservation Laws Model . . . . . . . . . . . . . . . . . . . . . . . . . . 133 2.9.5 Packet Loss and Velocity Functions on Transmission Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 2.9.6 Riemann Solvers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 2.9.7 Stochastic Velocities and Density Functions . . . . . . . . . . . 146 2.10 Matrix-Analytical Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 2.10.1 Phase Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 2.10.2 Examples for Different Phase Distributions . . . . . . . . . . . 153 2.10.3 Markovian Arrival Processes . . . . . . . . . . . . . . . . . . . . . . . . 156 2.10.4 Queueing Systems MAP/G/1 . . . . . . . . . . . . . . . . . . . . . . . 161 2.10.5 Application to IP Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 3 Mathematical Modeling of IP-based Traffic . . . . . . . . . . . . . . . . 181 3.1 Scalefree Traffic Observation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 3.1.1 Motivation and Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 3.1.2 Self-Similarity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 3.2 Self-Similar Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 3.2.1 Definition and Basic Properties . . . . . . . . . . . . . . . . . . . . . 184 3.2.2 Fractional Brownian Motion . . . . . . . . . . . . . . . . . . . . . . . . 190 3.2.3 α-stable Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 3.3 Long-Range Dependence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 3.3.1 Definition and Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 3.3.2 Fractional Brownian Motion and Fractional Brownian Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 3.3.3 Farima Time Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 3.3.4 Fractional Brownian Motion and IP Traffic – the Norros Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 3.4 Influence of Heavy-Tail Distributions on Long-Range Dependence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 3.4.1 General Central Limit Theorem . . . . . . . . . . . . . . . . . . . . . 226 3.4.2 Heavy-Tail Distributions in M/G/∞ Models . . . . . . . . . . 233 3.4.3 Heavy-Tail Distributions in On-Off Models . . . . . . . . . . . 235 3.4.4 Aggregated Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 3.5 Models for Time Sensitive Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . 245 3.5.1 Multiscale Fractional Brownian Motion . . . . . . . . . . . . . . 245 3.5.2 Norros Models for Differentiating Traffic . . . . . . . . . . . . . 249 3.6 Fractional L´evy Motion in IP-based Network Traffic . . . . . . . . . 259 3.6.1 Description of the Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 3.6.2 Calibration of a Fractional L´evy Motion Model . . . . . . . . 260 3.7 Fractional Ornstein-Uhlenbeck Processes and Telecom Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 3.7.1 Description of the Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 3.7.2 Fractional Ornstein-Uhlenbeck Gaussian Processes . . . . . 262 3.7.3 Telecom Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263 3.7.4 Representations of Telecom Processes . . . . . . . . . . . . . . . . 263 3.7.5 Application of Telecom Processes . . . . . . . . . . . . . . . . . . . . 265 3.8 Multifractal Models and the Influence of Small Scales . . . . . . . . 267 3.8.1 Multifractal Brownian Motion . . . . . . . . . . . . . . . . . . . . . . 267 3.8.2 Wavelet-Based Multifractal Models . . . . . . . . . . . . . . . . . . 270 3.8.3 Characteristics of Multifractal Models . . . . . . . . . . . . . . . . 280 3.8.4 Multifractal Formalism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292 3.8.5 Construction of Cascades . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 3.8.6 Multifractals, Self-Similarity and Long-Range Dependence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308 3.9 Summary of Models for IP Traffic . . . . . . . . . . . . . . . . . . . . . . . . . 316 4 Statistical Estimators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 4.1 Parameter Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 4.1.1 Unbiased Estimators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322 4.1.2 Linear Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 4.1.3 Estimation of the Heavy-Tail Exponent α . . . . . . . . . . . . 335 4.1.4 Maximum Likelihood Method . . . . . . . . . . . . . . . . . . . . . . . 344 4.2 Estimators of Hurst Exponent in IP Traffic . . . . . . . . . . . . . . . . . 349 4.2.1 Absolute Value Method (AVM) . . . . . . . . . . . . . . . . . . . . . 349 4.2.2 Variance Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 4.2.3 Variance of Residuals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 4.2.4 R/S Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356 4.2.5 Log Periodogram – Local and Global . . . . . . . . . . . . . . . . 359 4.2.6 Maximum Likelihood and Whittle Estimator . . . . . . . . . . 363 4.2.7 Wavelet Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368 4.2.8 Quadratic Variation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379 4.2.9 Remarks on Estimators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380 5 Performance of IP: Waiting Queues and Optimization . . . . . 383 5.1 Queueing of IP Traffic for Perturbation with Long-Range Dependence Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383 5.1.1 Waiting Queues for Models with Fractional Brownian Motion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384 5.1.2 Queueing in Multiscaling FBM . . . . . . . . . . . . . . . . . . . . . . 392 5.1.3 Fractional L´evy Motion and Queueing in IP Traffic Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395 5.1.4 Queueing Theory and Performance for Multifractal Brownian Motion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405 5.2 Queueing in Multifractal Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . 411 5.2.1 Queueing in Multifractal Tree Models . . . . . . . . . . . . . . . . 411 5.2.2 Queueing Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417 5.3 Traffic Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 5.3.1 Mixed Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 5.3.2 Optimization of Network Flows . . . . . . . . . . . . . . . . . . . . . 424 5.3.3 Rate Control: Shadow Prices and Proportional Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436 5.3.4 Optimization for Stochastic Perturbation . . . . . . . . . . . . . 442 5.3.5 Optimization of Network Flows Using an Utility Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479