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

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

Eric Thierry
email: thierry@ens-lyon.fr

Tight performance bounds in the worst-case analysis of feed-forward networks

Keywords: Network Calculus, feed-forward networks, blind multiplexing, linear programming

Network Calculus theory aims at evaluating worst-case performances in communication networks. It provides methods to analyze models where the traffic and the services are constrained by some minimum and/or maximum envelopes (arrival/service curves). While new applications come forward, a challenging and inescapable issue remains open: achieving tight analyzes of networks with aggregate multiplexing.

, those bounds can be arbitrarily far from the exact worst-case values, even in seemingly simple feed-forward networks (two flows and two servers), under blind multiplexing (i.e. no information about the scheduling policies, except FIFO per flow). For now, only a network with three flows and three servers, as well as a tandem network called sink tree, have been analyzed tightly.

We describe the first algorithm which computes the maximum end-to-end delay for a given flow, as well as the maximum backlog at a server, for any feed-forward network under blind multiplexing, with concave arrival curves and convex service curves. Its computational complexity may look expensive (possibly super-exponential), but we show that the problem is intrinsically difficult (NP-hard). Fortunately we show that in some cases, like tandem networks with crosstraffic interfering along intervals of servers, the complexity becomes polynomial. We also compare ourselves to the previous approaches and discuss the problems left open.

Calcul exact de performances pire cas dans les réseaux acycliques

Résumé : Le Network Calculus est une théorie visant à évaluer les performances pire-cas dans les réseaux de communication. Il fournit des méthodes pour analyser des modèles où le trafic et les services sont contraints par des enveloppes inférieures et/ou supérieures (courbes d'arrivée et de service). Alors que de nouvelle applications émergent, beaucoup de problèmes importants restent ouverts : analyser de manière exacte des réseaux o des flux sont agrégés. Cette théorie offre des méthodes efficaces pour obtenir des bornes supérieures sur les délais maximum de bout-en-bout et la charge locale maximum. Malheureusement, il a été montré dans un article récent [START_REF] Schmitt | Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch[END_REF] que ces bornes pouvaient être arbitrairement mauvaises vis-à-vis de bornes effectivement atteintes, et ceci pour des réseaux très simples (deux serveurs et deux flux), lorsqu'il n'y a aucune information a priori sur la politique de service entre les flux, excepté que individuellement chaque flux est servi en FIFO (FIFO/flux). Actuellement, seuls des réseaux avec trois flux et trois serveurs, ainsi que les réseaux sink trees ont été analysés de manière exacte.

Dans cet article, nous décrivons le premier algorithme qui calcule les performance pire cas exactes (pire délai de bout-en-bout pour un flux donné ou charge maximum pour un serveur donné) pour tout réseau acyclique quand on autorise toutes les politiques de service FIFO/flux. La complexité de cet algorithme peut paraître très élevée (super-exponentielle), mais nous montrons que ce problème est intrinsèquement difficile (NP-difficile). Heureusement, dans certains cas, le calcul devient polynomial, par exemple quand tout les trafics transverses d'un flux interfèrent avec ce flux sur un intervalle de serveurs. Nous comparons finalement notre méthode aux approches existantes.

Mots-clés : Network Calculus, réseaux acycliques, programmation linéaire

Introduction

Network Calculus (NC) is a theory of deterministic queuing systems encountered in communications networks. With methods to compute deterministic bounds on delays, backlogs and other Quality-of-Service (QoS) parameters, it aims at analyzing critical behaviors and usually focuses on worst-case performances, either local performances (i.e. maximum buffer size at a node) or end-to-end performances (i.e. maximum end-to-end delay). The informations about the system are stored in functions, such as arrival curves shaping the traffic or service curves quantifying the service guaranteed at the network nodes. Relevant applications range from Internet QoS [START_REF] Firoiu | Theories and models for internet quality of service[END_REF] to the analysis of wireless sensor networks [START_REF] Schmitt | Sensor network calculus: A framework for worst case analysis[END_REF], System-on-Chip [START_REF] Chakraborty | Performance evaluation of network processor architectures: Combining simulation with analytical estimation[END_REF], industrial Ethernets [START_REF] Skeie | Timeliness of real-time ip communication in switched industrial ethernet networks[END_REF], critical embedded networks [START_REF] Boyer | Tightening end to end delay upper bound for afdx network calculus with rate latency fcfs servers using network calculus[END_REF]. At the present time, the theory has developed and yield accomplished results which are mainly recorded in two reference books [START_REF] Chang | Performance Guarantees in Communication Networks[END_REF][START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF]. It is an alternative to other approaches for worst-case performance analysis like holistic methods [START_REF] Tindell | Holistic schedulability analysis for distributed hard real-time systems[END_REF], trajectory methods [START_REF] Martin | End-to-end response time with fixed priority scheduling: trajectory approach versus holistic approach[END_REF] or model checking [START_REF] Hendriks | Timed automata based analysis of embedded system architectures[END_REF]. It is believed that Network Calculus and its extensions have advantages like modularity and scalability that will allow valuable analyzes of complex networks [START_REF] Perathoner | Influence of different system abstractions on the performance analysis of distributed real-time systems[END_REF].

From the beginning [START_REF] Chang | A filtering theory for deterministic traffic regulation[END_REF][START_REF] Cruz | A calculus for network delay, part i: Network elements in isolation[END_REF][START_REF] Cruz | A calculus for network delay, part ii: Network analysis[END_REF], Network Calculus methods have always put an emphasis on the use of (min, +) or (max, +) tropical algebras, known for their applications to different discrete event systems [START_REF] Baccelli | Synchronization and linearity[END_REF]. The definitions of arrival curve as well as simple minimum service curve can be easily stated with the (min, +) convolution. A general scheme consists in combining constraint curves thanks to algebraic operations like (min, +) convolution or (max, +) deconvolution. Using a few lemmas, one can either propagate constraints through the network and then retrieve performance bounds from all those computations, or express the network behavior with a set of (min, +) functional equations which must be solved to get the bounds. In this framework, the analysis of a single flow crossing a sequence of servers is tight. The (min, +) convolution elegantly captures the Pay Burst Only Once (PBOO) phenomenon in tandems of servers (burstiness is amortized all along the servers). However as soon as the network presents some aggregate multiplexing of several flows, providing a tight analysis becomes much more difficult.

The NC models are usually classified according to the topology of the network, the scheduling policies and the type of service guaranteed at each server. For general topologies where the flows may interfere with cyclic dependencies, the complexity of computing worst-case performances is still open. Even the simpler question of deciding stability, i.e. whether global backlog or endto-end delays remain bounded, is unset for many policies. Related results can be found in the Adversarial Queuing literature where the Permanent Session Model matches Network Calculus models [START_REF] Borodin | Adversarial queuing theory[END_REF]. A well-known necessary condition for stability is an utilization factor < 1 at each server. This condition is also sufficient for feed-forward networks [START_REF] Cruz | A calculus for network delay, part ii: Network analysis[END_REF], or unidirectional rings [START_REF] Tassiulas | Any work-conserving policy stabilizes the ring with spatial re-use[END_REF]. But, this condition is not sufficient for FIFO scheduling since there exist unstable networks at arbitrarily low utilization factors [START_REF] Andrews | Instability of fifo in the permanent sessions model at arbitrarily small network loads[END_REF]. For general FIFO networks, the best sufficient conditions and associated bounds on delays are provided by [START_REF] Rizzo | Stability and delay bounds in heterogeneous networks of aggregate schedulers[END_REF] but they are usually not tight. More thrilling, for simple feed-forward networks like FIFO tandems, a recent paper [START_REF] Bisti | Estimating the worst-case delay in fifo tandems using network calculus[END_REF] improving delays bounds has shown that those bounds were not tight yet.

In this paper, we investigate the complexity of computing exact worst-case performances (endto-end delays and local backlogs) for feed-forward networks under blind multiplexing, i.e. no information about the policy except FIFO per flow (also called FIFO per micro-flow [START_REF] Rizzo | pay bursts only once" does not hold for non-fifo guaranteed rate nodes[END_REF]). This assumption is weaker than FIFO scheduling for the aggregated flows. A first study of tandem networks put forward a new phenomenon called Pay Multiplexing Once (PMOO) (competition between flows for the resources is amortized all along the servers) [START_REF] Schmitt | The disco network calculator: a toolbox for worst case analysis[END_REF]. It presented a new method taking into account PMOO and experiments showed a significant improvement to the end-to-end delay bounds with regard to previous NC approaches. This method could be formulated as a new (min, +) multi-dimensional convolution [START_REF] Bouillard | Optimal routing for end-to-end guarantees using network calculus[END_REF], thus preserving the NC spirit while being a good candidate for tight analysis of blind multiplexing. However a recent breakthrough paper [START_REF] Schmitt | Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch[END_REF] showed that those bounds could be arbitrarily far from the exact worst-case values, even in seemingly simple feed-forward networks (two flows and two servers). This paper suggested a new approach using linear programming, but for now, only a network with three flows and three servers, as well as sink-tree tandems, could be analyzed tightly.

Our paper describes the first algorithm which computes the maximum end-to-end delay for a given flow, as well as the maximum backlog at a server, for any feed-forward network under blind multiplexing, with concave arrival curves and convex strict service curves. It also provides a critical trajectory of the system, achieving the worst-case value. Its computational complexity may look expensive (possibly super-exponential), but we show that the problem is intrinsically difficult (NP-hard). Fortunately we show that in some cases, like tandem networks i.e. the scenarios studied in [START_REF] Schmitt | Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch[END_REF][START_REF] Schmitt | The disco network calculator: a toolbox for worst case analysis[END_REF], the complexity becomes polynomial. Beyond the fact that our solution applies to any feed-forward networks, and although we also use linear programming, several features distinguish our approach from [START_REF] Schmitt | Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch[END_REF]: we tackle both worst-case delays and backlogs, we directly compute worst-case performances instead of looking first for an end-to-end service curve, we avoid a decomposition/recomposition scheme for convex/concave curves which may lead to looser bounds and a more expensive complexity.

The paper is organized as follows: after a presentation of the network model and the main NC notions in Section 2, we describe and analyze our algorithm in Section 3 where we also set the NP-hardness of the problem. Section 4 shows how it applies to tandem networks and compares our solution to previous works namely [START_REF] Schmitt | Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch[END_REF][START_REF] Schmitt | Delay bounds under arbitrary multiplexing[END_REF], while experiments are discussed in Section 5 to assess the gain w.r.t. to older NC methods. Further interesting extensions and open problems are presented in Section 6.

Our results are relevant to Network Calculus and extensions like Real-Time Calculus [START_REF] Thiele | Embedded software in network processors models and algorithms[END_REF] (which uses strict service curves). But we do not address stochastic extensions like [START_REF] Fidler | A network calculus approach to probabilistic quality of service analysis of fading channels[END_REF][START_REF] Jiang | Stochastic Network Calculus[END_REF].

Model and assumptions

Network Calculus framework

NC functions and systems

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 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). We consider a fluid model where time is continuous, data can be divided into arbitrarily small pieces (time and data measures belong to R + ) 1 and cumulative functions will belong to F = {f : R + → R + | f non-decreasing, left-continuous, f (0) = 0}2 . Constraint functions either shape the traffic (arrival curves) or guarantee some service locally or globally (service curves). Constraint functions usually allow the +∞ value. In this paper we will usually assume that they belong to F for commodity, but a careful look will show that all our solutions can be adjusted with no extra cost to deal with some +∞ values if necessary.

Beyond usual operations like the minimum or the addition of functions, Network Calculus makes use of several classical (min, +) operations [START_REF] Baccelli | Synchronization and linearity[END_REF]

such as: let f, g ∈ F, ∀t ∈ R + , convolution: (f * g)(t) = inf 0≤s≤t (f (s) + g(t -s)); deconvolution: (f ⊘ g)(t) = sup u≥0 (f (t + u) -g(u)). An input/output system is a subset S of {(F in , F out ) ∈ F × F | F in ≥ F out }.
It models a flow crossing a system where F in (resp. F out ) is the cumulative function at the entry (resp. exit) of the system and F in ≥ F out indicates that the system only transmits data. The system may range from a single server to a large network with cross-traffic. A trajectory of the system S is an element (F in , F out ) of S.

Note that it is not required to suppose that the system is deterministic. The system may admit several trajectories (F in , F out ), with the same input F in associated with different outputs F out .

NC arrival curves

Given a data flow, let F ∈ F be its cumulative function at some point, i.e. F (t) is the number of bits that have reached this point until time t, with F (0) = 0. A function α ∈ F is an arrival curve for F if ∀ s, t ∈ R + , s ≤ t, we have F (t) -F (s) ≤ α(ts). We also say that F is upper-constrained by α. It means that the number of bits arriving between time s and t is at most α(ts). A typical example of arrival curve is the affine function α σ,ρ (t) = σ + ρt, σ, ρ ∈ R + (sometimes called leaky-bucket arrival curve). Then σ represents the maximal number of packets that can arrive simultaneously (the maximal burst) and ρ the maximal long-term rate of arrivals. An usual assumption is that α is sub-additive (otherwise it can be replaced by its sub-additive closure). Note that the sub-additive closure of our leaky-bucket curve α σ,ρ is still α σ,ρ except at t = 0 where the value must be 0.

NC service curves

Two types of minimum service curves are commonly considered: simple service curves and strict service curves. Given a trajectory (F in , F out ) of an input/output system, we need to define the notion of backlogged period which is an interval

I ⊆ R + such that ∀u ∈ I, F in (u) -F out (u) > 0. Given t ∈ R + , the start of the backlogged period of t is start(t) = sup{u ≤ t|F in (u) = F out (u)}.
Since F in and F out are left-continuous, we also have

F in (start(t)) = F out (start(t)). If F in (t) = F out (t), then start(t) = t. For instance, for any t ∈ R + , ]start(t), t[ is a backlogged period, as well as ]start(t), t] if F in (t) -F out (t) > 0.
Let β ∈ F, we define:

S simple (β) = {(F in , F out ) ∈ F × F | F in ≥ F out and F out ≥ F in * β}; S strict (β) = {(F in , F out ) ∈ F × F | F in ≥ F out and for any backlogged period ]s, t[, F out (t) -F out (s) ≥ β(t -s)}.
We say that a system S provides a (minimum) simple service curve (resp. strict service curve) β if S ⊆ S simple (β) (resp. S ⊆ S strict (β)). A typical example of service curve is the ratelatency function: β R,T (t) = R(t -T ) + where R, T ∈ R + and a + denotes max(a, 0). Note that for all β ∈ F, S strict (β) ⊆ S simple (β) (since for all (F in , F out ) ∈ S strict (β), we have ∀t ∈ R + ,

F out (t) ≥ F in (start(t)) + β(t -start(t)) ≥ (F in * β)(t))
. But the converse is not true [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF]. An usual assumption for strict service curves is that β is super-additive (otherwise it can be replaced by its super-additive closure).

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 (i.e. one works with the sum of the cumulative functions). This is the case here.

Performance characteristics and bounds

Given a input/output system, bounds for the worst backlog and worst delay can be easily read from arrival and service curves.

Given a flow going through a network, modeled by an input/output system S, let (F in , F out ) be a trajectory of S. The backlog of the flow at time t is b(t) = F in (t) -F out (t), and the delay endured by data entering at time t (assuming FIFO policy for the flow) is

d(t) = inf{s ≥ 0 | F in (t) ≤ F out (t + s)} = sup{s ≥ 0 | F in (t) > F out (t + s)}.
Beware that d(t) = sup{s ≥ 0 | F in (t) ≥ F out (t + s)} For instance, look at t = 1 for F in (t) = t and F out (t) = 0 over [0, 2] and = 1 over ]2, 4] and = t over ]4, +∞[. For the trajectory, the worst backlog is B max = sup t≥0 F in (t) -F out (t) and the worst delay

is D max = sup t≥0 d(t) = sup{t -s | 0 ≤ s ≤ t and F in (s) > F out (t)}.
For the system S, the worst backlog (resp. delay) is the supremum over all its trajectories.

The next theorem explains how to derive performance bounds from constraints and how traffic constraints can be propagated.

Theorem 1 ( [START_REF] Chang | Performance Guarantees in Communication Networks[END_REF][START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF]). Let S be an input/output system providing a simple service curve β and let (F in , F out ) be a trajectory such that α is an arrival curve for F in . Then,

1. B max ≤ sup{α(t) -β(t) | t ≥ 0} = v(α, β) (vertical distance). 2. D max ≤ inf{d ≥ 0 | ∀t ≥ 0, α(t) ≤ β(t + d)} = h(α, β) (horizontal distance). 3. α ⊘ β is an arrival curve for F out .

Network model

A network will be modeled, without loss of generality, by a directed graph where the flows must follow the arcs and the servers (commuters, transmission links, routers...) are represented by the vertices.

Servers and flows will be identified by indices. The set of servers is S = {1, . . . , n} and each server j offers a strict service curve β j ∈ F which is piecewise affine (with a finite number |β j | of pieces) and convex. Thus it can be written β j (t) = max 1≤ℓ≤|βj| (r j,ℓ th j,ℓ ) with r j,ℓ , h j,ℓ ∈ R +

The set of flows is F = {1, . . . , p}. Each flow i corresponds to a couple (α i , µ i ) where µ i is the (finite) ordered sequence of servers crossed by the flow and α i is an arrival curve for the cumulative function before entering the first server. We suppose that α i is non-negative, nondecreasing, piecewise affine (with a finite number |α i | of pieces) and concave 3 . Thus it can be written α i (t) = min 1≤ℓ≤|αi| (σ i,ℓ + ρ i,ℓ t) with σ i,ℓ , ρ i,ℓ ∈ R + . Let i ∈ F, we denote first(i) (resp. last(i)) the index of the first (resp. last) server encountered by flow i. We will abusively write j ∈ i to say that the server j belongs to the sequence µ i . Given j ∈ i, we will denote prec i (j) the index of the server preceding j in the sequence µ i (by convention, prec i (first(i)) = 0). These notations are illustrated on Fig. 2.

i j ∈ i j last(i) first(i) prec i (j)
Figure 2: Notations about flow i.

The overall network N is defined by S, F and the sets

{β j , 1 ≤ j ≤ n}, {(α i , µ i ), 1 ≤ i ≤ p}. The directed graph induced by N is G(N ) = (S, A)
, where S is the set of vertices and (j, j ′ ) ∈ A if and only if j and j ′ are consecutive servers for some sequence µ i . The sequences µ i are paths in the digraph (the converse is not necessarily true). Any path in G(N ) = (S, A) will be designated by its ordered sequence of vertices and often written as a word over the alphabet S (we will often use π to designate a path and for instance jπ will denote the path starting by vertex j followed by the path π).

In addition, we will use the following notations (similar to [START_REF] Schmitt | Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch[END_REF]): for all i ∈ F, the cumulative function of flow i at the entry of network is

F (0) i ;
for all j ∈ i, the cumulative function of flow i at the output of server j is

F (j) i . A set of cumulative functions {F (j) i ∈ F | i ∈ F, j ∈ S,
j ∈ i} will be called a trajectory of the network N if it respects the NC constraints of the network:

(T1) ∀i ∈ F, ∀j ∈ i, F (prec i (j)) i ≥ F (j) i ; (T2) ∀i ∈ F, F (0) i is α i -upper constrained; (T3) ∀j ∈ S, ( i∋j F (prec i (j)) i , i∋j F (j) i ) ∈ S strict (β j ).
Since we work under blind multiplexing, no other relation is imposed. The set of all trajectories of N is denoted Traj(N ).

Here are our objectives:

1. Worst end-to-end delay. Given a flow i 0 , we wish to compute the worst end-to-end delay endured by data of this flow, that is sup

{F (j) i }∈Traj(N ) sup 0≤s≤t {t -s | F (0) i0 (s) > F (last(i0)) i0 (t)}.
2. Worst local backlog. Given a server j 0 , we wish to compute the worst backlog endured by this server, that is sup

{F (j) i }∈Traj(N ) sup t≥0 { i∋j0 F (prec i (j0)) i (t) - i∋j0 F (j0) i (t)}.
Those are supremum over infinite sets, nevertheless they can be computed as shown next. Note that those supremum are not necessarily reached for some trajectory or some instants s, t. For example, for a single flow crossing a single server, let

F (0) 1 (t) = t and F (1)
1 (t) = 2(t -1) + then the worst delay is 1 but it is not reach for any instants s, t (it occurs when t = 1 and s tends to 0). In the same way, if

F (0) 1 (0) = 0, F (0) 1 (t) = 1 for t > 0 and F (1)
1 (t) = t, the worst backlog is 1 but it is not reach for any instant t (it occurs when t tends to 0).

Note also that, when dealing with complexity, we will assume that numerical parameters take their values in Q rather than R.

Analysis of general feed-forward networks

Theorem 2. Let N be a network with n servers and p flows. If its induced graph G(N ) is feedforward, then given a flow i (resp. a server j), there exists a finite set Λ of linear programs (LP) with respective optimum values opt λ , λ ∈ Λ, such that max λ∈Λ opt λ is the worst end-to-end delay for flow i (resp. worst backlog at server j). Each linear program has O(p|Π|) variables and O(p|Π| 2 ) linear constraints where Π is the set of paths ending at end(i) (resp. j). We have

|Π| ≤ 2 n-1 and |Λ| ≤ |Π|!2 |Π|-1 .
The description of the different LP instances and the proof of the theorem will be illustrated with the small but typical example of Fig. 3: the diamond network.

β 1 β 3 β 4 t ∅ t 34 β 2 t 4 F (3) 2 F (2) 1 t 24 F (1) 2 F
(1) 1

F (0) 1 t 124 t 134 F (4) 1 F (4) 2 F (0) 2

The LP instances

We present a set of LP instances such that any trajectory satisfies at least one of them.

Variables

Given the flow of interest i (resp. a server j) for which one wants to compute the maximum end-to-end delay (resp. the maximum backlog) over all trajectories of the network, let Π be the set of all paths ending at last(i) (resp j), including the empty path denoted ∅. Here are the variables that will appear in each LP instance:

t π for all π ∈ Π. Interpretation: t ∅ is the instant at which the worst-case occurs (output of data having endured the worst delay or instant of worst backlog). Then for all jπ ∈ Π, t jπ = start j (t π ), the start of the backlogged period of t π at the server j.

F (j) i (t π ) for all i ∈ F, j ∈ i, π ∈ Π j i = {π ′ , jπ ′ | jπ ′ ∈ Π}. Interpretation: the value of the cumulative function F (j) i at time t π . F (0) i (t π ) for all i ∈ F, π ∈ Π i = j∈i Π (j)
i . Interpretation: the value of the cumulative function F (0) i at time t π .

Diamond example

If we are studying the worst end-to-end delay for flow 1 (or for flow 2, or the worst backlog at server 4), we have to consider the set of paths ending at server 4, i.e. Π = {∅, 4, 24, 34, 124, 134}. Thus the temporal variables are t ∅ , t 4 , t 24 , t 34 , t 124 , t 134 .

For flow 1 and server 1, the set Π

(1)
1 is {124, 23, 134, 34}. Thus the corresponding variables are

F (1) 1 (t 124 ), F (1) 1 (t 24 ), F (1) 1 (t 134 ), F (1)
1 (t 34 ). For flow 1, we have Π 1 = {∅, 4, 24, 34, 124, 134}. Thus the corresponding input variables are

F (0) 1 (t 124 ), F (0) 1 (t 24 ), F (0) 1 (t 134 ), F (0) 1 (t 34 ), F (0) 1 (t 4 ), F (0) 1 (t ∅ ).
Note that one could have introduced the variables F (j) i (t π ) for all π ∈ Π, but many of them do not occur while describing the sequence of events leading to the worst case and are not necessary to rebuild critical trajectories.

In the text, we will carefully distinguish the expression "the variable x" which refers to the unassigned variable, from the expression "the value x" which refers to an assignement of the variable x.

Temporal constraints

A set of temporal constraints T over some subset Π ′ ⊆ Π is a set of equalities or inequalities of the form t π1 = t π2 , t π1 ≤ t π2 or t π1 < t π2 where π 1 , π 2 ∈ Π ′ , and such that its set of solutions Sol(T ) ⊆ R Π ′ + is non-empty.

To ensure the coherence of the t π values with their interpretation as starts of backlogged periods, we introduce two predicates over the t π variables:

(P1) For all jπ ∈ Π, t jπ ≤ t π . (P2) For all jπ 1 , jπ 2 ∈ Π, t jπ1 < t jπ2 =⇒ t jπ1 ≤ t π1 < t jπ2 ≤ t π2 .
The predicate (P1) comes from the fact that for any trajectory and any instant t, at server j, we have start(t) ≤ t. It is also clear that for any instants t, t ′ , at server j, an ordering start(t) < start(t ′ ) ≤ t can not occur, leading to predicate (P2).

We say that a set of temporal constraints T over Π ′ satisfies the predicates (P1) and (P2) if any solution to T with real values satisfies both (P1) and (P2). Note that this definition involves an infinite number of tests, but one can easily decide whether T satisfies (P1) and (P2) with a O(|T ||Π ′ |) algorithm (one can perform a transitive closure algorithm on T to get all existing comparisons between the variables t π , π ∈ Π ′ , with complexity O(|T ||Π ′ |), then checking (P1) is immediate and checking (P2) comes to check that there is no

t jπ1 < t jπ2 ≤ t π1 configuration, it can be done in O(|T | 2 )).
We say that a set of temporal constraints T is a total order over some subset

Π ′ ⊆ Π if it has the form {t π1 ⊳ 1 t π2 ⊳ 2 • • • ⊳ N -1 t πN } where π 1 , π 2 , . . . , π N is a permutation of all the elements of Π ′ and for all 1 ≤ k ≤ N -1, ⊳ k ∈ {=, <, ≤}.
Note that for all π, π ′ ∈ Π ′ , by considering the transitive closure, T implies a comparison between π and π ′ which is either =,<,>,≤ or ≥. This comparison is denoted T (π, π ′ ). The set of all total orders over Π ′ which satisfy (P1) and (P2) is denoted Tot(Π ′ ). Here is one way to enumerate all the elements of Tot(Π ′ ): generate the set of temporal constraints imposed by predicate (P1), it corresponds to a tree-like partial order, then generate all its linear extensions, generate for each linear extension all the possible combinations of comparisons =, < or ≤ and for each one check whether it satisfies (P2). Such an algorithm works and it has roughly a O(|Tot [START_REF] Pruesse | Generating linear extensions fast[END_REF]. We have not looked for a faster algorithm, there is probably some ways to speed up this step, but any algorithm will require at least a |Tot(Π ′ )| complexity which can be exponential w.r.t. |Π ′ |.

(Π ′ )|3 |Π ′ | |Π ′ | 2 ) complexity
Now we come back to our network. For each flow i, we have associated the set of paths Π i = {π, jπ | j ∈ i, jπ ∈ Π} and we know that Π = 1≤i≤n Π i . Let (T 1 , . . . , T p ) ∈ Tot(Π 1 ) × • • • × Tot(Π p ), we say that the total orders (T 1 , . . . , T p ) are mutually compatible if for all 1 ≤ i 1 , i 2 ≤ p and π, π ′ ∈ Π i1 ∩ Π i2 , we have T i1 (π, π ′ ) = T i2 (π, π ′ ). Note that it can be checked with a O(p|Π| 2 ) algorithm looking at all pairs π, π ′ . This condition ensures that there exists a solution (t π ) π∈Π ∈ R Π + to the set of constraints T 1 ∪ . . . ∪ T p . Moreover I can easily prove that this solution will always satisfy the predicates (P1) and (P2).

Each combination (T 1 , . . . , T p ) ∈ Tot(Π 1 ) × • • • × Tot(Π p ) of mutually compatible total orders will lead to a set of LP instances. The main issue leading to such a case study is that, unlike (P1), the predicate (P2) cannot be captured by a single set of linear constraints.

Note that to avoid the analysis of redondant cases, one may only consider set of constraints T i such that their set of solutions Sol(T i ) is maximal for the inclusion (e.g. among two eligible sets

T 1 = {t 12 = t 13 < t 2 = t 3 } and T 2 = {t 12 = t 13 ≤ t 2 ≤ t 3 }, only T 2 needs to be considered).
Example The set Π is {∅, 4, 24, 34, 124, 134} and Π 1 = Π 2 = Π.

To satisfy predicate (P1), one has the relations:

t 124 ≤ t 24 ≤ t 4 ≤ t ∅ and t 134 ≤ t 34 ≤ t 4 ≤ t ∅ .
Now t 124 and t 134 need to be ordered. There are four maximal total orders that also satisfy predicate (P2):

T 1 = {t 124 ≤ t 24 < t 134 ≤ t 34 ≤ t 4 ≤ t ∅ }; T 2 = {t 134 ≤ t 34 < t 124 ≤ t 24 ≤ t 4 ≤ t ∅ }; T 3 = {t 124 = t 134 ≤ t 24 ≤ t 34 ≤ t 4 ≤ t ∅ }; T 4 = {t 124 = t 134 ≤ t 34 ≤ t 24 ≤ t 4 ≤ t ∅ }.

Trajectory constraints

Let (T 1 , . . . , T p ) ∈ Tot(Π 1 ) × • • • × Tot(Π p ) be some mutually compatible total orders.

Here is the set of equalities and inequalities describing the states of the system for our selected events:

Temporal constraints: T = T 1 ∪ . . . ∪ T p .
Strict service constraints: for all j ∈ S and jπ ∈ Π, add

{ i∋j F (j) i (t π ) -i∋j F (j) i (t jπ ) ≥ β j (t π -t jπ )} (that is |β j | linear inequalities since β j is the maximum of affine functions). Moreover for all jπ 1 , jπ 2 ∈ Π such that T (jπ 1 , jπ 2 ) is = and T (π 1 , π 2 ) ∈ {=, ≤, <}, add { i∋j F (j) i (t π2 ) -i∋j F (j) i (t π1 ) ≥ β j (t π2 -t π1 )}.
Starts of backlogged periods: for all j ∈ S, jπ ∈ Π and i ∋ j, add {F

(prec i (j)) i (t jπ ) = F (j) i (t jπ )}.
Flow constraints: for all i ∈ F, j ∈ i and jπ ∈ Π, add

{F (0) i (t jπ ) ≥ F (j) i (t jπ ), F (0) i (t π ) ≥ F (j) i (t π )}.

Non-decreasing functions:

for all i ∈ F, j ∈ i and π 1 , π 2 ∈ Π (j) i , if T (π 1 , π 2 ) is =, then add {F (j) i (t π1 ) = F (j) i (t π2 )} and if T (π 1 , π 2 ) ∈ {≤, <}, then add {F (j) i (t π1 ) ≤ F (j) i (t π2 )}. Arrival constraints: for all 1 ≤ i ≤ p, for all π 1 , π 2 ∈ Π i such that T (π 1 , π 2 ) ∈ {=, ≤, <}, add {F (0) i (t π2 ) -F (0) i (t π1 ) ≤ α i (t π2 -t π1 )} (that is |α i | linear inequalities since α i is the minimum of affine functions).
Diamond example For T 1 = {t 124 ≤ t 24 < t 134 ≤ t 34 ≤ t 4 ≤ t ∅ }, flow constraints, nondecreasing constraints and starts of backlogged periods for flow 1, are depicted on Fig. 4.

F 0 1 (t 124 ) ≤ F 0 1 (t 24 ) ≤ F 0 1 (t 134 ) ≤ F 0 1 (t 34 ) ≤ F 0 1 (t 4 ) ≤ F 0 1 (t ∅ ) = ≥ = ≥ ≥ ≥ F 1 1 (t 124 ) ≤ F 1 1 (t 24 ) ≤ F 1 1 (t 134 ) ≤ F 1 1 (t 34 ) = F 2 1 (t 24 ) ≤ F 2 1 (t 4 ) = F 4 1 (t 4 ) ≤ F 4 1 (t ∅ )
Figure 4: Constraints for flow 1 and T 1 (except service/arrival constraints).

For server 1, strict service constraints are:

F (1) 1 (t 24 ) + F (1)
2 (t 24 ) -F

(1)

1 (t 124 ) + F (1)
2 (t 124 ) ≥ β 1 (t 24t 124 );

F (1) 1 (t 34 ) + F (1)
2 (t 34 ) -F

(1)

1 (t 134 ) + F (1)
2 (t 134 ) ≥ β 1 (t 34t 134 ). For flow 1, arrival constraints are:

F (0) 1 (t 24 ) -F (0) 1 (t 124 ) ≤ α 1 (t 24 -t 124 ), F (0) 1 (t 134 ) -F (0) 1 (t 124 ) ≤ α 1 (t 134 -t 124 ), F (0) 1 (t 134 ) -F (0) 1 (t 24 ) ≤ α 1 (t 134 -t 24 )... INRIA

Objective

Worst end-to-end delay for flow i 0 : maximize the objective function (t ∅u), where t ∅u is the delay endured by data that entered the network at time u and left at time t ∅ . Consequently one has to add several constraints linked to u and possibly to consider several cases depending on the choice of T i0 in Tot(Π i0 ):

Arrival time: {F (0) i0 (u) > F last(i0) i0 (t ∅ )}.
Insertion: one must position u within the total order T i0 . For each π ∈ Π i0 , we generate one LP instance by adding the constraints:

Position and monotony:

add {t π ≤ u, F (0) i0 (t π ) ≤ F (0)
i0 (u)}, and let t π ′ be the successor of

t π in T i0 (if any), add {u ≤ t π ′ , F (0) i0 (u) ≤ F (0) i0 (t π ′ )}.

Arrival curve constraints:

for all π ′ ∈ Π i0 , if T (π ′ , π) ∈ {=, ≤, <}, add {F (0) i0 (u)-F (0) i0 (t π ′ ) ≤ α i0 (u -t π ′ )}, otherwise add {F (0) i0 (t π ′ ) -F (0) i0 (u) ≤ α i0 (t π ′ -u)}.
Diamond example Some possible particular positions of u are t 124 ≤ u ≤ t 24 , t 24 ≤ u ≤ t 134 , ... As a matter of fact, one can consider fewer cases. First there may be some equal elements in T i0 which will yield the same additional constraints for u. Then more significantly, it is not necessary to consider all the possible positions of u between all the consecutive elements of T i0 . One only has to position u between consecutive elements of Start 0 = {t first(i0)π | first(i 0 )π ∈ Π i0 } the set of all starts of backlogged periods at server first(i 0 ). This general idea is is explained in the particular case of Theorem 4, but to ease a little the construction of critical trajectories, we keep all the cases mentioned before.

Worst backlog at server j 0 : maximize the objective function i∋j0 F

(prec i (j0)) i (t ∅ )-i∋j0 F (j0) i (t ∅ ).
It does not introduce new cases or new linear constraints.

From network trajectories to LP solutions

Let λ be an LP instance (possibly with strict inequalities) with optimal value opt λ , we call a solution of λ an assignation of the variables satisfying the linear constraints, and it is an optimal solution if it achieves opt λ (there may be no optimal solution if λ = +∞ or when there are some strict inequalities in the constraints).

Lemma 1. Let N be a feed-forward network and a flow of interest i 0 (resp. a server j 0 ). Let Λ be the set of LP instances constructed in Section 3.1. Given a trajectory {F (j) i } ∈ Traj(N ) where some data in flow i 0 is enduring an end-to-end delay d (resp. the backlog at j 0 becomes b), then there exists an LP instance λ ∈ Λ admitting a solution such that t ∅ -u = d (resp. i∋j0 F

(prec i (j0)) i (t ∅ )- i∋j0 F (j0) i (t ∅ ) = b).
Proof. Consider {F (j) i } ∈ Traj(N ), let t ∅ be the instant at which the data enduring the delay d leaves the networks (resp. at which the backlog is b). For the delay, there also exists in the trajectory a value u such that that u ≤ t ∅ ,

F (0) i0 (u) > F (last(i) i0 (t ∅ )} and d = t ∅ -u.
Consider the interpretation of the variable t π given in Section 3.1.1 and find out their values from the trajectory (it requires to compute for each server j, the functions i∋j F (prec i (j)) i and i∋j F (j) i to detect starts of backlogged periods). The values {t π , π ∈ Π} are totally ordered and satisfy the predicates (P1) and (P2). Thus there exists a family of time constraints (T 1 , . . . , T p ) ∈ Tot(Π 1 ) × • • • × Tot(Π p ) all satisfied by the set of values {t π , π ∈ Π}, and which use only = or < constraints (they are just read from the values). As a consequence those time constraints are mutually compatible. Then for all i, j, t π , read the value F (j) i (t π ) from the trajectory. The choice of (T 1 , . . . , T p ) (and for delays, the position of u in T i0 ) corresponds to a LP instance λ ∈ Λ.

By a careful but easy checking, the definition of the values t π (and u) and the fact that the trajectory satisfies (T1), (T2), (T3) ensures that all the linear constraints in the LP instance λ are satisfied. Moreover by definition of the value t ∅ (and u), we have t

∅ -u = d (resp. i∋j0 F (prec i (j0)) i (t ∅ ) -i∋j0 F (j0) i (t ∅ ) = b). t ∅ t 3 t 23 F (3) 1 F (1) 1 F (0) 1 α F (2) 1 u t 123

From LP solutions to network trajectories

Lemma 2. Let N be a feed-forward network and a flow of interest i 0 (resp. a server j 0 ). Let Λ be the set of LP instances constructed in Section 3.1. Consider an instance λ ∈ Λ and one of its solution (if any). Then there exists a trajectory {F (j) i } ∈ Traj(N ) where the worst end-to-end delay d for flow i 0 (resp. worst backlog b for server j 0 ) satisfies

d = t ∅ -u (b = i∋j0 F (prec i (j0)) i (t ∅ ) -i∋j0 F (j0) i (t ∅ )).
Proof. Before describing the construction of the trajectory {F (j) i }, we make a few remarks about our LP instances and their solutions.

Existence of solutions For the worst backlog, all our LP instances admit at least a solution by choosing a set of values t π complying to time constraints and all other values F (j) i (t π ) being null. For the worst end-to-end delay, solutions exist if and only if α i0 is not the null function. If α i0 = 0, since it is concave, α(u) > 0 if u > 0. Thus choose some value t π and u complying to time constraints and such that u > 0, impose that all other values F (j)

i (t π ) are null except F (first(i0)) i0 (t π ) = α(t π ). It ensures that F (0) i0 (u) > F last(i0) i0 (t ∅ ).
The < issue Our LP instance λ may use some strict linear inequalities. However LP solvers work with non-strict inequalities, and thus the LP instance which is actually solved is the instance λ where all signs < have been replaced by ≤. Since the set of solutions of λ is the closure of the non-empty convex set of solutions of λ, we have opt λ = opt λ and for any solution of λ there exists an arbitrarily close solution of λ. Consequently, if the LP solver does not provide a solution achieving opt λ and satisfying λ, we will work with a sequence of solutions of λ whose objective functions tends to opt λ . Thus, from now, we will discuss the construction of trajectories for solutions of λ.

The assignation issue for functions Since our LP instance λ uses some non-strict inequalities, the following case may occur in a solution to λ: for some i ∈ F, j ∈ i, π, π ′ ∈ Π (j) i , we may have the values

t π = t π ′ = t while F (j) i (t π ) < F (j) i (t π ′ ).
A careful look at our LP instances shows that it can occur only if {t π ≤ t π ′ } was a time constraint (due to non-decrease constraints). Then INRIA we can transform our solution by replacing F (j) i (t π ) by the value F (j) i (t π ′ ). Another careful look shows that such a transformation will not violate any constraint, thus we still have a solution to λ. Repeated if necessary, it comes to say that we will finally choose F (j) i (t) = max tπ=t F (j) i (t π ) which is well-defined for t.

The translation lemma and its application Given a solution to λ and an arbitrary constant c i ∈ R + , let us replace all values F (j) i (t π ) by the values F (j) i (t π )c i (we suppose that c i is sufficiently small so that those values remain non-negative). Then one can easily check that this new assignment of variables is still a solution to λ.

Given a solution to λ, we use this translation lemma for each flow i. Each set of values {t π , π ∈ Π i } admits a minimum t πmin(i) . Due to LP constraints, for all j ∈ i, the value F (0) i (t πmin(i) ) is lower or equal to all the other values F (j) i (t π ). We set c i = F (0) i (t πmin(i) ) and substract c i from all the values F (j) i (t π ). Once done for all flows, we still have a solution to λ, but now for all i ∈ F, we have

F (0) i (t πmin(i) ) = 0.
This transformation ensures that one can add the point (0, 0) among the points (t π , F (0) i (t π )), π ∈ Π i , and still satisfy the arrival curve constraints (since

F (0) i (t π )-0 = F (0) i (t π )-F (0) i (t πmin(i) ) ≤ α(t π -t πmin(i) ) ≤ α(t π ) -0)).
The linear interpolation lemma Let α (resp. β) be a concave (resp. convex) function in

F . Let x 1 < x 2 < • • • < x k and y 1 ≤ y 2 ≤ • • • ≤ y k be two sets of values in R + , such that ∀1 ≤ ℓ ≤ ℓ ′ ≤ k, y ℓ ′ -y ℓ ≤ α(x ℓ ′ -x ℓ ) (resp. y ℓ ′ -y ℓ ≥ β(x ℓ ′ -x ℓ )). Then the function F from [x 1 , x k ] into R +
which is the linear interpolation of the points (x 1 , y 1 ), (x 2 , y 2 ), . . . , (x k , y k ), is non-decreasing and satisfies for all

x 1 ≤ s ≤ t ≤ x k , F (t) -F (s) ≤ α(t -s) (resp. F (t) -F (s) ≥ β(t -s)).
The proof is a straightforward use of concavity (resp. convexity).

Reconstruction of cumulative functions for each flow

Given a solution to λ, apply first all the transformations described above. Then consider a flow i, all functions F (j) i , j ∈ i or j = 0, will be null from 0 to t πmin(i) the minimum value of {t π , π ∈ Π i }. Now we describe each F (j) i (t), j ∈ i or j = 0, for t ≥ t πmin(i) .

The function F (0) i is the linear interpolation of the points {(t π , F (0) i (t π )) | π ∈ Π i } and remains constant from its maximum point. Now we construct the functions F (j) i by induction while moving forward on the path µ i . Suppose that F prec i (j) i has been constructed. To construct F (j) i , we first have to define some intervals where data from flow i is backlogged at server j. Consider the values {t jπ | jπ ∈ Π i } which correspond to the starts of such backlogged periods. Some of these values can be equal, just consider the distinct values denoted t 1 < • • • < t m . By convention we denote t m+1 = +∞. Then to each t v we associate t

+ v = max{t π | t v ≤ t π < t v+1 , π ∈ Π (j)
i } and the points

P v = {(t π , F (j) i (t π )) | t v ≤ t π < t v+1 , π ∈ Π (j) i }. Then F (j) i
is defined as the linear interpolation of the points P v over each interval [t v , t + v ] and is equal to

F (prec i (j)) i
otherwise. Let j max be the last server from which there is a path in Π. Then, for all the next j on µ i , we set F

(j) i = F (jmax) i .
Once these constructions are done for all the flows, one can carefully check that this family of fonctions which belong to F satisfy (T1), (T2), (T3), thanks to the preceeding remarks et lemmas which enable to extend the trajectory constraints from a finite set of points to functions defined over R + .

This construction also ensures that the trajectory has a worst end-to-end delay for flow i 0 equal to t ∅u (resp. worst backlog for server j 0 equal to i∋j0 F

(prec i (j0)) i (t ∅ ) -i∋j0 F (j0) i (t ∅ )),.
It comes from the fact that F Note that the statements of Lemma 1 and Lemma 2, as well as Lemma 3, prove Theorem 2 while avoiding the question of unbounded delays or backlogs. The LP solvers will output a +∞ result if it is actually the worst-case. However if one wish to state a theorem characterizing scenarios with such +∞ worst end-to-end delays or local backlogs, rather than analyzing in details the properties of our set of LP instances, we prefer to refer to the following classical result: in a feed-forward network with a FIFO-per-flow policy, for any flow i (resp. server j) the worst end-to-end delay (resp. local backlog) is bounded if and only if each server on a path leading to last(i) (resp. j) has an utilization factor (asymptotic service rate/ sum of asymptotic arrival rates) which is < 1, as already proved in [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF].

(last(i0) i0 (t) = F (0) i0 (t) for t ≥ t ∅ . RR n 7012 S j S ′ i S ′′

Computational hardness

Theorem 3. Computing the worst backlog at a given server in a feed-forward network is NP-hard.

Proof. We reduce the problem "exact three-cover" (X3C) to our problem. An instance of X3C is a collection C = {c 1 , . . . , c 3q } of 3q elements and a collection U = {u 1 , . . . , u s } of s sets of 3 elements of C. The problem is to decide whether there exists a cover of S by q elements of C. We will reduce this problem to deciding whether a given backlog can be reached in a server of a network.

The network we use is as shown in Figure 6. The upper stage consists of 3q servers S 1 , . . . , S 3q , all with service curve β 1 : t → t. The middle stage consists of s servers S ′ 1 , . . . , S ′ s , all with service curve β 2 : t → 2.1t if t < 1; t → ∞ otherwise. Finally, the lower stage has only one server S ′′ , with service curve β 3 : t → Rt with R > 3s. There are 3s flows, each of them crossing three servers from top to bottom. A flow, F i,j crosses servers S j , S ′ i , S ′′ if and only if c j ∈ u i . Each of those interfering flows has an arrival curve α : t → min(t, 1) (note that there can be no burst).

One wants to decide whether the backlog in S ′′ can be at least 3(sq) + 0.9s. The worst-case backlog in server S ′′ will be obtained when flows arrive according to α (indeed, no burst can never arrive), and when servers S j and S ′ i are exact servers. Consider an infinitesimal time interval, during which each flow F i,j at the upper level is served at rate r i,j , with i:cj ∈ui r i,j = 1. The service rate if S ′ i is min(2.1, j:cj ∈ui r i,j ) and then the increase rate of the backlog during that time interval at the middle level is i∈{1,...s} ( j:cj ∈ui r i,j -2.1) + . At the upper level, the backlog is created at rate 3si,j r ij = 3(sq), which does not depend on the service rates. Maximizing the backlog is equivalent to maximizing the following function: i∈{1,...s} j:cj ∈ui r i,j -2.1 + with the constraints: ∀j ∈ {1, . . . , 3q}, i:cj ∈ui r i,j = 1 and ∀i, j, r i,j ≥ 0. Note that one can replace i:cj ∈ui r i,j = 1 by i:cj ∈ui r i,j ≤ 1. Now, discard the constraints of the network, and suppose that i:cj ∈ui r i,j ≤ 1 and r i,j ≥ 0 are the only constraints (U is the set of all 3-sets of C). Our problem boils down to the maximization of a convex function on a convex set. The maximum values are then obtained at some extremal vertices of the convex set. The extremal vertices of the convex set are such that i:cj ∈ui r i,j = 1, r i,j ∈ {0, 1} and then j:cj ∈ui r i,j ∈ {0, 1, 2, 3}. Maximizing our function is then equivalent to maximizing the number of i such that j:cj ∈ui r i,j = 3.

Note that any small variation will make the function decrease (for ǫ ≤ 0.9, 0 + (3 -2.1) = 0.9 > (ǫ -2.1) + + (3ǫ -2.1) + = 0.9ǫ). Then, the function reaches its maximum only at vertices that are in one-to-one correspondance with the X3C covers when U is the set af all 3-sets of C.

So, if one takes into account the constraints of the network (we get back to any collection U ), the backlog is created in the middle level at rate at most 0.9. This maximum is reached if and only if there exists an X3C cover.

Finally, the reasoning above is valid for the interval of time [0,1]. Indeed, the backlog is subadditive: if an arrival cumulative function F 1 defined on the interval [0, s] in a server creates a backlog b 1 at time s, and if the arrival cumulative function F 2 such that F 2 (s) = 0 creates a backlog b 2 at time t ≥ s (when the server is empty at time s), then the process

F 1 + F 2 creates a backlog b ≤ b 1 + b 2 at time t.
As a consequence, there is no advantage in changing the service rates r i,j during the interval of time [0, 1]. At time 1, servers S j and S ′ i serve all their backlog and the backlog in server S ′′ is then at most 3(sq) + 0.9s. This maximum is reached if and only if there is an X3C cover.

The NP-hardness has been proved only for the worst backlog. A similar result should hold for the worst end-to-end delay, using the same example, but this should be a little more tricky, as the entry of the bit of data that reaches (or almost reaches) the worst end-to-end delay may not arrive at time t = 1. Anyway we conjecture that computing the worst end-to-end delay for a given flow is also NP-hard.

The tandem scenario: a polynomial algorithm

We study here a special class of feed-forward networks: the tandem networks, i.e. networks N such that the induced digraph G(N ) is a directed path with no shortcut. It implies that any flow follows a sequence of consecutive servers in the path. Such scenarios have been highlighted by [START_REF] Schmitt | The disco network calculator: a toolbox for worst case analysis[END_REF][START_REF] Schmitt | Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch[END_REF][START_REF] Lenzini | A methodology for computing end-to-end delay bounds in fifo-multiplexing tandems[END_REF].

For this class of networks, the worst-case computation boils down to solving a single LP instance with a polynomial number of variables and constraints, and thus with a polynomial complexity. Moreover, we show for each flow how to reconstruct a minimum end-to-end service curve which is optimal in some sense.

The algorithm for the tandem scenario

Theorem 4. Let N be a tandem network with n servers and p flows. Then, given a flow i (resp. a server j), there exists one LP instance with O(pn) variables and O(pn 2 ) constraints such that the optimum is the worst end-to-end delay for flow i (resp. the worst backlog at server j).

Proof. Without loss of generality, we can assume that i = 1 and last(i) = n (resp. j = n) since what happens after the last server of interest does not INFLUER on the dynamics of the first part of the network (servers after the last server of interest do not appear in the LP formulations of the problem).

A direct application of Theorem 2 to tandem networks induces a single order on the n + 1 variables t πj , for the paths π j-1 = j • • • n and π n = ∅. This order is simply

t π0 ≤ t π1 ≤ • • • ≤ t πn .
So, computing the worst backlog at server n boils down to a single LP instance, while computing the worst end-to-end delay introduces the variable u and possibly n LP instances depending on the location of u.

Set f 1 = first(1) -1 and e 1 = last(1) = n. We now show that it is useless to consider several LP instances to compute the worst delay. There is no need to consider all the positions to insert u within the order t π f 1 ≤ • • • t πe 1 . We only need one LP instance and the constraints where u must appear are:

t π f 1 ≤ u ≤ t πe 1 , F (0) 1 (u) > F (n) 1 (t πe 1 ) and F (0) 1 (u) -F (0) 1 (t π f 1 ) ≤ α 1 (u -t π f 1 )
. The objective and the other constraints remain unchanged. Remark that the maximization of the objective function will lead to the equality

F (0) 1 (u) -F (0) 1 (t π f 1 ) = α 1 (u -t π f 1 ).
To prove this, we proceed by contradiction. Consider a worst-case trajectory for a tandem network. It is obtained as a solution of our n LP instances of the general method. If that worst-case trajectory is not obtained by the alternative single linear program, which means that

F (0) 1 (u) -F (0) 1 (t π f 1 ) < α 1 (u -t π f 1 ), one can replace F (0) 1|[tπ f 1 ,u] by α 1|[tπ f 1 ,u]
. Doing this the trajectory remains valid for the system: flow constraints, non-decrease, arrival and strict service are still satisfied. As far as the starts of backlog period are concerned, the additional data that arrived in a server are transmitted at the begin of the backlogged period of the next server (ensuring that the input cumulative function in that next server is not less than the original input cumulative function and then ensuring that the backlogged period will not end before the backlogged period of the original cumulative functions. Since F (0) 1 (u) < α 1 (ut π f 1 ) and the cumulative function

F (e1) 1
is non-decreasing, t πe 1 must increase, hence one can obtain a longer delay than in the original trajectory.

From delays to end-to-end service curves

Let N be a network and flow 1 be the flow of interest, for now we have investigated a way to compute the worst delay for fixed constraints (α i ) i∈F and (β j ) j∈S . One may want to measure how the global network acts upon flow 1, in particular whether some minimum end-to-end service curve can be guaranteed. Given β ∈ F, we say that β is an end-to-end (simple) service curve (or left-over service curve [START_REF] Schmitt | The disco network calculator: a toolbox for worst case analysis[END_REF][START_REF] Schmitt | Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch[END_REF]) if

F out i ≥ β * F in i .
It is called an universal end-to-end service curve if β is independent of α 1 (i.e. β remains an end-to-end service curve for any choice of α 1 ). Precomputing such an universal curve can be useful to quickly compute a bound on end-to-end delays for flow 1 for several different curves α 1 (thanks to the horizontal distance of Theorem 1). In the case of tandem networks, we now prove that one can compute an universal end-to-end service curve which is optimal in some sense.

Theorem 5. Let N be a tandem network with n servers and p flows. Then one can compute an universal end-to-end service curve for the flow 1, which is the maximum of all universal end-to-end service curves.

Proof. We prove that this service curve can effectively be computed, using the dual problem of an LP instance.

To compute an end-to-end service curve for flow 1, the idea is to send a burst of size σ (with α 1 (t) = σ) and compute the worst-case delay for that flow thank to our linear program. Let d(σ) be that maximal delay. Doing this for every σ, we compute the function d : σ → d(σ), which is trivially non-decreasing. We will first show its the pseudo-inverse β : t → inf{σ ≥ 0 | d(σ) ≥ t} is a service curve for flow 1 and then we will show how to compute d.

We make an induction on the number of servers and are interested in flow 1 that crosses every server (this assumption is only for the ease of the presentation, exactly the same can be done for any flow, the only change is that the initialization step is H(first(1)) and server 1 has to be replaced by server first(1)). Our induction hypothesis is:

H(n) Let {F (j) i
∈ F | i ∈ F, j ∈ S, j ∈ i} be a trajectory for a system with n servers in tandem. For every t ∈ R + , there exists t 0 such that there exists a trajectory { F (j) i ∈ F | i ∈ F, j ∈ S, j ∈ i} for the system such that 1.

F (0) 1 (s) = F (0) 1 (t) if s ≥ t 0 and F (0) 1 (s) = F (0) 1 (s) otherwise; 2. ∀i, ∀j ∈ i, F (j) i (s) = F (0) i (s) if s ≤ t 0 ; 3. Let t n = start n (t), F (n) 1 (s) = F (n)
1 (s) if s ≥ t n and t n is still the beginning of the backlogged period of t in server n in the trajectory { F (j) i }.

H( 1) is true: let t ∈ R + . Let t 1 = start 1 (t). Here, t 0 = t 1 and the trajectory F (j) i with ∀i,

F (0) i (s) = F (0) i (t) if s ≥ t 1 and F (0) i (s) = F (0) i (s) otherwise; F (1) i (s) = F (0) i (s) if s ≤ t 1 and F (1) i (s) = F (1)
i (s) otherwise is a trajectory for the system: before time t 0 , the system behaves as an infinite server and then has the same behavior as in the original system. As the server is strict, the behavior in a backlogged period only depends on the trajectory during that period. Moreover, at time t 0 , a burst arrives, so that a backlogged period begins, and as during that period and until time t,

F (0) i (s) = F (0) i (t) > F (1) i (t) ≥ F (1) i (s) = F (1)
i (s), then that backlogged period cannot end before time t, and as the server is strict, we have a trajectory for the system. This set of simple universal end-to-end service curves β R,T admits a maximum β (since R is fixed). It is achieved for a good choice of values s Then it is shown that for any arrival curve α 1 , the horizontal distance h(α 1 , β) between α 1 and β, which is an upper bound on the worst end-to-end delay, is actually tight, i.e. there exists a trajectory achieving this bound. Such a critical trajectory is fully described for sink-tree tandems, and in one case for the 3-servers 3-flows scenario (the other cases are left to the reader).

The second difference concerns the treatment of concave/convex arrival/service curves, if one already knows how to deal with leaky-bucket/rate-latency curves. Unlike the polynomial algorithm of Theorem 4, the scheme in [START_REF] Schmitt | Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch[END_REF] is to decompose the curves into maximum (resp. minimum) of rate-latency (resp. leaky-bucket) service (resp. arrival) curves, then compute the left-over service curves obtained for each combination of rate-latency/affine service/arrival curves, and finally compute the maximum of all those curves. One should notice that such a process does not guarantee that this maximum of simple service curves is still a simple service curve or that it will provide tight bounds. It only ensures that the horizontal distance between the arrival curve of the flow of interest and this maximum curve is an upper bound on delays.

As pointed out in the article, the decomposition/recomposition scheme has a cost ( p i=1 |α i | n j=1 |β j | combinations to consider). Moreover there are some examples where this method does not give tight bounds.

Take a system composed of two servers in tandem with respective service curve β 1 and β 2 , crossed by two flows: the cross-traffic flow with arrival curve α and the flow of interest where one only needs to consider an arbitrarily small amount of data. We are interested in the delay needed for that data to cross the system. This small data, that can be called infinitesimal data (or infinitesimal bit), is sometimes used in the reasoning as an existing data (it moves and endures delays, it may have priority or not, its presence in a queue is considered as a backlogged period, ...) but which has a null measure (it adds 0 to cumulative functions for arrival or service constraints). This notion is very convenient to describe critical trajectories and provides right behaviors at the end. It is especially useful for concise explanations.

However to be very rigourous one must reason with small positive amounts of data like bursts of ε > 0 data, then perform the analysis and finally let ε → 0 (otherwise with ε = 0 data directly, an application of the D max definition for delays will give 0 whatever is the network, whereas we usually give arguments showing that the delays can be large).

For commodity we will describe the examples below with the convenient infinitesimal data of null measure. To get the rigourous version, replace it by an infinitesimal data ε > 0 which is a burst of ε data at time t = 0, perform the computations and then let ε → 0. For the first numerical example, the good news is that this limit is obtained by assuming that the flow of interest has a null arrival curve as explained after Lemma 3. For the second example with parameters, with the same critical trajectories, one should compute closed-form formulas including ε and then let ε → 0 to get the results that we give. Now take for example β 1 (t) = 1.5(t -6) + , β 2 (t) = 6(t -8) + and α(t) = min(0.5t, 6 + 0.05t). Using the implementation of our solution, computations give that the worst delay is d = 17. Note that the difference between d and min(d 1 , d 2 ) can be arbitrary large. Here is another example with α = min(α 1 , α 2 ), and β 1 (t) = Rt, β 2 (t) = 2R(t -T ) + and α 2 : t → RT , we have: For α, d = 3/2T . Critical trajectory: all data α(t) is served instantaneously at server 1 including our infinitesimal data which arrives at server 2 at time t = 0, then at server 2 priority is given to the cross-traffic flow and our data is served at the end of the backlogged period which lasts 3/2T (intersection of α and β 2 ). For α 1 , d 1 = 2T . Critical trajectory: same as the previous one but the backlogged period at server 2 lasts 2T (intersection of α 1 and β 2 ).

For α 2 , d 2 = 2T . Critical trajectory: α 2 (t) bits arrive at server 1 including our infinitesimal data (that is a RT burst at time t = 0), server 1 gives priority to the cross-traffic and the ouput is served instantaneously by server 2, then at time t = T our infinitesimal data is finally served and enters server 2 where it starts a backlogged period which allows server 2 to add a delay T to our infinitesimal data. It endures an overall delay 2T .

The difference between min(d 1 , d 2 ) and d is then T /2 that grows infinitely large when grows (see Fig. 8).

Numerical results

We compare our results with the other existing methods. Up to now, two kinds of methods have been used (see [START_REF] Schmitt | Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch[END_REF][START_REF] Schmitt | Delay bounds under arbitrary multiplexing[END_REF] for detailed explanations): the total flow analysis (TFA), that consists in computing a delay upper bound for each server crossed by the flow of interest and then take the sum, and the separate flow analysis (SFA), that consists in computing a left-over service curve for every server on the path of the flow of interest, then compute the convolution of those service curves to get a left-over service curve for the whole path and finally compute an end-to-end delay bound using Theorem 1. To our knowledge, these are the only two systematic methods available for general feed-forward networks.

The linear program files used for our experiments can be found following this link: http://perso.bretagne.ens-cacha Here are the formulas we use for TFA and SFA with leaky-bucket arrival curves and rate-latency strict service curves. Consider a server (Fig. 9) offering a strict service curve β(t) = R(t -T ) + crossed by two flows 1 and 2 (it is often used with flow 1 being the flow of interest and flow 2 representing the aggregation of all the other flows crossing that server). If F in 1 is upper-constrained by α 1 (t) = σ 1 +ρ 1 t and F in 2 is upper-constrained by α 2 (t) = σ 2 +ρ 2 t, then a simple service curve for F 1 is β 1 = (βα 2 ) + .

An upper bound for the delay (used for TFA) for F 1 is

d 1 = T + σ 1 + σ 2 + ρ 2 T R -ρ 2
The service curve (used for SFA) for F 1 is:

β 1 (t) = (R -ρ 2 ) t -T - σ 2 + ρ 2 T R -ρ 2 + .
Now, the cumulative function F out 1 is upper constrained by

α ′ 1 (t) = σ 1 + ρ 1 T + σ 2 + ρ 2 T R -ρ 2 + ρ 1 t.
Of course, since we are under blind multiplexing and by symmetry, those results apply to flow 2 up to inverting indices 1 and 2 in the formulas.

To get the bounds for the whole network, one can use those formulas for every node of the network sorted by a topological order.

Tandem scenario

In order to generate the linear program files associated to a tandem network to compute worstcase delay and backlog bounds, we wrote a program, that can be downloaded from the web-page mentioned above. This program has been written in Ocaml4 . It generates a linear program from a small file describing the tandem network. The linear program can the be solved using solvers like lp solve 5 for example.

We first compare our results for a tandem scenario, where flows intersect two servers (except at the extremities) and the flow of interest crosses every server. An example is depicted in Fig. 10. Servers have the same characteristics: they have a latency of 0.1s, and a service rate of 10Mbps. Flows have a maximum burst of 1Mb and a arrival rate of 0.67Mbps. 11 shows the delay bound obtained for each of the three methods (TFA, SFA and the tight LP method). Unsurprisingly, the three methods give the same result when there is only one server. For a network with 20 servers, the LP method reduces the SFA bound by a factor 8/5 = 1.6, for an utilization rate of 20%. Fig. 12 depicts the variation between SFA and LP methods when the utilization rate of the servers varies and when the number of servers is 20. Only the arrival rate varies, according to the utilization rate. When the utilization factor grows, the gain becomes huge.

Feed-forward scenario

We illustrate our result on a small example, depicted in Fig. 13. There are four servers (with the same characteristics as in the previous example, and four flows, each having the same characteristics: a maximum burst of 1Mb, and we make the arrival rate vary from 0.5Mbps to 4.5Mbps (so the utilization rate in each server vary from 10% to 90%). We compute delay bounds for flow F 1 with four methods: (TFA), then (SFA), then (LP) by generating 11 linear programs, one for each possible order for our dates (as explained in Section 3), then the fourth method (ULP) is obtained by solving an unique linear program, where only the common constraints of the 11 programs are taken, i.e. constraints yielded by predicate (P1). The ULP method does not obtain the tight bounds, but the results are far better than TFA and SFA. Thus it is an interesting candidate as an approximation algorithm. All the results are depicted on Fig. 14.

F 2 F 3 F 1 F 4

Conclusion

We have shown that one can compute the exact worst local backlogs and end-to-end delays in the NC framework for feed-forward networks under blind multiplexing 6 . The number and the size of linear programs one has to solve can be small or extremely large depending on the network. Although we have shown that the problem is intrinsically difficult, one direction is to reduce this number of linear programs as well as their size. For example, our instances may present some redundant inequalities (e.g. between non-decrease and minimum service) or one could fix the value of t ∅ (since the set of trajectories and thus the set of LP solutions is invariant by time shifts). These are very small improvements, but one may hope that there exist more significant reductions. 6 The full implementation of our method for any feed-forward network as input is under development.

Fig. 1

 1 Fig. 1 illustrates those bounds.

Figure 1 :

 1 Figure 1: Guaranteed upper bounds on backlog and delay.

Figure 3 :

 3 Figure 3: Diamond network: two flows and four servers.

Figure 5 :

 5 Figure 5: Reading t π on a trajectory for a 1-flow 3-servers scenario.

Figure 6 :

 6 Figure 6: Transformation of an instance of X3C into a network.

  (j) i (t π ) values). Lemma 3. Let Λ be the set of LP instances constructed in Section 3.1, λ ∈ Λ and λ obtained by replacing < signs by ≤ in λ. Then opt λ = opt λ .

3

  which optimize T , it can be computed by solving an LP instance.

  4. If α(t) = 0.5t, then the worst delay is d 1 = 17.

  7 and if α(t) = 6 + 0.05t, then the worst delay is d 2 = 18.4 and d < min(d 1 .d 2 ). Three critical trajectories are shown on Fig 7 and illustrate the loss when considering only d 1 and d 2 .

1 Figure 7 :

 17 Figure 7: Decomposing arrival curves does not achieve tight bounds.Bold lines are the output processes. Continuous line: the arrival curve is α; dotted line: the arrival curve is α 1 ; dashed line: the arrival curve is α 2 .

Figure 8 :

 8 Figure 8: Arbitrarily large gaps between the decomposition/recomposition scheme and exact worst cases.

F in 1 F in 2 F out 1 F out 2 Figure 9 :

 12129 Figure 9: A server crossed by two flows.

Figure 10 :

 10 Figure 10: Tandem scenario with 4 servers.

Fig.

  Fig.11shows the delay bound obtained for each of the three methods (TFA, SFA and the tight LP method). Unsurprisingly, the three methods give the same result when there is only one server. For a network with 20 servers, the LP method reduces the SFA bound by a factor 8/5 = 1.6, for an utilization rate of 20%. Fig.12depicts the variation between SFA and LP methods when the utilization rate of the servers varies and when the number of servers is 20. Only the arrival rate varies, according to the utilization rate. When the utilization factor grows, the gain becomes huge.

Figure 11 :Figure 12 :

 1112 Figure 11: Upper bounds for the delay of the scenario of Fig. 10.

Figure 13 :

 13 Figure 13: The Square network.

Figure 14 :

 14 Figure 14: Upper bound on delays for flow F 1 in the Square network of Fig. 13.

RR n 7012

we will call bit the data unit of measure.

it is not exactly the same fluid model as[START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF] where functions are continuous rather than left-continuous INRIA

up to forcing a null value at t = 0, it belongs to F , however we do not force this value to keep an expression as a minimum of affine functions (it will be useful for the future LP translation of constraints)

http://caml.inria.fr/ocaml

http://lpsolve.sourceforge.net/5.5/ RR n 7012

10 12 14 16 18 20 number of servers TFA⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ SFA

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 utilization rate TFA ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆

Suppose that H(n -1) holds. Consider a tandem network with n servers and a trajectory {F (j) i ∈ F | i ∈ F, j ∈ {1, . . . , n -1}, j ∈ i} of that system. Let t ∈ R + and t n = start n (t). Apply H(n-1) to the n-1 first servers and to t n . Let a = F (n) 1 (t)-F (n) 1 (t n ). We modify the trajectories, up to time t n , F

in the following way: if

1 (t n ), then F (j) 1 (s) := F (j) 1 (s) + a, and remains unchanged otherwise. In other words, we add a burst of size a at time t 0 , and serve it as a burst when the data arrived at time ( F (0) 1 ) -1 (F (n) 1 (t 0 )) are served, in each server S 1 , . . . , S n-1 . It should be obvious that this is still a trajectory for the system.

We now deduce {

. . , n -1}, j ∈ i}} for the n -1 first servers satisfying the three conditions. The first condition is already satisfied, as it only concerns F (0)

1 . The second condition can also be satisfied, as from the induction hypothesis and flow constraints we have

s) if before time t 0 each server serves data as an infinite capacity server. Now, consider the n-th server from time t n . By construction, we have

1 (t n )+a, and t n = start n (t). The third condition can then be satisfied by setting

Now look at the trajectory { F (j) i }. Until time t 0 , servers act as infinite servers. Then, the departure function after time t 0 do not depend on the trajectory before time t 0 . At time t 0 one has a burst of size b = F

1 (t 0 ). So, the maximum delay for packets entering at time t 0 can be computed by our linear problem with α 1 : s → b. So, as

). Note that this service curve is optimal in the sense that it is the maximum of all universal end-to-end service curves for flow 1. Indeed, if there existed an universal end-to-end service curve β ′ for that flow and σ ∈ R + such that β -1 (σ) > β ′-1 (σ), this would invalidate the fact that the delay bound computed with our linear program is tight when the arrival curve for flow 1 is

Let us now go back to our linear problem when objective is to maximize the delay in a system where the arrival curve of our flow 1 is α 1 : t → σ. It should be clear that the only constraints where σ appears are the arrival curve constraints for flow 1, that is

≤ σ. Moreover σ does not appear in the objective constraint. So, one can express our optimization problem with matrices by Maximizing AX Subject to BX ≤ C(σ) and X ≥ 0, where only C depends on σ. From the strong duality theorem (see for instance [START_REF] Vanderbei | Linear Programming, Foundations and extensions[END_REF]), the following problem has the same solution:

Here, only the objective function depends on σ. The constraints B t Y ≤ A t and Y ≥ 0 define a convex polyhedron. For any linear objective function, the optimum value is obtained at an extremal vertex of the polyhedron. Thus, the delay can be computed in function of σ by computing min Y C t (σ)Y , where Y belongs to the extremal vertices of the polyhedron. Note that this number of vertices is finite but can be exponential in the number of constraints.

Beware that although this curve β is maximum among universal end-to-end service curves for flow 1, nothing ensures that for any arrival curve α 1 for flow 1, the horizontal distance between α 1 and β will be the exact worst end-to-end delay (except for α 1 (t) = σ where it is guaranteed by definition of β). This distance is an upper bound, but it could be loose. As a matter of fact, we conjecture that this distance is always tight, but we haven't proved this result yet.

The validity of this conjecture would be strongly related to blind multiplexing, since such universal and optimal end-to-end service curves do not necessarily exist for other policies. For instance, in FIFO networks, even for a single server with one cross-traffic flow, there is an infinity of incomparable simple service curves and their maximum is not a service curve [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF][START_REF] Lenzini | A methodology for computing end-to-end delay bounds in fifo-multiplexing tandems[END_REF].

Related work

Initiated in [START_REF] Schmitt | The disco network calculator: a toolbox for worst case analysis[END_REF], the study of tandem networks under blind multiplexing significantly improved in a recent breakthrough paper [START_REF] Schmitt | Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch[END_REF]. In this article the authors compute tight end-to-end delay bounds for some tandem networks, with detailed computations for a network with three servers and three flows and for sink-tree networks. For those particular cases, the authors manage to provide closed-form formulas (with disjunctions of cases). A method for general tandem networks is suggested in the corresponding technical report [START_REF] Schmitt | Delay bounds under arbitrary multiplexing[END_REF] but some details are not fully settled. We now discuss similarities and differences between our approaches.

Note that for the scenarios treated in [START_REF] Schmitt | Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch[END_REF], we have checked numerically on several examples that our algorithm using LP solutions gave the same results as their formulas (but we have not tried to solve by hand our LP instances to check whether we could reach the same disjunction of cases and closed-form formulas).

The main similarity concerns the choice of variables and set of constraints describing the system. We both start by writing down the system constraints over cumulative functions at starts of backlogged periods, leading to the same set of equalities and inequalities for tandem networks, up to some renaming: for instance if n = 2, t 2 , t ∅ here is t 1 , t 0 there, and

2 ≥ 0} there. It appears that those equalities and inequalities are linear (for leaky-bucket and rate-latency curves as noticed in [START_REF] Schmitt | Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch[END_REF], for piecewise affine concave/convex curves as noticed in the previous sections).

From that point, two major differences distinguish our approaches. First, while we directly try to solve this set of constraints using linear programming up to adding some constraints and considering several cases (due to the ordering of time events), the approach of [START_REF] Schmitt | Delay bounds under arbitrary multiplexing[END_REF][START_REF] Schmitt | Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch[END_REF] for leakybucket/rate-latency arrival/service curves consists in:

Performing algebraic manipulations (in particular using a lemma about the convolution of rate-latency functions) to mix the set of initial equalities and inequalities into an inequality looking like a simple end-to-end service curve constraint, that is for flow 1 in the 3-servers 3-flows scenario of [START_REF] Schmitt | Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch[END_REF]:

where the rate R is fixed, but the latency T depends on free variables s Another way to bypass NP-hardness is to look for fast approximation algorithms or exact algorithms which are fast on average.

Here are also a few features that can be added to refine the model: Add some other network elements which can not be modelled by strict service curves (like fixed delays).

Take into account maximum (resp. minimum) strict service (resp. arrival) curves as in RTC [START_REF] Thiele | Real-time calculus for scheduling hard real-time systems[END_REF] (preventing instantaneous propagation (resp. starvation) of data).

Take into account packet lengths.

Use curves with different shapes like ultimately pseudo-periodic curves [START_REF] Bouillard | An algorithmic toolbox for network calculus[END_REF].

Anyway, even without those additional features, the challenge of computing exact worst-case performances of general networks under blind multiplexing, or even feed-forward networks under other policies like FIFO, remains open.