Anne Bouillard
email: anne.bouillard@bretagne.ens-cachan.fr

Laurent Jouhet
email: laurent.jouhet@ens-lyon.fr

Eric Thierry
email: thierry@ens-lyon.fr

Service curves in Network Calculus: dos and don'ts

Keywords: Network Calculus, politique de service Network Calculus, politique de service

This report is a survey about service curves used in envelope-based models for worstcase performance evaluation, like Network Calculus or Real-Time Calculus. In a first part, we compare different models and their notions of service curves by establishing a hierarchy and similarities between different types of service curves and in a second part, we compare the behaviours of simple and strict service curves for concatenation and residual service curves.

Introduction

Network Calculus is a theory of deterministic queuing systems encountered in communications networks. It is based on (min, +) algebra and it can be seen as a (min, +) filtering theory by analogy with the (+, ×) filtering theory used in traditional system theory. More than just a formalism, it enables to analyze complex systems and to prove deterministic bounds on delays, backlogs and other Quality-of-Service (QoS) parameters. The analysis usually focuses on worstcase performances. The information about the system features are stored in functions, such as arrival curves shaping the traffic or service curves quantifying the service guaranteed at the network nodes. These functions can be combined together thanks to special Network Calculus operations, in order to analyze the system and compute bounds on local performances (i.e. maximum buffer size at a node) or on end-to-end performances (i.e. maximum end-to-end delay. At the present time, the theory has developed and yield accomplished results which are mainly recorded in two reference books: Chang's book [START_REF] Chang | Performance Guarantees in Communication Networks[END_REF] and Le Boudec and Thiran's book [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF].

Nevertheless it remains difficult to draw the exact borders of Network Calculus at the time being. One of the main obstacles comes from the apparent variety of service curve definitions in the literature which might lead to different types of models. In some papers, the use of one definition instead of another one does not seem to play an important role, whereas some other papers cautiously warn the readers to use the right definition to ensure relevancy or validity. One objective of this report is to unveil the differences between models yielded by the different definitions. Some of the results presented here could be classified as folklore theorems since they are sometimes quoted in the literature without proofs. We try to fill those gaps by proposing a proof for each of our statements.

Even if Network Calculus is still a developing theory without clear frontiers, some people have already described alternate theories using nevertheless close formalisms (envelope-based models, (min, +) operators) but claimed to be more precise or more relevant to their own applications. One can cite Real-Time Calculus, Sensor Calculus... A small presentation with apparent similarities/differences is presented in Table 1. The Applications line states the applications originally intended, or said differently the community that was involved in the first communications. DISCO Network Calculator [START_REF] Schmitt | The disco network calculator: a toolbox for worst case analysis[END_REF][START_REF] Gollan | The disco network calculator[END_REF], COINC [START_REF] Bouillard | COmputational Issues in Network Calculus[END_REF], Rockwell Collins ConfGen RTC Toolbox [START_REF] Wandeler | Modular Performance Analysis and Interface-Based Design for Embedded Real-Time Systems[END_REF][START_REF] Thiele | Embedded software in network processors models and algorithms[END_REF][START_REF] Wandeler | System architecture evaluation using modular performance analysis -a case study[END_REF][START_REF] Chakraborty | Performance evaluation of network processor architectures: Combining simulation with analytical estimation[END_REF],

CyNC [START_REF] Schioler | Network calculus for real time analysis of embedded systems with cyclic task dependencies[END_REF][START_REF] Schioler | Cync: a matlab/simulink toolbox for network calculus[END_REF] Table 1: Comparison between several theories based on the (min,plus) algebra.

One can question whether the models analyzed in those theories are really different from Network Calculus models. If so, where do the differences lie? and are they deep? We will try to give partial answers to those questions, in particular concerning Real Time Calculus. We will see that rather than alternate theories we are in presence of extensions of Network Calculus usual models (e.g. by taking into account maximal services and not only minimal services).

Note that we stay focused on models without probabilistic assumptions and theories aiming at computing (deterministic) worst case performances. On the probabilistic side, several formalisms have been presented in the literature under the banner "Stochastic Network Calculus" [START_REF] Chang | Performance Guarantees in Communication Networks[END_REF][START_REF] Ciucu | A network service curve approach for the stochastic analysis of networks[END_REF][START_REF] Fidler | A network calculus approach to probabilistic quality of service analysis of fading channels[END_REF][START_REF] Jiang | A basic stochastic network calculus[END_REF][START_REF] Jiang | Stochastic Network Calculus[END_REF]. They still use some envelope-based constraints, but with probabilistic assumptions, and still aim at evaluating worst case performances which now follow a random distributions. We will not deal with such probabilistic models in this report, although this field of investigation seems very attractive for future researches.

2 Comparison of current notions of service curves 2.1 Definitions and notation NC functions and operations. Network Calculus primal objective is the performance analysis of communication networks. Flows and services in the network are modelled by non-decreasing functions t → f (t) where t is time and f (t) an amount of data. There are different models depending on whether t (resp. f (t)) takes discrete or continuous values, e.g. in N or R + . Concerning data, one can even consider three models of granularity: infinitesimal (sometimes called fluid): data can be divided into arbitrarily small pieces (data measures are in R + ); unitary (sometimes called discrete): data is composed of indivisible packets of the same length (data measures are in N), multi-scaled: data may be divided into packets of variable lengths (possibly in N, R + or even infinitesimal).

In all cases, we will use the term bit as the data unit of measure. Note also that we do not exactly use the term fluid as in [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF] where the fluid model adds the condition that the manipulated functions are continuous.

In Network Calculus, one must distinguish two kinds of objects: the real movements of data and the constraints that these movements satisfy. The real movements of data are mainly modeled by cumulative functions: a cumulative function f (t) counts the total amount of data that has achieved some condition up to time t (e.g. the total amount of data which has gone through a given place in the network). In all the paper, we make the usual assumption that cumulative functions are left-continuous. This is not a huge restriction for the modeler: e.g. let f (t) be the total amount of data that has entered a system until time t, in case an instantaneous burst of b bits occur at time t 0 while a bits had already arrived, one only has to set f (t 0 ) = a and f (t 0 +) = a + b. This assumption has nevertheless a technical importance in the Network Calculus edifice (e.g. when defining the start of backlogged periods and using strict service curves as in Theorem 5). On the contrary, no assumption of (left-or right-)continuity is imposed to the constraint functions.

Network Calculus functions belong to F (resp. D) the set of functions (non necessarily nondecreasing

) from R + (resp. N) into R = R ∪ {-∞, +∞}, if time is continuous (resp. discrete). Cumulative functions usually belong to F ↑ = {f ∈ F | f non-decreasing, left-continuous, f (0) = 0} (resp. D ↑ = {f ∈ D | f non-decreasing , f (0) = 0})
Beyond usual operations like the minimum or the addition of functions, Network Calculus makes use of several classical operations [START_REF] Baccelli | Synchronization and linearity[END_REF] which are the translations of (+, ×) filtering operations into the (min, +) setting, as well as a few other transformations. Here is a sample of operations that can be encountered: let f, g ∈ F (resp. D), ∀t ∈ R + (resp. N),

(Inf-)convolution: (f * g)(t) = inf 0≤s≤t (f (s) + g(t -s)). Sup-convolution: (f * g)(t) = sup 0≤s≤t (f (s) + g(t -s)). (Sup-)deconvolution: (f ⊘ g)(t) = sup u≥0 (f (t + u) -g(u)). Inf-deconvolution:(f ⊘g)(t) = inf u≥0 (f (t + u) -g(u)). Positive rounding: f + (t) = max(f (t), 0).
Positive and non-decreasing upper closure: f ↑ (t) = max(sup 0≤s≤t f (s), 0). Such operations have interesting algebraic properties (see [START_REF] Baccelli | Synchronization and linearity[END_REF][START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF] for surveys). Using those operations, Network Calculus formulas combine the constraints on the traffic and the services in the network in order to output worst-case performance bounds.

For now on, we will do the presentation with continuous time and thus with functions in F . But one will easily check that all the results will remain true with discrete time and functions in D.

NC input/output systems. An NC model for a communication network usually consists in: a partition of the network into subsystems (often called nodes) which may have different scales (from elementary hardware like a processor to large sub-networks). a description of data flows, where each flow follows a path through a specified sequence of subsystems and where each flow is shaped by some arrival curve just before entering the network.

a description of the behavior of each subsystem, that is service curves bounding the performances of each subsystem, as well as service policies in case of multiplexing (several flows entering the same subsystem and thus sharing its service).

Systems or sub-systems are described as input/output systems (where the number of inputs is the same as the number of outputs). An (acceptable) trajectory for a system crossed by p flows is a set of cumulative functions (A k ) 1≤k≤p and (B k ) 1≤k≤p in F ↑ (where A k and B k respectively correspond to the cumulative functions of flow k at the input and the output of the system). For now, a system S over p flows will be simply defined as the set of all its acceptable trajectories, that is S ⊆ F p ↑ × F p ↑ . Such a black boxed view is usual in classical filtering theory and enables to deal with any scale of system. Note also that this definition allows to consider deterministic dynamics (one output for one input) and non-deterministic dynamics (several possible outputs for one input).

NC main performance measures: backlog & delay. Let (A, B) be an input/output trajectory for a flow in a system. Then the global backlog of the flow at time t is b(t) = A(t)-B(t) and the delay (under the FIFO policy assumption) endured after z input bits is d(z) = B (-1) (z)-A (-1) (z) where for all f ∈ F, f (-1)

(z) = inf{t ≥ 0 | f (t) ≥ z} (pseudo-inverse).
Let S be a system. The worst-case backlog over S is b max = sup (A,B)∈S sup t≥0 A(t) -B(t). The worst-case delay over S is

d max = sup (A,B)∈S sup z≥0 B (-1) (z) -A (-1) (z).
Given a trajectory (A, B) ∈ F ↑ × F ↑ , a backlogged period is an interval I ⊆ R + of time during which the backlog is non-null, i.e. ∀u ∈ I, A(u) -B(u) > 0. Let t ∈ R + , the start of the backlogged period of t is start(t) = sup{u ≤ t|A(u) = B(u)}. Since the cumulative functions A and B are assumed left-continuous, we also have

A(start(t)) = B(start(t)). If A(t) = B(t), then start(t) = t. For any t ∈ R + , ]start(t), t[ is a backlogged period (]start(t), t] if A(t) -B(t) > 0).
In the definition of backlogged period, the interval I can be closed, semi-closed or open. Such a flexible definition is convenient in some future definitions or proofs where the precise description of trajectories requires a particular type of intervals, e.g. semi-closed rather than open (see the consequences of such choices in the Complement about strict service curves below). Note that in the literature, backlogged periods have been sometimes defined for open intervals only [START_REF] Bouillard | Optimal routing for end-to-end guarantees using network calculus[END_REF] (page 885) or without worrying about this question [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF] (Definition 1.3.2, page 21).

NC arrival curves: one definition. Given a data flow traversing a network, let A ∈ F ↑ be its cumulative function at some point in the network, i.e. A(t) is the number of bits that have gone through this point until time t, with A(0

) = 0. A function α ∈ F is an arrival curve for A if ∀ s, t ∈ R + , 0 ≤ s ≤ t, we have A(t) -A(s) ≤ α(t -s).
The set of all arrival curves for A ∈ F ↑ admits a minimum which remains an arrival curve: it is α = A ⊘ A and we call it the canonical arrival curve for A.

NC service curves: several definitions. In the literature, the definitions of service curves usually concern: minimum service curves which are lower bounds on the service provided in a system (useful for upper bounds on worst case performances).

single flow systems S, that is S ⊆ F ↑ × F ↑ .
Note that in NC models with multiplexing, the aggregation (Σ) of all the flows entering the system is often considered as a single flow to which the minimum service is applied.

A B S

Figure 1: A single flow input/output system.

For each type T of service curve, we define for any β ∈ F and for any input/output trajectory (A, B) ∈ F ↑ × F ↑ the conditions so that β is a T -service curve for (A, B) (we also say that (A, B) admits β as a T -service curve). We then define for all β ∈ F, S T (β) the set of all trajectories admitting β as a T -service curve. We say that a system S admits β as a T -service curve if it is true for all its trajectories, i.e. S ⊆ S T (β).

Simple service curve:

S simple (β) = {(A, B) ∈ F ↑ × F ↑ | A ≥ B ≥ A * β}. Strict service curve (weak sense): S wstrict (β) = {(A, B) ∈ F ↑ × F ↑ | A ≥ B, and ∀t ≥ 0, B(t) -B(start(t)) ≥ β(t -start(t))}.
Strict service curve:

S strict (β) = {(A, B) ∈ F ↑ × F ↑ | A ≥ B, and ∀ backlogged period ]s, t], B(t) -B(s) ≥ β(t -s)}.
Variable capacity node:

S vcn (β) = {(A, B) ∈ F ↑ × F ↑ | ∃C ∈ F ↑ , ∀t ≥ 0, B(t) = inf 0≤s≤t A(s) + C(t) -C(s) and ∀0 ≤ s ≤ t, C(t) -C(s) ≥ β(t -s)}.
Two classical functions used as service curves are:

Pure delay T ∈ R + ∪ {+∞}: δ T (t) = 0 if t ≤ T , = +∞ otherwise. Constant rate r ∈ R + ∪ {+∞}: λ r (t) = rt (if r = +∞, we set λ r = δ 0 ).
Nothing prevents from using some service curves which are not in F ↑ , e.g. with negative values, decreasing parts or left-discontinuities. Nevertheless note that it is usually required that at least β(0) ≤ 0, otherwise β(0) > 0 require that B(0) > A(0) and

S simple (β) = S wstrict (β) = S strict (β) = S vcn (β) = ∅.
Complement about strict service curves. The definition of strict service curves presented here is the one used by Schmitt et al [START_REF] Schmitt | The disco network calculator: a toolbox for worst case analysis[END_REF][START_REF] Schmitt | Performance bounds in feed-forward networks under blind multiplexing[END_REF]. Some papers do not choose exactly the same definition for strict service curves [START_REF] Bouillard | Optimal routing for end-to-end guarantees: the price of multiplexing[END_REF][START_REF] Bouillard | Optimal routing for end-to-end guarantees using network calculus[END_REF]: they replace the backlogged interval ]s, t] in the definition by ]s, t[ (both definitions allow B(s) = A(s), but this variant also allows B(t) = A(t)). For β ∈ F, let us denote S ′ strict (β) the set of trajectories satisfying this variant of our definition. How do those slightly different definitions compare ? It is clear that ∀β ∈ F, S ′ strict (β) ⊆ S strict (β). If β is leftcontinuous, since all cumulative functions are assumed to be left-continuous, we have the equality S ′ strict (β) = S strict (β): let (A, B) ∈ S strict (β), if ]s, t[ is a backlogged period, then ∀s < t ′ < t, ]s, t ′ ] is a backlogged period, thus B(t ′ ) -B(s) ≥ β(t ′s) and B(t) -B(s) ≥ β(ts) by letting t ′ tend to t. If β is not left-continuous, then we may have a strict inclusion S ′ strict (β) S strict (β). Consider the example of Figure 2 where A(t) = 1/2 if t > 0 and = 0 if t = 0, B(t) = min(t/2, 1/2) and β(t) = ⌊t⌋. There is a unique maximal backlogged period which is ]0, 1[. One can check that

(A, B) ∈ S strict (β) (since ∀]s, t], 0 ≤ s ≤ t < 1, B(t)-B(s) ≥ β(t-s) = 0), but (A, B) ∈ S ′ strict (β) (since B(1) -B(0) = 1/2 ≥ β(1 -0) = 1)
. Note by the way that (A, B) ∈ S vcn (β) (e.g. one can choose C(t) = B(t) if t < 1 and = t if t ≥ 1). It is not surprising since Theorem 1 will show that S vcn (β) ⊆ S strict (β). Complement about Variable Capacity Nodes.

Lemma 1 (Consistence and alternate characterization).

Let A, C ∈ F ↑ and B ∈ F such that ∀t ≥ 0, B(t) = inf 0≤s≤t A(s) + C(t) -C(s) . Then B ∈ F ↑ and ∀t ≥ 0, B(t) = A(start(t)) + C(t) -C(start(t)).
Proof. Since A(0) = C(0) = 0, it is clear that B(0) = 0. Note that by hypothesis, ∀t ≥ 0, B(t) ≤ A(t) (choose s = t) and B(t) ≤ C(t) (choose s = 0). Since A and C are left-continuous, one can check that the formula for B ensures that it is also left-continuous.

Let t < t ′ , since A and C are non-decreasing, we have:

B(t ′ ) = inf inf 0≤s≤t A(s) + C(t ′ ) -C(s) =C(t ′ )-C(t)+B(t)≥B(t) , inf t≤s≤t ′ A(s) + C(t ′ ) -C(s) =A(t)+C(t ′ )-C(t ′ )≥B(t)
.

Thus B(t ′ ) ≥ B(t), that is B is non-decreasing.
For all t ≥ 0, start(t) is well defined due to left-continuity of A and B and A(0) = B(0) = 0. For all t ≥ 0, we have:

B(t) = inf inf 0≤s≤start(t) A(s) + C(t) -C(s) = B(start(t)) + C(t) -C(start(t)) = A(start(t)) + C(t) -C(start(t))
, inf

start(t)≤s≤t A(s) + C(t) -C(s) .
The first term A(start(t))+C(t)-C(start(t)) appears in the second term when taking s = start(t).

Thus we have for all t ≥ 0,

(V CN ) B(t) = inf start(t)≤s≤t A(s) + C(t) -C(s) . Now if B(t) = A(t), we have start(t) = t and thus A(start(t)) + C(t) -C(start(t)) = A(t) = B(t)
which concludes the proof. Otherwise B(t) < A(t) (and thus start(t) < t). In this case,

∀start(t) < s ≤ t, A(s) > B ′ (s) = inf start(s)≤u≤s A(u) + C(s) -C(u) , RR n 7094 inria-00431674, version 1 -12 Nov 2009 with start(s) = start(t) by definition. Thus ∀start(t) < s ≤ t, A(s) + C(t) -C(s) > inf start(t)≤u≤s A(u) + C(t) -C(u) ≥ inf start(t)≤u≤t A(u) + C(t) -C(u) = B(t)
Thus the infimum in Equation (V CN ) is necessarily reached at s = start(t), that is

B(t) = A(start(t)) + C(t) -C(start(t)).
Note that to prove this formula we have not used the non-decreasing property of A, B, C.

Comparison of NC service curves

All the definitions from the literature share the same natural monotonic behavior about trajectories.

Proposition 1 (Monotony). For any type T of service curve in the literature, for all

β, β ′ ∈ F (not necessarily in F ↑ ), if β ≤ β ′ then S T (β) ⊇ S T (β ′ ).
Moreover, for strict and weakly strict service curves, one can replace service curves by their closure.

Proposition 2. Let β ∈ F, then S wstrict (β) = S wstrict (β ↑ ), S strict (β) = S strict (β ↑ ) and S strict (β) = S strict (β * ).
A hierarchy can now be established between all those notions of service curves. The hierarchy given below is strict in most of the cases (the inclusions are strict). Nevertheless, this is not always true.

Theorem 1 (Hierarchy). For all β ∈ F, we have the following inclusions:

S vcn (β) ⊆ S strict (β) ⊆ S wstrict (β) ⊆ S simple (β).
Proof. We suppose that β(0) ≤ 0, otherwise all the sets are empty.

The inclusion S strict (β) ⊆ S wstrict (β) is clear, since for all t ∈ R + , either ]start(t), t] is a backlogged period and thus

B(t) -B(start(t)) ≥ β(t -start(t)), or ]start(t), t[ is a backlogged period and B(t) = A(t) but then start(t) = t and B(t) -B(start(t)) = 0 ≥ β(t -start(t)) = 0.
The inclusion S wstrict (β) ⊆ S simple (β) comes from the remark that if (A, B) ∈ S wstrict (β), then

B(t) ≥ B(start(t)) + β(t -start(t)) = A(start(t)) + β(t -start(t)) ≥ inf 0≤s≤t (A(s) + β(t -s)). Now let us show that S vcn (β) ⊆ S strict (β). Let (A, B) ∈ S vcn (β), there exists C ∈ F ↑ such that ∀t ≥ 0, B(t) = inf 0≤s≤t A(s) + C(t) -C(s) and ∀0 ≤ s ≤ t, C(t) -C(s) ≥ β(t -s). Consider a backlogged period ]s, t] for (A, B), then by definition start(s) = start(t) = p. From Lemma 1, we have B(t) = B(p)+ C(t)-C(p) and B(s) = B(p)+ C(s)-C(p). Thus B(t)-B(s) = C(t) -C(s) ≥ β(t -s)
and we have proved that β is a strict service curve for (A, B).

RTC vs NC

Real Time Calculus is presented as an alternative to Network Calculus. Admitting some kinship like the use of envelopes shaping the cumulative curves of traffic and services, it also claims new features allowing more precise models, tighter bounds and a way to compute them in any complex system.

In the literature, the comparisons with NC are very informal [START_REF] Wandeler | System architecture evaluation using modular performance analysis -a case study[END_REF]. We now try to provide a mathematical comparison between RTC models and NC models. The RTC presentation is extracted from the very good and comprehensive Wandeler's PhD Thesis [START_REF] Wandeler | Modular Performance Analysis and Interface-Based Design for Embedded Real-Time Systems[END_REF], in particular its Appendix A, page 197 (proofs and details are often omitted in other references). All the RTC notation and results below are extracted from this thesis.

To be precise, we will draw the comparison between RTC Greedy Processors (GP) and NC Variable Capacity Nodes.

RTC Greedy Processor

NC Variable Capacity Node R[s, t), s ≤ t, s, t ∈ R, non-negative, satisfying the Chasles relation:

∀u ≤ v ≤ w, R[u, w) = R[u, v) + R[v, w).
R(t), t ∈ R or more often t ∈ R+, non-decreasing and R(0) = 0.

Spaces of functions.

Here are the main differences which are listed in RTC references [START_REF] Wandeler | System architecture evaluation using modular performance analysis -a case study[END_REF]: RTC temporal variables range over all R (and not just R + as it is often the case in NC), RTC gets rid of the NC initialization point t = 0 where all NC functions are null, RTC functions have two arguments instead of one in NC (which is presented as one way to deal with all R).

Here is one important omission in the hypotheses about RTC functions: the Chasles relation is never explicitly exposed in the hypotheses, although it is intensively used in the proofs. Of course the interpretation of R[s, t) as the amount of data (or service) provided during the interval [s, t[ suggests the Chasles relation. Nevertheless a formal presentation should mention the relation. Now what about the claims that RTC functions have a better modeling power with tighter bounds [START_REF] Wandeler | Modular Performance Analysis and Interface-Based Design for Embedded Real-Time Systems[END_REF][START_REF] Wandeler | System architecture evaluation using modular performance analysis -a case study[END_REF]? They are rather unclear (due to the Chasles relation) as explained below.

Let R(.) a function defined on R (if it is defined on R + , an usual and natural extension is

R(t) = 0 if t < 0). Then we define R[s, t) = R(t) -R(s)
for all s, t. One can check that R satisfies the Chasles relation and if R is non-decreasing, then R is non-negative.

Let R[., .) a function defined on {(s, t) ∈ R 2 | s ≤ t}. Then we define Ř = R[0, t) for t ≥ 0 and = -R[t, 0) for t < 0. If R satisfies the Chasles relation, then it is easy to check that Ř(0) = 0 and Ř(t)-Ř(s) = R[s, t) for all s ≤ t (i.e. R = R). Thus if R is non-negative, then Ř is non-decreasing (note that all of this also works for Ř = R[p, t) with an arbitrary p ∈ R, except that Ř(0) is not necessarily 0).

We sum up these simple remarks in the next proposition.

Proposition 3. The mapping R → Ř is a bijection between non-negative functions over {(s, t) ∈ R 2 | s ≤ t} with the Chasles relation and non-decreasing functions over R with null value at t = 0. Its inverse is the mapping R → R.

Thus the only justification for the use of RTC functions with two arguments might be that it is easier to write the equations for the dynamics.

RTC equations

, C ′ Backlog: b (A7) R ′ [s, t) = C[s, t) -C ′ [s, t) (A8) C ′ [s, t) = sup s≤u≤t ˆC[s, u) -R(s, u) -B(s), 0 (A10) b(t) -b(s) = R[s, t) -R ′ [s, t) (B1) R ′ (t) = inf 0≤u≤t ˆC(t) -C(u) + R(u) (B2) C ′ (t) = C(t) -R ′ (t) (B3) b(t) = R(t) -R ′ (t)
When looking at Variable Capacity Node equations, one can easily see that for any input functions R and C, there exists output functions R ′ , C ′ satisfying the equations and they are unique ((B1) gives R ′ from R and C, then (B2) gives C ′ from R ′ and C). The backlog is also well defined in an unique way (with (B3)). When looking at RTC, given some input functions R and C, the existence of functions R ′ , C ′ , b satisfying the equations is not obvious (two unknown functions per equation).

RR n 7094 inria-00431674, version 1 -12 Nov 2009 [α ℓ , α u ] (a) (b) [α ′ ℓ , α ′ u ] [β ′ ℓ , β ′ u ] [β ℓ , β u ] C R ′ C ′ R
Lemma 2 (Coherence of RTC equations). Given R, C, let R ′ , C ′ , b be some solutions (if any) to the system of equations (A7), (A8), (A10). If R and C satisfy the Chasles relation and are non-negative, then so do R ′ and C ′ . In this case, if R and C are also non-negative, then so are

B, R ′ , C ′ .
Proof. Concerning the preservation of the Chasles relation, due to Equation (A7) and since C satisfies the Chasles relation, it is sufficient to prove that either R ′ or C ′ satisfies the relation so that both of them do.

Let s ≤ u ≤ t, we have:

C ′ [s, u) + C ′ [u, t) (A8) = C ′ [s, u) + sup u≤w≤t C[u, w) C[s,w)-C[s,u) -R[u, w) R[s,w)-R[s,u) -b(u), 0 (A10) = C ′ [s, u) + sup u≤w≤t C[s, w) -R[s, w) + R ′ [s, u) -C[s, u) -b(s), 0 (A7) = C ′ [s, u) + sup u≤w≤t C[s, w) -R[s, w) -C ′ [s, u) -b(s), 0 = sup u≤w≤t C[s, w) -R[s, w) -b(s), C ′ [s, u) = sup u≤w≤t C[s, w) -R[s, w) -b(s), sup s≤w≤u [C[s, w) -R[s, w) -b(s), 0] = sup s≤w≤t C[s, w) -R[s, w) -b(s), 0 = C ′ [s, t). Now, if C ′ satisfies the Chasles relation, then for all s ∈ R, C ′ [s, s) = 0. That is sup C[s, s) - R[s, s) -b(s), 0 = 0 and thus b(s) ≥ 0. Moreover, since C ′ is a supremum with 0, C ′ [s, t) ≥ 0 for all s ≤ t. Then checking whether R ′ [s, t) ≥ 0 comes to checking that C ′ [s, t) ≤ C[s, t). This is true because C ′ [s, t) = sup s≤u≤t C[s, u) ≤C[s,t) -R[s, u) ≥0 -b(s) ≥0 , 0 ≤C[s,t) . Lemma 3 (A recursive equation). Let A ∈ R R , then the functions F ∈ R R satisfying: ∀s ≤ t, F (t) = inf inf s≤u≤t A(u), F (s)
are exactly the functions of the form F (t) = inf inf -∞≤u≤t A(u), a) where a ∈ R is a constant.

Proof. We proceed by necessary conditions. Any function F ∈ R R satisfying the initial relation are such that:

∀s ≤ t, F (t) ≤ F (s), thus F is non-increasing over R. It admits a limit lim s→-∞ F (s) = a ∈ R. ∀s ≤ t, F (t) ≤ inf s≤u≤t A(u). Thus F (t) ≤ inf -∞≤u≤t A(u).
It also means that we can write

F (t) = inf inf -∞≤u≤t A(u), F (s)
This last expression for F is true for all s ≤ t. Take the limit s → -∞ and we obtain

F (t) = inf inf -∞≤u≤t A(u), a).
Conversely, it is easy to check that any function of this type satisfies the initial relation.

F (t) = F [p, t) if t ≥ p, and = -F [t, p) if t < p. Let ω = inf -∞≤u≤p Ř(u) -Č(u) .
The set of solutions R ′ , C ′ , b to the system of equations (A7), (A8), (A10) is given by R ′ [s, t) = Ř′ (t) -Ř′ (s), s ≤ t (and the same for C ′ ) and for all t ∈ R,

Ř′ (t) = Č(t) + inf inf -∞≤u≤t Ř(u) -Č(u) + σ , γ Č′ (t) = Č(t) -Ř′ (t) b(t) = Ř(t) -Ř′ (t) + σ,
where σ, γ ∈ R are constants such that (σ = -ω and γ ≥ 0), or (σ ≥ -ω and γ = 0). We always have b(p) = σ, and in case b(p) = 0, then for all t ≥ p,

Ř′ (t) = inf p≤u≤t Ř(u) + Č(t) -Č(u) .
which is a Variable Capacity Node description with initial point at t = p (both functions Ř and Č are non-decreasing, equal to 0 at t = p, and non-negative over [p, +∞[).

Proof. We proceed by necessary conditions to find some closed form expressions of the solutions of the system (A7), (A8), (A10).

Under our hypotheses about R and C, due to Lemma 2, R ′ and C ′ must satisfy the Chasles relation. Fix p ∈ R some arbitrary real number. Following Proposition 3 and using the notation

F (t) = F [p, t) if t ≥ p and = -F [p, t) if t < p, for any function F [., .) defined over {(s, t) ∈ R 2 | s ≤ t},
we know that R ′ (resp. C ′ ) will be fully defined by the values of Ř′ (resp. Č′ ). We can rewrite and mix Equations (A7), (A8), (A10) where the unknowns are now Ř′ , Č′ ∈ F ↑ and b ∈ F. Here is a set of equations they must satisfy.

First Ř′ (p) = 0 and Č′ (p) = 0. When the Chasles relation is satisfied everywhere, (A7) is clearly equivalent to (A7 ′ ): ∀t ∈ R, Ř′ (t) = Č(t) -Č′ (t). Since we know that Č(p) = 0, Ř′ (p) = 0 implies Č′ (p) = 0 and reciprocally.

Mixing (A7) and (A8) gives: for all s ≤ t,

R ′ [s, t) = C[s, t) -sup s≤u≤t C[s, u) -R[s, u) -b(s), 0 .
With our one-argument functions, it gives: for all s ≤ t,

Ř′ (t) = inf s≤u≤t Č(t) -Č(u) + Ř(u) -Ř(s) + b(s) + Ř′ (s), Č(t) -Č(s) + Ř′ (s) .
RR n 7094

inria-00431674, version 1 -12 Nov 2009

Equation (A10) implies in particular that for all s ≥ p, b(s

) -b(p) = R[p, s) -R ′ [p, s), that is (A10 ′ ): b(s) -b(p) = Ř(s) -Ř′ (s). When s < p, b(p) -b(s) = R[s, p) -R ′ [s, p) = -Ř(s) + Ř′ (s).
Thus (A10 ′ ) is satisfied for any s ∈ R.

The expression Ř′ (t) is thus equal to:

Ř′ (t) = inf s≤u≤t Č(t) -Č(u) + Ř(u) + b(p), Č(t) -Č(s) + Ř′ (s) .
It can be reformulated into (A8 ′ ): for all s ≤ t,

Ř′ (t) -Č(t) = inf inf s≤u≤t Ř(u) -Č(u) + b(p) , Ř′ (s) -Č(s) .
Applying Lemma 3, the function Ř′ is of the form: for all t ∈ R,

Ř′ (t) -Č(t) = inf inf -∞≤u≤t Ř(u) -Č(u) + b(p) , γ ,
where γ ∈ R is a constant.

The new system of Equations (A7 ′ ), (A8 ′ ), (A10 ′ ) and Ř′ (p) = 0 has clearly some solutions Ř′ , Č′ , b: one has to adjust b(p) and γ so that Ř′ (p) = 0, i.e. inf inf -∞≤u≤p Ř(u)-Č(u)+b(p) , γ = 0. Let us denote ω = inf -∞≤u≤p Ř(u) -Č(u) . We know that ω ≤ 0 (take u = p). Thus the set of solutions for b(p) and γ is given by b(p) = -ω and γ ≥ 0, or b(p) ≥ -ω and γ = 0. Now a careful look of the reasoning above shows that it can be inverted: if Ř′ , Č′ , b satisfy (A7 ′ ), (A8 ′ ), (A10 ′ ) and Ř′ (p) = 0, then the associated R, C, b satisfy (A7), (A8), (A10). This gives the first part of the theorem.

When t ≥ p, we have:

Ř′ (t) -Č(t) = inf inf p≤u≤t Ř(u) -Č(u) + b(p) , inf -∞≤u≤p Ř(u) -Č(u) + b(p) , γ .
We know that the last two terms are equal to Ř′ (p) = 0. Thus

Ř′ (t) -Č(t) = inf inf p≤u≤t Ř(u) -Č(u) + B(p) , 0 .
In the special case where we also assume that b(p) = 0, if t ≥ p, we have:

Ř′ (t) -Č(t) = inf inf p≤u≤t Ř(u) -Č(u) , 0 .
When u = p, the main term Ř(p) -Č(p) is equal to 0 by definition, so it covers the value 0 and we have:

Ř′ (t) -Č(t) = inf p≤u≤t Ř(u) -Č(u) .
Thus, for all t ≥ p,

Ř′ (t) = inf p≤u≤t Ř(u) + Č(t) -Č(u) .
Both functions Ř and Č are non-decreasing, equal to 0 at t = p, and non-negative over [p, +∞[. This is exactly the dynamics of a Variable Capacity Node (with a initial point at t = p).

The RTC models combine upper and lower bounds on the traffic and on the services. Consider an RTC Greedy Processor as illustrated by Figure 3. Each traffic (or rather event stream in RTC) cumulative curve R can be constrained by a pair of RTC arrival curves (α l , α u ) ∈ F ↑ × F ↑ : for all s ≤ t, let R[s, t) the number of events that have arrived in the interval [s, t[, then

α l (t -s) ≤ R[s, t) ≤ α u (t -s).
In the same way, each resource cumulative curve C can be constrained by a pair of RTC service curves (β l , β u ) ∈ F ↑ × F ↑ : for all s ≤ t, let R[s, t) the number of processing cycles available in the interval [s, t[, then

β l (t -s) ≤ C[s, t) ≤ β u (t -s).
If inputs are shaped by such curves, one can propagate the same kind of constraints to the outputs. Such output constraints are given by the following formulas proved in [START_REF] Wandeler | Modular Performance Analysis and Interface-Based Design for Embedded Real-Time Systems[END_REF]: with the notation of Figure 3,

α ′u = min (α u * β u ) ⊘ β l , β u ; α ′l = min (α l ⊘ β u ) * β l , β l ;
β ′u = (β uα l )⊘0;

β ′l = (β l -α u ) * 0 = (β l -α u ) ↑ .
The proofs in [START_REF] Wandeler | Modular Performance Analysis and Interface-Based Design for Embedded Real-Time Systems[END_REF]

Composition of service curves: convolution

We have now compare different notions of service curves under various versions of the Network Calculus framework. In the two next section, we study more precisely simple and strict service curves, which are widely used in the NC community. We focus on the stability of the type of curves with two operators: composition and remaining service curves. In this section, we focus on the composition of service curves (servers in tandem).

Stability/instability results

Theorem 3. Consider two servers in tandem, of respective service curves β 1 for A and β 2 for B. Then 1. β 1 * β 2 is a service curve for A.

2. If β 1 and β 2 are strict, β 1 * β 2 is not necessarily strict.

Proof. The first part of the theorem is a classical property of the concatenation of servers, which can be found in [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF][START_REF] Chang | Performance Guarantees in Communication Networks[END_REF].

We then only show an example to illustrate the fact that β 1 * β 2 is not necessarily a strict service curve for their concatenation. Here is a counterexample with burst-delay strict service curves. As a direct application of definitions, a node admits δ T as a strict service curve if and only if the duration of any backlogged period is at most T . Consider the system on Figure 4 composed of two nodes in tandem. Suppose that Node 1 (resp. Node 2) works as the following server: as soon as a positive amount of data arrives, it waits a time T 1 = 2 (resp. T 2 = 3) while its queue fills up, and then it serves instantaneously all the data in its queuing. Node 1 (resp. Node 2) clearly has δ T1 (resp. δ T2 ) as a strict service curve. Figure 4 shows what happens to a flow crossing Node 1 and 2 with the cumulative arrival function A(t). The duration of the backlogged period is 9, and thus δ T1 * δ T2 = δ T1+T2 is not a strict service curve since T 1 + T 2 = 5.

δ T 1 δ T 2 C(t) A(t) A(t)

An intermediate notion of service curve?

One of our main motivation was to try to define an intermediate notion of service curve that would in particular be preserved with the concatenation. We now show that this is not possible: the next theorem shows that considering only the concatenation, the notion of intermediate service curve must coincide with that of service curve. As we will see later, no residual service curve notion can be defined from the notion of service curve. As a consequence, no notion of intermediate service curve can be preserved both through concatenation and "residuation". Let us recall the properties that our intermediate service should satisfy to be preserved with concatenation (we denote by S inter (β) the relation between trajectories that must be satisfied for an intermediate service curve β): Proof. The idea is two decompose one server with a (strict) service curve β into a sequence of servers with of service curves β i such that β = ¶β i , and to compare the departure processes when servers are used as strict service curves or as service curves. We will see that when the number of servers grows to infinity, the behaviors tend to be the same. Note that as the convolution is associative, the departure process corresponding to an arrival process A though a server offering a service curve β is the same as the departure process through servers in tandem offering β i as service curves. As a consequence, we will mainly focus of the departure processes where the services are strict.

1. S strict (β) ⊆ S inter (β) ⊆ S simple (β); 2. S inter (β 2 ) • S inter (β 1 ) = S inter (β 1 * β 2 ): if β 1 and

Pure delay curve

Before proving the result for any convex service curve, let first prove it for a curve δ d , where δ d : t → 0 if t ≤ d; +∞ otherwise. This case gives the intuition that lays behind the proof.

Let A be a cumulative arrival process. Let n be the number of servers in tandem and d/n be the pure delay of each server (each server offers a service curve δ d/n ). Let us compute the delay of each packet in the process. Let B n be the departure process of A after crossing the n servers in tandem when the services are strict and exact and let t 0 be the arrival time of the packet we want to compute the delay.

The delay in the first server in upper bounded by d/n, and is served at time t 1 ≤ t 0 + d/n. The process after the first server is bursty (it is a stair function), and time between to bursts is at least d/n. Then, at the second server, as every packet of the backlogged period has been served at the same time, the packet arrives at the beginning of a busy period and will be served at time t 2 = t 1 + d/n. It is obvious that the same will hold for the n -2 next servers. Then, the overall delay δ for this packet is bounded by:

n -1 n d ≤ δ ≤ d.
When n grows to infinity, the delay of the packet tends to d. As this holds for every packet,

B n (t) → A(t -d).
(a) (b) and departure process for non strict service curve (green). From light to dark, the departure process after each server with strict service curve δ d/4 .

Elementary segment service curve

We now prove the theorem for a curve of the following form: β λ,d : t → λt if t ≤ d; +∞ otherwise. This is the result that will be use to prove the theorem for any convex curve. First, remark that, as in the previous case, β λ,d = β n λ,d/n . Let A be a cumulative arrival process. The same cumulative departure processes can be obtain if we consider that the flow crosses one server with minimal service curve β λ,d or n servers with minimal service curve β λ,d/n in tandem. The output process obtained when the service is not strict, if the servers are exact, is A * β λ,d . Graphically, this is the minimal closure of the points of the segments of slope λ and of length d when the starting points of the segments follow A, as depicted in Figure 6.

inria-00431674, version 1 -12 Nov 2009

The behavior is different when the service curves are strict. Let us see what happen (we will suppose that the services are exact to construct the processes). The backlogged period of a process through a server of strict service curve β λ,d/n is at most d/n. If it is exactly d/n, then the slope of the departure process in that backlogged period is exactly λ. Otherwise, this means that the arrival process has intersects the segment of slope λ that starts at the beginning of the backlogged period, which means that the backlogged period ends at the intersection, and a new one may begin. The remaining of the segment of length d would not be of interest for the computation of the convolution, as it is covered by the segment that begins at the intersection. After crossing one such server, the slopes of B ′ , the departure process after crossing the first server at most λ, and there may be discontinuities (bursts). When the delay is strictly less that λ, this means that the delay is 0. When there are discontinuities, the backlogged period ending with it is of length d/n. The different cases that can occur are depicted in Figure 7.

A t 1 2 3 B ′
Figure 7: Different cases for elementary segment strict service curves. 1: the backlogged period is exactly d/n, the slope of the departure process during this period is λ and there is a burst at the end of the backlogged period. 2: the backlogged period is strictly less than d/n, as the segment of slope λ and of length d/n intersects A. After the intersection, the segment is above the curves or segments that begin the next backlogged period. 3: the slope of the arrival process is less than λ at the end of a backlogged period, then, the departure process is not delayed.

For what has been said before, one can deduce that the departure process B (1) can be written as

B (1) (t) = min s∈D∩[0,t] A(s) + β λ,d/n (t -s),
where D ⊂ R + such that 0 ∈ D and ∀s ∈ D, ∃u ∈ D such that us ≤ d/n. Consider B (i) the departures processes after crossing the i-th server (B (i-1) is the the arrival process in the i-th server). The same observations can be made than between A and B (1) : the slopes of B (i) are at most λ, there can be bursts. Backlogged period (of positive length) necessarily start when there is a burst. For each burst in B (i) , i > 1, say at time t, there was a burst at time td/n for B (i-1) , and by induction, at time t -(i -1)d/n for B (1) , and the beginning of the backlogged period in the first server is at time t-id/n. Bursts correspond to the end of backlogged period of length d/n. Now, if there is a backlogged period of length less that d/n in the i-th server that starts at time t, this means that s → B (i-1) (t) + β λ,d/n (s) and s → B (i-1) (t + s) intersect each other (which corresponds to case 2 of Figure 7). The slope of B (i-1) at that intersection (t ′ ) is strictly less than λ, so B (i-1) (t ′ ) = A(t ′ ). The beginning of the corresponding backlogged period in the first server is t -(i -1)d/n. Between t -(i -1)d/n and t ′ , B (i) is affine of slope λ. Applying this to i = n, one gets, with

B n = B (n) , B n (t) = min s∈D∩[0,t] A(s) + β λ,d (t -s).
Elements in D correspond to the beginning of backlogged period in the first server, taking into account the periods of length 0. The horizontal distance between B and B n is then bounded by d/n and then, when n → ∞, B n → B.

Convex service curve

Let β be a convex service curve piece-wise affine, composed of k finite segments of respective slope λ i and length λ i and of one semi-infinite segment of slope λ. we know that β = ¶ k i=1 β λi,di * β λ,∞ . One can decompose that service curve into kn + 1 curves: β λ,∞ , and n curves of each β λi,di/n .

The behavior of a server with service curve β λ,∞ is the same if the service is strict of not when the service is exact. So put this server first. The order of the servers is depicted on Figure 8. Let A be an arrival process in the concatenation of servers. We denote by B 0 (resp. B ′ 0 ) the departure process after the first server when the service is simple (resp. strict), B i (resp. B ′ i ) the departure process after n the servers β λi,di/n when the service is simple (resp. strict). One has B 0 = B ′ 0 . We now prove by induction on

β λ1,d1/n β λ1,d1/n β λ k ,d k /n β λ k ,d k /n A B 0 B 1 B k B k-1 β λ,∞
k that B ′ k ≥ B k ≥ B ′ k (. - k i=1 d i /n).
The case k = 1 corresponds to the case of an elementary segment of the previous paragraph. Suppose that the result is true for k elementary segments. We prove it for k + 1 segments using the monotony of the convolution: if f 1 ≥ f 2 , then f 1 * g ≥ f 2 * g and the previous paragraph to the shifted process

B ′ k+1 (. - k i=1 d i /n
) When the services are strict, the departure process is B ′ k+1 when the arrival process in the servers

β λ k+1 ,d k+1 /m is B ′ k and is B ′ k+1 (. - k i=1 d i /n) when the arrival process in the servers β λ k+1 ,d k+1 /m (. - k i=1 d i /n).
When the services are not strict, the departure process is

B k * β λ k+1 ,d k+1 ≥ B ′ k (. - k i=1 d i /n) * β λ k+1 ,d k+1 ≥ B ′ k+1 (. - k+1 i=1 d i /n).
When n grows to infinity, this horizontal distance between B k and B ′ k tends to 0. This finishes the proof.

Residual service curves

This section is dedicated to the second aspect of NC we want to study: the remaining service curves: what service can be guaranteed for a flow if it suffers from another flow in the same server? As we have to deal with several flows, the use of arrival curves will be necessary here. Moreover, we will study here two type of service policy: blind multiplexing (any service policy can be used by the server) and the fix priority (FP) policy (some flows have higher priority than others). Remaining service curves under bling multiplexing has been extensively studied in the last years ([]), whereas fix priority policy is rather used with the RTC model ([]). We show that we can translate the results from RTC (hence from VCN service curves) with strict service curves.

We will use the following notation for priorities: if a flow F 2 has higher priority tha F 2 , we write F 1 ≻ F 2 .

Stability results for a fluid model

Theorem 5. Consider a server offering a strict service curve β to A 1 + A 2 and suppose that flow A 1 is α 1 upper-constrained.

1. The server service a service curve (βα 1 ) ↑ for A 2 .

RR n 7094 inria-00431674, version 1 -12 Nov 2009

2. If A 1 ≻ A 2 , then (β -α 1 ) ↑ is a strict service curve.
As far a strict service curves are concerned, a similar result is already known for the RTC model with fix priorities. Nevertheless, we will give a direct proof in the Network Calculus framework. In this latter framework, the existing result is that (βα 1 ) + is a service curve. Having the positive, non-decreasing upper closure can be useful when dealing with sub-additive, non-concave arrival curves.

Proof. In addition to the two items of the theorem, we will give an example to illustrate that it there is no fix priority among the two flows, the remaining service curve may not be strict.

We first show that if A 1 has a higher priority than A 2 , then the server offers a strict service curve (βα 1 ) ↑ to A 2 .

Let u and v, u < v be times in the same backlogged period for A 2 in the server. As a consequence, u and v are in the same backlogged period of the aggregate flow, and we have:

B 1 (v) + B 2 (v) ≥ B 1 (u) + B 2 (u) + β(v -u).
Let p be the start of the backlogged period of u for F 1 . As the period between p and u is a backlogged period for F 1 , and u is in a backlogged period for F 2 , no data can be served for F 2 between p and v and we have:

B 1 (u) -B 1 (p) ≥ β(u -p) B 2 (u) -B 2 (p) = 0 A 1 (p) -B 1 (p) = 0.
Between times p and v, we also have:

B 2 (v) -B 2 (p) + B 1 (v) -A 1 (p) ≥ β(v -p). As B 1 (v) -A 1 (p) ≤ A 1 (v) -A 1 (p) ≤ α 1 (v -p), we obtain: B 2 (v) -B 2 (p) ≥ β(v -p) -α 1 (v -p).
One can apply the formula above for every w ∈ [p, v], w remains in the same backlogged period as v:

∀w ∈ [p, v] B 2 (w) -B 2 (p) ≥ β(w -p) -α 1 (w -p).
As B 2 is non-decreasing, we also have

∀w ∈ [p, v] B 2 (v) -B 2 (p) ≥ B 2 (w) -B 2 (p) ≥ β(w -p) -α 1 (w -p)
and

B 2 (v) -B 2 (p) ≥ sup w∈[p,v] β(w -p) -α 1 (w -p) (1)
≥ sup s∈[0,v-p] β(s) -α 1 (s) (2)
≥ sup

s∈[0,v-u] β(s) -α 1 (s). (3)
As B 2 (u) = B 2 (p), we have

B 2 (v) -B 2 (u) ≥ sup s∈[0,v-u] β(s) -α 1 (s).
Moreover, as B 2 is non-decreasing,

B 2 (v) -B 2 (u) ≥ sup s∈[0,v-u] (β(s) -α 1 (s)) + .

INRIA inria-00431674, version 1 -12 Nov 2009

To show that under blind multiplexing, (βα 1 ) ↑ is a service curve is quite straightforward from what has been written above: Equations ( 1) and ( 2) still hold, and A 2 (p) = B 2 (p), so

B 2 (v) ≥ A 2 (p) + sup s∈[0,v-p] β(s) -α 1 (s) ≥ A 2 * (β -α 1 ) ↑ .
We now give an example where the remaining service curve is not strict. Suppose for instance that we are in the infinitesimal data model and consider a node which serves data at a constant rate 2. Such a node has β(t) = 2t as a strict service curve. Let two flows cross this node with respective cumulative arrival functions A 1 (t) = t + 1 and A 2 (t) = t. An arrival curve of Flow 2 is α 2 (t) = t. Figure 9 shows the trajectory of the system for the following policy: at first, for 0 ≤ t ≤ 1, Flow 1 is given top priority, then for t > 1, Flow 2 is given top priority. Since the sum A 1 (t) + A 2 (t) = 2t + 1, the node is always backlogged and the sum of the cumulative departure functions is B 1 (t) + B 2 (t) = 2t. It can be checked that β 1 (t) = (βα 2 ) + (t) = t is a service curve for Flow 1 (B 1 ≥ A 1 * β) but it is not a strict service curve: during the period 1 ≤ t ≤ 2, Flow 1 has some data backlogged in the node but this data is not served at all.

What about the packet size?

Theorem 6. Consider a server with a strict service curve β for A 1 + A 2 . Suppose that flow A 1 is α 1 upper-constrained, that A 1 ≻ A 2 and that ℓ 2,max is the maximum size of a packet in F 2 .

1. The server guaranties a service curve (βα 1 ) ↑ for A 2 .

2. The server guaranties a strict service curve (βα 1ℓ 2,max ) ↑ for A 2 .

3. The server guaranties a strict service curve (βℓ 2,max ) ↑ for A 1 .

Proof. The first part of the theorem is a direct consequence of Theorem 5.1. The second and third parts can be proved the same way as Theorem 5 or one can make the following observations to apply that Theorem 5.2: as the server is non-preemptive, when a packet of F 2 is served, a packet of flow F 1 can arrive in the system, starting a backlogged period for this server. But the packet of F 2 being served by the system can be seen as a priority flow. This flow is upper-constrained by t → ℓ 2,max , hence (βℓ 2,max ) ↑ is a strict service curve for A 1 .

The same way, in the proof of Theorem 5, A 1 can be replaced by A 1 + ℓ 2,max , a flow upperconstrained by t → ℓ 2,max + α 1 (t), hence (β 1α 1ℓ 2,max ) ↑ in a strict service curve for A 2 .

We can also adapt the example in proof of Theorem 5 to show that (βα 1 ) ↑ may not be strict. We still take β(t) = 2t, A 2 (t) = α 2 (t) = 1 + t. We set ℓ 2,max = 1, α 1 (t) = 1/2 + t and A 1 (t+ 1/2) = α 1 (t) or 0 if t < 1/2. At time 0, a packet of size ℓ 2,max arrives, so it is served as there RR n 7094 inria-00431674, version 1 -12 Nov 2009 is no packet of flow 1 in the server at time 0. At time 1, the packet of size ℓ 2,max is served, so that packets of F 1 can be served. After that, the behavior is the same as in the proof of Theorem 5: between time 1 and 2, no packet of flow 2 is served, whereas (βα 1 ) ↑ (t) = 2(t -1/4) + , and the interval during which no packet of F 2 is served in a backlogged period for tat flow cannot exceed 1/4. As a direct application, this theorem can be used to compute a minimal (strict) service curve for each flow of a server, with fix priorities on the flows.

Corollary 2. Consider a single server with a minimal strict service curve β and m flows crossing it, F 1 , . . . , F m . The maximum packet size of flow F i is ℓ 1,max and is upper-constrained by the arrival curve α i . Flows are ordered in their order of priority :

F i ≺ F j ⇔ i < j. For each i ∈ {2, . . . , m}, 1. (β -j<i α j -∨ k>i ℓ k,max ) + is a service curve for flow F i . 2. (β -j<i α j -∨ k≥i ℓ k,max ) + is a strict service curve for flow F i .

Composition of residual services: nested flows with fix priorities

In this section, we study more precisely scenarii where the strict service curve composition would have been useful. We show that even if the strict property is lost, computations are still possible and valid. There is one kind of scenarii where direct composition is efficient: when we have servers in tandem with nested flows.

We will use the following notation:

F i represent flows;
If there are n servers in tandem, F

i , represent the arrival process of flow i in the j + 1-th server and the departure process of the j-th server;

F (0) i is α i -upper constrained;
β j is the strict service curve of the j-th server.

Consider n servers in tandem aditting respective strict service curves β j . The service curve of one flow is

β 1 * • • • * β n .
Lemma 4 (One nested flow). Consider a flow F 2 crossing the servers β b , . . . , β e that is α 2 -upper constrained. A service curve for flow

F 1 is β 1 * • • • β b-1 * (β b * • • • * β e -α 2 ) + * β e+1 * • • • * β n .
Proof. First consider the service curve between servers b and server e, and then the other are obtained by concatenation, which is valid for any service curve.

∀t i ∈ R + , there exists t i-1 , first instant of backlogged period such that

F (i) 1 (t i ) + F (i) 2 (t i ) ≥ F (i-1) 1 (t i-1 ) + F (i-1) 2
(t i-1 ) + β i (t i -t i-1 ).
Then, ∀t e ∈ R + , there exists t b-1 , . . . , t e-1 such that

F (i) 1 (t e ) + F (i) 2 (t e ) ≥ F (b-1) 1 (t b-1 ) + F (b-1) 2 (t b-1 ) + e i=b β i (t i -t i-1 ), and
F (e) 1 (t e ) ≥ F (b-1) 1 (t b-1 ) + e i=b β i (t i -t i-1 ) -α 2 (t e -t b-1 ).
Moreover, F (t b-1 ), so

F (e) 1 (t e ) ≥ F (b-1) 1 (t b-1 ) + ( ¶ e i=b β i (t e -t b-1 ) -α 2 (t e -t b-1 )) + .
Suppose now that there exist m transversal flows F 1 , . . . , F m . Flow F i interfere with a flow F 0 on line on the n servers previously defined on the interval I i = {b i , . . . , e i } and we suppose that the flows are nested: ∀i, j, either I i ∩ I j = ∅ or I i ⊆ I j or I j ⊆ I i . Furthermore, suppose that the priorities of the flows is fixed, forms a total order, and respects the following rule: (R) ∀i, j ∈ {1, . . . , m}, F i ≻ F j ⇒ I i ⊆ I j .

For i ∈ {0, . . . , m}, we denote by P i the set of flows that has higher priority than F i and interfere with it (P i = {j ∈ {0, . . . , m} | F j ≻ F i and I j ⊆ I i } and by P im i the set of flows of minimal priority among those that have higher priority than F i :

P im i = {j ∈ P i | ∀k ∈ P i \ {j} F k ≻ F j }.
Finally we denote by N i the set of servers crossed by F i that are not crossed flows of higher priority:

N i = {j ∈ I i | ∀k ∈ {1, . . . , m}, F k ≻ F i ⇒ j / ∈ I k }.
We are going to prove by induction that the service can be removed by one by one in decreasing order of priorities to obtain a global remaining service curve, although the strictness property of the service curves in not preserved. More formally, we have the following theorem: Theorem 7. If flows respect rule (R) and using the notations defined above, for every i ∈ {0, . . . , m}, β ′ i is a service curve for flow F i .

β ′ i = ¶ j∈Ni β j * ¶ k∈P im i (β ′ k -α k ) + .
Proof. We show this result by induction. Our induction hypothesis (H m ) for m interfering flows is: consider m flows F 1 , . . . , F m interfering with a line of n servers with fixed priorities respecting rule (R). For any aggregate flow F m+1 with lower priority than F 1 , . . . , F m , 1. For each server j / ∈ i∈{1,...,m} I i , ∀t ∈ R + , ∃u j such that

F (j) m+1 (t) ≥ F (j-1)
m+1 (u j ) + β j (tu j ).

2. For each k ∈ P im m+1 , ∀t ∈ R + , ∃u k such that

F (e k ) m+1 (t) ≥ F (b k -1) m+1 (u k ) + (β ′ k -α k ) + (t -u k ).
(H 0 ) holds: as there is no interfering flows, only the first case has to be considered, for any server. By definition of strict service curves, the first case holds for any server.

Suppose that (H m ) holds. We now show that (H m+1 ) also holds. Consider a line of n servers with m + 1 flows with fixed priorities. Without loss of generality, one can suppose that F m+1 has the lowest priority. So, (H m ) holds for F 1 , . . . , F m . Also consider F m+2 a flow with lower priority than F m+1 . Three cases can occur:

1. Server j does not interfere with F 1 , . . . , F m+1 . Then as server j offers a strict service curve β j , ∀t ∈ R + , ∃u j such that

F (j) m+2 (t) ≥ F (j-1)
m+2 (u j ) + β j (tu j ).

2. For each k ∈ P im m+2 such that I k ∩ I m+1 = ∅, as F k has higher priority that F m+1 , those two flow do not interfere with each other. Then, using the induction hypothesis, we have ∀t ∈ R + , ∃u k such that

F (e k ) m+2 (t) ≥ F (b k -1) m+2 (u k ) + (β ′ k -α k ) + (t -u k ).
3. Flows F m+2 and F m+1 interfere on I m+1 . Every other flow that interfere with F m+1 has higher priority and respects rule (R). Let β1 , . . . , βℓ the ordered sequence of service curves crossed by F m+2 and F m+1 (i.e. only those crossed by F m+1 ), βq being β j for some j or (β ′ kα k ) + for some k satisfying (H m ). For every u ℓ , there exists u 0 , . . . , u ℓ-1 such that for each p ∈ {1, . . . , ℓ}, with r p = j and q p = j -1 if βp = β j or r p = e k and q p = b k -1 if βp = (β ′ k -α k ) + . Moreover, as the servers are in sequence, we have r p = q p+1 for p ∈ {1, . . . , ℓ -1} and q 1 = b m+1 -1 and r ℓ = e m+1 .

Let add those ℓ inequations, we get:

Conclusion

This report has two aims: comparing several models having their root in Network calculus and comparing different notions of service curves in the original Network calculus model. First, we show that the main alternative to Network calculus (NC), real-time calculus (RTC), is in fact very similar to NC. The service curve in RTC corresponds to the strict service curve in NC.

Second, we compare strict and simple service curves, and explicit what can be done or cannot be done with which type of service curve, concerning the composition of service curves and the computation of residual service curves. Moreover, we explain why we cannot define a new notion of service curve which enables and is stable with those two operations.

Although looking a bit formal, this work is relevant, as it showed some important details we -and, to our knowledge, the NC community -were not conscious of. For example, as far as residual service curves are concerned, there is a difference between blind multiplexing and fixed priorities, event if the worst departure process for blind multiplexing is obtained with fixed priorities. Studying RTC helped us with such remarks.

This study is somewhat incomplete when dealing with the hierarchy between the types of service curves. Of course, the hierarchy has been recalled, but no precise new result has been given. For example, it has not been studied precisely the family of functions for which two kinds of service curves coincide, nor had been investigated if a (family of) service curve of one type can be modeled by a (family of) service curves of another type. This would be interesting for modeling purposes to know for example what kind of systems can be modeled using simple service curve, strict service curves or both. This will be the object of further work concerning service curves in Network Calculus.

Another point that has not been discussed here is the tightness issue, that is, whether, for a given server, there exists a trajectory whose maximum delay reaches the delay computed with NC methods. For example for the computations in the last section, it is now well-known that bounds are not tight is the general case, but it would be interesting to quantify that non-tightness and to characterize the cases of tightness. This formula should also be compared to the computations in RTC.

Acknowledgements

This work has been partially supported by the ONERA under the contract number CNRS 038361.

Figure 2 :

 2 Figure 2: Beware of the definition of strict service curves.

Figure 3 :

 3 Figure 3: A single flow input/output system. (a) cumulative functions; (b) arrival/service lower and upper arrival curves.

Figure 4 :

 4 Figure 4: Tandem: strict service curve * strict service curve = strict service curve.

Figure 5 :

 5 Figure 5: Example of output service curve after 4 servers in tandem. (a) the arrival process (blue) and departure processes for strict (red) and non strict (green) service curves. (b) Arrival (blue) and departure process for non strict service curve (green). From light to dark, the departure process after each server with strict service curve δ d/4 .

Figure 6 :

 6 Figure 6: Convolution with an elementary segment: in bold and plain, β λ,d , in bold and dotted, some segments following A, B = A * β λ,d .

Figure 8 :

 8 Figure 8: Decomposition of a server with convex service curve into a concatenation of elementary servers.

Figure 9 :

 9 Figure 9: Residual service curves are not necessarily strict.

(e) 1 (

 1 t e ) ≥ F (b-1) 1

F

  p ) + F rp m+1 (u p ) ≥ F qp m+2 (u p-1 ) + F qp m+1 (u p-1 ) + βp (u pu p-1 ),

F

  pu p-1 ).AsF (em+1) m+1 (u ℓ ) -F (bm+1-1) m+1 (u 0 ) ≤ F (bm+1-1) m+1 (u ℓ ) -F (bm+1-1) m+1 (u 0 ) ≤ α m+1 (u pu 0 ) and F (em+1) m+2 (u ℓ ) ≥ F (bm+1-1) m+2 (u 0 ), we have F (em+1) m+2 (u ℓ ) ≥ F (bm+1-1) m+2 (u 0 ) + ( ℓ p=1 βp (u pu p-1 )α m+1 (u pu 0 )) + and F (em+1) m+2 (u ℓ ) ≥ F (bm+1-1) m+2 * ( ¶ ℓ p=1 βpα m+1 ) + (H m+1) is then satisfied. The rest of the proof is straightforward.

  (Appendix A, pages 201-204) use additional assumptions on the model: the existence of arbitrary small instants p such that b(p) = 0. As a consequence of Theorem 2, over such intervals [p, +∞[, the RTC Greedy Processors behave exactly as NC Variable Capacity Nodes. Consequently one can retrieve results from Variable Capacity Nodes like the link with strict service curves of Theorem 1.

Corollary 1. Consider an RTC Greedy Processor where inputs R and C are given, and C has a lower RTC service curve β l . Consider a solution (R, C, R ′ , C ′ , b) satisfying Equations (A7), (A8), (A10). Suppose that ∃p ∈ R such that B(p) = 0. Then the trajectory ( Ř, Ř′ ) (where F (.) = F [p, .)) admits β l as a strict service curve.

Remark 1 (Old RTC vs new RTC). The comparison above is drawn between Variable Capacity

Nodes and a recent presentation of RTC. Note that in the very first papers about RTC the Greedy Processors were defined exactly as Variable Capacity Nodes

[START_REF] Thiele | Real-time calculus for scheduling hard real-time systems[END_REF][START_REF] Thiele | Embedded software in network processors models and algorithms[END_REF]

. The reason for choosing a new RTC formalism (mainly with functions defined over all R) remains unclear for us, although the information might be present in the literature.

Remark 2 (What is a proof ? Equations vs interpretation). A temptation is to do proofs "by interpretation", i.e. one describes with words what is happening in the system. Ok it can be an useful approach and intuitions can be mentioned but the final proof should stick to the mathematical formalism, otherwise there are great risks of errors or ambiguities. Consequence: it requires very rigorous definitions at the beginning.

  β 2 are the respective intermediate service curves for two servers S 1 and S 2 in tandem, then β 1 * β 2 is an intermediate service curve for the concatenation of those two servers.

	Theorem 4. No notion of intermediate service curve can be strictly more restrictive than the
	notion of service curve.

RR n 7094 inria-00431674, version[START_REF] Schmitt | Performance bounds in feed-forward networks under blind multiplexing[END_REF]


Aymen Baouab
email: aymen.baouab@loria.fr

Olivier Perrin
email: olivier.perrin@loria.fr

Nicolas Biri
email: biri@lippmann.lu

Claude Godart
email: claude.godart@loria.fr

Security Meta-Services Orchestration Architecture

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

During the last few years, the architecture of IT environments has significantly changed. Legacy solutions based on huge monolithic applications lack in agility when responding to the evolution of IT and business needs. As a consequence, many enterprises have moved to service oriented architectures (SOA) aiming to achieve a more flexible system landscape, which facilitates integration of new components.

Indeed, SOA offers companies new ways to exchange data with their customers, partners and suppliers. To secure these exchanges, the use of new suitable security mechanisms is needed. In this type of architecture, third-party services are often deployed in public areas (usually nonsecure) in order to simplify the exchange and promote interoperability. In this case, security at the transport level is not enough and it is therefore necessary to move up to security at the application level. To deal with this requirement, several standards (WS-Security, SAML, XACML, WS-Trust, WS-Federation, WS-Policy) which cover security issues of Web services architectures have been developed. However, their current use addresses security at deployment time and not throughout the entire application lifecycle. These specifications are difficult to integrate into each business service especially when security requirements change frequently. Implementing these specifications without defining architectural guidelines makes the architecture much more complex and challenges the main features of SOA such as agility, flexibility and interoperability. Thus, as some legacy applications exposed as business services already have their own security mechanisms, managing the overall security chain when composing these business services represents a difficult task. Security functions must be handled dynamically depending on the security requirements and the legacy security mechanisms. For instance, when considering the project of the Luxemburg National Family Benefits Funds (CNPF) in which we are involved and the technical challenges encountered while migrating its IT environment, we have to propose a new architectural model that reduces the complexity resulting from the combination of various technologies. In fact, we aim to find a better way to integrate security that provides a high degree of reusability without impacting the business layer. Some specific approaches expose the best practices for securing SOAs. Most of them focus on the development of the Enterprise Service Bus (ESB) [START_REF] Chappel | Enterprise Service Bus[END_REF][START_REF] Woolf | Enterprise Integration Patterns, Designing, Building, and Deploying Messaging Solutions[END_REF] or similar middleware solutions [START_REF] Khalaf | Lightweight middleware for service-oriented computing[END_REF]. These solutions answer the agility issues and allows for a transparent access to the services. However, each change in the IT environment should correspond to an adaptation in the organization of the ESB. The problem of agility is only moved up to the ESB, but still unsolved. To address this issue, security functions can be implemented into separated services communicating with the rest of the system by means of messages. With a such solution, security will be decoupled not only from the business logic but also from the middleware system. The problem is then to find out how to make services operating together without having unwanted consequences on the security of the whole system.

In this paper, we address these aspects by introducing a new approach that overcome these limitations concerning SOA security and we define an adequate architectural framework called Security Meta-Services Orchestration Architecture, SMSOA. This architectural framework consists of security meta-services and a central service used for the orchestration of the meta-services depending on the policy associated with the business service to be protected.

Section 2 presents the motivations. Section 3 introduces the meta-service concept. Section 4 describes the most relevant elements of the proposed architecture, their communication and their composition. Section 5 comments on some similar approaches and finally, Section 6 concludes.

Motivation

A key objective of SOA consists of increasing the flexibility and the agility of the business [START_REF] Report | State of soa adoption report -gauging the use of soa systems in the enterprise[END_REF]. When considering security for SOA, several possibilities can be investigated. First, one possible architecture is to provide an unique security component (including authorization, authentication, audit, etc.) integrated with the ESB. This solution breaks the modular approach of SOA, and its flexibility and is difficult to adapt to the specific needs of each service. A second approach is to include security in each business service of the SOA. This solution appears to be time consuming and its cost is very high as it needs to rewrite each business service. Furthermore, with a such solution, SOA governance and security management may become much more complicated to ensure. A third approach is to provide security services that can be composed depending on the requirements of the business service to be protected. This approach is the one we have chosen. It takes its inspiration from Aspectoriented Programming (AOP) [START_REF] Kiczales | Aspect-oriented programming[END_REF]. The goal of AOP is to respond to the separation of concerns issue: many modules in a program share common components as, for instance, logging framework. These components are called crosscutting concerns, because they "cut" across several concerns. AOP aims in finding a way to isolate these crosscutting concerns in one central place, and to facilitate their management. The idea of our approach is to apply the separation of concerns in the SOA context in order to reduce the complexity, to provide a modular approach, and to strengthen the agility of the architecture.

Meta-services concept

We first introduce the concept of security meta-services in SOA architectures. Meta-services do not offer business operations, but act as helper services trying to optimize and simplify business services and their design. Meta-services centralize common functions used by multiple business ser-vices. These common functions are externalized from existing business services and managed independently. Metaservices help to improve the efficiency and flexibility and also have a positive impact onto occurring costs. Concrete instances of meta-services can be for instance orchestration services that offer service composition functionalities, security services that ensure the protection of business services, or monitoring services that control the correct execution of other services.

In our case, the meta-services offer a security service to other services (Security as a Service). In other words, they will ensure the security functions needed for the protection of business services. By externalizing security aspects from the business logic, Web services will be loosely-connected through a messaging interface. Moreover, the meta-services will be shared by different business services. This will reduce the complexity of the architecture, increase the degree of reusability and make the security system more scalable and more portable.

Security meta-services taxonomy

The possible meta-services for handling security requirements are:

Gateway meta-service This service, located at the federation perimeter intercepts all incoming and outgoing messages and appends security relevant information. Authentication meta-service This entity will verify that the supplied identification information is sufficient and correct. It checks the validity of authentication credentials (digital signatures, certificates, tokens, etc.). Authorization meta-service This meta-service determines applicable authorization policy, checks message relevant information (i.e. identity attributes) and makes an authorization decision. Audit meta-service It is designed to log certain parts of the message (passive audit) and to determine whether an exceptional state is reached. In this case, a notification describing the situation could be sent to the system administrator. Cryptographic meta-services They are responsible for applying cryptographic functions (i.e. digital signature calculation and verification, specific parts or whole message encryption / decryption). Separating these functions from the protected business service can be justified by the fact that they require significant computational power and therefore should be implemented on more powerful machines.

Verification, validation and filtering meta-services

These meta-services can be located at the federation perimeter in order to verify that the semantics of the incoming/outgoing messages is ensured. They provide attacks prevention mechanisms (i.e. DoS, XML injection, buffer overflow, replay attacks) [START_REF] Chappel | Enterprise Service Bus[END_REF][START_REF] Oneill | Web Services Security[END_REF]. Message filtering can be done by an XML Firewall. Accounting meta-services These meta-services are designed to meter the usage of protected services which are not offered free-of-charge.

Security meta-services granularity

The granularity of meta-services represents an important issue that should depend on the concrete deployment scenario and the required security functions. It plays a very important role in the evolution of the agility and the performance of the whole system. A finer granularity leads to a good separation of concerns which increases flexibility and agility and makes the meta-services more reusable. On the other hand, because each intermediate service must process the message content, increasing the number of metaservices implies a higher latency due to the additional network traffic and overhead resulting from XML parsing. This results to a compromise between agility and flexibility, on the one side, and performance on the other side. Otherwise, we need to choose between a specialized metaservice and a more general meta-service more configurable and therefore less reusable.

To make the choice on the granularity, it is important to consider all the needs of the customer and the provider. This may also depend on the size of the infrastructure, the average of throughput, the distribution of services (in the same server, same network, etc.) and available resources on each machine. One must also consider the frequency of security parameters changes and the evolution of business services needs in term of security.

The proposed architecture

In our approach, the architecture is composed of security meta-services, an orchestrator, and business services that are located in a trusted zone. Each security meta-services implements one or more security enforcement functions, depending of the desired granularity. A message reaching the trusted zone will be intercepted by a gateway service and be routed to the orchestrator. The response message will be returned to the orchestrator to eventually invoke some security meta-services before being routed to the requester (for instance, the audit meta-service).

To ensure the security needs of a business service, we need an entity that determines which meta-services should be invoked according to the security policies. This task is done by a central point (an orchestrator) that orchestrates security meta-services depending on the destination business service. If one of the security checks failed, an exception is raised and the orchestrator stops the security process by returning an access denied to the requester. If all security functions succeed, the business service is invoked and then the response is returned to the requester. Eventually, some meta-services can be invoked after the response of the business service in order to secure the outgoing messages. Figure 1 shows a use case scenario (steps are numbered). In this example, the requester looks for the address of the business service 2 and required security mechanisms (step 0) by invoking a public registry (i.e. UDDI). It then composes the message and invokes the service. The gateway service (here gateway and orchestrator are implemented as a single service) intercepts the message (step 1) and search for the policy corresponding to the protected service. The orchestrator invokes the needed meta-services (in this scenario, authentication, authorization and audit) and the business service respecting the security process described in the policy (steps 2,3,3',4,5,5',6,7) 1 . If one security function fails, the orchestrator stops the process and returns a deny message to the requester. Otherwise, the gateway returns the response to the customer service (step 8).

WS Security gateway Orchestrator

Authentication

Authorization

Specific orchestration

Using WS-BPEL [START_REF]Web services business process execution language version 2.0[END_REF], coding all combinations of possible meta-services (meta-services composition for each security policy) and updating them whenever a policy change occurs, represents a complicated task. To reduce this complexity and to improve the agility of the security system, there are two possible strategies.

One orchestrator per policy

This strategy introduces a specific orchestrator for each group of business services requiring exactly the same security functions. In this way, each orchestrator ensures the security of his group by invoking a static list of security meta-services whenever an incoming message reaches his area.

The gateway meta-service, located in the federation perimeter, dispatches incoming messages to the specific orchestrator according to the message destination. After receiving a message, the orchestrator invokes security metaservices and the target business service and then returns the response to the gateway service before being routed to the requester. Figure 2 shows a use case with ordered steps. In this example, zone A includes business services that require exactly three security functions while zone B includes business services that require only two security functions.

Figure 2. One orchestrator per policy

The decomposition of the federation into zones allows to distribute the load on several more specific orchestrators instead of having a central orchestrator that manages all the messages. However, there must be an orchestrator for each policy and therefore an addition (resp. deletion) of an orchestrator for each policy addition (resp. deletion).

One orchestrator per business service

The second strategy implements an orchestrator for each business service (Figure 3). In this way, a change in the policy might induce a change in the code of the orchestrator, but we will have a better distribution of load. Implementing an orchestrator for each business service can avoid all the problems linked to the compatibility, as we do not need to define the same interface for each business service in order to exchange messages with the orchestrator.

Note that in case of one orchestrator per policy (Section 4.1.1), all business services are connected to the same partner link and that is why they should satisfy a well-defined message format exchange and so a common interface.

Generic orchestration

Another strategy for orchestrating the meta-services is to use a generic orchestrator, rather than specific orchestrators as in 4.1. In this case, only one orchestrator is implemented to manage the whole system security. This orchestrator needs to be quite flexible and dynamic to permit the addition or the removal of security meta-services according to changing needs of each protected business service. Here, WS-BPEL is not well adapted because it does not allow flexibility in Partner Links. In fact, in BPEL, the partner link information is defined at design time. However, our scenarios require to define the partner link at run time, depending the policy of the business service. Oracle provides an ad-hoc solution to this problem, called dynamic service binding. However, the solution is conceptually poor, as all the services should be described in one WSDL file that is then used as the partner link [START_REF] Opincaru | Service oriented security architecture[END_REF]. That means for instance that no operation, message, input or output can be specified. It should be considered as a redirection.

To address this problem, we design our own orchestrator in order to be more generic (independent of the policy and the business service interface). The orchestrator should be able to carry a message according to its destination, based only on data obtained from a policy database. A change in policy and/or addition/removal of business services and security meta-services should not cause any change in the code of the orchestrator. Only a modification in the policy database will be needed.

To formally specify our architecture, we begin by distinguishing five types of components : a set of business services B, a set of meta-services S, an orchestrator O, a set of policies P and a list of operators OP.

Security process description

In order to make the orchestrator completely autonomous, we define a policy description language which will describe, for each business service, the security meta-services to call. To do this, we will first need two operators: "//" and ",". "S 1 //S 2 " means that the orchestrator can invoke both services S 1 and S 2 in parallel, while "S 1 ,S 2 " means that the orchestrator must invoke S 2 after S 1 .

To simplify the security management, we group the business services according to their security functions needs. Therefore, we need two tables in our policy database: one for the correspondence between each business service and its security policy (see Figure4.A) and another for the description of each security policy indicating meta-services to invoke using our description language (see Figure4.B).

Figure 4. Policy database

Figure 4 shows that for all incoming messages having the business service B 1 as destination, the orchestrator must invoke S 1 , S 3 and B 1 in parallel with S 4 , wait for their responses and then, if there is no exception, invokes S 4 and sends the reply to the requester.

Note that to change the policy of a business service, one can simply change its entry in the first table. To add a new business service, a new entry can be created and an existing policy can be selected. However, the second table allows to change a specific policy (i.e. add/remove of security metaservices). To add a new policy, a new entry can be created and the required security meta-services can be selected and organized. All these changes did not affect the orchestrator that will be designed to be able to parse any valid policy.

Policy validation

In order to avoid security process execution problems, it is necessary to validate every policy described with our language before its activation. To do this, policies should be analyzed and should satisfy a specific grammar. Using this grammar, invalid policies will be rejected by the orchestrator.

Definition 1 (Policy validation) Let S = [S 1 ; S 2 ; ...; S n ], B = [B 1 ; B 2 ; ...; B m ] and P = [P 1 ; P 2 ; ...; P l ]. P i (with 0 ≤ i ≤ l) is valid if it takes the following form :

{{S 1 |S 2 |...|S n }{//|, }} * X B {{//|, }{S 1 |S 2 |...|S n }} *
with X B ∈ B and P (X B ) = P i , and {A} * means that A is repeated 0 or more times.

For instance, "S 1 //S 2 , B//S 3 " and "S 1 //B" are valid policies, while "S 1 S 2 , B//S 3 " and "//S 1 , B," are not.

Security process instance state

The orchestrator needs some information (current status) to identify each received message in order to determine to which process instance the message is associated and what is the next step. Furthermore, the orchestrator may need to transmit some information (identity attributes, credentials, etc.) from one security meta-service to another. To do this, there are two possibilities. The first approach called stateful orchestrator is to store and manage instance identifiers and variables in the memory of the orchestrator. The second called stateless orchestrator appends such information to the message header (i.e. annotations).

A stateful orchestrator must read the destination of each incoming message, look for the security policy corresponding to this destination, extract the path described by the description language that we have defined, create an instance with a new state (in the memory) containing the necessary information and execute the process. Once implemented, the orchestrator will be autonomous as it will always be able to transform a security policy defined by our description language into a new process and be able to execute it.

With a stateless orchestrator, each incoming message must be annotated with a path containing an ordered list of security meta-services to invoke and an actual position indicator. This annotation represents the status of the security process and can be implemented as one or more tags of the SOAP message header. The orchestrator updates the status indicator after each invocation and then prepares himself to invoke the next meta-service. In this case, the orchestrator does not need memory to store the state of each instance. This will improve his treatment capacity and increase the throughput. In addition, with such a solution, it will have much less risks of memory crash (buffer overflow, etc.) which makes the orchestrator more reliable.

On the other hand, a stateless orchestrator may have to deal with some interoperability problems, especially when the orchestrator needs to call a security service located outside the trusted zone (security off-shoring). In this case, the annotation can be lost or modified by the external service which may cause disturbance in the security system. To tackle this problem, we can combine the two alternatives storing the state in the orchestrator memory only when an external service invocation occurs. This hybrid solution aims at combining the advantages of previous solutions to resolve problems encountered in each particular situation.

Synthesis

Since the security functions are not bound to the application and implemented into separated services, each one independent of the other, they can be shared by the different business services located in the same private network or a trusted area. This will reduce the costs associated with implementation, facilitate upgrades and allow the small functionnal components to be better tested (i.e. using unit tests) [START_REF] Opincaru | Service oriented security architecture[END_REF]. All these advantages address the agility and the extensibility of the architecture.

Implementing the security aspect using the principle of the separation of concerns reduces the complexity of the whole security system and allows for a clear design easy to configure and document. Configuration may be made by the orchestration of the security meta-services according to the needs of each business service (as shown in section 4.2.1).

Another advantage of our architectural design is that the administration and the control become simpler by centralizing security. Security administrators can control the whole system by acting only on the orchestrator. This may also simplify federated authentication, federated single sign on (SSO) and federated access control.

However, performance represents a possible disadvantage to our solution. In fact, SMSOA may higher latencies because of the additional network traffic and message content processing (i.e. XML parsing by each security metaservice). However, as descibed in section 3.2, performance can be modulated by varying the granularity of services.

In conclusion, our approach has several advantages: it is extensible, it provides a high degree of reusability and it improves the agility and the flexibility of service-oriented architecures. In addition, the fact that security services are independent and can be hosted in different physical locations represents another advantage.

Related Work

[9] outlines a holistic approach to protecting applications and services with the use of Web Services security infrastructure. Here, some security functions are implemented into a perimeter gateway which enforce security for the entire network. In addition, a service agent will be implemented to enforce individual service security. [START_REF] Brose | Securing web services with soap security proxies[END_REF] presents an approach where a single proxy acting as a gateway is implementing different security functions to enforce the security of several services. However, all these approaches does not respect the principle of separation of concerns. In [START_REF] Hondo | Security patterns within a service-oriented architecture[END_REF], security functions are realized into different services and combined by means of an ESB. However, communication between security services still not designed and no architectural analysis is made.

In [START_REF] Opincaru | Service oriented security architecture[END_REF], an architectural model called SOSA was described. Security is splitted into small functional components (security services) that can be separately developed. Because components are less complex, it will be easier to reuse them. This results in a more flexible design for security system. However, combining services by means of message routing patterns using itinerary attachment decen-tralize the security system and make it more difficult to control and to administrate. Furthermore, it is often necessary to implement an additional service for the invocation of the protected business service (and also in case of security offshoring) which will increase latency in both directions (additional processing of the incoming and the outgoing messages). Moreover, the fact that each security service must implement a message routing mecanism represents another drawback. In fact, in addition to its task, each security service needs to determine the next service to which the message should be forwarded. This is due to the fact that SOSA is based on a decentralized message routing pattern which is called Itinerary Routing.

Conclusion

In this paper, we proposed a new architectural framework for Web services security systems named Security Meta-Services Orchestration Architecture or SMSOA. The architecture is composed of three types of components: business services, security meta-services and orchestrators. Each meta-service implements one or more security functions and is invoked by an orchestrator according to business services security policies. This results to the separation of the security aspect from business services which reduce design complexity and development costs. In addition, orchestration solution centralize the security system and therefore easier to control and administrate.

Figure 1 .

 1 Figure 1. Meta-services orchestration

Figure 3 .

 3 Figure 3. One orchestrator per business service.

the prime denotes that x and x' are executed in parallel.