第1页 / 共264页
第2页 / 共264页
第3页 / 共264页
第4页 / 共264页
第5页 / 共264页
第6页 / 共264页
第7页 / 共264页
第8页 / 共264页
Network Calculus.pdf
NETWORK CALCULUS
A Theory of Deterministic Queuing Systems for the Internet
JEAN-YVES LE BOUDEC
PATRICK THIRAN
Online Version of the Book Springer Verlag - LNCS 2050
Version May 10, 2004
2
A Annelies
A Joana, Ma¨elle, Audraine et Elias
A ma m`ere
—- JL
A mes parents
—- PT
Pour ´eviter les grumeaux
Qui encombrent les r´eseaux
Il fallait, c’est compliqu´e,
Maˆıtriser les seaux perc´es
Branle-bas dans les campus
On pourra dor´enavant
Calculer plus simplement
Grˆace `a l’alg`ebre Min-Plus
Foin des obscures astuces
Pour estimer les d´elais
Et la gigue des paquets
Place `a “Network Calculus”
—- JL
vi
Summary of Changes
2002 Jan 14, JL Chapter 2: added a better coverage of GR nodes, in particular equivalence with service
curve. Fixed bug in Proposition 1.4.1
2002 Jan 16, JL Chapter 6: M. Andrews brought convincing proof that conjecture 6.3.1 is wrong. Re-
designed Chapter 6 to account for this. Removed redundancy between Section 2.4 and Chapter 6.
Added SETF to Section 2.4
2002 Feb 28, JL Bug fixes in Chapter 9
2002 July 5, JL Bug fixes in Chapter 6; changed format for a better printout on most usual printers.
2003 June 13, JL Added concatenation properties of non-FIFO GR nodes to Chapter 2. Major upgrade of
Chapter 7. Reorganized Chapter 7. Added new developments in Diff Serv. Added properties of PSRG
for non-FIFO nodes.
2003 June 25, PT Bug fixes in chapters 4 and 5.
2003 Sept 16, JL Fixed bug in proof of theorem 1.7.1, proposition 3. The bug was discovered and brought
to our attention by Franc¸ois Larochelle.
2004 Jan 7, JL Bug fix in Proposition 2.4.1 (ν > 1
2004, May 10, JL Typo fixed in Definition 1.2.4 (thanks to Richard Bradford)
h−1 instead of ν < 1
h−1)
Contents
Introduction
I A First Course in Network Calculus
xiii
1
1 Network Calculus
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1.3 Service Curves
1.2 Arrival Curves .
1.1 Models for Data Flows .
Sub-additivity and Arrival Curves .
1.3.1 Definition of Service Curve
1.3.2 Classical Service Curve Examples . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
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
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
3
3
3
5
6
7
1.2.1 Definition of an Arrival Curve . .
7
1.2.2 Leaky Bucket and Generic Cell Rate Algorithm . . . . . . . . . . . . . . . . . . . . 10
1.2.3
. 14
1.2.4 Minimum Arrival Curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
. 20
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.4.1 Three Bounds . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.4.2 Are the Bounds Tight ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.4.3 Concatenation .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
. 29
1.4.4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
. 30
.
Input-Output Characterization of Greedy Shapers . . . . . . . . . . . . . . . . . . . 31
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
1.5 Greedy Shapers .
1.5.1 Definitions
1.5.2
1.5.3
1.4 Network Calculus Basics .
.
. . . . . . . . . . . . . . . . . . . . .
Improvement of Backlog Bounds
. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
vii
viii
CONTENTS
.
. .
1.7 Handling Variable Length Packets
1.8 Effective Bandwidth and Equivalent Capacity . . .
Packetized Greedy Shaper
. . . . . . . . . . . . . . . . .
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
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
. . . . . . . . . 40
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
. 45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
. . . . . . . . . . . . . . . . . . . . . . 53
1.8.1 Effective Bandwidth of a Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
1.8.2 Equivalent Capacity .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
1.8.3 Example: Acceptance Region for a FIFO Multiplexer . . . . . . . . . . . . . . . . . 55
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
. 59
.
.
. 59
.
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.9 Proof of Theorem 1.4.5 .
.
1.10 Bibliographic Notes .
1.11 Exercises
.
.
. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2 Application to the Internet
2.1 GPS and Guaranteed Rate Nodes . . .
.
.
.
.
.
2.2 The Integrated Services Model of the IETF .
Proofs .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
Packet Scheduling .
2.1.1
2.1.2 GPS and a Practical Implementation (PGPS)
2.1.3 Guaranteed Rate (GR) Nodes and the Max-Plus Approach .
2.1.4 Concatenation of GR nodes
2.1.5
.
67
. 67
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
. . . . . . . . . . . . . . . . . . . . . 68
. 70
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
. 73
.
. 75
2.2.1 The Guaranteed Service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
2.2.2 The Integrated Services Model for Internet Routers . . . . . . . . . . . . . . . . . . 75
2.2.3 Reservation Setup with RSVP . . . .
. 76
2.2.4 A Flow Setup Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
2.2.5 Multicast Flows .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Flow Setup with ATM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
2.2.6
.
. 79
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
2.3.1 EDF Schedulers
2.3.2
SCED Schedulers [73] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
2.3.3 Buffer Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
. 86
2.4.1 Differentiated Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
2.4.2 An Explicit Delay Bound for EF . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
2.4.3 Bounds for Aggregate Scheduling with Dampers . . . . . . . . . . . . . . . . . .
. 93
Static Earliest Time First (SETF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
2.4.4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.5 Bibliographic Notes .
.
2.6 Exercises
.
.
.
.
.
2.3 Schedulability .
.
.
.
.
2.4 Application to Differentiated Services . . .
.
CONTENTS
II Mathematical Background
3 Basic Min-plus and Max-plus Calculus
ix
101
103
3.1 Min-plus Calculus .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 103
Infimum and Minimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.1.1
3.1.2 Dioid (R ∪ {+∞},∧, +)
3.1.3 A Catalog of Wide-sense Increasing Functions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
. . . . . . . . . . . . . . . . . . . . 105
3.1.4
Pseudo-inverse of Wide-sense Increasing Functions . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
. 108
3.1.5 Concave, Convex and Star-shaped Functions
. . . . . . . . . . . . . . . . . . . . . 109
3.1.6 Min-plus Convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
3.1.7
3.1.8
Sub-additive Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
Sub-additive Closure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
3.1.9 Min-plus Deconvolution . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 122
3.1.10 Representation of Min-plus Deconvolution by Time Inversion . . .
. . . . . . . . . 125
3.1.11 Vertical and Horizontal Deviations . . . . .
. . . . . . . . . . . . . . . . . . . . .
. 128
3.2 Max-plus Calculus
.
.
.
.
.
.
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
3.2.1 Max-plus Convolution and Deconvolution .
. . . . . . . . . . . . . . . . . . . . . . 129
3.2.2 Linearity of Min-plus Deconvolution in Max-plus Algebra .
.
.
.
.
.
.
.
.
.
.
.
.
. 129
3.3 Exercises
.
.
.
.
.
.
.
.
.
.
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. 130
4 Min-plus and Max-Plus System Theory
131
4.1 Min-Plus and Max-Plus Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
4.1.1 Vector Notations .
4.1.2 Operators .
.
.
.
.
.
.
.
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.1.3 A Catalog of Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.1.4 Upper and Lower Semi-Continuous Operators . . . . . . . . . . . . . . . . . . . . . 134
4.1.5
Isotone Operators .
4.1.6 Linear Operators .
4.1.7 Causal Operators .
.
.
.
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. 136
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
4.1.8
4.1.9
Shift-Invariant Operators . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 140
Idempotent Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4.2 Closure of an Operator
.
.
.
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4.3 Fixed Point Equation (Space Method)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
4.3.1 Main Theorem .
.
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
4.3.2 Examples of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
4.4 Fixed Point Equation (Time Method) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
4.5 Conclusion .
.
.
.
.
.
.
.
.
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
x
III A Second Course in Network Calculus
CONTENTS
153
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
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
155
. 155
.
. . . . . . . . . . . . . . . . . . . . . . 156
. 157
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
Set of Optimal Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
5.5 Optimal Constant Rate Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
5.6 Optimal Smoothing versus Greedy Shaping . . . . . . . . . . . . . . . . . . . . . . . . . . 163
5.7 Comparison with Delay Equalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
. 168
5.8 Lossless Smoothing over Two Networks .
5.8.1 Minimal Requirements on the Delays and Buffer Sizes for Two Networks . . . . . . 169
5.8.2 Optimal Constant Rate Smoothing over Two Networks . . . . . . . . . . . . . . . . 171
. 172
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.9 Bibliographic Notes .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6 Aggregate Scheduling
.
Introduction .
6.1
6.2 Transformation of Arrival Curve through Aggregate Scheduling . .
6.2.1 Aggregate Multiplexing in a Strict Service Curve Element
6.2.2 Aggregate Multiplexing in a FIFO Service Curve Element
6.2.3 Aggregate Multiplexing in a GR Node . . .
175
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
. 176
.
. . . . . . . . . 176
. . . . . . . . . 177
. . . . . . . . . . . . . . . . . . . . . . 181
6.3 Stability and Bounds for a Network with Aggregate Scheduling . . . . . . . . . . . . . . . . 181
6.3.1 The Issue of Stability .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
6.3.2 The Time Stopping Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
6.4.1 The Ring is Stable .
6.4.2 Explicit Bounds for a Homogeneous ATM Network with Strong Source Rate Con-
6.4 Stability Results and Explicit Bounds
.
. . . . .
. . . . .
.
.
.
.
.
.
.
.
.
ditions .
.
6.5 Bibliographic Notes .
6.6 Exercises
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
.
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
.
.
.
.
.
.
.
Introduction .
7 Adaptive and Packet Scale Rate Guarantees
197
. 197
7.1
7.2 Limitations of the Service Curve and GR Node Abstractions
. . . . . . . . . . . . . . . . . 197
7.3 Packet Scale Rate Guarantee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
. . . . . . . . . . . . . . . . . . . . . . 198
Practical Realization of Packet Scale Rate Guarantee . . . . . . . . . . . . . . . . . 202
7.3.1 Definition of Packet Scale Rate Guarantee .
7.3.2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
