E-Book Overview
Network Calculus is a set of recent developments that provide deep insights into flow problems encountered in the Internet and in intranets. The first part of the book is a self-contained, introductory course on network calculus. It presents the core of network calculus, and shows how it can be applied to the Internet to obtain results that have physical interpretations of practical importance to network engineers. The second part serves as a mathematical reference used across the book. It presents the results from Min-plus algebra needed for network calculus. The third part contains more advanced material. It is appropriate reading for a graduate course and a source of reference for professionals in networking by surveying the state of the art of research and pointing to open problems in network calculus and its application in different fields, such as mulitmedia smoothing, aggegate scheduling, adaptive guarantees in Internet differential services, renegotiated reserved services, etc.
E-Book Content
Lecture Notes in Computer Science
Edited by G. Goos, J. Hartmanis and J. van Leeuwen
2050
3
Berlin Heidelberg New York Barcelona Hong Kong London Milan Paris Singapore Tokyo
Jean-Yves Le Boudec Patrick Thiran
Network Calculus A Theory of Deterministic Queuing Systems for the Internet
13
Series Editors Gerhard Goos, Karlsruhe University, Germany Juris Hartmanis, Cornell University, NY, USA Jan van Leeuwen, Utrecht University, The Netherlands Authors Jean-Yves Le Boudec Patrick Thiran EPFL INN Ecublens 1015 Lausanne, Switzerland E-mail:{jean-yves.leboudec/patrick.thiran}@epfl.ch
Cataloging-in-Publication Data applied for Die Deutsche Bibliothek - CIP-Einheitsaufnahme Le Boudec, Jean-Yves: Network calculus : a theory of deterministic queuing systems for the Internet / Jean-Yves Le Boudec ; Patrick Thiran. - Berlin ; Heidelberg ; New York ; Barcelona ; Hong Kong ; London ; Milan ; Paris ; Singapore ; Tokyo : Springer, 2001 (Lecture notes in computer science ; Vol. 2050) ISBN 3-540-42184-X
CR Subject Classification (1998): C.2, D.4.4, D.4, E.4, H.3.5, H.4.3 ISSN 0302-9743 ISBN 3-540-42184-X Springer-Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. Springer-Verlag Berlin Heidelberg New York a member of BertelsmannSpringer Science+Business Media GmbH http://www.springer.de © Springer-Verlag Berlin Heidelberg 2001 Printed in Germany Typesetting: Camera-ready by author Printed on acid-free paper SPIN 10781496
06/3142
543210
A Annelies A Joana, Ma¨elle, Audraine et Elias A ma m`ere —- JL A mes parents —- PT
Pour e´ viter 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
Contents Introduction
I A First Course in Network Calculus
xiii
1
1 Network Calculus 3 1.1 Models for Data Flows . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.1 Cumulative Functions, Discrete Time versus Continuous Time Models . . . . . . . . . . . . . . . . . . . . . .