Network Calculus A Theory of Deterministic Queuing Systems for the Internet.pdf

NETWORK CALCULUS

A Theory of Deterministic Queuing Systems for the Internet

J EAN -Y VES L E B OUDEC

P ATRICK T HIRAN

Online Version of the Book Springer Verlag - LNCS 2050

Version May 10, 2004

A Annelies

A Joana, Maelle, Audraine et Elias

A ma mere

- 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 dorenavant

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

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 xes in Chapter 9

2002 July 5, JL Bug xes 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 xes 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 Fran¸ois Larochelle.

2004 Jan 7, JL Bug x in Proposition 2.4.1 ( >

instead of <

h1 )

2004, May 10, JL Typo xed in Denition 1.2.4 (thanks to Richard Bradford)

Contents

Introduction

xiii

I A First Course in Network Calculus

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 Denition 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 Denition 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 Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: