Network traffic engineering : stochastic models and applications /
Andrea Baiocchi, University of Roma, Rome, IT.
- First edition.
- 1 PDF.
Includes bibliographical references and index.
Preface xv -- Acronyms xvii -- Part I Models for Service Systems -- 1 Introduction 3 -- 1.1 Network Traffic Engineering: what, why, how 3 -- 1.2 The art of modeling 7 -- 1.3 An example: delay equalization 11 -- 1.3.1 Model setting 12 -- 1.3.2 Analysis by equations 13 -- 1.3.3 Analysis by simulation 16 -- 1.3.4 Takeaways 18 -- 1.4 Outline of the book 18 -- 1.4.1 Plan 18 -- 1.4.2 Use 21 -- 1.4.3 Notation 23 -- 1.5 Further readings 24 -- Problems 25 -- 2 Service systems and queues 27 -- 2.1 Service system structure 27 -- 2.2 Arrival and service processes 28 -- 2.3 The queue as a service system model 32 -- 2.4 Queues in equilibrium 33 -- 2.4.1 Queues and stationary processes 33 -- 2.4.2 Little's law 37 -- 2.5 Palm's distributions for a queue 40 -- 2.6 The traffic process 44 -- 2.7 Performance metrics 46 -- 2.7.1 Throughput 47 -- 2.7.2 Utilization 49 -- 2.7.3 Loss 49 -- 2.7.4 Delay 51 -- 2.7.5 Age of Information 51 -- Problems 54 -- 3 Stochastic models for network traffic 59 -- 3.1 Introduction 59 -- 3.2 The Poisson process 60 -- 3.2.1 Light versus heavy tails 65 -- 3.2.2 Inhomogeneous Poisson process 66 -- 3.2.3 Poisson process in multidimensional spaces 70 -- 3.2.4 Testing for Poisson 80 -- 3.3 The Markovian Arrival Process 83 -- 3.4 Renewal processes 86 -- 3.4.1 Residual interevent time and renewal paradox 91 -- 3.4.2 Superposition of renewal processes 93 -- 3.4.3 Alternating renewal processes 94 -- 3.4.4 Renewal reward processes 95 -- 3.5 Birthdeath processes 97 -- 3.6 Branching processes 102 Problems 107 -- Part II Queues -- 4 Single server queues 113 -- 4.1 Introduction and notation 113 -- 4.2 The Embedded Markov Chain analysis of the M/G/1 queue 114 -- 4.2.1 Queue length 116 -- 4.2.2 Waiting time 120 -- 4.2.3 Busy period and idle time 123 -- 4.2.4 Remaining service time 126 -- 4.2.5 Output process 127 -- 4.2.6 Evaluation of the probabilities 129 -- 4.3 The M/G/1/K queue 130 -- 4.3.1 Exact solution 130 -- 4.3.2 Asymptotic approximation for large K 133 -- 4.4 Numerical evaluation of the queue length PDF 141. 4.5 A special case: the M/M/1 queue 143 -- 4.6 Optimization of a single server queue 145 -- 4.6.1 Maximization of net profit 146 -- 4.6.2 Minimization of age of information 149 -- 4.7 The G/M/1 queue 152 -- 4.8 Matrixgeometric queues 159 -- 4.8.1 Quasi BirthDeath (QBD) processes 159 -- 4.8.2 M/G/1 and G/M/1 structured processes 161 -- 4.9 A general result on single server queues 164 -- Problems 167 -- 5 Multiserver queues 171 -- 5.1 Introduction 171 -- 5.2 The Erlang loss system 173 -- 5.2.1 Insensitivity property of the Erlang loss system 182 -- 5.2.2 A finite population model 183 -- 5.2.3 NonPoisson input traffic 184 -- 5.2.4 Multiclass Erlang loss system 189 -- 5.3 Application of the Erlang loss model to cellular radio access network 192 -- 5.3.1 Cell dimensioning under Quality of Service constraints 193 -- 5.3.2 Number of handoffs in a connection lifetime 198 -- 5.3.3 Blocking in a cell with user mobility 199 -- 5.3.4 Tradeoff between location updating and paging 201 -- 5.3.5 Dimensioning of a cell with two service classes 202 -- 5.4 The M/M/m queue 204 -- 5.4.1 Finite queue size model 209 -- 5.4.2 Resource sharing versus isolation 209 -- 5.5 Infinite server queues 212 -- 5.5.1 Analysis of message propagation in a linear network 216 -- Problems 221 -- 6 Priorities and scheduling 227 -- 6.1 Introduction 227 -- 6.2 Conservation law 230 -- 6.3 M/G/1 priority queueing 233 -- 6.3.1 NonFCFS queueing disciplines 234 -- 6.3.2 HeadOfLine (HOL) priorities 237 -- 6.3.3 Preemptresume priority 243 -- 6.3.4 Shortest Job First 244 -- 6.3.5 Shortest Remaining Processing Time 245 -- 6.3.6 The μC rule 247 -- 6.4 Processor sharing 248 -- 6.4.1 The M/G/1 Processor Sharing model 248 -- 6.4.2 Generalized Processor Sharing 250 -- 6.4.3 Weighted Fair Queueing 255 -- 6.4.4 Creditbased scheduling 258 -- 6.4.5 Deficit Round Robin scheduling 262 -- 6.4.6 Least Attained Service scheduling 263 -- 6.5 Miscellaneous scheduling 266 -- 6.5.1 Scheduling on a radio link 266 -- 6.5.2 Job dispatching 271. 6.6 Optimal scheduling 276 -- 6.6.1 Anticipative systems 277 -- 6.6.2 Serversharing, nonanticipative systems 277 -- 6.6.3 Nonserversharing, nonanticipative systems 278 -- Problems 279 -- 7 Queueing networks 283 -- 7.1 Structure of a queueing network and notation 283 -- 7.2 Open queueing networks 284 -- 7.2.1 Optimization of network capacities 295 -- 7.2.2 Optimal routing 297 -- 7.2.3 Braess paradox 300 -- 7.3 Closed queueing networks 303 -- 7.3.1 Arrivals See Time Averages (ASTA) 306 -- 7.3.2 Buzen's algorithm for the computation of the normalization constant 307 -- 7.3.3 Mean Value Analysis 308 -- 7.4 Loss networks 315 -- 7.4.1 Erlang fixedpoint approximation 319 -- 7.4.2 Alternate routing 323 -- 7.5 Stability of queueing networks 326 -- 7.5.1 Definition of stability 329 -- 7.5.2 Turning a stochastic discrete queueing network into a deterministic fluid network 331 -- Appendix 334 -- Problems 337 -- 8 Bounds and approximations 341 -- 8.1 Introduction 341 -- 8.2 Bounds for the G/G/1 queue 343 -- 8.2.1 Mean Value Analysis 345 -- 8.2.2 Output process 347 -- 8.2.3 Upper and lower bounds of the mean waiting time 348 -- 8.2.4 Upper bound of the waiting time probability distribution 350 -- 8.3 Bounds for the G/G/m queue 352 -- 8.4 Approximate analysis of isolated G/G queues 355 -- 8.4.1 Approximations from bounds 356 -- 8.4.2 Approximation of the arrival or service process 356 -- 8.4.3 Reflected Brownian Motion approximation 358 -- 8.4.4 Heavytraffic approximation 361 -- 8.5 Approximate analysis of a network of G/G/1 queues 364 -- 8.5.1 Superposition of flows 365 -- 8.5.2 Flow through a queue 365 -- 8.5.3 Bernoulli splitting of a flow 366 -- 8.5.4 Putting pieces together: the decomposition method 366 -- 8.5.5 Bottleneck approximation for closed queueing networks 378 -- 8.6 Fluid models 379 -- 8.6.1 Deterministic fluid model 379 -- 8.6.2 From fluid to diffusion model 386 -- 8.6.3 Stochastic fluid model 389 -- 8.6.4 Steadystate analysis 392 -- 8.6.5 First passage times 398. 8.6.6 Application of the stochastic fluid model to a multiplexer with ON-OFF traffic sources 400 -- Problems 403 -- Part III Networked Systems and Protocols -- 9 Multiple access 409 -- 9.1 Introduction 409 -- 9.2 Slotted ALOHA 411 -- 9.2.1 Analysis of the na ıve Slotted ALOHA 412 -- 9.2.2 Finite population Slotted ALOHA 416 -- 9.2.3 Stabilized Slotted ALOHA 422 -- 9.3 Pure ALOHA with variable packet times 426 -- 9.4 Carrier Sense Multiple Access (CSMA) 431 -- 9.4.1 Finite population model of CSMA 435 -- 9.4.2 Multipacket reception CSMA 438 -- 9.4.3 Stability of CSMA 447 -- 9.4.4 Delay analysis of stabilized CSMA 452 -- 9.5 Analysis of the WiFi MAC protocol 455 -- 9.5.1 Outline of the IEEE 802.11 DCF protocol 456 -- 9.5.2 Model of CSMA/CA 459 -- 9.5.3 Optimization of backoff parameters 473 -- 9.5.4 Fairness of CSMA/CA 481 -- Appendix 487 -- Problems 489 -- 10 Congestion control 493 -- 10.1 Introduction 493 -- 10.2 Congestion control architecture in the Internet 497 -- 10.3 Evolution of congestion control in the Internet 500 -- 10.3.1 TCP Reno 500 -- 10.3.2 TCP CUBIC 507 -- 10.3.3 TCP Vegas 509 -- 10.3.4 Data Center TCP (DCTCP) 512 -- 10.3.5 Bottleneck Bandwidth and RTT (BBR) 514 -- 10.4 Traffic engineering with TCP 520 -- 10.5 Fluid model of a single TCP connection congestion control 522 -- 10.5.1 Classic TCP with fixed capacity bottleneck link 523 -- 10.5.2 Classic TCP with variable capacity bottleneck link 525 -- 10.5.3 Application to wireless links 536 -- 10.6 Fluid model of multiple TCP connections congestion control 540 -- 10.6.1 Negligible buffering at the bottleneck 540 -- 10.6.2 Classic TCP with droptail buffer at the bottleneck 541 -- 10.6.3 Classic TCP with AQM at the bottleneck 542 -- 10.6.4 Data Center TCP 543 -- 10.7 Fairness and congestion control 545 -- 10.8 Network Utility Maximization (NUM) 548 -- 10.9 Challenges to TCP 553 -- 10.9.1 Fatlong pipes 554 -- 10.9.2 Wireless channels 556 -- 10.9.3 Bufferbloat 557 -- 10.9.4 Interaction with applications 558. Appendix 559 -- Problems 564 -- 11 Quality of Service guarantees 567 -- 11.1 Introduction 567 -- 11.2 Deterministic service guarantees 568 -- 11.2.1 Arrival curves 571 -- 11.2.2 Service curves 575 -- 11.2.3 Performance bounds 578 -- 11.2.4 Regulators 579 -- 11.2.5 Network calculus 584 -- 11.3 Stochastic service guarantees 596 -- 11.3.1 Multiplexing with marginal buffer size 596 -- 11.3.2 Multiplexing with nonnegligible buffer size 603 -- 11.3.3 Effective bandwidth 605 -- 11.3.4 Network analysis and dimensioning 611 -- 11.4 Further readings 616 -- Appendix 617 -- Problems 622 -- A Refresher of probability, random variables and stochastic processes 623 -- A.1 Probability 623 -- A.2 Random variables 625 -- A.3 Transforms of probability distribution functions 627 -- A.4 Inequalities and limit theorems 631 -- A.4.1 Markov inequality 631 -- A.4.2 Chebychev inequality 632 -- A.4.3 Jensen inequality 632 -- A.4.4 Chernov bound 633 -- A.4.5 Union bound 633 -- A.4.6 Central Limit Theorem (CLT) 634 -- A.5 Stochastic processes 634 -- A.6 Markov Chains 635 -- A.6.1 Classification of states 636 -- A.6.2 Recurrence 637 -- A.6.3 Visits to a state 640 -- A.6.4 Asymptotic behavior and steadystate 641 -- A.6.5 Absorbing Markov chains 646 -- A.6.6 Continuoustime Markov processes 647 -- A.6.7 Sojourn times in process states 649 -- A.6.8 Reversibility 650 -- A.6.9 Uniformization 651 -- A.7 Wiener process (Brownian Motion) 652 -- A.7.1 Wiener process with an absorbing barrier 654 -- A.7.2 Wiener process with a reflecting barrier 655 -- References 657 -- Index 669.
Restricted to subscribers or individual electronic text purchasers.
"This book provides an advanced level queuing theory guide for students with a strong mathematical background who are interested in analytic modeling of communication networks. It begins with the basics of queueing theory before moving on to more advanced levels. The topics covered in the book and their organization and presentation come out of research work, project development, teaching activity and discussions drawn from the author's professional experience. Topics are selected for their relevance, so as to provide a consistent view of most useful models. Examples are taken from real technical problems or engineering applications of interest to current and foreseeable future systems (e.g., LTE, Wi-Fi, ad-hoc networks, automated vehicles, reliability). They show how insight into real-world problems can be gained by means of quantitative modeling"--