Journal of Applied Mathematics and Physics, 2014, 2, 987995 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, 987995. 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 FriedrichAlexand erUniversitä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 worstcase performance measures. This is why it is often used to appoint Quality of Service guarantees in packetswitched 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 minplus convolution and, accordingly, facilitate the corresponding calculations. Keywords Network Calculus, MinPlus 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 safetycritical 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 worstcase 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 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 minplus 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 be a nonnegative, nondecreasing function. Flow with input at time t is constrained by or has arrival curve iff for all . Flow is also called smooth. Example 1 A commonly used arrival curve is the token bucket constraint: ( ) , : 0 0: 0 rb b rtt tt α +> =≤ (1) Figure 1 shows an arrival curve which represents an upper limit for a given traffic flow with an aver age rate and an instantaneous burst . Therefore: . For and : ( )() {} { } 0 lim lim ts t xtxsrt bb → ∆→ −≤⋅∆ += (2) Next the convolution operation, which plays the most important role in Network Calculus will be defined. Definition 2 (Minplus convolution) Let and be nonnegative, nondecreasing functions that are 0 for . A third function, called min plus convolution is defined as ()( )()() { } 0 inf st fgtf sgts ≤≤ ⊗ =+− (3) On this basis we can characterize the arrival curve with respect to a given as: 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 , i.e. the amount of data that leaves the system. The following definition deals with this problem. Definition 3 (Service curve) Let a system with input flow and output flow be given. The system provides a (minimu m ) service curve to the flow, iff is a nonnegative, nondecreasing function with and if is lower bounded by the convolution of and , i.e.: Figure 1. Token bucket arrival curve.
U. Klehmet, R. Berndt (4) Figure 2 shows ()( )()() { } 0 inf st xtxst s ββ ≤≤ ⊗ =+− as lower bound of output and input . 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 ratelatency function: ( )( ) [ ] { } ,:max 0, RT tt RtTRtT ββ + ==⋅− =⋅− (5) This function reflects a service element which offers a minimum service of rate after a worstcase latency of . Since we want to analyze the worstcase performance, it is possible to abstractly model the complex in ternal behavior of the node by just describing the worstcase service using this curve. This is very important in practical utilization. In Figure 4, the (green) line depicts the ratelatency service curve with rate and latency . Consider a system with input flow , arrival curve , output flow and service curve . According to [1] the following three bounds can be derrived: • Backlog Bound : ( )()( )()() { } 0 sup s vtxt ytss αβ ≥ =−≤ − • Delay Bound in case of FIFO service: ( )() {} { } 0 inf : sup s d ss ταβτ ≥ ≤ ≤+ • Output Bound : ( )()() { } 0 :sup s tts s α αβαβ ∗ ≥ = =+− Rema rk: The complete backlog at time within a system is also called unfinished work or buffer . The expression is called virtual delay: the minimal time distance which is ne cessary for input 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 and for a given arrival and service curve. Example 3 Let a system with a token bucketsmooth input and ratelatency service be given, thus: and Figure 2. Convolution as a lower output bound.
U. Klehmet, R. Berndt ( )()() { } , inf s tRT ytxst s β ≤ ≥ +− . Based on the three bounds above we can calculate the delay bound as , the output bound as , and the backlog bound as . Figure 4 shows these results. 3. Difficulties of the Convolution Operation Within the Network Calculus (NC) the o ry, the convolution operation of socalled minplus 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 as the lower bound for output needs to be com puted. 3.1. Analytical Computation of Convolution Operator a) Figure 3. Backlog and delay bound. Figure 4. Example for the bounds.
U. Klehmet, R. Berndt ( ) ( )() [ ] { } ( ) { } ( ) ,, ,,, infinf000 0 rb RTrbrbrb st st tts RsTts αβ ααα + ≤≤ ⊗= −+−= −+=+= b) ( ) ( ) ( ) [ ] { } ( ) [ ] { } ( ) [ ] { } ( ) [ ] { } ( ) { } () () { } ( ) { } ( ) { } ( ) { } { } ( ) { } ( ) { } ( ) { } ( ) { } ( ) { } ( ) { } ,, , , ,, inf inf inf inf inf0 inf0 inf rb RT rb st rbrb rb sTT stst sTT st Tst t tsRs T tsRs TtsRs TtsRs T b rt sb rt sRsTRtT brtT brtRTRrsRtT brtT brtTRtT brtT RtT αβ α α αα + ≤ + ++ ≤≤≤ = ≤ << << ++ ⊗ =−+ − =−+ −∧−+ −∧−+ − =+ −+∧+ −+−∧+− = +−∧+−+−∧− =+−∧+−∧ − =+−∧− . (6) Here and convolution with result (6) is depicted in Figure 5. For the following convolution of two ratelatency 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 errorprone. 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 NCrelevant functions are defined as nonnegat i ve , nondecreasing, 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 .
U. Klehmet, R. Berndt • Rule 1 (Commutativity of ): • Rule 2 (Associativity of ): • Rule 3 (Distributivity of and ): • Rule 4 (Addition of a constant): • Rule 5 (Concave functions passing through the origin): • Rule 6 (Shifting of f to right): with for and otherwise. Now, we only apply these algebraic rules to compute the convolution . We consider Example 3 in an even more general form: with any constant ; let ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) { } ,, Rule1 Rule6Rule4 ,, ,, Rule2Rule5 Rule3 ,, , Rule6 Rule4 Rule6 ,, ,, rb RT RTrbT RrbTRrb T RrbT RrbTRTrb RTTrRTT rRTrT K KK K KKK KbKbKb KbrtTR αβ βαδλ αδλ α δλαδλαδλδα βδ λβδλββ + ⊗+ = +⊗=+⊗⊗=+ ⊗⊗ =+⊗⊗ =+⊗∧ =+⊗∧⊗ = +∧⊗+= +∧⊗+= +∧+ =++ −∧ ( ) { } .tT + − (9) Or take the concatenation example: : ( )() ( ) ( ) ( ) ( ) ( ) ( ) ()( )( ) ( ) ( ) {}( )( ) ( ) ( ) {} () ( ) ( ) 1 212 12 12 12 Rule6 Rule2 1 1221212 Rule5 Rule6 12121 2min ,, min,min,. T TTT TT RRT T R tTRtTRttRttRtRttt RR 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 be any closed convex function on n . ( )( ) { } : sup,dom t fsstf ttf ∗= −∈ is called the conjugate of or Fencheltran sfo rm , with the inner product in . Theorem 1 (Conjugate f**) The conjugate of is : ( )() { } sup ,dom s ftstfssf ∗∗∗ ∗ = −∈ . Theorem 2 (Convolution) Let be proper convex functions on . Then: . Rema rk: In case of the convex NC functions of : . From Theorem 1 and 2 we get ( ) ( ) 11nn ffff ∗ ∗∗ ⊗⊗ =++ . Example: Again the aim is the concatenation with ( ) ( ) , : 1,2 0: ii ii i RT i RtTt Ti ttT β − ≥= =< (11)
U. Klehmet, R. Berndt First of all, the conjugate of the ratelatency function i.e. needs to be determined. From defini tion 4 we know that ()( ) { } ( ) { } supdom sup tt sstttstR tT β ββ ∗ = −∈= −− (12) So, we get: ( ) : 0 and for Case 0:: Tss R ss sR β ∗ <≤ >= ∞> ( )( ) , : 0 Altogether:: 0 : RT s ssTss R sR ββ ∗∗ ∞< = =≤≤ ∞> (13) Determination of as conjugate of with : ( )() { } {( ) , : 0 supsup: 0 : s sRT s tstsstTss Rt sR ββ β ∗∗ ∗ ∞< =−=−≤≤ = ∞> (14) This certainly confirms Theorem 1. Applying Theorem 2: and by applying Theorem 1: ; here . For the concatenation we obtain (let and , , ) ()()( )()() 1 2121122121 12 1 : 0: 0: 0 : 0: 0: 0 : : : ss s sssTs sRTs sRTTs sR sR sRsR βββ β ∗∗∗ ∞< ∞<∞< ⊗=+=≤≤ =≤≤=+≤≤ ∞> ∞>∞> (15) ( ) ( ){() 1 2121 1 : 0 sup: 0 : s s tstTT ssR sR ββ ∗ ∗∗ ∞< ⇒ +=−+≤≤ ∞> (16) But this is the same structure as in expression for and therefore () () ( ) 11 212 1 2 12, min ,, RT TRRT T t βββ β ∗ ∗∗ ++ +== holds. Figure 6 depicts this operation. Figure 6. Concatenation of two ratelatency functions.
U. Klehmet, R. Berndt In conclusion, the use of convex analysis seems to be a further approach to determine the minplus convolu tion operation—at least in the context of convex functions like the set of piecewise linear functions where belongs. Question: How to deal with nonconvex functions . Take Example 3 with input and service curve . The minplus convolution realizes a guaranteed lower bound for the output: . ( ) , : 0 But function 0: 0 rb rt bt tt α +> == is not convex because the relation in: ( ) ( ) ( ) ( ) ( ) ,0 1,0,1 11 rbrb rb ttt t αλλλ αλα −+ ≤−+ for and 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. ). For examp le, we change to such that is convex and still reflects the arrival curve feature well: (17) Now, is convex and the principles of convex analysis are applicable. Although (since ) it represents the important burst feature of the arrival curve (of formula 2): ( )() { } {}( )( ) 00,0, limlimlim lim tstt rbt rb xtxsrtbttb αα →∆→∆→ ∆→ −≤⋅∆+= ∆=∆= . Since the convolution of ( ) { } ,, rb RT brt T αβ + ⊗ =+− differs from ( ) { } ( ) { } ,,rb RT brtTRtT αβ ++ ⊗ =+−∧− . The expression is identical in both formulas. When considering ratelatency functions (c.f. Example 2) where an incoming input is served with minimal rate after a maximal delay , the output is lower bounded not only by but by ( )( ) { } min ,brtT RtT ++ +− − Of course, in the long run for the term is the dominant one, as you can see in Figure 5. 4. Conclusions The most important operation within the Network calculus is the minplus convolution. But the calculation of this fundamental operation still is complex and errorprone. 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 nonconvex into convex functions (e.g. keeping the tokenb 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 nonconvex functions or even to mixed classes of convex and nonconvex 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 [2] Cruz, R. (1991) A Calculus for Network Delay, Part I: Network Elements in Isolation. IEEE Transactions on Informa tion Theory, 37, 114131. [3] Cruz, R. (19 91 ) A Calculus for Network Delay, Part Ii: Network Analysis. IEEE Transactions on Information Theory, 37, 132141. [4] P arekh, A. K. and Gallager, R. G. (1993) A Generalized Processor Sharing Approach to Flow Control in Integrated Ser vice Networks: The SingleNode Case. IEEE/ACM Transactions on Networking, 1, 344357. 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, 11711185. 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, 5986. [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 MinPlus Con volu ti on. Technical Report.
