文档介绍：NETWORK CALCULUS
A Theory of Deterministic Queuing Systems for the
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
A ma mer` e
—- JL
A mes parents
—- PT
Pour eviter´ les grumeaux
Qui brent les reseaux´
Il fallait, c’plique,´
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
2002 Jan 16, JL Chapter 6: M. Andrews brought convincing proof that conjecture is wrong. Re-
designed Chapter 6 to account for this. Removed redundancy between Section and Chapter 6.
Added SETF to Section
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. anized 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 , 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 (ν> h−1 instead of ν< h−1 )
2004, May 10, JL Typo fixed in Definition (thanks to Richard Bradford)
Contents
Introduction xiii
I A First Course work Calculus 1
work Calculus 3
Models for Data Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Cumulative Functions, Discrete Time versus Continuous Time Models . . . . . . . .