Contents
Introduction xiii
I A First Course in Network Calculus 1
1 Network Calculus 3
1.1 Models for Data Flows . . ................................... 3
1.1.1 Cumulative Functions, Discrete Time versus Continuous Time Models ........ 3
1.1.2 Backlog and Virtual Delay ............................... 5
1.1.3 Example: The Playout Buffer ............................. 6
1.2 Arrival Curves .......................................... 7
1.2.1 Definition of an Arrival Curve . ............................ 7
1.2.2 Leaky Bucket and Generic Cell Rate Algorithm .................... 10
1.2.3 Sub-additivity and Arrival Curves ........................... 14
1.2.4 Minimum Arrival Curve . . .............................. 16
1.3 Service Curves ......................................... 18
1.3.1 Definition of Service Curve .............................. 18
1.3.2 Classical Service Curve Examples . . . . . ...................... 20
1.4 Network Calculus Basics . ................................... 22
1.4.1 Three Bounds . . . . . . ................................ 22
1.4.2 Are the Bounds Tight ? ................................. 27
1.4.3 Concatenation . . . . . ................................ 28
1.4.4 Improvement of Backlog Bounds ........................... 29
1.5 Greedy Shapers . . . . . . . . . ................................ 30
1.5.1 Definitions ....................................... 30
1.5.2 Input-Output Characterization of Greedy Shapers ................... 31
1.5.3 Properties of Greedy Shapers . ............................. 33
1.6 Maximum Service Curve, Variable and Fixed Delay . . . ................... 34
1.6.1 Maximum Service Curves . .............................. 34
1.6.2 Delay from Backlog .................................. 38
1.6.3 Variable versus Fixed Delay .............................. 39
vii
