Network calculus

Informations

• Publié par: angueran
• Nombre de lectures: 230
• Langue: Français
• Poids de l'ouvrage: 2 Mo

Extrait

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, Maelle¨ , Audraine et Elias Amamer` e —- JL A mes parents —- PT Pour eviter´ les grumeaux ´Qui encombrent les reseaux Il fallait, c’est complique,´ Maˆıtriser les seaux perces´ Branle-bas dans les campus On pourra dorena´ vant Calculer plus simplement Graceˆ a` l’algebre` Min-Plus Foin des obscures astuces Pour estimer les delais´ 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 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 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. 1 1 2004 Jan 7, JL Bug fix in Proposition 2.4.1 (ν> instead ofν< )h−1 h−1 2004, May 10, JL Typo fixed in Definition 1.2.4 (thanks to Richard Bradford)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 Curve18 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 Delay39 viiviii CONTENTS 1.7 Handling Variable Length Packets . . .............................40 1.7.1 An Example of Irregularity Introduced by Variable Length Packets . .........40 1.7.2 The Packetizer . . ...................................41 1.7.3 A Relation between Greedy Shaper and Packetizer ..................45 1.7.4 Packetized Greedy Shaper ...............................48 1.8 Effective Bandwidth and Equivalent Capacity . . . ......................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 1.9 Proof of Theorem 1.4.5 . . . . .................................56 1.10 Bibliographic Notes.......................................59 1.11 Exercises . . ..........................................59 2 Application to the Internet 67 2.1 GPS and Guaranteed Rate Nodes . . ..............................67 2.1.1 Packet Scheduling ...................................67 2.1.2 GPS and a Practical Implementation (PGPS) .....................68 2.1.3 Guaranteed Rate (GR) Nodes and the Max-Plus Approach ..............70 2.1.4 Concatenation of GR nodes72 2.1.5 Proofs . . ........................................73 2.2 The Integrated Services Model of the IETF ..........................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 2.2.6 Flow Setup with ATM . ................................79 2.3 Schedulability ..........................................79 2.3.1 EDF Schedulers .80 2.3.2 SCED [73] .................................82 2.3.3 Buffer Requirements . .86 2.4 Application to Differentiated Services . . ...........................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 2.4.4 Static Earliest Time First (SETF)............................95 2.5 Bibliographic Notes.......................................97 2.6 Exercises . . ..........................................97CONTENTS ix II Mathematical Background 101 3 Basic Min-plus and Max-plus Calculus 103 3.1 Calculus........................................103 3.1.1 Infimum and Minimum.................................103 3.1.2 Dioid (R∪{+∞},∧, +) ...............................104 3.1.3 A Catalog of Wide-sense Increasing Functions ....................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 Convolution110 3.1.7 Sub-additive Functions . ................................116 3.1.8ve Closure ..................................118 3.1.9 Min-plus Deconvolution . . . .............................12 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 . ...................................131 4.1.2 Operators ........................................133 4.1.3 A Catalog of Operators .................................133 4.1.4 Upper and Lower Semi-Continuous Operators.....................134 4.1.5 Isotone Operators .135 4.1.6 Linear .136 4.1.7 Causal Operators . ...................................139 4.1.8 Shift-Invariant Operators . . ..............................140 4.1.9 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 CONTENTS III A Second Course in Network Calculus 153 5 Optimal Multimedia Smoothing 155 5.1 Problem Setting .........................................15 5.2 Constraints Imposed by Lossless Smoothing . . . . . . . ...................156 5.3 Minimal Requirements on Delays and Playback Buffer . . ..................157 5.4 Optimal Smoothing Strategies . ................................158 5.4.1 Maximal Solution . . .158 5.4.2 Minimal . . . .158 5.4.3 Set of Optimal Solutions159 5.5 Optimal Constant Rate Smoothing . ..............................159 5.6 Smoothing versus Greedy Shaping ..........................163 5.7 Comparison with Delay Equalization . .............................165 5.8 Lossless Smoothing over Two Networks ............................168 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 5.9 Bibliographic Notes.......................................172 6 Aggregate Scheduling 175 6.1 Introduction ...........................................175 6.2 Transformation of Arrival Curve through Aggregate Scheduling . ..............176 6.2.1 Aggregate Multiplexing in a Strict Service Curve Element . . . . . . . . . .....176 6.2.2 Aggregatexing in a FIFO Service Curve . . . . . . . . .177 6.2.3 Aggregate Multiplexing in a GR Node . . . ......................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 6.4 Stability Results and Explicit Bounds .............................185 6.4.1 The Ring is Stable ...................................186 6.4.2 Explicit Bounds for a Homogeneous ATM Network with Strong Source Rate Con- ditions..........................................189 6.5 Bibliographic Notes.......................................194 6.6 Exercises . .195 7 Adaptive and Packet Scale Rate Guarantees 197 7.1 Introduction ...........................................197 7.2 Limitations of the Service Curve and GR Node Abstractions .................197 7.3 Packet Scale Rate Guarantee . . ................................198 7.3.1 Definition of Pa