Marc Boyer

Pierre Roux

A common framework embedding network calculus and event stream theory

teaching and research institutions in France or abroad, or from public or private research centers.

A common framework embedding network calculus and event stream theory

Introduction

The correct behaviour of cyber-physical systems requires some real-time control capabilities, i.e. the guarantee that some response to some stimulus can be computed and sent to some actuator within a given latency budget. The engineers need some method to compute the response time of the computing platform (involving calculators, busses, gateways, etc.) when designing the system and allocating resources. Several methods target this goal, and among others, event stream theory and network calculus are compositional methods, i.e. methods where each component is stimulated by request flows (task releases, message arrivals...), uses local resources, and where an analytic method computes the flow output and bounds on latency and memory usage.

In event stream theory [START_REF] Rox | Compositional performance analysis with improved analysis techniques for obtaining viable end-to-end latencies in distributed embedded systems[END_REF], a flow is modelled by a function E : R + → N where E(t) represents the accumulated number of task activation up to time t, whereas in network calculus [START_REF] Boudec | Network Calculus, ser. LNCS[END_REF], a function A : R + → R + represents the accumulated amount of data received up to time t. Both CPU and network can be generalised as resources, where E(t) represents the number of requests (task activation, packets...), and A(t) the amount of workload (CPU cycles, number of bits...).

The response time of a component mostly depends on its workload: number of CPU cycles to execute, number of bits to send, etc. From this assessment, one may conclude that an amount-based model is the most adequate one. But in a distributed system, where a component produces some output that activates some work on a second component, to situations occur: in network elements (switches, routers), the workload is directly related to the data size, whereas in computing elements, the reception of a message is an event that will release a task, whose workload is often independent of the message size. Then, analysing a distributed system requires to handle both event arrivals and data/workload amount.

In most studies, only one function, E or A is modelled, and the other one is implicit and deduced from the first one using some model assumption on packets size or task execution time. For example, considering a flow of packets of size p, the number of packets received up to time t can be deduced from A, setting E(t) = A(t) p . Conversely, if an event sequence E generates, for each event, a packet of fixed size p, the amount of data generated is simply A(t) = pE(t). This network-based example can be translated into CPU scheduling, where E counts the number of jobs and A the accumulated CPU workload. In case of variable packet size, one may consider a minimal and maximal size, p, p, and consider lower and upper bounds: pE(t) ≤ A(d) ≤ pE(t).

In our experience, difficulties arise when considering flows with correlated packets sizes: either because the flow itself has different sizes (like the I,B,P frames of MPEG video encoding) or, more often, because a flow is the aggregation of sub-flows with different packet sizes.

A few works tried to generalise the minimal/maximal size approach, introducing a function capturing this packet size correlation, using either an explicit data amount and an implicit event count [START_REF] Bouillard | Packetization and aggregate scheduling[END_REF][START_REF]Packetization and packet curves in network calculus[END_REF] or an explicit event count and an implicit workload amount [START_REF] Wandeler | Quantitative characterization of event streams in analysis of hard real-time applications[END_REF][START_REF] Wandeler | Characterizing workload correlations in multi processor hard real-time systems[END_REF].

This paper presents a model embedding explicitly both aspects, in order to, first, have a better understanding of each theory, and second, to be able to analyse a system with both event stream and network calculus, enhancing at each step the result of one theory with the one of the other.

This paper does not study how an input flow is transformed into an output flow: network calculus and/or event stream theory are designed for the analyse of each component. This work targets the interfaces of the components.

The outline of the paper is as follows: first, Section 2 gives an overview of the related work. Then, Section 3 introduces some basic mathematical tools required to support this framework. The model itself is presented and discussed in Section 4. Section 5 shows how informations on two functions can be combined to enhance our knowledge on the third one. Last, Section 6 shows how to model two important elements: the packetizer and the aggregator.

Related work

The event stream theory, with the pioneer work of Gresser [START_REF] Gresser | An event model for deadline verification of hard real-time systems[END_REF], has been developed to allow a compositional analyse of real-time systems where several real-time components are hosting tasks, sharing resources, communicating through data flows. As said in [START_REF] Rox | Compositional performance analysis with improved analysis techniques for obtaining viable end-to-end latencies in distributed embedded systems[END_REF], "Compared to the holistic approach, the compositional models are modularly structured with respect to the architecture". This work has been extended by Richter et al. [START_REF] Henia | System level performance analysis -the SymTA/S approach[END_REF][START_REF] Richter | Compositional scheduling analysis using standard event model -the SymTA/S approach[END_REF]. At this time, the goal was to rely, for each component, on the analyses of response time already existing and to use the event stream model to compose them1 . But this first goal has been extended, and several specific analyses have been developed for specific cases [START_REF] Rox | Exploiting inter-event stream correlations between output event streams of non-preemptively scheduled tasks[END_REF][START_REF]Formal timing analysis of full duplex switched based ethernet network architectures[END_REF][START_REF] Axer | Exploiting shaper context to improve performance bounds of Ethernet AVB networks[END_REF]. A global overview is presented in [START_REF] Rox | Compositional performance analysis with improved analysis techniques for obtaining viable end-to-end latencies in distributed embedded systems[END_REF] whereas the complete formal model can be found in [START_REF] Schliecke | Performance analysis of multiprocessor real-time systems with shared resources[END_REF].

In event stream theory, tasks are released by either some internal timing decision (period, offset, etc.) or by reception of an external packet or signal. Both notions are called events. An event stream E(t) counts the accumulated number of events received up to time t, and two functions, called event models, denoted η + (∆) and η -(∆), are respectively an upper and lower bounds on the number of events received during any interval of length ∆.

The network calculus theory has been developed independently, from the seminal paper on network calculus [START_REF] Cruz | A calculus for network delay, part I: Network elements in isolation[END_REF], using the term "a calculus for network delay", to compute upper bounds on network latency. In network calculus, the amount of traffic received up to time t, A(t), is upper bounded by an arrival curve α [START_REF] Cruz | A calculus for network delay, part I: Network elements in isolation[END_REF][START_REF] Chang | Stability, queue length, and delay of deterministic and stochastic queueing networks[END_REF]. But network calculus theory does not rely on existing response time analyses, and develops its own analyses methods. A real breakthrough, from our point of view, is the introduction of the min-plus convolution, independently done in [START_REF] Cruz | Service guarantees for window flow control[END_REF], [START_REF] Boudec | Network calculus made easy[END_REF] and [START_REF] Chang | A filtering theory for deterministic traffic regulation[END_REF].

The real-time calculus [START_REF] Wandeler | Modular performance analysis and interface-based design for embedded realtime systems[END_REF][START_REF] Thiele | Real-time calculus for scheduling hard realtime systems[END_REF] is an adaptation of network calculus to real-time time systems. Despite some changes in notations, the formal models are, in fact, equivalents [START_REF] Bouillard | Service curves in Network Calculus: dos and don'ts[END_REF]. The introduction of the lower bound on arrival was done in the real-time calculus community [START_REF] Chakraborty | Performance evaluation of network processor architectures: Combining simulation with analytical estimation[END_REF], as well as the main related results [START_REF] Wandeler | Modular performance analysis and interface-based design for embedded realtime systems[END_REF].

The event stream theory and network/real-time calculus are somehow different in the algorithms used to compute bounds, but they are very close on the way to represent requests: as see in introduction, in event stream theory, the flows are modelled by the number of events, E(t), whereas in network/real-time calculus, the flows are modelled by A(t) the amount of the data or workload2 .

Both notions are equivalent when considering packets of constant size, but in real systems, different flows may have different packet sizes, and even in the same flow, the size may vary from one packet to another. If only upper and lower bound are known, simple approximations are sufficient, but the sequence of sizes my have some regularity (also known as correlation in [START_REF] Wandeler | Characterizing workload correlations in multi processor hard real-time systems[END_REF]), requiring a more general model.

So, to link both notions, the sizes of a sequence of packets/requests must be captured. This has be done independently in [START_REF] Wandeler | Quantitative characterization of event streams in analysis of hard real-time applications[END_REF][START_REF] Wandeler | Characterizing workload correlations in multi processor hard real-time systems[END_REF] and in [START_REF]Packetization and packet curves in network calculus[END_REF][START_REF] Bouillard | Packetization and aggregate scheduling[END_REF].

In [START_REF]Packetization and packet curves in network calculus[END_REF][START_REF] Bouillard | Packetization and aggregate scheduling[END_REF] a function P is introduced such that P (a) represents the number of packets received for the amount of data a, i.e. P (A(t)) is the number of packets received up to time t, and two functions π, π are used to capture the minimal an maximal values of the variation of P on some interval. In this work, A is explicit and E implicit.

Conversely, in [START_REF] Wandeler | Quantitative characterization of event streams in analysis of hard real-time applications[END_REF][START_REF] Wandeler | Characterizing workload correlations in multi processor hard real-time systems[END_REF], two functions γ l , γ u are used to bound the workload generated by a sequence of events: E is explicit and A is implicit.

This paper is a direct continuation of [START_REF]Packetization and packet curves in network calculus[END_REF][START_REF] Bouillard | Packetization and aggregate scheduling[END_REF]: considering that E(t) is also the number of packets received up to t, the relation P • A = E is explicitly set and the mathematical implications of this modelling are studied 3 .

The results on aggregation of flows or packetizer are the same in [START_REF]Packetization and packet curves in network calculus[END_REF][START_REF] Bouillard | Packetization and aggregate scheduling[END_REF] and in this paper. Last, this paper only deals with data flow models, and does not consider how an input flow is transformed in an output flow by a component. Such results on blind components are given in [START_REF]Packetization and packet curves in network calculus[END_REF][START_REF] Bouillard | Packetization and aggregate scheduling[END_REF]. And in [START_REF] Wandeler | Characterizing workload correlations in multi processor hard real-time systems[END_REF], a workload-based service curve is derived from the event-based service curve, and both are used in each component.

Mathematical background

After introducing some notations and definitions related to functions, section 3.1 presents the notion of interval bounding pair (that generalises the notion of arrival curve and event model) and section 3.2 presents the notion of pseudo-inverse.

The set of natural numbers is N. The set of reals is R and the subset of non-negative reals is R + . Let us denote ∨, ∧ the infix maximum and minimum operators (a ∨ b = max(a, b), a ∧ b = min(a, b)), and • the composition operator (f • g)(x) = f (g(x)).

In the remainder of the paper, D and I will each denote either

N def = N ∪ + {∞} or R + def = R + ∪ {+∞}. Definition 1 (Non-decreasing function). A function f : D → I is called non-decreasing when for all x, y ∈ D, if x < y, then f (x) ≤ f (y). A non-decreasing function f is divergent if lim x→∞ f (x) = ∞.
Definition 2 (Right-and left-continuous extensions). . For any piece-wise continuous function f : R + → I, its right-and left-continuous extensions f r and f l are defined respectively as

f r (x) = lim →0+ f (x + ) for all x ∈ R + and f l (0) = f (0) and f l (x) = lim →0+ f (x -) for all x ∈ R + , x = 0. Definition 3 (2-surjective function). A function f : D → I is said 2-surjective if ∀y ∈ I, ∃x, x ∈ D, x = x , f (x) = f (x ) = y. (1)
Proposition 1. A non-decreasing and 2-surjective function f : D → I satisfies f (0) = 0.

Min/max-plus and interval bounding pairs

Definition 4 (Convolutions). Let f, g : R + → I two functions. The min-plus, and max-plus convolutions are respectively defined as

(f * g)(t) def = inf f (u) + g(v) u, v ∈ R + , u + v = t , (f * g)(t) def = sup f (u) + g(v) u, v ∈ R + , u + v = t .
The respective Kleene-star closures, also known as sub-additive and sup-additive closure, are defined by

f * def = inf {e, f, f * f, f * f * f, . . .} f * def = sup {-e, f, f * f, f * f * f, . . .}
with e the neutral element of the min-plus convolution, e(0) = 0, e(x) = ∞ otherwise.

In [START_REF] Boudec | Network Calculus, ser. LNCS[END_REF] is given a comprehensive list of properties of these operators (associativity, commutativity, isotonicity, etc.)

∀t, d ∈ R + , φ(d) ≤ f (t + d) -f (t) ≤ φ(d). (2)
The pair (φ, φ) is often denoted φ. This pair is called interval bounding pair.

Conversely, the set of functions respecting the constraint φ is denoted

F(φ) def = f ∀t, d ∈ R + , φ(d) ≤ f (t + d) -f (t) ≤ φ(d) . The condition (2) is equivalent with f * φ ≤ f ≤ f * φ [2].
Theorem 1 (Tightening interval bounding pair). Let φ, φ, φ , φ : R + → R + be two pairs of functions. Then

F φ, φ = F φ * , φ * F(φ, φ) ∩ F(φ , φ ) = F(φ ∨ φ , φ ∧ φ )
The proof can be found in [START_REF] Boudec | Network Calculus, ser. LNCS[END_REF]. A better results, F(φ, φ) = F(φ φ, φ φ) involving the mindeconvolution, and the max-deconvolution, can be found in [START_REF] Moy | Arrival curves for real-time calculus: The causality problem and its solutions[END_REF][START_REF]Arrival curves for real-time calculus: the causality problem and its solutions[END_REF], but these operators are not presented in this article, by lack of space.

Pseudo inverse

The core of the model presented in this paper is the function P that associate to an amount of data the related count of events. But the inverse relations is also of interest. And since the function P is non-decreasing, the inverse functions P -1 may not exist. More generally, event stream theory and network calculus handle non-decreasing functions. But even if the inverse does not exist, two pseudo-inverses can be defined, and some of their properties are presented. This works partially generalises the one presented in [START_REF] Embrechts | A note on generalized inverses[END_REF] or in [2, § 3.1.4]. The intuition is quite simple, and is illustrated in Figure 1. Only f -1 is plotted. The function f -1 is equal to f -1 except at discontinuity point, where f -1 is right-continuous. The proofs are in Appendix A.1.

Definition 6 (Pseudo inverse). Let f : R

+ → R + be a non-decreasing function. Then, f -1 and

f -1 : R + → R + are defined for all y ∈ R + as f -1 (y) = inf x ∈ R + f (x) ≥ y f -1 (y) = sup x ∈ R + f (x) ≤ y
with the convention that sup ∅ = 0 and inf ∅ = ∞.

Proposition 3 (Pseudo inverses are non-decreasing). For any non-decreasing function f : R + → R + , the functions f -1 and f -1 are non-decreasing.

Proposition 4 (Alternative definitions). For any non-decreasing function f : R

+ → R + , for all y ∈ R + f -1 (y) = sup {x f (x) < y} f -1 (y) = inf {x f (x) > y} .
Proposition 5 (Continuity of pseudo inverses). For any non-decreasing function f : R

+ → R + , f -1 is left-continuous and f -1 is right-continuous.
Proposition 6 (Basic properties of pseudo inverses). For any non-decreasing f : R

+ → R + and for all y, y ∈ R + f (0) = 0 =⇒ f -1 (0) = 0 (3) f -1 (y) ≤ f -1 (y) (4)
y < y =⇒ f -1 (y) ≤ f -1 (y ) (5)
and for all

x ∈ R + f (x) ≤ y =⇒ x ≤ f -1 (y) (6) f (x) ≥ y =⇒ x ≥ f -1 (y) (7) f (x) < y =⇒ x ≤ f -1 (y) (8)
f (x) > y =⇒ x ≥ f -1 (y) (9)
x

> f -1 (y) =⇒ f (x) ≥ y (10) x < f -1 (y) =⇒ f (x) ≤ y (11) x > f -1 (y) =⇒ f (x) > y (12) x > f -1 (y) =⇒ f (x) > y (13) x < f -1 (y) =⇒ f (x) < y. ( 14
)
Moreover, if f is right-continuous at point x f (x) < y =⇒ x < f -1 (y) (15)
x

≥ f -1 (y) =⇒ f (x) ≥ y (16)
and when f is left-continuous at point

x f (x) > y =⇒ x > f -1 (y) (17) x ≤ f -1 (y) =⇒ f (x) ≤ y. ( 18
)
Proposition 7 (Pseudo inverses and composition). For any non-decreasing functions f, g :

R + → R + f -1 • f (x) ≤ x ≤ f -1 • f (x) (19) Moreover, if f is right-continuous f • f -1 • f = f (20)
and if it is left-continuous

f • f -1 • f = f. ( 21
) (f • g) -1 ≥ g -1 • f -1 (22) (f • g) -1 ≤ g -1 • f -1 . ( 23
) x f (x) y f -1 (y) y f -1 (y) Figure 1: Illustration of pseudo-inverse. Moreover, if f is right-continuous (f • g) -1 = g -1 • f -1 (24)
and if it is left-continuous

(f • g) -1 = g -1 • f -1 . ( 25
)
Proposition 8 (Pseudo inverses and IBP). For any non-decreasing function f : R

+ → R + , if φ, φ is an IBP for f , then φ -1 , φ -1 is an IBP for both f -1 and f -1 . That is, for all y, δ ∈ R + φ -1 (δ) ≤ f -1 (y + δ) -f -1 (y) ≤ φ -1 (δ) (26)
φ -1 (δ) ≤ f -1 (y + δ) -f -1 (y) ≤ φ -1 (δ). (27)
Moreover, for all y, δ ∈ R

+ φ -1 (δ) ≤ f -1 (y + δ) -f -1 (y) ≤ φ -1 (δ). ( 28
)
Proposition 9 (Bound on discontinuities). Let f : R + → R + be a function and φ such that

φ(0+) = lim →0 φ( ), ∀t, d ∈ R + , f (t + d) -f (t) ≤ φ(d) and let f -1 ∈ f -1 , f -1 be one pseudo-inverse. ∀y ∈ [f (0), f (+∞)] : y -f • f -1 (y) ≤ φ(0+) (29) for f left continuous, ∀y ∈ [f (0), f (+∞)] : y -φ(0+) ≤ f • f -1 (y) ≤ y (30) for f right continuous, ∀y ∈ [f (0), f (+∞)] : y ≤ f • f -1 (y) ≤ y + φ(0+) (31)
Proposition 10 (Pseudo inverses and convolution). For any non-decreasing functions f, g :

R + → R + f -1 * g -1 -1 ≤ f * g f -1 * g -1 -1 ≥ f * g

The linking model

This section presents the data flow model, made of three curves, A, E, P . The definition, presented in Section 4.1, will be discussed just after.

A mathematical definition

Before giving a formal definition of the model, a data-flow based interpretation is proposed.

In this model, a data flow is modelled by three curves, A such that A(t) represents the cumulative amount of data/bits sent by the flow up to time t, E such that E(t) represents the cumulative number of (full) packets sent by the flow up to time t, and P such that P (a) is the number of (full) packets in the a first bits of the flow. These three functions are linked by the relation P

• A = E.
While considering the workload generated by a task, E(t) represents the number of task instances (often called "jobs") released up to time t, A(t) represents the total workload associated to these jobs, and P (a) the number of task instances associated with the global workload a.

On may wonder why not to derive A from E and individual packets sizes or task instance workload, that uses a more intuitive semantics than the one of P . This will be discussed in Sections 4.3 and 4.5.

Naming The A function represents the amount of data. In previous network calculus publications, the A was used for arrival. The P is of course for packet count. The E comes from the event stream theory.

Definition 7 (Flow tuple). A flow is modelled by a tuple A, E, P such that

A : R + → R + , E : R + → N, P : R + → N, P • A =E.
The three functions, A, E, P are non-decreasing, piecewise continuous and A(0) = 0. Moreover, the P function is 2-surjective.

Corollary 1. For any flow A, E, P , P (0) = E(0) = 0.

Proof. By Proposition 1, P (0) = 0, and by definition E(0) = P (A(0)) = 0.

On function domain

We chose a dense time domain, whereas some other real-time models assume a discrete time domain, N. Since a computer-based system is driven by a discrete clock, a discrete time domain is a sound assumption. Nevertheless, while considering a distributed system, made of different sub-systems, each sub-system may have its own clock, and hence its own clock drift. There is then no guarantee that a common discrete clock exists. This justifies our choice of a dense time domain.

We also set R + as the domain of P . When a flow sends an infinite amount of data, i.e.

lim t→∞ A(t) = ∞, it is an obvious requirement, but event with a flow sending a finite amount of data, i.e. lim t→∞ A(t) = M ∈ R + , the model requires that P is defined even for values on [M, ∞). The theoretical model may have been defined to weaken this requirement, but it would imply a more complex definition. Nevertheless, the Definition 10 will later have to restrict some condition on P on its relevant prefix. This is a trade-off between including the specific case of finite flow in the flow definition or further.

On information redundancy

It is clear that the use of an explicit function E creates information redundancy, but one of the purposes of this model is to build an explicit link between network calculus and event stream theories. Then, existing results in one theory can be transferred to the other. Moreover, when dealing with contracts, three interval bounding pairs captures more information than only two, as will be shown in Section 5. Note also that even if, obviously, E can be deduced from A and P , the converse is not true. First, P can not be deduced from A and E, in general: if several packets are received at the same time (when it exists t such that E(t+) -E(t-) ≥ 2), there is no way to know the individual size of each packet, it exists an infinite number of P satisfying the relation. Second, neither can A be deduced from E and P : E represents the instant of the end of packet arrival, and P the size of individual packets, but the information of bit arrival rate "inside" each packet is lost.

t 1 2 3 4 5 A(t) 1 2 t E(t) 1 2 t E (t)

On continuity

In classical network calculus theory, the A function is left-continuous, but the handling of packets is a pity4 . Let us illustrate the impact of left-or rigth-continuity on some examples when handling packets.

As an example, let us consider the A function in Figure 2. To model packets of size 1, the E function in Figure 2 can be used. This function counts one packet when exactly one unit of data is received, that is at time t = 1. It then counts the second packet when exactly two units of data are received, that is at time t = 3. This function E is then right-continuous.

To get a left-continuous function, one could think about E = E l the left-continuous extension of E, as depicted in Figure 2. Unfortunately, this function breaks the constraint P • A = E . Indeed, for any function P such that P • A = E , we would have 0 = E (1) = P (A(1)) = P (1) = P (A(2)) = E (2) = 1 which is impossible.

The function E in Figure 2 could constitute a valid choice but it then models the time at which the emission of each packet of size 1 starts. This is not very satisfactory as one usually expects to count packets only when they are complete.

To sum up, we have presented arguments to use right-continuous functions, but there also are arguments in favour of left-continuous functions in network calculus theory.

On the packet function and individual packet sizes

We have justified, while giving the definition of a flow, why it uses the P function, whose semantics is not obvious at first glance. Here is presented the equivalence between this notion and the individual packet sizes.

Assume that the data flow is a sequence of packets, the i-th packet having length

5 l i . Let L : N → R + defined as L(n) = n i=1 l i .
This cumulative packet size function is equivalent to the list of individual packets sizes, since l i = L(i) -L(i -1), but easier to handle in our context.

Definition 8 (Cumulative packet length). A function L

: N → R + is a cumulative packet length function if 1. it is increasing (n < n =⇒ L(n) < L(n )), a (P(L))(a) L(1) L(2) L (3)
a

(P (L))(a)
Figure 3: The packet function built from cumulative length.

2. it is null at 0 (L(0) = 0),

3. it is divergent (lim n→∞ L(n) = ∞).
Definition 9 (From packet function to cumulative packet length and back). Let P, P two operators which maps each cumulative packet length function L to the non-decreasing piecewise continuous 2-surjective functions defined as

(P(L))(a) def = max {n ∈ N L(n) ≤ a} , ( 32
) (P (L))(a) def = [min {n ∈ N L(n) ≥ a} -1] + . (33)
Let L the operator which maps each non-decreasing piecewise continuous 2-surjective function to the cumulative packet length function

(L(P ))(n) def = inf d ∈ R + P (d) ≥ n . (34)
Note that eq. 34 is equivalent to L(P ) = P -1 .

We have to prove that the definition is well formed, that is to say that P(L) is a non-decreasing piecewise continuous 2-surjective function, and that L(P ) is a cumulative packet length function. To do so, the following Lemma gives the main arguments. The proof itself is in Appendix A.2.

Lemma 1 (Equivalent definitions of P). Let L be a cumulative packet length function, and n ∈ N, then:

∀a ∈ [L(n), L(n + 1)) : (P(L))(a) = n (35) (P(L))(a) = sup x ∈ R + L( x ) ≤ a (36) ∀a ∈ (L(n), L(n + 1)] : (P (L))(a) = n ( 37
) (P (L))(0) = 0 ( 38
)
The Figure 3 illustrates the eq. ( 35) and (37). The eq. 36 is useful since it allows to define the operator P as a pseudo-inverse:

P(L) = (L • • ) -1 .
Proof. Let L be a cumulative packet length function, P = P(L) and P = P (L). For the eq. (35

), if a = L(n), n ∈ {n L(n ) ≤ L(n)}, and since L(n) is increasing, given m > n, L(m) > L(n) and m / ∈ {n L(n ) ≤ L(n)}. Otherwise, if a ∈ (L(n), L(n + 1)
) and to ease readability, set N = {n ∈ N L(n) ≤ a}. Then, L(n) ≤ a, so n ∈ N , and n ≤ max N = P (a). Consider m = n + 1: a < L(m), so m / ∈ N , so m > max N i.e. n + 1 > P (a). Combining n + 1 > P (a) ≥ n leads to P (a) = n. The eq (37) is done the same way: if a = L(n + 1), n + 1 ∈ {n L(n ) ≥ L(n + 1)}, then n ≥ P (L(n + 1)). For any m < n + 1, m / ∈ min {n L(n) ≥ a}, so m < min {n L(n) ≥ a}.

Otherwise, if a ∈ (L(n), L(n + 1)), n ∈ {n L(n ) ≥ L(n)}, then [n -1] + ≥ P (L(n)).
If n = 0, the equality holds. If n > 0, for any m < n, m / ∈ min {n L(n) ≥ a}, so m < min {n L(n) ≥ a}.

Last, value of P at 0 is obvious.

For eq (36), pick some a, keep the same definition of N and set X = x ∈ R + L( x ) ≤ a .

Given n ∈ N , n = n so n ∈ X , i.e. N ⊆ X and max N ≤ sup X . Conversely, given x ∈ X , it exists n ∈ N (consider n = x ) such that x ≤ n. Then, sup X ≤ max N .

Theorem 2 (Equivalence between cumulative packet length and packet functions). For any cumulative packet length function L, (L • P)(L) = L, and

(L • P )(L) = L.
This theorem states that cumulative packet length functions and the non-decreasing piecewise continuous 2-surjective functions are equivalent, that is to say, in our context, that modelling the packet sizes either by a P or an L function is equivalent. The proof is in Appendix A.2.

Flow contracts

The real behaviour of a data flow, or request sequence, is in general unknown, or too complex to be handled. Then, some contracts, or patterns, on the behaviour are used, involving often some period, jitter, minimal or maximal size, etc. Such constraints are called "arrival curves" in network calculus, or "event model" in event stream theory. Here is defined a notion of contract that embraces the previous notions.

Definition 10 (Interval bounding tuple of flow). Let A, E, P be a flow, and α, η, π three IBP. Then, the flow A, E, P respect the contract α, α, η, η, π, π if the pairs (α, α), (η, η) are respectively interval bounding pairs for functions A and E, and

∀a, d ∈ R + , a + d ≤ lim x→∞ A(x) : π(d) ≤ P (a + d) -P (d) ≤ π(d) (39)
Conversely, the (possibly empty) set of flow satisfying theses constraints is denoted F(α, η, π).

The semantics of α and η are quite intuitive: they are lower and upper bounds on the amount of data or event received on some interval. The semantics of π deserves a discussion: π could be counter-intuitive since a flow with large packets will have a smaller π function than a flow with small packets. The mathematical reason is that P is the pseudo-inverse of the packet length function L, as presented in Section 4.5. The semantics of π could be the following: imagine that there exists a "end of packet" delimiter in the data flow just after each packet. Then, given any slice of a trace of length a, π(a) and π(a) are respectively lower and upper bounds on the number of "end of packet" delimiters than can be found in the slice.

Once defined this contract notion, this section will show how to automatically tighten these contracts using algebraic properties, and using information on some functions to get a better characterisation of the other ones.

First, the equations ( 40) and ( 41) allow to tighten a contract, pair per pair. Second, the Theorems 4, 5 and 6 allow to transfer information from two contracts on the third one. Combining all these results with eq. ( 42) enables to build a sequence of contracts, converging to a fixpoint. Theorem 3 (Tightening contracts). Let α, α , η, η , φ, φ three interval bounding pairs functions. Then

F(α, α, η, η, π, π) = F(α * , α * , η * , η * , π * , π * ) (40) F(α, α, η, η, π, π) = F(α, α, η , η , π , π ) (41) F(α, α, η, η, π, π) ∩ F(α , α , η , η , π , π ) = F(α ∨ α , α ∧ α , η ∨ η , η ∧ η , π ∨ π , π ∧ π ) ( 42
)
The eq. ( 41) allows to restrict values of bounds on P and E to integer values. We may have enforced it by setting N as the image of these functions in the definitions, but when implementing tools, it may be easier to handle functions with real values 6 . Then, the formal model allows to use R

+ as image and also to restrict it to N.

Proof. The eq. ( 40) and ( 42) are a direct application of Theorem 1. Consider first the restriction to η , η . Let A, E, P ∈ F(α, α, η, η, π, π) and t, d ∈ R + .

Since E(t), E(t + d) ∈ N, and E is non-decreasing, then

E(t + d) -E(t) ∈ N. So, η(d) ≤ E(t+d)-E(t) ≤ η(d) implies η (d) ≤ E(t+d)-E(t) ≤ η (d). Conversely, since η(d) ≤ η (d) and η(d) ≥ η (d), η (d) ≤ E(t + d) -E(t) ≤ η (d) =⇒ η(d) ≤ E(t + d) -E(t) ≤ η(d).
Then F(α, α, η, η, π, π) ⊆ F(α, α, η , η , π, π). The restriction on π , π is done the same way.

Theorem 4 (Bounding event count from data and packet bounds). Let α, π two IBP. Then

F(α, •, π) ⊆ F (α, (π • α, π • α) , π) . ( 43
)
This theorem allows, for each flow A, E, P , to compute an IBP for E from the ones for A and P .

Example of event count with linear arrival Consider a flow made of packets of maximal size 3 and minimal size 1 2 . Then, π(a) = a 3 and π(a) = 2a . Consider that the flow throughput is at most 2 and at least 1 5 , leading to α(t) = t 5 and α(t) = 2t. Then, the Theorem 4 states that 4t is an upper bound on the number of event: since the maximal rate is 2 per time unit, the flow can send one packet of size 1 2 every 1 4 time unit. Conversely, t 15 is a lower bound: it may take 15 time units to send a packet of size 3 with a throughput of 1 5 .

Proof. Let A, E, P ∈ F(α, •, π) a flow. Given t, ∆ ∈ R + , by definition of a flow,

E(t + ∆) -E(t) = P (A(t + ∆)) -P (A(t)).
By definition of α and α

α(∆) ≤ A(t + ∆) -A(t) ≤ α(∆) ⇐⇒ α(∆) + A(t) ≤ A(t + ∆) ≤ α(∆) + A(t)
then, since P is a non-decreasing function

P (α(∆) + A(t)) ≤ P (A(t + ∆)) ≤ P (α(∆) + A(t)).
Now, add -P (A(t)) to each term P (α(∆) + A(t)) -P (A(t)) ≤ P (A(t + ∆)) -P (A(t)), P (A(t + ∆)) -P (A(t)) ≤ P (α(∆) + A(t))) -P (A(t)).

Consider now the upper bound, by definition of π

P (α(∆) + A(t))) -P (A(t)) ≤ π(α(∆)).
The same way, for the lower bound:

P (α(∆) + A(t))) -P (A(t)) ≥ π(α(∆)).
Then,

E ∈ F(π • α, π • α), and A, E, P ∈ F (α, (π • α, π • α) , π).
Theorem 5 (Bounding data amount from event and packet bounds). Let η, π two interval bounding pairs, then

F(•, η, π) ⊆ F π -1 • η, π -1 • η , η, π . ( 44
)
6 For example, consider two period flow, one sending one packet every 5 time unit, and the other every 7 time unit. Then, η 1 = • 5 and η 1 = • 7 are two upper bounds on the event number with values in N and η 1 (t) = t 5 + 1, η 2 (t) = t 7 + 1 are two others, wider, with values in R + . But the sum of the two last ones is easier to represent in computer than the sum of the two first ones.

π = η = • π = • π -1 π -1 • η E = P = • A Figure 4: Example of periodic constant size packet. Proof. Let A, E, P ∈ F(α, •, π) a flow. From relation P • A = E, it comes P -1 (E) ≤ A ≤ P -1 (E). Then, given t, ∆ ∈ R + : A(t + ∆) -A(t) ≤ P -1 (E(t + ∆)) -P -1 (E(t)) ( 45
)
by definition of η, and monotony of P -1

≤ P -1 (E(t) + η(∆)) -P -1 (E(t)) (46)
and from Prop. 8, eq. ( 28),

≤ π -1 (η(∆)) (47)
The proof for the lower bound is done the same way.

Example of arrival curve with unit model Consider a flow sending one packet of size one every time instant. That is to say E(t) = t and P (d) = d . It admits IBP η = π = • , and η = π = • . What can be the arrival curve of such a flow? One may expect to get no more than one unit of data per unit of time (A = • ), but it is not necessarily the case. Applying Thm. 5 leads to the arrival curve α = π -1 • η = • + 1, enabling a burst of one packets in null time and two packets on any interval of arbitrary small length > 0.

Using sub-additive closure, one may enhance slightly the result, and consider (α) * = ( • + 1) ∧ δ 0 , but it still allows the arrival of two packets in any interval of arbitrary small length. This is somehow counter intuitive.

But it may happen, up to some . Keep in mind that E is increased when a packet is fully received. One can build a flow A that send one "full" packet of size 1 each time unit but that can send 2 -data on some interval of width : see the A drawn in Figure 4 with some linear slopes to connect the points

A(0) = 0, A(1 -) = , A(1 + ) = 2 -, A(3 -) = 2 + , etc.
Theorem 6 (Bounding packet sizes from event and data bounds). Let α, η two interval bounding pairs, then

F(α, η, •) ⊆ F α, η, η l • α -1 , η r • α -1 . (48)
Proof. Let A, E, P a flow. Let u, Γ ∈ R + , be two values of data amount. The proof has to bound P (u + Γ) -P (u) for any u + Γ ≤ lim t→∞ A(t).

Since A(0) = 0 and A is non-decreasing, it exists t (for instance t := A -1 (u)) such that for any > 0, A((t -) ∨ 0) ≤ u ≤ A(t + ). Since P is non-decreasing, it leads to P (u + Γ) -P (u) ≤ P (A(t + ) + Γ) -P (A((t -) ∨ 0)).

S A, E, P

A , E , P Now, let ∆ = α -1 (Γ). By definition of the pseudo inverse, for all > 0, α(∆ + ) > Γ, hence

P (u + Γ) -P (u) ≤ P (A(t + ) + α(∆ + )) -P (A((t -) ∨ 0)).
By definition of α, α(∆ + ) ≤ A(t + + ∆ + ) -A(t + ), so P (u + Γ) -P (u)

≤ P (A(t + + ∆ + )) -P (A((t -) ∨ 0)) = E(t + + ∆ + ) -E((t -) ∨ 0) ≤ η(∆ + 2 + )
To sum up, for any u, Γ ∈ R + , > 0 and > 0,

P (u + Γ) -P (u) ≤ η(α -1 (Γ) + 2 + )
And now, letting and tend to 0, by definition of right-continuous extension

P (u + Γ) -P (u) ≤ η r (α -1 (Γ))
The proof on the lower bound is done the same way.

Application: modeling packetizers and aggregation

Once defined the model and its main intrinsic properties, this section presents two basic applications, the modelling of a packetizer, and its interval bounding tuple, and the same for aggregation of two flows.

Packetizer

A packetizer, as in Figure 5, takes as input a flow and outputs another flow with the same packets but in which data are released only when a full input packet is received. An example of input and output is displayed in Figure 6.

Definition 11. A packetizer maps any input flow A, E, P such that P is right-continuous to an output flow A , E , P such that

A = P -1 • P • A, E = E, P = P. S A 1 , E 1 , P 1 A 2 , E 2 , P 2
A, E, P Proof. We have to prove that A , E , P defined as above is a flow. In particular, we need to prove that P (A ) = E , that is P • P -1 • P • A = P • A. This holds according to Proposition 6 since P is right-continuous.

Remark 1. If P is not right-continuous, the above property may not hold. For instance, for P = • , we have P (1.5) = 2 whereas

P • P -1 • P (1.5) = P • P -1 (2) = P (1) = 1.
Proposition 11 (Contract at packetizer output). Given a flow A, E, P ∈ F (α, η, π) entering a packetizer, and let A , E , P be the output, then

A , E , P ∈ F π -1 • η, π -1 • η , η, π .
Proof. For any t, δ ∈ R + , A (t+δ)-A (t) = P -1 •E(t+δ)-P -1 •E(t) and since E(t+δ)-E(t) ≤ η(δ) and P -1 is non-decreasing, we then have

A (t + δ) -A (t) ≤ P -1 (E(t) + η(δ)) -P -1 (E(t)) ≤ π -1 (η(δ))
by Prop. 8, eq [START_REF] Bouillard | An algorithmic toolbox for network calculus[END_REF]. The proof for the lower bound is similar.

Aggregation

Aggregation takes two flows A 1 , E 1 , P 1 and A 2 , E 2 , P 2 as input and immediately puts their packets in a common output flow A, E, P . This is pictured in Figure 7. In network calculus, as in the event stream theory, the aggregation of two flows is defined as the sum of the modelling functions, that is

A = A 1 + A 2 and E = E 1 + E 2 .
The definition of P is less obvious. Of course, for A, E, P to be a flow according to Definition 7, P must satisfy P • A = E, that is P (A 1 + A 2 ) = E 1 + E 2 = P 1 (A 1 ) + P 2 (A 2 ). However, this does not precisely define P , particularly when A 1 and A 2 present discontinuities, which happens for instance when they are taken as output of packetizers. As we would like to keep the fact that the packets in the ouput flow are just an interleaving of the one in the two input flows, we additionally require that L := L (P ) is an interleaving of L 1 := L (P 1 ) and L 2 := L (P 2 ). We thus end up with the following definition.

Definition 12 (Aggregation). Aggregation maps any two input flows (A 1 , E 1 , P 1 ) and (A 2 , E 2 , P 2 ) to an output flow (A, E, P ) such that

A = A 1 + A 2 , E = E 1 + E 2 , P (A 1 + A 2 ) = P 1 (A 1 ) + P 2 (A 2 )
and there exists ϕ 1 , ϕ 2 : N → N such that for all n ∈ N, 0

≤ ϕ 1 (n + 1) -ϕ 1 (n) ≤ 1, ϕ 2 (n) = n -ϕ 1 (n) and P = P (L (P 1 ) (ϕ 1 (n)) + L (P 2 ) (ϕ 2 (n))) .
Intuitively, ϕ 1 (n) (resp. ϕ 2 (n)) denotes the number of packets taken from the first (resp. second) flow among the first n packets of the output flow.

Remark 2. The input flows should be taken as output of packetizers, otherwise the above conditions usually have no solution.

Proposition 12 (Contract on aggregation output). Given two flows A 1 , E 1 , P 1 ∈ F (α 1 , η 1 , π 1 ) and A 2 , E 2 , P 2 ∈ F (α 2 , η 2 , π 2 ), and let A, E, P be one aggregation, then

A, E, P ∈ F α 1 + α 2 , η 1 + η 2 , π 1 * π 2 , π 1 * π 2 .
Proof. In the output A and E are defined as sums of the input, hence the result for α and η.

The result for π is slightly more involved. For all i ∈ {1, 2}, by definition π i is an IBP for P i , hence, by Prop. 8, eq. ( 26), for all n , m ∈ N

π i -1 (m ) ≤ L i (n + m ) -L i (n ) ≤ π i -1 (m )
where L i := L (P i ) = P i -1 . Thus, for any n, m ∈ N and ϕ i satisfying the constraints in Definition 12

π i -1 (ϕ i (n + m) -ϕ i (n)) ≤ L i (ϕ i (n + m)) -L i (ϕ i (n)) and L i (ϕ i (n + m)) -L i (ϕ i (n)) ≤ π i -1 (ϕ i (n + m) -ϕ i (n)).
By definition of ϕ 2 : n → n -ϕ 1 (n), we have for all n, m ∈ N, (ϕ

1 (n + m) -ϕ 1 (n)) + (ϕ 2 (n + m) -ϕ 2 (n)) = m, hence for L := L 1 • ϕ 1 + L 2 • ϕ 2 π 1 -1 * π 2 -1 (m) ≤ L(n + m) -L(n) ≤ π 1 -1 * π 2 -1 (m).
Then, for all y, δ ∈ R

+ π 1 -1 * π 2 -1 ( δ ) ≤ L( y + δ ) -L( y ) and L( y + δ ) -L( y ) ≤ π 1 -1 * π 2 -1 ( δ ).
Thus, for P := P (L) = (L • . ) -1 , by applying Prop. 8, eq. ( 27), we have for all u, Γ ∈ R

+ π 1 -1 * π 2 -1 • . -1 (Γ) ≤ P (u + Γ) -P (u)
and

P (u + Γ) -P (u) ≤ π 1 -1 * π 2 -1 • . -1 (Γ).
Since, by Proposition 5, π 1 -1 and π 1 -1 are right-continuous, π 1 -1 * π 2 -1 is right continuous, according to Proposition 2, and by Proposition 7

π 1 -1 * π 2 -1 • . -1 = . -1 • π 1 -1 * π 2 -1 -1 = π 1 -1 * π 2 -1 -1 .
Hence the upper bound, according to Proposition 10. The proof for the lower bound is completed in the same way.

Conclusion

This work presents a common model that embeds the flow models of network calculus, based on data amount, and event stream theory, based on event count. As presented in the introduction, the expected benefits are: first, a better understanding of each theory; second, the ability to analyse a component with one theory or the other, or even both, and to re-inject the results from one of the flow model into the other ; last, the ability to model systems that are coarsely modelled up to now .

In distributed system, the tightness of the bounds relies on the ability to model what is called serialisation [?], grouping [?], shaping [START_REF] Boudec | Network Calculus, ser. LNCS[END_REF], or flow correlation [START_REF] Rox | Compositional performance analysis with improved analysis techniques for obtaining viable end-to-end latencies in distributed embedded systems[END_REF], i.e. the fact that when several flows share the same resource (a bus, a data link, a CPU), at the output, some serialisation exists, since not all packets/requests can have been served at the same time. Some (dynamic) offset exists between the packets/requests, and modelling this aspects may have an important impact on performance evaluation. From the point of view of methods based on arrival curves, this requires to compute an upper bound on the packets/requests of a set of flows that is tighter than the sum of the individual upper bounds. And in the case of network, this shaping is related to the throughput, then, to the amount of data, independently of the packet boundaries. On the opposite, when a task is released by a message, the workload may be independent of the packet size. Then, one have to extract the number of messages from the data amount: this is quite easy if all messages have the same size, but if each flow may have its own message size, our model can capture it.

This first work defines the model and its basic properties, inside a robust mathematical framework. The results involve compositions, convolutions, and pseudo-inverses on functions. Such operations have been implemented for the ultimately pseudo-periodic class of functions [START_REF] Bouillard | An algorithmic toolbox for network calculus[END_REF], except the composition, which is a on-going work.

We then plan to test the accuracy of this model on some realistic examples, and especially some where the resource consumption is a function of both the workload and the number of requests: for example, some switch where the memory allocation is done by block of size b, i.e. the memory used to store a packet of size s is b s b . An accurate bound requires both packet sizes and the number of packets. Another example is a gateway that performs some data format conversion: in this case, the task workload is a constant, plus a part proportional to the packet size. Moreover, such a gateway often extracts some payload, removing some header, and forwards the payload with a new header. This model is also designed to model such header change.

Last, two technical remarks on the model.

• First, the choice was made to define a flow as a tuple A, E, P , but once the work done, we wonder whether P does not over specify the model, since it imposes some continuity choice, whereas the sequence L contains as much useful information. Then, in a future work, we may chose to define a flow as a tuple A, E, L .

• Second, we gave arguments to consider only right-continuous functions (see Section 4.4 and Definition 11). But, the proofs in network calculus are simpler with left-continuous assumption, even if the results still hold without, as shown in [?]. The continuity choice is postponed to further studies.

Thanks

We would like to thank Anne Bouillard, for the pioneer work done in [START_REF]Packetization and packet curves in network calculus[END_REF][START_REF] Bouillard | Packetization and aggregate scheduling[END_REF], and some informal discussions on the subject, and Sophie Quinton, for her great interest on this thematic that gave us the energy to formalise it.

→0+

f (x + ) = f (x) < y and there exists x > x such that f (x) < y. From (8), we get x ≤ f -1 (y), hence x < f -1 (y). Eq. ( 16): if x > f -1 (y), (10) concludes. If x = f -1 (y) = inf S ≥ then for all x > x, f (x ) ≥ y and by right-continuity f (x) ≥ y.

Eq. ( 17): similar to eq. ( 15). Eq. ( 18): similar to eq. ( 16).

Proof of Proposition 7. Eq. Eq. ( 21): similar to eq. ( 20). Eq. ( 22): For any y ∈ R + , for any x ∈ {x | f (g(x)) ≥ y}, by applying (7) twice, x ≥ g -1 (f -1 (y)), hence the result by definition of (f • g) -1 . Eq. ( 23): similar to eq. ( 22). Eq. ( 24): for any y ∈ R + , for any x ∈ {x | f (g(x)) < y}, by applying ( 15) and ( 8), x ≤ g -1 (f -1 (y)), hence, according to Proposition 4, (f • g) -1 ≤ g -1 • f -1 . Eq. ( 25): similar to eq. ( 24).

Proof of Proposition 8. We will only prove the last inequality f -1 (y + δ) -f -1 (y) ≤ φ -1 (δ), the other -If f -1 = f -1 , the proof is very similar.

• Inequality 30 and 31: proof uses the previous inequality and the continuity hypothesis.

Proof of Proposition 10. We have to prove that, for any t ∈ R

+ f -1 * g -1 -1 (t) ≤ (f * g) (t)
that is, by Proposition 4 and definition of *

sup x f -1 * g -1 (x) < t ≤ sup f (u) + g(v) u, v ∈ R + , u + v = t .
This amounts to prove that for any x ∈ R + , if f -1 * g -1 (x) < t, then

x ≤ sup f (u) + g(v) u, v ∈ R + , u + v = t (49) which, by definition of * amount to prove that, if inf f -1 (u ) + g -1 (v ) u , v = x < t, then (49) which again amounts to prove that, if there exist u , v such that u + v = x and f -1 (u ) + g -1 (v ) < t, then (49).

Since f -1 (u ) + g -1 (v ) < t, there exist u and v such that f -1 (u ) < u, g -1 (v ) < v and u + v = t. By Proposition 6, we have u < f (u) and v < g(v), hence

x = u + v < f (u) + g(v)
and eventually (49) since u + v = t.

The proof of the second inequality is similar.

A.2 On the packet function and individual packet sizes

Proof that the P operator of Def. 9 returns a packet function. Let L a cumulative packet length function. Let Pr = (P )(L), P l = (P )(L). We have to show that Pr, P l are piecewise continuous, nondecreasing, 2-surjective.

• Non-decreasing, continuity: The fact that Pr and P l are non-decreasing and piecewise linear is obvious from equivalent definition of Thm. 1. It also proves that P L l is left-continuous and P L r is right-continuous.

• 2-surjective: The property 2-surjective is also simple: for any n ∈ N, consider the interval (L(n), L(n + 1)). Since L(n) < L(n + 1), it exists two different elements, a, a such that L(n) < a < a < L(n + 1) and L(a) = L(a ) = n.

Figure 2 :

 2 Figure 2: Continuity and packet sizes.

Figure 5 Figure 6 :

 56 Figure 5: Packetizer. A E P

Figure 7 :

 7 Figure 7: Aggregation.

  [START_REF] Wandeler | Modular performance analysis and interface-based design for embedded realtime systems[END_REF]: by simple look on the definitions:inf {x f (x ) ≥ f (x)} ≤ x ≤ sup {x f (x ) ≤ f (x)} Eq. (20): By eq. (19), f -1 • f (x) ≤ x, hence by monotonicity of f , f • f -1 • f (x) ≤ f (x).Let's consider the other inequality. For any y, f -1 (y) = inf {x | f (x) ≥ y}, hence for any x > f -1 (y), f (x ) ≥ y and by right continuity of f , f f -1 (y) ≥ y. This gives the result for y def = f (x).

•-

  proofs being similar. Given y, δ ∈ R + , for any x ∈ {x | f (x) ≤ y + δ} andx ∈ {x | f (x ) ≥ y}, if x ≤ x, then φ(x -x ) ≤ f (x) -f (x ) ≤ δ by hypothesis. Thus x -x ≤ sup ∆ ϕ(∆) ≤ δ = φ -1 (δ)by definition of φ -1 . This also holds when x < x since thenx -x < 0 ≤ φ -1 (δ), hence sup {x f (x) ≤ y + δ} -inf {x f (x) ≥ y} ≤ φ -1 (δ)which concludes by definitions of f -1 and f -1 .Proof of Proposition 9. Inequality 29: Iff -1 = f -1 , for y ∈ [f (0), f (+∞)]: * If f -1 (y) = 0, then by hypothesis and definition of f -1 , for all > 0,f (0) ≤ y ≤ f ( ). By monotonicity of f , f (0) = f • f -1 (y) ≤ f f -1 (y) + = f ( ).Since both y andf • f -1 (y) are in [f (0), f ( )], we have y -f • f -1 (y) ≤ f ( ) -f (0) ≤ φ( ), hence the result. * If f -1 (y) > 0, denoting x := f -1 (y), by definition of x and since y ≤ f (+∞), we have for all ∈ (0, x], f (x -) ≤ y ≤ f (x + ).By monotonicity of f , f (x-) ≤ f (x) = f •f -1 (y) ≤ f (x+ ). Since both y and f •f -1 (y)are in [f (x -), f (x + )], we have y -f • f -1 (y) ≤ f (x + ) -f (x -) ≤ φ(2 ), hence the result.

"We don't necessarily need to develop new local analysis techniques if we can benefit from the host of work in real-time scheduling analysis."[START_REF] Henia | System level performance analysis -the SymTA/S approach[END_REF].

The arrival curve is even defined as a generalisation of even stream model in[START_REF] Wandeler | Modular performance analysis and interface-based design for embedded realtime systems[END_REF].

The Section

4.3 will justify why we chose P and not γ.

For example, in[START_REF] Boudec | Network Calculus, ser. LNCS[END_REF], the remark after the Lemma 1.2.1 states that "we use the convention that the cumulative functions ... are left continuous". But on the section of packetizers, § 1.7.2 and Fig.1.17, right-continuous functions are used.

One often uses the term "size" of packet, but the letter "s" is commonly used to denote servers.

A Proof of equivalence between cumulative packet length and packet functions

Here are gathered proofs whose details are not essential to the understanding of the paper.

A.1 Mathematical background

Proof of Proposition 1. f being 2-surjective, there exists x ∈ D such that f (x) = 0. Since f is nondecreasing, f (0) ≤ f (x) = 0.

Proof of Proposition 2. We have to prove that for any x ∈ R + , lim

f and g are non-decreasing, f * g is also non decreasing and lim

. It then remains to show the other inequality, that is that for all , there exists η such that for all ∈ (0, η]

by right-continuity of f and g, there exists η such that for all ∈ (0, η], f

The proof of the second property is similar.

Proof of Proposition 3. Let y, y ∈ I such that y < y . Then ∀x ∈ D,

The proof on f -1 is done the same way.

Proof of Proposition 4. Given f , for any with ∈ {≤, <, >, ≥}, let us introduce the notation S y = {x f (x) y}, and do the proof for f -1 . The goal is to prove that inf S ≥ y = sup S < y . For any x ∈ S ≥ y , f (x) ≥ y and for any x ∈ S < y , y > f (x ), leading to f (x) > f (x ), and, since f is non-decreasing, to x > x . Then, inf S ≥ y ≥ sup S < y . The second step of the proof is done by contradiction. Assume that inf S ≥ y > sup S < y , then, it exists x such that inf S ≥ y > x > sup S < y . If x < inf S ≥ y , then x / ∈ S ≥ y , i.e. f (x) < y, that implies x ∈ S < y and x ≤ sup S < y . The proof for f -1 is done the same way.

Proof of Proposition 5. Only left-continuity of f -1 is given. The right-continuity of f -1 can be done the same way.

Given y ∈ R + , and set X = {x f (x) < y} and x = sup X. Then f -1 (y) = x (equivalent definition, Proposition 4). Now consider f (x-) = lim →0 f (x -) the limits to the left of f at x. First, consider the case where y = f (x-), and let > 0.

In this case, for any y ∈ (f (x-), y], it does not exists any x such that y > f (x ) > y (otherwise, such x would be an element of X), meaning that {x f (x) < y} = {x f (x) < y }, leading to f -1 (y ) = f -1 (y). That is to says, it exists interval (f (x-), y] such than, for any y ∈ (f (x-), y], f -1 (y)-f -1 (y ) = 0 ≤ .

• lima→∞ Pr(a) = ∞: set some m ∈ R + , the goal is to prove that it exists a such that Pr(a) ≥ m.

From Prop. 1, for any a ∈ (L(m), L(m + 1), Pr(a) = m, so it exists a such that Pr(a) ≥ m. The proof for P l is the same.

Proof that the L operator of Def. 9 returns a cumulative packet length function. Let P be a piecewise continuous, non-decreasing, 2-surjective function, and L = L(P ).

To show that L is a cumulative packet length function, the three sub-objectives are: L is increasing, L(0) = 0 and L diverges.

• L is increasing: Let n, n ∈ N such that n < n . Since P is 2-surjective, it exists x, y such that x < y, P (x) = P (y) = n. The equality

This part of the proof requires that P is 2-surjective. Otherwise, P L can be only non-decreasing, not increasing i.e. it can exists a packet of null size.