¨    ¨
                      Technische Universitat Munchen
                                ¨
                     Lehrstuhl fur Kommunikationsnetze
                           Prof. Dr.-Ing. Wolfgang Kellerer
                         Technical Report No. 201603
             Network Calculus: A Comprehensive Guide
                                     1                  1
                     AmauryVanBemten andWolfgangKellerer
                  1                                  ¨  ¨
                   Chair of Communication Networks, Technische Universitat Munchen
                                        ¨
                           Arcisstr. 21, 80333 Munchen, Germany
                       {amaury.van-bemten|wolfgang.kellerer}@tum.de
                                 October 8, 2016
                             Abstract
            Network calculus is a mathematical framework allowing to analyze the worst-case
            performance of communication networks. As high performance is the goal of any
            communication network, we believe that the theory is a very useful tool for network
            researchers and engineers. However, because it relies on non-traditional algebras,
            namely the min-plus and max-plus algebras, researchers and engineers are usually
            reluctant to use network calculus or use it in a non-optimal or wrong way. Therefore,
            as an objective to make it more understandable and usable by the community, this
            document tries to present major results of network calculus in a comprehensive way.
            Proofs and detailed developments are intentionally omitted. We do not pretend to
            present any new result. Each statement is accompanied by a pointer to a proof or to a
            moredetailed explanation for it. The goal of this document is to provide researchers
            and engineers with a comprehensive guide they can use as a reference to properly
            apply network calculus to their specific application.
                Hopingfor the best but expecting the worst
                                                                   Contents
                              1 Introduction                                                                                 1
                                  1.1 Network Calculus as a System Theory . . . . . . . . . . . . . . . . . . .              1
                                  1.2 MakingNetworkCalculus Friendly . . . . . . . . . . . . . . . . . . . .                 2
                              2 Mathematical Background                                                                      4
                                  2.1 Min-Plus Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .           4
                                        2.1.1   Introduction     . . . . . . . . . . . . . . . . . . . . . . . . . . . .     4
                                        2.1.2   Wide-Sense Increasing Functions . . . . . . . . . . . . . . . . .            5
                                        2.1.3   Pseudo-Inverse of Wide-Sense Increasing Functions . . . . . . .              5
                                        2.1.4   Concave, Convex and Star-Shaped Functions            . . . . . . . . . .     6
                                        2.1.5   Min-Plus Convolution . . . . . . . . . . . . . . . . . . . . . . .           9
                                        2.1.6   Min-Plus Deconvolution . . . . . . . . . . . . . . . . . . . . . .         10
                                        2.1.7   Vertical and Horizontal Deviations . . . . . . . . . . . . . . . .         12
                                        2.1.8   Sub-Additivity     . . . . . . . . . . . . . . . . . . . . . . . . . . .   13
                                  2.2 Max-Plus Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .         14
                                        2.2.1   Max-Plus Convolution . . . . . . . . . . . . . . . . . . . . . . .         15
                                        2.2.2   Max-Plus Deconvolution . . . . . . . . . . . . . . . . . . . . . .         15
                                        2.2.3   Linearity of Min-Plus Deconvolution . . . . . . . . . . . . . . .          15
                                        2.2.4   Super-Additivity     . . . . . . . . . . . . . . . . . . . . . . . . . .   15
                              3 DataModeling                                                                               16
                                  3.1 Data Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        16
                                  3.2 System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .       16
                                  3.3 Backlog and Virtual Delay . . . . . . . . . . . . . . . . . . . . . . . . .          18
                              4 Arrival Curves                                                                             20
                                  4.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        20
                                  4.2 Token Bucket and Leaky Bucket Algorithms . . . . . . . . . . . . . . .               21
                                  4.3 GoodArrival Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . .           23
                                  4.4 MinimumArrival Curve . . . . . . . . . . . . . . . . . . . . . . . . . .             24
                              5 Service Curves                                                                             25
                                  5.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        25
                                  5.2 CommonServiceCurves . . . . . . . . . . . . . . . . . . . . . . . . . .              26
                                  5.3 Other Classes of Service Curves . . . . . . . . . . . . . . . . . . . . . .          26
                                        5.3.1   Strict Service Curve     . . . . . . . . . . . . . . . . . . . . . . . .   26
                                        5.3.2   MaximumServiceCurve . . . . . . . . . . . . . . . . . . . . . .            27
                                  5.4 Concatenation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .         28
                                  5.5 Greedy Shapers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .         29
                                                                              i
                              6 NetworkCalculus Basics                                                                      31
                                  6.1 Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .          31
                                        6.1.1    Backlog Bound . . . . . . . . . . . . . . . . . . . . . . . . . . .        31
                                        6.1.2    Delay Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . .        32
                                        6.1.3    Output Flow Bound . . . . . . . . . . . . . . . . . . . . . . . .          32
                                        6.1.4    Delay from Backlog . . . . . . . . . . . . . . . . . . . . . . . . .       33
                                                 6.1.4.1   Classical Service Curve Case       . . . . . . . . . . . . . .   33
                                                 6.1.4.2   Strict Service Curve Case . . . . . . . . . . . . . . . .        33
                                        6.1.5    Output from Delay . . . . . . . . . . . . . . . . . . . . . . . . .        34
                                  6.2 CommonBoundsResults . . . . . . . . . . . . . . . . . . . . . . . . . .               34
                                        6.2.1    Leaky Bucket Flow through Rate Latency Server . . . . . . . . .            34
                                        6.2.2    VBRFlowthroughRateLatencyServer . . . . . . . . . . . . . .                34
                                  6.3 Pay Bursts Only Once (PBOO) . . . . . . . . . . . . . . . . . . . . . . .             37
                                  6.4 Greedy Shapers Come For Free . . . . . . . . . . . . . . . . . . . . . .              38
                              7 Packet-Based Systems                                                                        39
                                  7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        39
                                  7.2 ThePacketizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .           39
                                  7.3 Impact of the Packetizer . . . . . . . . . . . . . . . . . . . . . . . . . .          40
                                  7.4 Packetized Greedy Shaper . . . . . . . . . . . . . . . . . . . . . . . . .            41
                              8 Service Curve Determination                                                                 43
                                  8.1 Constant Delay Line . . . . . . . . . . . . . . . . . . . . . . . . . . . .           43
                                  8.2 Schedulers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        44
                                        8.2.1    First-In First-Out (FIFO) . . . . . . . . . . . . . . . . . . . . . .      44
                                        8.2.2    Priority Queuing (PQ) . . . . . . . . . . . . . . . . . . . . . . .        44
                                        8.2.3    Generalized Processor Sharing (GPS) . . . . . . . . . . . . . . .          46
                                        8.2.4    Packet by Packet GPS (PGPS) . . . . . . . . . . . . . . . . . . .          46
                                        8.2.5    Guaranteed Rate (GR) . . . . . . . . . . . . . . . . . . . . . . .         46
                                                 8.2.5.1   The Framework . . . . . . . . . . . . . . . . . . . . .          46
                                                 8.2.5.2   Characterization of Nodes as GR Nodes . . . . . . . .            47
                                                 8.2.5.3   Concatenation of GR Nodes . . . . . . . . . . . . . . .          48
                                  8.3 Flows Aggregation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .           49
                                        8.3.1    Strict Service Curve Element       . . . . . . . . . . . . . . . . . . .   49
                                        8.3.2    FIFO Service Curve Element . . . . . . . . . . . . . . . . . . . .         49
                                        8.3.3    GRNode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .         50
                                                                              ii