Cover image for Deterministic Network Calculus

Deterministic Network Calculus

Author Euriell Le Corronc , Marc Boyer , Anne Bouillard
Release Date: 2018/12/01
ISBN: 9781848218529
Topic:
0%
28
Chapters
0-1
Hours read
0k
Total Words
    Start Reading Now    
       Add to Wishlist       
View table of contents

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
3.145.191.169