Network Calculus: A Theory of Deterministic Queuing Systems for the Internet (Lecture Notes in Computer Science, 2050)

✍ Scribed by Le Boudec, Thiran

• Publisher: Springer
• Year: 2001
• Tongue: English
• Leaves: 280
• Category: Library

✦ Synopsis

Network Calculus is a set of recent developments that provide deep insights into flow problems encountered in the Internet and in intranets. The first part of the book is a self-contained, introductory course on network calculus. It presents the core of network calculus, and shows how it can be applied to the Internet to obtain results that have physical interpretations of practical importance to network engineers. The second part serves as a mathematical reference used across the book. It presents the results from Min-plus algebra needed for network calculus. The third part contains more advanced material. It is appropriate reading for a graduate course and a source of reference for professionals in networking by surveying the state of the art of research and pointing to open problems in network calculus and its application in different fields, such as mulitmedia smoothing, aggegate scheduling, adaptive guarantees in Internet differential services, renegotiated reserved services, etc.

✦ Table of Contents

Network Calculus
Dedications
Contents
Introduction
What this Book is About
Network Calculus, a System Theory for Computer Networks
Acknowledgement
Network Calculus
1.1 Models for Data Flows
1.1.1 Cumulative Functions, Discrete Time versus Continuous Time Models
1.1.2 Backlog and Virtual Delay
1.1.3 Example: The Playout Buffer
1.2 Arrival Curves
1.2.1 Definition of an Arrival Curve
1.2.2 Leaky Bucket and Generic Cell Rate Algorithm
1.2.3 Sub-additivity and Arrival Curves
1.2.4 Minimum Arrival Curve
1.3 Service Curves
1.3.1 Definition of Service Curve
1.3.2 Classical Service Curve Examples
1.4 Network Calculus Basics
1.4.1 Three Bounds
1.4.2 Are the Bounds Tight?
1.4.3 Concatenation
1.4.4 Improvement of Backlog Bounds
1.5 Greedy Shapers
1.5.1 Definitions
1.5.2 Input-Output Characterization of Greedy Shapers
1.5.3 Properties of Greedy Shapers
1.6 Maximum Service Curve, Variable and Fixed Delay
1.6.1 Maximum Service Curves
1.6.2 Delay from Backlog
1.6.3 Variable versus Fixed Delay
1.7 Handling Variable Length Packets
1.7.1 An Example of Irregularity Introduced by Variable Length Packets
1.7.2 The Packetizer
1.7.3 A Relation between Greedy Shaper and Packetizer
1.7.4 Packetized Greedy Shaper
1.8 Lossless Effective Bandwidth and Equivalent Capacity
1.8.1 Effective Bandwidth of a Flow
1.8.2 Equivalent Capacity
1.8.3 Example: Acceptance Region for a FIFO Multiplexer
1.9 Proof of Theorem 1.4.5
1.10 Bibliographic Notes
1.11 Exercises
Chapter 2: Application of Network Calculus to the Internet
2.1 GPS and Guaranteed Rate Schedulers
2.1.1 Packet Scheduling
2.1.2 GPS and a Practical Implementation (PGPS)
2.1.3 Guaranteed Rate Schedulers
2.2 The Integrated Services Model of the IETF
2.2.1 The Guaranteed Service
2.2.2 The Integrated Services Model for Internet Routers
2.2.3 Reservation Setup with RSVP
2.2.4 A Flow Setup Algorithm
2.2.5 Multicast Flows
2.2.6 Flow Setup with ATM
2.3 Schedulability
2.3.1 EDF Schedulers
2.3.2 SCED Schedulers [65]
2.3.3 Buffer Requirements
2.4 Application to Differentiated Services
2.4.1 Differentiated Services
2.4.2 A Bounding Method for Aggregate Scheduling
2.4.3 An Explicit Delay Bound for Differentiated Services Networks
2.4.4 Bounds for Aggregate Scheduling with Dampers
2.5 Exercises
Chapter 3: Basic Min-plus and Max-plus Calculus
3.1 Min-plus Calculus
3.1.1 Infimum and Minimum
3.1.2 Dioid $\mathcal R cup {+ infty}, wedge, +)$
3.1.3 A Catalog of Wide-sense Increasing Functions
3.1.4 Pseudo-inverse of Wide-sense Increasing Functions
3.1.5 Concave, Convex and Star-shaped Functions
3.1.6 Min-plus Convolution
3.1.7 Sub-additive Functions
3.1.8 Sub-additive Closure
3.1.9 Min-plus Deconvolution
3.1.10 Representation of Min-plus Deconvolution by Time Inversion
3.1.11 Vertical and Horizontal Deviations
3.2 Max-plus Calculus
3.2.1 Max-plus Convolution and Deconvolution
3.2.2 Linearity of Min-plus Deconvolution in Max-plus Algebra
3.3 Exercises
Chapter 4: Min-plus and Max-plus System Theory
4.1 Min-plus and Max-plus Operators
4.1.1 Vector Notations
4.1.2 Operators
4.1.3 A Catalog of Operators
4.1.4 Upper and Lower Semi-continuous Operators
4.1.5 Isotone Operators
4.1.6 Linear Operators
4.1.7 Causal Operators
4.1.8 Shift-invariant Operators
4.1.9 Idempotent Operators
4.2 Closure of an Operator
4.3 Fixed Point Equation (Space Method)
4.3.1 Main Theorem
4.3.2 Examples of Application
4.4 Fixed Point Equation (Time Method)
4.5 Conclusion
Chapter 5: Optimal Multimedia Smoothing
5.1 Problem Setting
5.2 Constraints Imposed by Lossless Smoothing
5.3 Minimal Requirements on Delays and Playback Buffer
5.4 Optimal Smoothing Strategies
5.4.1 Maximal Solution
5.4.2 Minimal Solution
5.4.3 Set of Optimal Solutions
5.5 Optimal Constant Rate Smoothing
5.6 Optimal Smoothing versus Greedy Shaping
5.7 Comparison with Delay Equalization
5.8 Lossless Smoothing over Two Networks
5.8.1 Minimal Requirements on the Delays and Buffer Sizes for Two Networks
5.8.2 Optimal Constant Rate Smoothing over Two Networks
5.9 Bibliographic Notes
Chapter 6: FIFO Systems and Aggregate Scheduling
6.1 Introduction
6.2 General Bounds for Aggregate Scheduling
6.3 Stability of a Network with Aggregate Scheduling
6.3.1 The Open Issue of Stability
6.3.2 The Ring is Stable
6.4 Bounds for a FIFO Service Curve Element
6.5 Bounds for a Network of FIFO CBR Servers
6.5.1 Closed Form Bounds for an ATM Network with Strong Source Rate Conditions
6.5.2 Proof of Theorem 6.5.1
6.6 Bibliographic Notes
6.7 Exercises
Chapter 7: Adaptive and Packet Scale Rate Guarantees
7.1 Introduction
7.2 Adaptive Guarantee
7.2.1 Limitations of the Service Curve Abstraction
7.2.2 Definition of Adaptive Guarantee
7.2.3 Properties of Adaptive Guarantees
7.3 Application to the Internet: Packet Scale Rate Guarantee
7.3.1 Definition of Packet Scale Rate Guarantee
7.3.2 Practical Realization of Packet Scale Rate Guarantee
7.3.3 Proof of Theorem 7.3.1
7.4 Bibliographic Notes
7.5 Exercises
Chapter 8: Time Varying Shapers
8.1 Introduction
8.2 Time Varying Shapers
8.3 Time Invariant Shaper with Non-zero Initial Conditions
8.3.1 Shaper with Non-empty Initial Buffer
8.3.2 Leaky Bucket Shapers with Non-zero Initial Bucket Level
8.4 Time Varying Leaky-Bucket Shaper
8.5 Bibliographic Notes
Chapter 9: Systems with Losses
9.1 A Representation Formula for Losses
9.1.1 Losses in a Finite Storage Element
9.1.2 Losses in a Bounded Delay Element
9.2 Application 1: Bound on Loss Rate
9.3 Application 2: Bound on Losses in Complex Systems
9.3.1 Bound on Losses by Segregation between Buffer and Policer
9.3.2 Bound on Losses in a VBR Shaper
9.4 Solution to Skohorkhod’s Reflection Problem with Two Boundaries
9.5 Bibliographic Notes
Bibliography
Index