﻿ Alternative Approaches of Convolution within Network Calculus

Journal Menu >>

 Journal of Applied Mathematics and Physics, 2014, 2, 987-995 Published Online October 2014 in SciRes. http://www.scirp.org/journal/jamp http://dx.doi.org/10.4236/jamp.2014.211112 How to cite this paper: Klehmet, U. and Berndt, R. (2014) Alternative Approaches of Convolution within Network Calculus. Journal of Applied Mathematics and Physics, 2, 987-995. http://dx.doi.org/10.4236/jamp.2014.211112 Alternative Approaches of Convolution within Network Calculus Ulrich Klehmet, Rüdiger Berndt Computer Networks and Communication Systems Friedrich-Alexand er-Universität, Erlangen, German y Email: ulrich.klehmet@cs.fau.de, ruediger.berndt@cs.fau.de Received Ju ly 2014 Abstract Network Calculus is a powerful mathematical theory for the performance evaluation of communi-cation systems; among others it allows to determine worst-case performance measures. This is why it is often used to appoint Quality of Service guarantees in packet-switched systems like the internet. The main mathematical operation within this deterministic queuing theory is the min- plus convolution of two functions. For example the convolution of the arrival and service curve of a system which reflects the data’s departure. Considering Quality of Service measures and per-formance evaluation, the convolution operation plays a considerable important role, similar to classical system theory. Up to the present day, in many cases it is not practical and simple to per-form this operation. In this article we describe approaches to simplify the min-plus convolution and, accordingly, facilitate the corresponding calculations. Keywords Network Calculus, Min-Plus Convolution, Algebraic Laws, Convex Analysis 1. Introduction Timeliness plays an important role regarding systems with real time requirements. This Quality of Service (QoS) requirement can be found in many kinds of embedded systems which permanently exchange data with their en-vironment; like safety-critical automotive systems or real time networks. Since knowledge of mean values is not sufficient, analytical performance evaluation of such systems cannot be based on stochastic modeling as applied in traditional queuing theory. For these systems worst-case performance parameters like maximum delay of ser-vice times are required. In order to specify guarantees of performance figures—in terms of bounding values which are valid in any case—a mathematical tool Network Calculus (NC) as a novel system theory for determi-nistic queuing theory has been developed [1]. The development of this theory has been started by Cruz [2] [3] on the ( ),σρ traffic description and his calculus for network delay. Further steps towards NC were taken by the work of Parekh and Gallagher [4] to determine the service curve of Generalized Processor Sharing (GPS) schedulers. The NC framework has been successfully applied for the analysis and dimensioning in various domains, including industrial automation net-works [5] or automotive communications bus systems [6]. This article is structured as follows, in Section 2 we describe the basic modeling elements of NC theory. The U. Klehmet, R. Berndt 988 subsequent Section 3 demonstrates the difficulties of convolution calculation and describes possible solution approaches. Finally, Section 4 draws a conclusion and indicates future steps. 2. Basic Modeling Elements of Network Calculus The most important modeling elements of NC are the arrival curve (denoted by α in the figure s) and the ser-vice curve (denoted by β in the figures) together with the min-plus convolution. The arrival and the service curve are the basis for the computation of maximum deterministic boundary values like backlog and delay bounds [1]. Definition 1 (Arrival curve) Let ( )tα be a non-negative, non-decreasing function. Flow F with input ( )xt at time t is constrained by or has arrival curve ( )tα iff ( )()()xtxst sα− ≤− for all 0ts≥≥. Flow F is also called α-smooth. Example 1 A commonly used arrival curve is the token bucket constraint: ( ),: 00: 0rbb rttttα+>=≤ (1) Figure 1 shows an arrival curve which represents an upper limit for a given traffic flow ( )xt with an aver-age rate r and an instantaneous burst b. Therefore: ( )()(),rbxtxst sα−≤ −. For :t ts∆=− and 0t∆→: ( )(){}{ }0lim limts txtxsrt bb→ ∆→−≤⋅∆ += (2) Next the convolution operation, which plays the most important role in Network Calculus will be defined. Definition 2 (Min-plus convolution) Let ( )ft and ( )gt be non-negative, non-decreasing functions that are 0 for 0t≤. A third function, called min -plus convolution is defined as ()( )()(){ }0infstfgtf sgts≤≤⊗ =+− (3) On this basis we can characterize the arrival curve ( )tα with respect to a given ( )xt as: ( )()()xt xtα≤⊗ In other words, arrival curves describe an upper bound to the input stream of a system. Considering the sys-tem’s output, we might be interested in service guarantees: like a minimum of output ( )yt, i.e. the amount of data that leaves the system. The following definition deals with this problem. Definition 3 (Service curve) Let a system S with input flow ( )xt and output flow ( )yt be given. The system provides a (minimu m ) service curve ( )tβ to the flow, iff ( )tβ is a non-negative, non-decreasing function with ( )00β= and if ( )yt is lower bounded by the convolution of ( )xt and ( )tβ, i.e.: Figure 1. Token bucket arrival curve. U. Klehmet, R. Berndt 989 ( )()( )yt xtβ≥⊗ (4) Figure 2 shows ()( )()(){ }0infstxtxst sββ≤≤⊗ =+− as lower bound of output ( )yt and input ( )xt. Such service curves are functions of the time and describe the service of network elements like routers or sche-dulers in an abstract manner [7]. Example 2 A commonly used service curve of practical applications is the rate-latency function: ( )( )[ ]{ },:max 0,RTtt RtTRtTββ+==⋅− =⋅− (5) This function reflects a service element which offers a minimum service of rate R after a worst-case latency of T. Since we want to analyze the worst-case performance, it is possible to abstractly model the complex in-ternal behavior of the node by just describing the worst-case service using this curve. This is very important in practical utilization. In Figure 4, the (green) line depicts the rate-latency service curve with rate R and latency T. Consider a system with input flow ( )xt, arrival curve ( )tα, output flow ( )yt and service curve ( )tβ. According to [1] the following three bounds can be derrived: • Backlog Bound v: ( )()( )()(){ }0supsvtxt ytssαβ≥=−≤ − • Delay Bound d in case of FIFO service: ( )(){}{ }0inf :supsd ssταβτ≥≤ ≤+ • Output Bound ( )tα∗: ( )()(){ }0:supstts sα αβαβ∗≥= =+− Rema rk: The complete backlog ( )( )( )vtxt yt= − at time t within a system is also called unfinished work or buffer( )t. The expression ( )(){ }inf :ssταβ τ≤+ is called virtual delay: the minimal time distance which is ne-cessary for input x for being served to output. Thus, the backlog and delay bound are the maximal vertical and horizontal deviation between arrival and service curve. Figure 3 depicts d and v for a given arrival- and service curve. Example 3 Let a system with a token bucket-smooth input and rate-latency service be given, thus: ( )()(),rbxtxst sα−≤ − and Figure 2. Convolution as a lower output bound. U. Klehmet, R. Berndt 990 ( )()(){ },infs tRTytxst sβ≤≥ +−. Based on the three bounds above we can calculate the delay bound as bdTR≤+, the output bound as ( )()trt Tbα∗= ++, and the backlog bound as vb rT= +. Figure 4 shows these results. 3. Difficulties of the Convolution Operation Within the Network Calculus (NC) the o ry, the convolution operation of so-called min-plus algebra is considered the most essential operation. This is because—based on the arrival- and service curve—it computes the depar-ture of a network element, therefore it is the main instrument of analytical performance evaluation. For example in [1], this operation is carried out “by hand” using pure analytical calculation. Take Example 3 for which ,,rb RTαβ⊗ as the lower bound for output ,,:rb RTyyαβ≥⊗ needs to be com-puted. 3.1. Analytical Computation of Convolution Operator ⊗ a) 0:tT≤≤ Figure 3. Backlog and delay bound. Figure 4. Example for the bounds. U. Klehmet, R. Berndt 991 ( )( )()[ ]{ }( ){ }( ),, ,,,infinf000 0rb RTrbrbrbst sttts RsTtsαβ ααα+≤≤⊗= −+−= −+=+= b) :tT> ( )( )( )[ ]{ }( )[ ]{ }( )[ ]{ }( )[ ]{ }( ){ }() (){ }( ){ }( ){ }( ){ }{ }( ){ }( ){ }( ){ }( ){ }( ){ }( ){ },,,, ,,infinf inf infinf0 inf0infrb RTrbstrbrb rbsTT ststsTT stTstttsRs TtsRs TtsRs TtsRs Tb rt sb rt sRsTRtTbrtT brtRTRrsRtTbrtT brtTRtTbrtT RtTαβαα αα+≤+ ++≤≤≤ =≤ <<<<++⊗=−+ −=−+ −∧−+ −∧−+ −=+ −+∧+ −+−∧+−= +−∧+−+−∧−=+−∧+−∧ −=+−∧− . (6) Here { }min ,A BAB∧= and convolution ( ),,rb RTαβ⊗ with result (6) is depicted in Figure 5. For the following convolution of two rate-latency service curves (concatenation) a similarly complex calcula-tion is requir e d . ( )112212 12,,min ,,RT RTRRT Tββ ββ+=⊗= (7) As we can see from above, this analytical approach is cumbersome and error-prone. But, similar to convolu-tion of classical systems theory, the convolution ⊗ is of great importance for NC theory. This is why we are looking for other more elegant methods to computation. Next, two alternative approaches called Use of algebraic laws and Use of convex analysis will be introduced. 3.2. Use of Algebraic Laws In the following, the NC-relevant functions Φ are defined as non-negat i ve , non-decreasing, and passing through the ori gin: ( )( )( ){ }1 010:0 ,00fftftttfΦ=≥≥∀≥= (8) Among others, the following algebraic properties for the set of functions Φ can be found in literature [1] Figure 5. Convolution of ,,rb RTαβ⊗. U. Klehmet, R. Berndt 992 • Rule 1 (Commutativity of ⊗): f gg f⊗=⊗ • Rule 2 (Associativity of ⊗): ()( )f ghfgh⊗⊗=⊗⊗ • Rule 3 (Distributivity of ⊗ and ∧): ()() ()h fghfhg⊗∧=⊗∧⊗ • Rule 4 (Addition of a constant): ( )( ) 0gKfK gfK⊗+=+⊗∀≥ • Rule 5 (Concave functions passing through the origin): { }min ,f gfg⊗= • Rule 6 (Shifting of f to right): ( )()()TftftTδ+⊗=− with ( )0Ttδ= for tT≤ and ∞ otherwise. Now, we only apply these algebraic rules to compute the convolution ⊗. We consider Example 3 in an even more general form: ( ),,rb RTKαβ⊗+ with any constant K; let rrtλ= ⋅ ( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( ){ },,Rule1 Rule6Rule4,, ,,Rule2Rule5 Rule3,, ,Rule6 Rule4 Rule6,, ,,rb RTRTrbT RrbTRrbT RrbT RrbTRTrbRTTrRTT rRTrTKKK KKKKKbKbKbKbrtTRαββαδλ αδλ αδλαδλαδλδαβδ λβδλββ+⊗+= +⊗=+⊗⊗=+ ⊗⊗=+⊗⊗ =+⊗∧ =+⊗∧⊗= +∧⊗+= +∧⊗+= +∧+=++ −∧( ){ }.tT+− (9) Or take the concatenation example: 112 2,,RT RTββ β= ⊗: ( )()( )( )( )( )( )( )()( )( )( )( ){}( )( )( )( ){} ()( )( )1 21212 12 12Rule6 Rule21 1221212Rule5 Rule612121 2min ,, min,min,.T TTTTT RRT TR tTRtTRttRttRtRtttRR tttRRtTTβδ δδδδδ β+++=−⊗−=⊗ ⊗⊗=⊗⊗ ⊗=⊗⊗=−+ = (10) 3.3. Use of Convex Analysis The next approach is based on the theory of convex analysis [8]. Similar considerations related to NC theory can be found at [9]. However, we go another way considering “incomplete” convex functions. In Rockafellar’s book [8] all necessary preconditions for the following definition and proofs of the next theorems can be found. Definition 4 (Conjugate function) Let f be any closed convex function on nR. ( )( ){ }: sup,domtfsstf ttf∗= −∈ is called the conjugate of f or Fenchel-tran sfo rm , with , nst R∈ ,⋅⋅ the inner product in nR. Theorem 1 (Conjugate f**) The conjugate f∗∗ of f∗ is f: ( )(){ }sup ,domsftstfssf∗∗∗ ∗= −∈. Theorem 2 (Convolution) Let 1,,nff be proper convex functions on nR. Then: ( )11nnfff f∗∗∗⊗⊗= ++. Rema rk: In case of the convex NC functions of Φ: 1nRR≡. From Theorem 1 and 2 we get ( )( )11nnffff∗∗∗⊗⊗ =++. Example: Again the aim is the concatenation 112 2,,RT RTββ β= ⊗ with ( )( ),: 1,20: iiii iRT iRtTt TittTβ− ≥==< (11) U. Klehmet, R. Berndt 993 First of all, the conjugate of the rate-latency function ,RTβ i.e. ,RTβ∗ needs to be determined. From defini-tion 4 we know that ()( ){ }( ){ }supdom supttsstttstR tTβ ββ∗= −∈= −− (12) So, we get: Case 0:s< ( )sβ∗= ∞ Case 0:s= ( )0sβ∗= ( ): 0and for Case 0:: Tss Rss sRβ∗<≤>=∞> ( )( ),: 0Altogether:: 0: RTsssTss RsRββ∗∗∞<= =≤≤∞> (13) Determination of ( )tβ∗∗ as conjugate of ( )sβ∗ with domsβ∗∈: ( )(){ }{( ),: 0supsup: 0: s sRTststsstTss RtsRββ β∗∗ ∗∞<=−=−≤≤ =∞> (14) This certainly confirms Theorem 1. Applying Theorem 2: ( )12 12ββ ββ∗∗∗⊗=+ and by applying Theorem 1: ( )()12 12ββ ββ∗∗⊗=⊗; here ( )12ββ∗∗∗+. For the concatenation 112 2,,RT RTββ⊗ we obtain (let 111,RTββ= and 222,RTββ=, 210TT>>, 210RR>>) ()()( )()()1 212112212112 1: 0: 0: 0: 0: 0: 0: : : ss ssssTs sRTs sRTTs sRsR sRsRβββ β∗∗∗∞< ∞<∞<  ⊗=+=≤≤ =≤≤=+≤≤  ∞> ∞>∞>  (15) ( )( ){()1 21211: 0sup: 0: sststTT ssRsRββ∗∗∗∞<⇒ +=−+≤≤∞> (16) But this is the same structure as in expression for ( )tβ∗∗ and therefore ()()( )11 212 1 212, min ,,RT TRRT Ttβββ β∗∗∗+++== holds. Figure 6 depicts this operation. Figure 6. Concatenation of two rate-latency functions. U. Klehmet, R. Berndt 994 In conclusion, the use of convex analysis seems to be a further approach to determine the min-plus convolu-tion operation—at least in the context of convex functions like the set of piecewise linear functions where ,RTβ belongs. Question: How to deal with non-convex functions f∈Φ. Take Example 3 with input ,rbxα= and service curve ,RTβ. The min-plus convolution realizes a guaranteed lower bound for the output: ( )( )( ),,rb RTyt tαβ≥⊗. ( ),: 0But function 0: 0rbrt btttα+>== is not convex because the ≤ relation in: ( )( )( )( )( ),0 1,0,111rbrb rbttt tαλλλ αλα−+ ≤−+ for 010, t tR= ∈ and 01λ<< is not fulfilled. Therefore Theorem 1 and 2 are not readily applicable. However, in contrast to [9] other ways are possible. Here the following one is suggested: making functions convex by redefining their values at certain points, e.g. where unnatural discontinuities appear (e.g. 0t=). For examp le, we change ( ),rb tα to ( ),rb tα such that ( ),rbtα is convex and still reflects the arrival curve feature well: ( ), for 0rbtrtbtα=+≥ (17) Now, ,rbα is convex and the principles of convex analysis are applicable. Although ,rbα∉Φ (since ( ),00rbα≠) it represents the important burst feature ( ):0t ts∆=−→ of the arrival curve ,rbα (of formula 2): ( )(){ }{}( )( )00,0,limlimlim limtstt rbt rbxtxsrtbttbαα→∆→∆→ ∆→−≤⋅∆+= ∆=∆=. Since ,,rb rbαα≠ the convolution of ( ){ },,rb RTbrt Tαβ+⊗ =+− differs from ( ){ }( ){ },,rb RTbrtTRtTαβ++⊗ =+−∧−. The expression ( ){ }brt T++− is identical in both formulas. When considering rate-latency functions (c.f. Example 2) where an incoming input is served with minimal rate R after a maximal delay T, the output y is lower bounded not only by ( ){ }brt T++− but by ( )( ){ }min ,brtT RtT+++− − Of course, in the long run for t→∞ the term ( ){ }brt T++− is the dominant one, as you can see in Figure 5. 4. Conclusions The most important operation within the Network calculus is the min-plus convolution. But the calculation of this fundamental operation still is complex and error-prone. For this reason we introduced other computation approaches to perform the convolution: here called Use of algebraic laws and Use of convex analysis. In order to apply the convex analysis we transform non-convex into convex functions (e.g. keeping the token-b ucket arrival curve property) which is different, for example, from the approach of [9]. This article reflects work in progress and the presented examples ought to demonstrate these techniques. In future work we will continue to investigate the procedures of subsection 3.2 and 3.3 to answer the following questions: Can we extend the principles to some classes of non-convex functions or even to mixed classes of convex and non-convex functions? Which kinds of applications are suited considering algebraic laws and con-vex analysis? Are there even cases where a combination of both methods is beneficial? To all of these, we want to find answers in future work. References [1] Le Boudec, J.-Y. and Thiran, P. (2001) Network Calculus. Springer Verlag LNCS 2050. U. Klehmet, R. Berndt 995 [2] Cruz, R. (1991) A Calculus for Network Delay, Part I: Network Elements in Isolation. IEEE Transactions on Informa-tion Theory, 37, 114-131. [3] Cruz, R. (19 91 ) A Calculus for Network Delay, Part Ii: Network Analysis. IEEE Transactions on Information Theory, 37, 132-141. [4] P arekh, A. K. and Gallager, R. G. (1993) A Generalized Processor Sharing Approach to Flow Control in Integrated Ser-vice Networks: The Single-Node Case. IEEE/ACM Transactions on Networking, 1, 344-357. http://dx.doi.org/10.1109/90.234856 [5] Kersch bau m, S., Hielsch er, K., Kleh met, U. and German, R. (2012) Network Calculus: Application to an Industrial Automation Network. In: MMB and DFT 2012 Workshop Proceedings (16 th GI/ITG Conference), Kaiserslau tern, March 2012. [6] Herp el, T., Hi elscher , K. , Kleh met , U. and German, R. (2009) Stochastic and Deterministic Performance Evaluation of Automotive CAN Co mmunicati on. Computer Networks, 53, 1171-1185. http://dx.doi.org/10.1016/j.comnet.2009.02.008 [7] Fidler, M. (2010 ) A Survey of Deterministic and Stochastic Service Curve Models in the Network Calculus. IEEE Communications Surveys & Tutorials, 12, 59-86. [8] Ro ckafellar, R .T. (1970) Convex Analysis. Princeton University Press. [9] P and it, K., Schmitt, J., Kirchner , C. and Steinmetz, R. (2004) Optimal Allocation of Service Curves by Exploiting Properties of the Min-Plus Con volu ti on. Technical Report.