Deterministic Network Calculus

Deterministic Network Calculus

by Anne Bouillard, Marc Boyer, Euriell Le Corronc
Released December 2018
Publisher(s): Wiley-ISTE
ISBN: 9781848218529

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to live online training experiences, plus books, videos, and digital content from O’Reilly and nearly 200 trusted publishing partners.

Start your free trial

Book description

Deterministic network calculus is a theory based on the (min,plus) algebra. Its aim is to compute worst-case performance bounds in communication networks. Our goal is to provide a comprehensive view of this theory and its recent advances, from its theoretical foundations to its implementations.

The book is divided into three parts. The first part focuses on the (min,plus) framework and its algorithmic aspects. The second part defines the network calculus model and analyzes one server in isolation. Different service and scheduling policies are discussed, particularly when data is packetized. The third part is about network analyses. Pay burst only once and pay multiplexing only once phenomena are exhibited, and different analyses are proposed and compared. This includes the linear programming approaches that compute tight performance bounds. Finally, some partial results on the stability are detailed.

Table of contents

  1. Cover
  2. Acknowledgments
  3. Introduction
  4. 1 Basic Model: Single Server, Single Flow
    1. 1.1. Modeling principles
    2. 1.2. Constant rate server
    3. 1.3. Flow model
    4. 1.4. Server model
    5. 1.5. Delay and memory usage models
    6. 1.6. Summary
  5. PART 1: (min,plus) Functions and Algorithms
    1. 2 The (min,plus) Functions Semi-ring
      1. 2.1. The (min,plus)-based dioids
      2. 2.2. Sub-additive closure
      3. 2.3. Deconvolution
      4. 2.4. Link with (max,plus) dioid
      5. 2.5. Summary
    2. 3 Sub-classes of Functions
      1. 3.1. Usual functions
      2. 3.2. Non-negative and non-decreasing functions
      3. 3.3. Concave and convex functions
      4. 3.4. Summary
    3. 4 Efficient Computations for (min,plus) Operators
      1. 4.1. Classes of functions with finite representations
      2. 4.2. Piecewise linear concave/convex functions
      3. 4.3. A stable class of functions
      4. 4.4. Containers of (min,plus) functions
      5. 4.5. Implementations
  6. PART 2: Network Calculus: Local Analysis
    1. 5 Network Calculus Basics: a Server Crossed by a Single Flow
      1. 5.1. Arrival curve
      2. 5.2. Service curves
      3. 5.3. From curves to performance guarantees
      4. 5.4. Bibliographic and historic notes
      5. 5.5. Summary
    2. 6 Single Flow Crossing Several Servers
      1. 6.1. Servers in tandem
      2. 6.2. Control design
      3. 6.3. Essential use cases
      4. 6.4. Summary
    3. 7 Multiple Flows Crossing One Server
      1. 7.1. MIMO servers and aggregation of flows
      2. 7.2. Blind or arbitrary multiplexing
      3. 7.3. Some service policies
      4. 7.4. Summary
    4. 8 Packets
      1. 8.1. Packetizer
      2. 8.2. Packet-based schedulers
      3. 8.3. Bibliographic notes
      4. 8.4. Summary
    5. 9 A Hierarchy of Service Curves
      1. 9.1. Different types of service curves
      2. 9.2. Comparison of service curves
      3. 9.3. No intermediate service curve
  7. PART 3: Network Calculus: Global Analysis
    1. 10 Modular Analysis: Computing with Curves
      1. 10.1. Network model
      2. 10.2. Some special topologies
      3. 10.3. The pay multiplexing only once phenomenon
      4. 10.4. Per-flow analysis of networks
      5. 10.5. NP-hardness of computing tight bounds
      6. 10.6. Conclusion
    2. 11 Tight Worst-case Performances
      1. 11.1. Tandem networks under arbitrary multiplexing
      2. 11.2. Tandem networks under the FIFO policy
      3. 11.3. Bibliographic notes
    3. 12 Stability in Networks with Cyclic Dependencies
      1. 12.1. Network stability
      2. 12.2. The fix-point method: sufficient condition for global stability
      3. 12.3. Universally stable service policies
      4. 12.4. Instability of some systems
      5. 12.5. Bibliographic notes
  8. Conclusion
  9. Appendix
  10. List of Symbols
  11. References
  12. Index
  13. End User License Agreement

Product information

  • Title: Deterministic Network Calculus
  • Author(s): Anne Bouillard, Marc Boyer, Euriell Le Corronc
  • Release date: December 2018
  • Publisher(s): Wiley-ISTE
  • ISBN: 9781848218529