Anne Bouillard
email: anne.bouillard@ens.fr

Giovanni Stea
email: g.stea@iet.unipi.it

Exact Worst-case Delay in FIFO-multiplexing Feed-forward Networks *

Keywords: Network Calculus, Worst-case Delay, FIFO multiplexing

In this paper we compute the actual worst-case endto-end delay for a flow in a feed-forward network of FIFOmultiplexing service curve nodes, where flows are shaped by piecewise-affine concave arrival curves, and service curves are piecewise affine and convex. We show that the worst-case delay problem can be formulated as a mixed integer-linear programming problem, whose size grows exponentially with the number of nodes involved. Furthermore, we present approximate solution schemes to find upper and lower delay bounds on the worst-case delay. Both only require to solve just one linear programming problem, and yield bounds which are generally more accurate than those found in the previous work, which are computed under more restrictive assumptions.

I. INTRODUCTION

Several of today's networked applications require deterministic guarantees on the worst-case end-to-end delay that a packet may be experience. This is true of multimedia applications, where packets exceeding the maximum tolerable delay are discarded -with ensuing performance degradation, and all the more for real-time applications involving Machineto-Machine communications through a multi-hop network. Examples of networks used to carry either or both types of traffic range from multi-service networks, such as the Internet, to dedicated networks, such as Network-on-Chips [START_REF] Jafari | Worst-case delay analysis of variable bit-rate flows in network-on-chip with aggregate scheduling[END_REF] and AFDX avionic networks [START_REF] Bauer | Improving the worst-case delay analysis of an AFDX network using an optimized trajectory approach[END_REF], wireless sensor networks [START_REF] Koubaa | Modeling and worst-case dimensioning of cluster-tree wireless sensor networks[END_REF], [START_REF] Schmitt | Sensor network calculus: A framework for worst case analysis[END_REF], or industrial Ethernet installations [START_REF] Skeie | Timeliness of real-time IP communication in switched industrial ethernet networks[END_REF]. In several of these, due to scalability reasons, nodes (e.g., switches or routers) maintain a limited number of queues, and traffic belonging to several flows is buffered First-Come-First-Served, or FIFO. We call this paradigm flow aggregation or multiplexing. For instance, in the Internet domain, Behavior Aggregates of Differentiated Services networks (DiffServ [START_REF] Blake | An Architecture for Differentiated Services[END_REF]), or traffic trunks in Multi-Protocol Label Switching (MPLS, [START_REF] Rosen | Multiprotocol Label Switching Architecture[END_REF]), are in fact composed of many flows sharing the same queue at each node. In the above context, assessing the worst-case delay for single traffic flows is a challenging task, since the latter depends on the behavior of all the other flows that the tagged flow, i.e., the one being investigated, may find along its path.

In the recent past, Network Calculus (NC, [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], [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF]) a theory for deterministic network performance analysis, has been employed to compute upper and lower bounds on the worst-case delay (WCD) of a flow traversing a tandem of nodes employing flow aggregation. Both FIFO and blind multiplexing, i.e., one where no assumption is made regarding the order of queueing of packets from different flows, have been analyzed using NC. For feed-forward networks of blind multiplexing nodes, the exact WCD has been computed in [START_REF] Bouillard | Tight performance bounds in the worst-case analysis of feed-forward networks[END_REF], where authors show that the problem is NP-hard in general, but becomes polynomial for tandem networks. This result is, in theory, applicable to FIFO-multiplexing networks as well, FIFO multiplexing being a sub-case of blind multiplexing. However, in this case, it yields an overly pessimistic upper bound on the WCD, rather than the WCD itself. As far as FIFO multiplexing is concerned, tandem networks have been analyzed using NC, and both upper and lower bounds on the WCD have been derived using a method called Least Upper Delay Bound (LUDB) [START_REF] Lenzini | Tight end-toend per-flow delay bounds in FIFO multiplexing sink-tree networks[END_REF], [START_REF] Lenzini | A methodology for computing end-to-end delay bounds in FIFO-multiplexing tandems[END_REF], [START_REF] Bisti | Estimating the worst-case delay in FIFO tandems using network calculus[END_REF], [START_REF] Bisti | Deborah: A tool for worst-case analysis of FIFO tandems[END_REF], [START_REF] Bisti | Numerical analysis of worst-case end-to-end delay bounds in FIFO tandem networks[END_REF]. The LUDB method relies on using equivalent service curves, obtained by progressively removing the flows that intersect the path of the tagged flow. However, equivalent service curves often introduce pessimism, hence the LUDB is not guaranteed to be equal to the WCD. For some specific networks e.g., sinktree networks ( [START_REF] Lenzini | Tight end-toend per-flow delay bounds in FIFO multiplexing sink-tree networks[END_REF]), it actually is, but [START_REF] Bisti | Estimating the worst-case delay in FIFO tandems using network calculus[END_REF] shows that this is not always the case, even in simple tandems. Work [START_REF] Bisti | Numerical analysis of worst-case end-to-end delay bounds in FIFO tandem networks[END_REF] compares the LUDB and lower bounds on the WCD in several scenarios, showing that there are cases when the two diverge, and provides further arguments against the tightness of the LUDB in the general case. Furthermore, the only topologies that have been analyzed so far using this method are tree networks ( [START_REF] Lenzini | Tight end-toend per-flow delay bounds in FIFO multiplexing sink-tree networks[END_REF], [START_REF] Lenzini | A methodology for computing end-to-end delay bounds in FIFO-multiplexing tandems[END_REF]) and tandems ( [START_REF] Lenzini | A methodology for computing end-to-end delay bounds in FIFO-multiplexing tandems[END_REF], [START_REF] Bisti | Deborah: A tool for worst-case analysis of FIFO tandems[END_REF], [START_REF] Bisti | Numerical analysis of worst-case end-to-end delay bounds in FIFO tandem networks[END_REF]). No generalization to feed-forward networks has ever been presented. Therefore, computing the WCD in a general feedforward FIFO-multiplexing network remains an open problem.

In this paper, we solve the above problem using a Mathematical Programming (MP) approach. Unlike the LUDB method, we avoid using equivalent service curves. Instead, we characterize the nodes through accurate input-output relationships, derived by combining aggregate service-curve constraints and the FIFO property. This way, we are able to formulate the WCD problem as a Mixed Integer-Linear Programming (MILP) problem, which can be solved by standard solvers (e.g., CPLEX). We show that, its theoretical significance notwithstanding, MILP-based computation of the WCD is feasible only at small network sizes (i.e., up to six or seven nodes). However, the MILP formulation can be modified to obtain very good upper and lower bounds, which require solving only linear programs. MP-based upper and lower bounds can be obtained much faster, and they are nearly always surprisingly close (i.e., less than 1% apart in practical cases).

More importantly, the LP-based upper bound does not diverge from the WCD, hence it can be used in lieu of the LUDB when the latter is known to be unreliable. The MP approach presents additional points of strength: unlike the LUDB, it can be applied to any feed-forward network. Furthermore, it can be used with arbitrary piecewise-affine concave arrival curves and for arbitrary piecewise-affine convex service curves, whereas the LUDB only works with simpler single leaky-bucket arrival curves and rate-latency service curves. The first generalization allows double leaky-bucket curves to be used, which are of practical significance (see, e.g., [START_REF] Boyer | Half-modeling of shaping in FIFO net with network calculus[END_REF], [START_REF] Jafari | Worst-case delay analysis of variable bit-rate flows in network-on-chip with aggregate scheduling[END_REF]), since they model finite peak-rate constraints. Moreover, the MP approach can be used to obtain the worst-case backlog at each node. Finally, it yields exact results with fluid-flow traffic, but it can be used to compute bounds with packetized traffic as well.

We evaluate the MP approach numerically in the two dimensions of computation time and bound accuracy, comparing it against the LUDB in several scenarios. Our results show that the MP upper bound outperforms the LUDB as for accuracy (the ratio between the two being as low as 40% in some cases). Such accuracy, however, comes at the expenses of an increase in computation time. The MP upper bound does scale worse than the LUDB, although such a comparison is rendered somewhat unfair by the different structure of the software employed, i.e., a general-purpose optimizer against a highly specialized software (called DEBORAH, DElay BOund Rating AlgoritHm, [START_REF] Bisti | Deborah: A tool for worst-case analysis of FIFO tandems[END_REF]), whose performance enhancement was itself the subject of a paper [START_REF] Bisti | Numerical analysis of worst-case end-to-end delay bounds in FIFO tandem networks[END_REF].

The rest of the paper is organized as follows: Section II reports some background and notation on Network Calculus. In Section III we introduce the hypotheses and state our problem formally. We present our contribution in Section IV. Section V discusses the related work in detail. We report evaluation results in Section VI. Finally, conclusions are reported in Section VII.

II. NETWORK CALCULUS BACKGROUND

This section introduces basic Network Calculus concepts, using the same notation as in [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF]. In NC, a data flow is described by means of a wide-sense increasing and leftcontinuous cumulative function R : R + → R + , where R(t) is the number of bits seen on the flow in time interval [0, t[. In particular, R(0) = 0.

A wide-sense increasing function α is said to be an arrival curve for a flow characterized by a cumulative function A (or, equivalently, A is α-upper constrained) if:

∀s ≤ t, A(t) -A(s) ≤ α(t -s).
As an example, a common leaky-bucket shaper, with sustainable rate ρ and burst size σ, enforces the concave affine arrival curve γ σ,ρ (t) = σ + ρt.

Let A and D be the Cumulative Arrival and Cumulative Departure functions (CAF and CDF) characterizing the same data flow at the input and output of a network element (or node), respectively. If the network element is lossless and does not create any data (an assumption we stick to throughout the paper), it is A ≥ D. This said, the network element can be modeled through the service curve β if:

∀t ≥ 0, D(t) ≥ inf 0≤s≤t A(s) + β(t -s).
(

) 1
The flow is said to be guaranteed the (minimum) service curve β. The infimum on the right side of Eq. ( 1), as a function of t, is called the min-plus convolution of A and β, and is denoted by A ⊗ β. Min-plus convolution is commutative and associative. Figure 1, center, shows how convolution is computed by sliding β along A and taking the infimum for each time. A well-known property of convolution is given by the following lemma (see again Figure 1, center):

Lemma 1. [17, Chapter 1.3] If f and g are left-continuous and wide-sense increasing, then for all t ≥ 0, there exists

s ≤ t such that f ⊗ g(t) = f (s) + g(t -s).
Several network elements, such as delay elements, packet schedulers, links, and regulators, can be modeled through service curves. Many (e.g., most packet schedulers) can be modeled through rate-latency service curves, defined as:

β θ,R (t) = R(t -θ) + .
for some θ > 0 (the latency) and R > 0 (the rate). Notation (.) + denotes max(., 0) and should not be confused with f (t + ) which instead denotes the right limit of f at t in the following. For instance, a constant-rate server (e.g., a wired link) can be modeled as a rate-latency curve with a null latency. Note that rate-latency curves are convex. A fundamental result of Network Calculus is that the service curve of a tandem of network elements traversed by the same flow is obtained by convolving the service curves of each network element.

In a network element that serves bits in FIFO order, one can determine the delay of each bit and the backlog at each time instant by comparing the CAF and the CDF. More specifically, the delay of a bit arriving at s is equal to:

d(s) = inf{u ≥ 0 : A(s) ≤ D(s + u)}.
In other words, it is the horizontal distance between the CAF and the CDF measured at time s on the former. If A and D are continuous, then it is D(t) = A(s), where t = s + d(s) and d(s) is the smallest value that satisfies this equation (see Figure 1, right). The same holds for a tandem of N nodes traversed by a flow: the end-to-end delay of the bit arriving at time t is the horizontal distance between point (t, A(t)) on the CAF at node 1 and the point at the same quota of the CDF at node N . An upper bound on the delay for a flow can be computed by combining its arrival curve α and the service curve β of the (tandem of) node(s) it traverses. The delay bound is:

h(α, β) = sup t≥0 [inf{d ≥ 0 | α(t -d) ≤ β(t)}]. (2)
Intuitively, h(α, β) is the amount of time the curve α must be shifted forward in time so that it lies below β. The backlog at time s is B(s) = A(s) -D(s), i.e., the vertical distance between the CAF and the CDF at time s. In a similar way as for the delay, the backlog is upper bounded by:

v(α, β) = sup t≥0 [α(t) -β(t)]. (3)
FIFO Multiplexing: All the above modeling holds when a single flow traverses a node (or tandem thereof). Under FIFO multiplexing, traffic of flows arriving at a node are buffered First-Come-First-Served in a single queue. Thus, a bit of a tagged flow arriving at time t will depart only when all the traffic arrived before time t (and belonging to any flow traversing that node) has left.

This property (henceforth referred to as the FIFO property) is a strong hypothesis, which allows one to compute the CDFs of single flows from their CAFs, despite multiplexing. We exemplify this in Figure 2, where two flows, 1 and 2, traverse a FIFO-multiplexing node characterized by a ratelatency service curve β θ,R (this can obviously be generalized to any number and shape of CAFs and any service curve). The two piecewise-linear CAFs, A 1 and A 2 are shown at the bottom-left corner. What the node really sees as an input is the multiplexing of the two CAFs, i.e., their aggregate A = A 1 + A 2 , shown in the top graph. The node transforms the aggregate CAF A into an aggregate CDF D, which is wide-sense increasing and satisfies Eq. ( 1). The figure reports the one obtained when equality holds in Eq. ( 1), which is always continuous if the service curve rate is finite, and has a slope R. Now, take a point on D, e.g., (t, D(t)). There exists a unique s ≤ t such that A(s) ≤ D(t) ≤ A(s + ) (even if A is discontinuous), and all the traffic that has departed by t has arrived by s (recall that CAFs are left-continuous). Then, D 1 (t) and D 2 (t) -which are such that

D 1 (t) + D 2 (t) = D(t) -must also satisfy A i (s) ≤ D i (t) ≤ A i (s + ), i ∈ {1, 2}
, otherwise there would be some bit in either CAF that arrived later than s and departed by t, which would make the node non-FIFO. This can be exploited to compute D 1 (t) and D 2 (t) (bottom of Figure 2). In fact, three cases are possible: III. SYSTEM MODEL We analyze a network of FIFO multiplexing nodes, i.e., queueing points where flows contend for the output link bandwidth (e.g. router interfaces). A flow is a distinguishable stream of traffic, traversing a single path, i.e., a sequence of nodes. For instance, path p = (i 1 , . . . , i ) is the one of a flow that enters the network at node i 1 , traverses nodes i 1 , . . . , i in that order and then departs. We restrict ourselves to feed-forward networks, i.e., those whose nodes can be numbered in such a way that the path of every flow is an increasing sequence. Many interesting networks are feedforward, e.g. those having a linear, star or tree topology and those employing spanning-tree routing, up-down routing [START_REF] Schroeder | Autonet: a highspeed, self-configuring local area network using point-to-point links[END_REF], and turn-prohibition [START_REF] Starobinski | Application of network calculus to general topologies using turn-prohibition[END_REF]. Thus, we henceforth assume that nodes are labeled as explained above, and paths consist of increasing label sequences. For ease of notation we assume that no two flows traverse the same path p, hence we can identify a flow through its path. This is not restrictive, since two flows traversing the same path of FIFO nodes are subject to the same WCD, and piecewise-affine concave arrival curves are additive. We write h ∈ p if node h belongs to path p, and define the front of a path p = (i 1 , . . . , i ) as f r(p) = i 1 . We denote by the empty path. Given a path p = (i 1 , . . . , i ), we define succ p (i j ) = i j+1 , for j < and succ p (i ) = . We are interested in observing one tagged flow.

1) If A 2 is discontinuous in s (e.g., A 2 (s + ) = A 2 (s) + σ),
ρ 1 +ρ 2 R D R A D1 ρ1 A 1 A 2 D 1 D 2 D2 R A2 s
A feed-forward network can be represented by a Directed Acyclic Graph (DAG), whose vertices are the network nodes. In the latter, a directed edge between nodes i and j exists if j = succ p (i) for some path p. We denote with succ(i) the set of successors of node i. Therefore, two flows share resources if both their paths traverse the same node. Consider a tagged flow p, whose WCD we want to compute. By the very definition of feed-forward network, we need only consider the sub-graph consisting of the nodes from which the exit node of p can be reached. In fact, what happens at any other node cannot be relevant to the WCD of p. Thus, from now on we will only consider the sub-graph given by the fan-in of p, and number the nodes from 1 to N accordingly, N being the exit node of the tagged flow. With reference to Figure 3, assuming that the tagged flow's path is p = (5, 6, 7, 8), then nodes 9, 10 and 11 need not be included in our model. For a flow p = (i 1 , . . . , i ), the CDF at a node i j is the CAF at succ p (i j ), hence we need a non-ambiguous notation to identify per-flow cumulative functions: for h ∈ p, we will use F h p (t) to denote the cumulative function of flow p observed at the input of node h at time t. F p (t) will denote the CDF of the flow at its exit node. Furthermore, we will occasionally denote the aggregate CAF at node h as A h = p h F h p and the aggregate CDF as

D h = p h F succp(h) p
, where p h = {p | h ∈ p}. Nodes will always be indicated in superscripts, and flows/paths in subscripts.

We assume that node h offers a service curve β h to A h , and β h is wide-sense increasing, piecewise affine and convex. Note that both constant-rate curves (e.g. a wired link) and ratelatency curves (which model a multi-queue link arbitrated by a scheduler) fall into this category. Furthermore, we assume that the arrival process of flow p, F f r(p) p , is α p -upper constrained, where α p is wide-sense increasing, piecewise affine and concave (i.e., a multiple leaky-bucket curve).

A system is said to be stable if there exists a constant C such that the backlog of each node is upper bounded by C. Let R h = lim t→∞ β h (t)/t and ρ p = lim t→∞ α p (t)/t. We assume that the system is stable, that is, ∀h ∈ [1, N ], R h ≥ p h ρ p (see [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF] for an example). Furthermore, we assume that nodes are lossless. We will show later on that this assumption can be verified a posteriori, by computing the amount of required worst-case buffer space.

A scenario for a feed-forward network with N nodes is a family of cumulative functions F h p , p path, h ∈ p, such that: 1) ∀p, h, F h p are wide-sense increasing and left-continuous; 2) ∀p,

F h p ≥ F succp(h) p ; 3) ∀p, F f r(p) p is α p -upper constrained; 4) ∀h ∈ [1, N ], D h ≥ A h ⊗ β h ; 5)
Nodes satisfy the FIFO property. Scenarios describe the feasible trajectories of the system under the assumptions of the system model. We are interested in finding the WCD for a tagged flow p, i.e. the maximum delay that one of its bit can experience under all the scenarios.

IV. MATHEMATICAL PROGRAMMING APPROACH

In this section, we show that the WCD is the optimum of a mixed integer-linear program (MILP), and that -by relaxing and imposing constraints, respectively -upper and lower bounds on the WCD can be obtained as the optima of linear programs. Furthermore, we show that the same model can be adapted to compute the worst-case backlog at a node. We carry out the analysis assuming that traffic is fluid, and we discuss how packetization affects our findings at the end of the section. Unfortunately, our approach is notationally heavy. We thus introduce notation and concepts progressively, describing two relatively simple examples first, and then move to considering arbitrary feed-forward networks. A table of symbols is reported in Appendix A for ease of reference.

A. Single-node scenario

Let us first focus on the simple, yet meaningful example of a single node traversed by two flows. Note that, for this example only, we have to derogate slightly from our hypotheses and notation and assume that two flows traverse the same path (there being just one). While merging them into a single flow would yield exactly the same results, keeping them separate allows for writing the model in a more general way, which will facilitate understanding later on. We thus denote the two CAFs/CDFs as A 1 , A 2 and D 1 , D 2 . For each departure time t 1 of a bit of data, there exists another time t 2 when that bit arrived (henceforth referred to as the FIFO time of t 1 , F IF O(t 1 )), and a time t 3 which verifies the convolution property stated in Lemma 1 at time t 1 (henceforth referred to as the service curve time of t 1 , SC(t 1 )). As β ≥ 0, t 3 ≤ t 2 , and obviously t 2 ≤ t 1 since the system is causal. Now, the WCD is the maximum horizontal distance between a point that lies on the CDF of the tagged flow -representing one bit of the latter -and the corresponding point "on" its CAF (see, e.g., Figure 2 at times s and t). This is complicated by the fact that CAFs may not be continuous, i.e., the bit we are looking at may have arrived within a burst. However, given a point on the CDF, the point in the Cartesian plane "on" the CAF at the same quota is always defined, even when the CAF is discontinuous (see, e.g., flow 2 in Figure 2). We then set up a linear programming problem with the following variables: time variables: t 1 , t 2 , t 3 , which are the abscissas of the points we need to examine; function variables:

D i t 1 , A i t k , with i ∈ {1, 2}, k ∈ {2, 3}
, where D i t 1 = D i (t 1 ) and:

A i t k = D i t 1 if t k = F IF O(t 1 ) A i (t k ) otherwise which represent their ordinates. Note that, as shown in Fig- ure 4, variable A i t k is always equal to A i (t k ) unless function A i is discontinuous in t k .
In this last case, it is equal to the number of the bit inside the burst at t k having the same quota as the bit of the CDF that we are looking at, i.e. D i (t 1 ).

Then, the WCD is computed by solving the following problem (i ∈ {1, 2}):

max t 1 -t 2 s.t. D 1 t 1 + D 2 t 1 ≥ A 1 t 3 + A 2 t 3 + β(t 1 -t 3 ) (i) D i t 1 = A i t 2 ∀i (ii) t 3 ≤ t 2 ≤ t 1 (iii) A i t 3 ≤ A i t 2 ∀i (iv) A i t 2 -A i t 3 ≤ α i (t 2 -t 3 ) ∀i (v) t k ∈ R + , A i t k ∈ R + , D i t k ∈ R + ∀i, k (vi)
where (i) is the service curve constraint, (ii) is the FIFO property, (iii) is the time ordering, (iv) is the monotonicity, and (v) is the arrival curve constraint. We use a notation for function variables which mirrors the functional one, so as to allow readers to easily switch between MP constraints (i-v) and the NC properties expressed in the scenario constraints (1-5) reported at the end of Section III.

All the above constraints are linear, or can be easily linearized: if α 1 and α 2 are piecewise affine and concave, then they can be written as

α i (t) = [min m Y i,m ](t),
where Y i,m are affine curves. Hence, arrival curve constraints can be linearized as follows:

A i t 2 -A i t 3 ≤ α i (t 2 -t 3 ) ⇔ ∀m, A i t 2 -A i t 3 ≤ Y i,m (t 2 -t 3 ).
Thus, each arrival curve constraint yields as many linear constraints as its linear pieces. The same holds, mutatis mutandis, for service curve constraints, given that β is piecewise affine and convex. The objective function is linear as well, hence computing the WCD entails solving an LP problem.

t 3 t 2 t 1 At3 A1t2 D1t1 Dt1 At2 delay At2 At3 t3 = t2 A1t2 delay t1 Dt1 D1t1
(t) = A 1 (t) + A 2 (t)
, the green the CDF D(t). The red curve represents A 1 (t). Relevant points of the plane either on the curves or included in a discontinuity are also highlighted.

B. Two-node scenario

Consider now a tandem of two nodes traversed by three flows as in Figure 5. Let the tagged flow be the one traversing the whole tandem, i.e. p = (1, 2). At its exit node 2, both the service curve constraints and the FIFO constraints for flows (2) and (1, 2) can be written down. Therefore, given a departure time at node 2, call it t 1 , we can add its FIFO time t 2 = F IF O 2 (t 1 ) and its SC time t 3 = SC 2 (t 1 ) at node 2. We use a node superscript, i.e., F IF O h and SC h , to emphasize the node h where the FIFO and SC properties are applied. Times t 2 and t 3 are those at which we observe the input of node 2 and the output of node 1. We have an arrival curve constraint for flow [START_REF] Bauer | Applying trajectory approach with static priority queuing for improving the use of available AFDX resources[END_REF]. Instead, we have no arrival curve constraints for cross-flow (1) and for the tagged flow (1, 2), since these constraints have effect at the ingress of node 1. The inequalities concerning node 2 are hence similar to those of the single-node case, i.e.:

             F (2) t 1 + F (1,2) t 1 ≥ F 2 (2) t 3 + F 2 (1,2) t 3 + β 2 (t 1 -t 3 ) F (p) t 1 = F 2 (p) t 2 , p ∈ {(2), (1, 2)} t 3 ≤ t 2 ≤ t 1 F 2 (p) t 3 ≤ F 2 (p) t 2 , p ∈ {(2), (1, 2)} F 2 (2) t 2 -F 2 (2) t 3 ≤ α (2) (t 2 -t 3 )
Now, in order to compute the end-to-end delay of the bit that departs node 2 at t 1 , we need the FIFO time of t 2 , i.e. the time at which the same bit enters node 1. In order to compute it, we iterate the same procedure at node 1, now for each of the two times t 2 and t 3 at which we observe its output: let t 4 = F IF O 1 (t 2 ) and t 5 = SC 1 (t 2 ), and similarly let t 6 = F IF O 1 (t 3 ) and t 7 = SC 1 (t 3 ). The bit that exits node 1 at time t 2 entered that node at time t 4 . Hence, the WCD is the maximum difference t 1 -t 4 , which is in fact the objective function to be maximized. To complete the example, we must add the set of constraints related to node 1, i.e. service curve, FIFO, time ordering, monotonicity and arrival constraints.

(1, 2) (1) (2) 2 1 t 2 , t 3 t 1 t 4 , t 5 , t 6 , t 7
The service constraints are:

F 2 (1,2) t i +F 2 (1) t i ≥ F 1 (1,2) t j + F 1 (1) t j + β 1 (t i -t j ), with (t i , t j ) ∈ {(t 2 , t 5 ), (t 3 , t 7 )}.
The FIFO constraints are:

F 2 p t i = F 1 p t j , with p ∈ {(1), (1, 2)} and (t i , t j ) ∈ {(t 2 , t 4 ), (t 3 , t 6 )}.
The time ordering constraints are:

       t 2 ≥ t 4 ≥ t 5 t 3 ≥ t 6 ≥ t 7 t 4 ≥ t 6 t 5 ≥ t 7
Again, the first two follow from causality and from β ≥ 0, same as for node 2. The third one instead arises from the fact that cumulative functions are non decreasing, hence

t 2 ≥ t 3 implies that t 4 = F IF O 1 (t 2 ) ≥ t 6 = F IF O 1 (t 3
). The fourth one derives from the above and from the fact that β is convex, hence t 2 ≥ t 3 implies that t 5 = SC 1 (t 2 ) ≥ t 7 = SC 1 (t 3 ). We leave to the alert reader the straightforward task of adding the monotonicity constraints that are implied by the above time ordering. Unfortunately, although the set of output times at node 1, i.e., t 2 , t 3 , is totally ordered, the set of input times t 4 , . . . , t 7 is only partially ordered. In fact, the above inequalities are not enough to discriminate whether t 5 ≥ t 6 or vice-versa. This creates a problem, because we need to ensure that, whichever the order, monotonicity is preserved: we cannot have both t 5 > t 6 and F 1 p (t 5 ) < F 1 p (t 6 ). In principle, monotonicity may be guaranteed by including nonlinear constraints, e.g.:

(t 5 -t 6 ) • (F 1 p t 5 -F 1 p t 6 ) ≥ 0, p ∈ {(1)
, (1, 2)}. However, these constraints are non-linear and (worse yet) nonconvex, hence including them would make the problem very hard to solve in practice. We can instead preserve monotonicity by using indicator constraints, i.e. constraints activated by binary variables. We define a binary variable b, a large positive constant M , and we replace the above constraints with the following set:

       t 5 + (1 -b) • M ≥ t 6 t 5 ≤ b • M + t 6 F 1 p t 5 + (1 -b) • M ≥ F 1 p t 6 F 1 p t 5 ≤ b • M + F 1 p t 6
This way, for a large enough M , odd constraints are active if b = 1, otherwise they are inactive. The reverse holds for even constraints. This allows us to preserve linearity, hence to take advantage of off-the-shelf MILP solvers (e.g., CPLEX), which are generally faster. Note that CPLEX computes a suitable value for M by itself, which is clearly a plus. From now on, we will use the shorthand x ≥ b y to denote the following pair of constraints:

x

+ (1 -b) • M ≥ y x ≤ b • M + y
where b is a binary variable, M is a large constant and x, y, are arbitrary variables. For ease of notation, we will also use x ≥ ∅ y to mean x ≥ y.

Coming to arrival constraints at node 1, those related to pairs of ordered times are the following: [START_REF] Bisti | Deborah: A tool for worst-case analysis of FIFO tandems[END_REF][START_REF] Blake | An Architecture for Differentiated Services[END_REF], (4, 7), (5, 7), (6, 7)}, p ∈ {(1), (1, 2)}.

F 1 p t k -F 1 p t ≤ α p (t k -t ), (k, ) ∈ {(4, 5),
Furthermore, we must add arrival constraints for unordered times t 5 , t 6 . In fact, we cannot simply write F 1 p t 5 -F 1 p t 6 ≤ α p (t 5 -t 6 ), since the arrival curve is only defined for non negative arguments (see the definition in Section II). If t 5 ≤ t 6 , then F 1 p t 5 ≤ F 1 p t 6 by monotonicity, hence the correct arrival curve constraint should be F 1 p t 6 -F 1 p t 5 ≤ α p (t 6 -t 5 ). Thus, we proceed as follows: assuming α p (t) = σ p + ρ p • t (if α p is piecewise affine and concave, we can simply iterate the reasoning over all its linear pieces, themselves affine functions as above), it is trivial to show that the two following constraints:

F 1 p t 5 -F 1 p t 6 ≤ α p (t 5 -t 6 ) if t 5 ≥ t 6 F 1 p t 6 -F 1 p t 5 ≤ α p (t 6 -t 5 ) if t 5 ≤ t 6 are equivalent to: F 1 p t 5 -F 1 p t 6 ≤ α p (t 5 -t 6 ) + (1 -b) • M F 1 p t 6 -F 1 p t 5 ≤ α p (t 6 -t 5 ) + b • M
The last two constraints are linear. When b = 1 the first one is active and the second is inactive, and vice-versa for b = 0. Using a similar notation as for the previous case, we will write

F 1 p t 5 -F 1 p t 6 ≤ b α p (t 5 -t 6
) as a shorthand for the above two linear inequalities (or 2n linear inequalities, if α p is the min of n affine functions). The complete formulation of the above two-node problem is reported in Appendix B for ease of reference.

Putting numbers into the above problem, if we consider

α (1,2) (t) = α (1) (t) = 1 + t/3, α (2) (t) = min(t, 11 + t/3), β 1 (t) = β 2 (t) = (t -1) + ,
we obtain that the maximum of t 1 -t 4 is equal to 10.167, obtained for b = 1, i.e. t 5 ≥ t 6 . The maximum is indeed the WCD, since the constraints describe all the possible scenarios (the formal proof will be given later on). Besides, we observe that, if we do not take into account flow (2)'s peak-rate constraint, assuming instead α (2) (t) = 1+ t/3, we obtain a WCD of 15.33, which confirms that allowing for more general, piecewise-affine concave arrival curves is indeed useful.

C. General feed-forward network

Summarizing from the previous examples, computing the WCD entails writing a linear programming problem, whose variables are the times at which the cumulative functions must be observed, and the cumulative function values at these times. For networks consisting of two or more nodes, times are not totally ordered, hence binary variables must be added to preserve monotonicity and correctness of the arrival constraints. It is evident that, if we observe the output of node j at k times, then we need 2k times at the input of the same node, since each output time t spawns two input times t = F IF O j (t) and t = SC j (t). Therefore, the number of variables and constraints of the problem is exponential in the number of nodes. For instance, the number of times for a tandem network of N nodes is equal to 2 N +1 -1 (see [START_REF] Bouillard | Exact worst-case delay for FIFO-multiplexing tandems[END_REF]).

At a high level, the algorithm for writing down the MILP whose optimum solution is the WCD of the tagged flow can be explained as follows. Starting from node (the exit node of the tagged flow N , we visit the nodes in inverse label order, until we get to node 1. At each node j, we do the following:

• first, we collect all the output times. These are the input times at all the successors of j (if j < N ), or set {t 1 } at node N . Call T j out the set of output times at node j; • then, we construct the set of input times for node j, call it T j in , from the FIFO and SC times of each time in T j out ; • we then order the times in T j out . The latter, in fact, may not be totally ordered if j has more than one successor. If this is the case, binary variables are required;

• we then derive a total order for times in T j in , starting by inferring inequalities from the ones in T j out , and adding binary variables when needed;

• we finally write down all the constraints related to node j (i.e., FIFO, service curve, time ordering, monotonicity, arrival constraints). The fact that we proceed in inverse label order ensures us that set T j out is always well-defined, since we already possess the sets T k in of all nodes k that are reachable from j. Finally, in order to write down the objective function, we start from time t 1 at the output of node N and trace back the FIFO times by following backwards the path of the tagged flow until its ingress node. As an example, consider the three-node network of Figure 6. The figure reports the sets T j out and T j in for all the nodes, which are computed from right to left. Assume that, at node 1, input times are added by following the order of the output times, so that t 8 = F IF O 1 (t 2 ), t 9 = SC 1 (t 2 ), t 10 = F IF O 1 (t 3 ), and so on until t 19 = SC 1 (t 7 ). Then, if we assume that the tagged flow is (1, 3), the objective function will be t 1 -

t 8 = t 1 -F IF O 1 (F IF O 3 (t 1 )
). If, instead, we want to compute the WCD for flow (1, 2, 3), we will need to maximize t 1 -

t 12 = t 1 -F IF O 1 (F IF O 2 (F IF O 3 (t 1 ))). 1 2 3 T 2 in = {t 4 = F IF O 2 (t 2 ), . . . , t 7 = SC 2 (t 3 )} T 2 out = T 3 in = {t 2 , t 3 } T 1 in = {t 8 , . . . , t 19 } T 3 out = {t 1 } T 3 in = {t 2 = F IF O 3 (t 1 ), t 3 = SC 3 (t 1 )} T 1 out = T 2 in ∪ T 3 in = {t 2 , . . . , t 7 }
Fig. 6. Three-node network.

We now describe the constraints formally. a) Times and their ordering constraints: We define the time variables recursively (from N to 1) as:

• T N out = {t 1 }; • ∀j ∈ {1, . . . , N }, T j in = F IF O j (T j out ) ∪ SC j (T j out ); • ∀j ∈ {1, . . . , N -1}, T j out = ∪ k∈succ(j) T k in ,
where for a set S, F IF O j (S) = {F IF O j (t) | t ∈ S}, (the same holds for SC j (S)), and F IF O j (t) (resp. SC j (t)) entails creating a new variable. Note that sets T j in are disjoint. We now need to derive a set of time inequalities to ensure the monotonicity of functions and the arrival constraints. We do not need to order every pair of times, rather, only those that appear in the same constraint. For example, for the tandem of subsection IV-B, the order of t 2 and t 7 is irrelevant. Thus, we need a total order on T j in and T j out for all j. Ordering constraints for T j in are of three types: • known: those included in K, defined as the transitive closure of the following set:

{t ≥ F IF O j (t) ≥ SC j (t) | 1 ≤ j ≤ N, t ∈ T j out } ∪ {F IF O j (t) ≥ F IF O j (t ) and SC j (t) ≥ SC j (t ) | 1 ≤ j ≤ N, t, t ∈ T j out , t ≥ t }
• inherited: those concerning pairs of times t x , t y ∈ T j in , whose order can be inferred from the order of two times (of its successors) t, t , such that t ≥ b t . The "old" binary variable b will thus be inherited to order these times as well, i.e. t x ≥ b t y ;

• new: those concerning the pair of times in T j in whose order is neither known nor inherited from successors. For these, a "new" binary variable must be defined.

For instance, for the network of Figure 6, we have that t 5 ≥ b t 6 , which is a new constraint at the input of node 2. Furthermore, at the input of node 1, we have t 14 = F IF O 1 (t 5 ), t 15 = SC 1 (t 5 ), t 16 = F IF O 1 (t 6 ), hence t 14 ≥ b t 16 is an inherited constraint, whereas t 15 and t 16 must instead be ordered through a new binary variable. Now, the ordering of T j in depends on the ordering of T j out , and that of T j out will depend on T k in , where k is a successor of j. Hence, in order to sort the times, we need to proceed recursively backwards. Let us denote by I j in (resp. I j out ) the set of inequalities required to totally order T j in (resp. T j out ). I j in is built by adding known constraints first, then those inherited from I j out , and finally adding new binary variables when required. I j out , instead, is built by assembling sets I k in for all nodes k = succ(j), and then ordering unordered times (i.e., belonging to different successors) by adding new variables. The starting point is I N out = ∅, from which every other set can be computed. The pseudocode for computing sets I j in and I j out is shown in Appendix C. Let C T denote the set of time constraints, i.e.:

C T = 1≤j≤N (I j in ∪ I j out ).
b) Function variables and their constraints: Now that all the time constraints are set, we can write down all the function constraints, which depend on the latter. For each node j, we have the following constraints:

FIFO constraints: ∀p j, ∀t ∈ T j out , and t = F IF O j (t), F j p t = F succp(j) p t.

SC constraints: ∀t ∈ T j out , and t = SC j (t),

p j F succp(j) p t = p j F j p t + β j (t -t ).
Monotonicity constraints: ∀p j, ∀t ≥ b t ∈ I j in , F j p t ≥ b F j p t ,

and ∀t ≥ b t ∈ I j out , F succp(j) p t ≥ b F succp(j) p t .
Arrival constraints: ∀p j, such that j

= f r(p), ∀t ≥ b t ∈ I j in , F j p t -F j p t ≤ b α p (t -t ).
Call C F the set of all the function variables constraints. c) Objective: If the objective is to compute the maximum delay of flow (j 1 , . . . , j k ) with j k = N , then set

t 0 = F IF O j1 (F IF O j2 (• • • (F IF O j k (t 1 )))). Our MILP is then: ( * ) Maximize (t 1 -t 0 ) subject to constraints C T ∪ C F .
We now prove that the optimum of ( * ) is the WCD.

Theorem 1. The optimum of ( * ) is the WCD for the flow of interest.

We give the proof in two separate lemmas. Lemma 2 states that, given a scenario with a delay d, ( * ) has a solution with the same delay. Lemma 3 shows that, given a solution of ( * ), there is a scenario having at least the same delay.

Lemma 2. Let F be a scenario of the network with delay d.

There exists a feasible solution in ( * ) such that t 1 -t 0 = d.

Proof: Let F = (F j p ) be a scenario and t 1 be the time of departure of the bit of interest (the one that experiences delay d). Recall that A j = p j F j p , D j = p j F succp(j) p , and that cumulative functions are left-continuous. Then, by Lemma 1 we can find a time t 3 such that D N (t 1 ) ≥ A N (t 3 ) + β N (t 1 -t 3 ) and a time t 2 such that ∀p N ,

F N p (t 2 ) ≤ F p (t 1 ) ≤ F N p (t + 2 )
. In ( * ), we set time variables t, again to account for discontinuities. After the above variables have been assigned, we enforce a total order on the times related to node j: if t < t , then we add constraint t ≤ t to ( * ). If t = t and there exists p such that F j p (t) < F j p (t ), then we also set t ≤ t . Since we started from a feasible scenario, one cannot have F j p (t) < F j p (t ) and F j p (t) > F j p (t ) for two different flows p and p . Binary variables in ( * ) are assigned using this total order. Once this is done, since we started from a feasible scenario, cumulative functions are non-decreasing and the arrival processes F f r(p) p are α p -upper constrained. The corresponding constraints in (*) are thus satisfied with the above-mentioned assignment of function variables, times and binary variables.

t 2 = F IF O N (t 1 ), t 3 = SC N (t
To conclude the proof, we just need to observe that t 1 belongs to the CDF of the last node by definition, and that

t 0 = F IF O j1 (F IF O j2 (• • • (F IF O j k (t 1 )))). Then, d = t 1 -t 0 is a solution of ( * ).
Lemma 3. For any solution of ( * ) such that t 1 -t 0 = d, there exists a scenario of the system where the bit that leaves at t 1 has a delay at least equal to d.

Proof: Consider a solution of ( * ). We will construct a scenario F = (F j p ) that verifies constraints 1-5 listed at the end of Section III. Fix a path p, a node j and consider pairs of variables t k ,

F j p t k . Let E t k = {t h | t h = t k }.
We set F j (p) (t k ) = min t h ∈Et k F j p t h for each j ∈ p hence these functions are defined at times t k in ( * ), and constraints therein ensure that they are non-decreasing, if observed at these times only. For the starting node of a path j = f r(p) we extrapolate from the above values F j p as the largest α p -upper constrained function. Such function is (see [START_REF] Bouillard | Worst-case delay bounds with fixed priorities using network calculus[END_REF], Lemma 2):

F j p (t) = min(min{F j p (t k ) + α p (t -t k ) | t ≤ t k }, min{F j p (t k ) | t ≥ t k }
). This function is continuous except at some times where the variable F f r(p) t k exists. In that case, due to arrival and monotonicity constraints,

F f r(p) p (t + k ) ≥ max t h ∈Et k F f r(p) p t h .
If j is a generic node in p (but different from N ), we extrapolate:

F succp(j) p (t) = min[F j p (t), min t k ≥t F succp(j) p (t k )],
so that outside the times t k defined in ( * ), F succp(j) p is made of bursts only or it is equal to its predecessor's CDF. Finally, if j = N , F p are defined so that the FIFO order is preserved and F p (t) = F N p (t) for t ≤ t 3 and D N (t) = max(A N (t 3 ), A N ⊗ β N (t)) for t ≥ t 3 . Due to the latter equality (service curve constraint), we may have to replace t 1 by t 1 > t 1 , to maintain F p (t 1 ) = F N p t 2 . It is always possible for a single server to set the CDFs so that the FIFO order is preserved. The above extrapolation yields wide-sense increasing, left-continuous functions.

For each pair of times defined in ( * ), the FIFO order is preserved and D h ≥ A h ⊗ β h , since the constraints ensure it. Now, we move to considering times which are not part of problem ( * ): for t h < t ≤ t k , where t h and t k are consecutive times defined at server j in ( * ), first:

F succp(j) p (t) = min(F j p (t), F succp(j) p (t k )) = min(F j p (t), F j p F IF O j (t k ))
. Now, either of two cases are given:

1) t < F IF O j (t k ) and F succp(j) p (t) = F j p (t) 2) t ≥ F IF O j (t k ) and F succp(j) p (t) = F j p F IF O j (t k ). As F IF O j (t k )
does not depend on p, given a time t, the same case will hold for each path p traversing j. In both cases, the FIFO order is preserved. This property also implies that

D h (t) = p h F succp(h) p (t) = A h (t) if t < F IF O j (t k ) or D h (t) = p h F j p F IF O j (t k ) = p h F succp(j) p (t k ) = D h (t k ) if t ≥ F IF O j (t k ). Then: D h (t) = min(A h (t), D h (t k )) ≥ min(A h (t), A h ⊗ β h (t k )) ≥ A h ⊗ β h (t),
hence the service constraints are satisfied. This also holds for node N by construction. We have then built a scenario that verifies properties 1-5 in Section III. The arrival time of the bit of data leaving at time t 1 is t 0 , so the delay of this bit is t 1 -t 0 ≥ t 1 -t 0 = d, hence it is at least equal to the one of the solution of ( * ).

D. Upper and lower bounds on the WCD

Computing the WCD requires solving a MILP, whose number of variables and constraints grows exponentially with the number of nodes. However, it is easy to find good bounds on the WCD at a reasonable computation cost, i.e., solving just one linear program. An upper bound can be found by giving up monotonicity (which, we recall, is what puts binary variables into the picture). We only keep the partial ordering of time and function variables, the service constraints, and those arrival constraints that follow from pairs of ordered times (e.g., the first set in the two-node example in the Appendix), and solve one LP with these constraints. Since this problem is a relaxation of the one for the WCD, its optimum is clearly an upper bound on the WCD, call it V LP . This may indeed verify all monotonicity constraints (which can be easily checked a posteriori), in which case it is the WCD.

Similarly, if we enforce manually a total order on the times (and on the corresponding function values), we obtain a feasible scenario, i.e. one where all cumulative functions satisfy all the constraints, and we can dispense with the binary variables. This way, we instead obtain a lower bound on the WCD. An efficient way to obtain a lower bound is to reduce the number of times, by imposing additional constraints on the latter. We do this by forcing the SC times related to all the times of a node to be equal. In other words, if T j out is the set of times at the output of node j, then we add the constraints:

∀t x , t y ∈ T j out , SC j (t x ) = SC j (t y ). (4)
This way, instead of doubling, the number of times only increases by one at each node. The alert reader will observe that, starting from a totally ordered T j out , Eq. ( 4) yields a totally ordered T j in : this is because FIFO times inherit a total order from the output times, and the earliest FIFO time is larger than the corresponding SC time by definition. Therefore, Eq. ( 4) is sufficient to produce the required time order in every network whose DAG is a tree (therein including tandem networks). For general DAGs, where a node j may have two or more successors, we still need to enforce a total order on T j out . The rule that we adopt is to sort the times based on the node label: if

T j out = T k in ∪ T l in , with k > l, then we set min{t|t ∈ T k in } ≥ max{t|t ∈ T l in }.
We call v LP the lower bound thus obtained.

Note that the complexity of computing the two bounds is different: the upper bound requires solving one LP, whose size (in terms of variables and constraints) is always exponential with the number of nodes, hence it is still an exponential problem. The number of times for the lower bound, instead, varies with the topology. For instance, when the DAG is a tree, it is quadratic, hence polynomial with the number of nodes. Since LPs can be solved in polynomial time, computing the lower bound is itself a polynomial problem in that case. In any case, the number of times of the lower-bound problem is always considerably smaller than the one of the upper-bound problem for the same topology. In the next section we will show how accurate the two bounds are, and how costly it is to compute them.

E. Worst-case backlog at nodes

The same model used so far lends itself to computing the worst-case backlog (WCB) at a node (or bounds on the latter). This is especially useful to dimension the buffers at each nodes so that no overflow occurs. Without loss of generality, we can assume that we compute the WCB at node N (otherwise we just need to remove some nodes from the DAG).

Let t 1 be the time at which the WCB occurs. Then, we have to modify our linear program as follows:

• ∀j ∈ {1, . . . , N }, add t 1 to every set T j out and T j in ; • ∀j, ∀t ∈ T j in add t 1 ≥ t to T j in ;

• ∀j, ∀p j, ∀t ∈ T j in , write the monotonicity and the arrival constraints related to t 1 : F j p t 1 ≥ F j p t and if j = f r(p), then F j p t 1 -F j p t ≤ α p (t 1 -t). The WCB at node N is then obtained by maximizing

p N F f r(p) p t 1 - p N F p t 1 .
Indeed, as we have no constraints on the maximum service rate, the latter can become infinite at time t 1 , and all the data that arrived in the network and exit the network at node N can be served instantaneously at every node except N .

To illustrate why we need to consider infinite service, consider the following simple case: a two-node tandem traversed by one flow. Figure 7 shows the three cumulative functions F j , j ∈ {1, 2, } and the backlog at node 2. On the left, the service is exact, meaning that F 2 = F 1 ⊗ β 1 and F = F 2 ⊗ β 2 . On the right, the service rate at node 1 becomes infinite at time t 1 . It is obvious that the maximum backlog at node 2 is larger in this second case.

t1 F ( ) F (2)
F (1) t

F (1) F (2)

F. Packetization

All the results shown so far hold for fluid-flow traffic. When traffic is packetized, CAFs and CDFs are staircase functions, as in Figure 8, whose steps occur whenever the last bit of a packet arrives or departs. Network calculus accounts for packetization as follows [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF]: if a node offering β as a service curve is traversed by packetized traffic whose maximum packet length is , then a lower bound on the packetized CDF will be obtained by using β = (β -) + in [START_REF] Bauer | Improving the worst-case delay analysis of an AFDX network using an optimized trajectory approach[END_REF]. In other words, β is a service curve for the packetized traffic, and it is β < β. As the figure shows, the only points where the packetized CDF attains its lower bound are the departure times of maximumsized packets. Let p denote the maximum packet size for flow p. At node j, we then have βj = (β j -max p j { p }) + . Call ( * ) the MILP obtained from ( * ) when βj is substituted to β j at each node j < N ( [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF] shows that the fluid SC β N can still be used at the last node). Direct consequences of Theorem 1 are:

• the optimum of ( * ) is a lower bound on the packet WCD. This is because a scenario of ( * ) is feasible in a packetized environment as well, if we consider that every flow can always send arbitrarily small packets. • the optimum of ( * ) is an upper bound on the packet WCD, since it uses lower bounds on the service. The above two properties imply that v LP and ṼLP are also lower and upper bounds for the packet WCD, and they are faster to compute. The same reasoning holds, mutatis mutandis, for the packet WCB.

V. RELATED WORK

The starting point for a review on delay bounds in FIFO networks is [START_REF] Charny | Delay bounds in a network with aggregate scheduling[END_REF], which shows that, for a general FIFO network (i.e., not necessarily feed-forward), upper bounds on the WCD can only be computed for small utilization factors. A critical utilization factor ν is defined, which is inversely proportional to the maximum path length. For a utilization u ≤ ν the bound is proportional to 1/(ν-u), hence approaches infinity as the utilization approaches ν. Moreover, for any utilization u > ν and finite delay d, it is possible to construct a (non feed-forward) network where some traffic exhibits a delay larger than d. However, FIFO feed-forward networks are known to be stable for any utilization up to 100%, hence better bounds can be found in the latter.

Some papers related to delay bounds in FIFO tandem (or linear) networks have appeared recently [START_REF] Lenzini | Delay bounds for FIFO aggregates: a case study[END_REF], [START_REF] Lenzini | Tight end-toend per-flow delay bounds in FIFO multiplexing sink-tree networks[END_REF], [START_REF] Lenzini | A methodology for computing end-to-end delay bounds in FIFO-multiplexing tandems[END_REF], [START_REF] Bisti | Estimating the worst-case delay in FIFO tandems using network calculus[END_REF], [START_REF] Bisti | Deborah: A tool for worst-case analysis of FIFO tandems[END_REF], [START_REF] Bisti | Numerical analysis of worst-case end-to-end delay bounds in FIFO tandem networks[END_REF], [START_REF] Boyer | Half-modeling of shaping in FIFO net with network calculus[END_REF], [START_REF] Jafari | Worst-case delay analysis of variable bit-rate flows in network-on-chip with aggregate scheduling[END_REF]. They all rely on computing and manipulating equivalent service curves for a tagged flow. At a single node, this is done through the following theorem: Theorem 2. [17, Chapter 6] Consider a node serving two flows, 1 and 2, in FIFO order. Assume that the node guarantees a minimum service curve β to the aggregate of the two flows and that flow 2 has α 2 as an arrival curve. Define the family of functions:

β 1 (t, τ ) = [β(t) -α 2 (t -τ )] + 1 t>τ ,
where 1 t>τ is equal to 1 if t > τ and zero otherwise. For any τ ≥ 0 such that β 1 (t, τ ) is wide-sense increasing, then flow 1 is guaranteed the (equivalent) service curve β 1 (t, τ ).

 1  1 2 FIFO 2   2 R  2 R      2 R      2 R           2 2 2 R                 2 R R           R 2 R   Fig. 9.
Equivalent service curve for flow 1 at a FIFO node.

The method known as Least Upper Delay Bound (LUDB) attempts to remove the cross flows by iteratively applying Theorem 2. This may or may not be possible, depending on the paths of the cross flows. Two cases are given, shown in Figure 10: in a so-called "nested" tandem, i.e., one where either any two flow paths are disjoint or one includes the other, it is possible to compute an equivalent end-to-end service curve for the tagged flow [START_REF] Lenzini | A methodology for computing end-to-end delay bounds in FIFO-multiplexing tandems[END_REF], by removing cross flows starting from the inmost ones. Otherwise, no end-to-end service curve can be computed: first, the tandem has to be cut into (possibly many) nested sub-tandems; then, bounds on the WCD of each sub-tandem must be computed and summed up to obtain a bound on the end-to-end WCD. Moreover, note that -by Theorem 2 -a flow is guaranteed an infinity of equivalent service curves, each one of which is obtained for a nonnegative value of τ . For instance, Figure 9 shows some of them when α 2 (t) = γ σ2,ρ2 and β(t) = β θ,R . This means that, if Theorem 2 is applied iteratively n times to find an equivalent end-to-end service curve for the tagged flow, this will be a function of n non-negative parameters. Therefore, if one wants to compute a delay bound for the tagged flow through Eq. ( 2), the latter will itself be a (piecewise-linear) function of n parameters. The tightest delay bound is therefore computed by taking the minimum of that function, computed on all the values of the parameters, which entails solving a piecewiselinear programming (P-LP) problem. A tool called DEBORAH has been devised to solve the problem. It transforms the P-LP problem into a number of LPs, each one of which produces an upper bound on the WCD, solves all the LPs and takes the minimum solution (i.e., the least upper bound). The LUDB method, in general, does not compute the WCD. It does in sink-tree networks ( [START_REF] Lenzini | Tight end-toend per-flow delay bounds in FIFO multiplexing sink-tree networks[END_REF]) and in some more special cases ( [START_REF] Bisti | Numerical analysis of worst-case end-to-end delay bounds in FIFO tandem networks[END_REF]), but this is not always the case, even in simple nested tandems, as proved in [START_REF] Bisti | Estimating the worst-case delay in FIFO tandems using network calculus[END_REF]. This is due to two reasons: first, equivalent service curves are pessimistic constraints, i.e., given a CAF, they also allow CDFs which cannot be obtained in practice. (an example is reported in [START_REF] Bisti | Estimating the worst-case delay in FIFO tandems using network calculus[END_REF]). Second, [START_REF] Bisti | Numerical analysis of worst-case end-to-end delay bounds in FIFO tandem networks[END_REF] argues that, in nonnested tandems, the LUDB may be grossly overrated, due to the fact that cutting the tandem entails assuming separate, non compatible worst-case scenarios at each sub-tandem, hence introducing more pessimism. On the other hand, computing the LUDB is relatively easy. While the problem is still exponential with the tandem size, some intuitions described in [START_REF] Bisti | Numerical analysis of worst-case end-to-end delay bounds in FIFO tandem networks[END_REF] allow great speedups, so that the analysis of a 10-node tandem takes less than a second. Works [START_REF] Boyer | Half-modeling of shaping in FIFO net with network calculus[END_REF], [START_REF] Jafari | Worst-case delay analysis of variable bit-rate flows in network-on-chip with aggregate scheduling[END_REF] discuss the advantages of including peak constraints (i.e., double-leaky-bucket arrival curves) in the model. While such a constraint can be freely assumed for the tagged flow, as shown in [START_REF] Boyer | Half-modeling of shaping in FIFO net with network calculus[END_REF], it cannot be assumed for cross flows, which limits its usefulness in practice. In fact, if we assume cross-flows to be shaped by double leakybuckets, if the overall peak rate of cross flows is larger than the node's rate, then Theorem 2 yields curves which are not widesense increasing, hence cannot be assumed to be equivalent service curves.

Other works in the recent past (e.g. [START_REF] Bouillard | Tight performance bounds in the worst-case analysis of feed-forward networks[END_REF], [START_REF] Schmitt | Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch[END_REF]) have focused on computing delay bounds for flows in feed-forward networks of blind multiplexing nodes, still using NC. Blind means that no assumption is made regarding the flow multiplexing criterion: for instance, both a FIFO multiplexing scheme and a strict priority multiplexing scheme in which the tagged flow is always multiplexed at the lowest priority are compatible with this hypothesis. For blind-multiplexing networks the exact WCD has been computed using mathematical programming techniques in [START_REF] Bouillard | Tight performance bounds in the worst-case analysis of feed-forward networks[END_REF]. While the problem is NP-hard for general feed-forward networks, it can be solved with a single linear program of polynomial size for tandems. Even though the bounds computed therein are tight for a blind multiplexing scenario, they are not so under the FIFO property, and the gap between the WCD and these bounds can be shown to approach infinity as the node utilization approaches 100%. Assume in fact a simple scenario, where two flows share a single node: the tagged flow sends only one bit, and the cross flow has a nonnull burst and a rate equal to the node rate. In a worst case, the node is always backlogged, hence -assuming that the tagged flow has the lowest priority -the bit of the tagged flow may remain in the buffer forever. This is not the case, obviously, if the node is FIFO. All the above literature applies Network Calculus. A comprehensive survey on the recent advancements in NC can be found in [START_REF] Fidler | A survey of deterministic and stochastic service curve models in the network calculus[END_REF].

A related stream of literature is instead based on a different method, called the Trajectorial Approach (TA, see, e.g., [START_REF] Martin | Deterministic end-to-end guarantees for real-time applications in a diffserv-mpls domain[END_REF], [START_REF] Martin | Schedulability analysis of flows scheduled with FIFO: application to the expedited forwarding class[END_REF], [START_REF] Bauer | Improving the worst-case delay analysis of an AFDX network using an optimized trajectory approach[END_REF], [START_REF] Bauer | Applying trajectory approach with static priority queuing for improving the use of available AFDX resources[END_REF]. In the latter, all the trajectories of a systems, i.e., the feasible interleavings of packets at the nodes, are considered, and a bound on the WCD is computed as a maximum among all the scenarios. A comparison between NC and TA was attempted in [START_REF] Bauer | Improving the worst-case delay analysis of an AFDX network using an optimized trajectory approach[END_REF], where an AFDX network is employed as a case study. The results are that the TA gives better bounds most of the times (although, significantly, not always). On the other hand, [START_REF] Bisti | Numerical analysis of worst-case end-to-end delay bounds in FIFO tandem networks[END_REF] argues that such a comparison is not conclusive, due to the different underlying hypotheses. In fact, the TA relies on sporadic task arrival constraints, which are less general than concave arrival curves (i.e., some trajectories allowed under the latter are not allowed under the former). Furthermore, no study that we are aware of describes the computational cost and scalability of TA, and no publicly available tools exist that allow one to test these aspects.

VI. NUMERICAL RESULTS

In this section we provide numerical results about the speed and accuracy of the WCD and the upper and lower bounds. An initial validation phase has been done using scenarios where the WCD can actually be computed using the LUDB method (see [START_REF] Lenzini | Tight end-toend per-flow delay bounds in FIFO multiplexing sink-tree networks[END_REF] and [START_REF] Bisti | Numerical analysis of worst-case end-to-end delay bounds in FIFO tandem networks[END_REF]). In all these cases, the MP optimum matches the analytical result, barring negligible numerical errors.

In order to compare our results against those of the only other comparable method we know of, i.e., DEBORAH [START_REF] Bisti | Deborah: A tool for worst-case analysis of FIFO tandems[END_REF], we analyze tandem networks, where arrival curves are single leaky-bucket ones, service curves are rate-latency. Experiments are carried out on a machine equipped with an Intel Core i7-3820 3.6GHz CPU, 16 Gb of RAM, Windows 7 64bit and CPLEX 12.5. We only measure the time spent by CPLEX, which also includes the time for reading the model and writing the solution. CPLEX is used with default options, a time limit of 2000s, and a MILP optimality gap of 1% (i.e., if a computation ends by 2000s, the WCD is within 101% of its result). Instances exceeding the time limit are discarded.

Scenarios are generated by specifying the number of nodes and a tandem type among the following: one-hop persistent, two-hop persistent (i.e., with cross-flows entering every node and spanning two hops, hence non-nested), source-tree, and random. The first three are shown in Figure 10. In random tandems, the path of the flows is selected at random (the tandem is however checked to be non-nested), and the overall number of flows F can be set as a percentage of their maximum possible number (i.e., N • (N -1)/2 for N nodes, excluding flows traversing only one hop). Furthermore, the following variables can be set: flows bursts and rates, nodes latency, rate and utilization, instantiated by sampling a uniform distribution within a configurable range [min, max]. Scenarios with randomness are run 50 times with indepedent initial conditions.

The first group of results, shown in Figure 11, refer to computation times. They are obtained varying the number of nodes, with 50 replicas per scenario, under the following common settings:

• flow bursts: σ p ∈ U [100, 1000] ∀p;

• flow rates: ρ p ∈ U [10, 100] ∀p;

• node latencies: θ j ∈ U [0, 1] ∀j;

• node utilization: U j ∈ U [0.2, 1.0] ∀j, meaning that the rate of node j is set to the sum of the rates of the flows traversing it, divided by U j . The only exceptions are the rightmost graphs of Figures 11,[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], where all the nodes have the same utilization.

1 N N -1 2 (1, . . . , N ) (1, 2, . . . , N -1) (1, 2) (1) 1 2 N -1 N (1, . . . , N ) (1)
(2) (N -1) (N )

1 2 3 N -1 N (1, . . . , N ) (1) (2, 3) (1, 2) (3, 4) (N -1, N ) (N )
Fig. 10. Two nested tandems, called one-hop (top) and source-tree (middle), and a two-hop, non-nested tandem (bottom).

The results can be commented as follows: as already anticipated, computing the WCD is a lengthy task, whose complexity is exponential in the number of nodes. It takes 4-10 minutes to obtain the WCD for a tandem of six nodes. The upper bound -being an LP -takes considerably less, and we can obtain it for tandems of up to ten nodes within similar times. The lower bound is instead very fast, being polynomial. We observe that these network sizes are normally sufficient for most purposes, the number of hops in real-time networks rarely exceeding the single figure. In all the above cases, DEBORAH computes the LUDB in less than 30ms, i.e. much faster. Finally, the spread in the computation time (measured by the ratio of the standard deviation to the average value, not shown in the figures) increases as well with the number of nodes. 0.7% of WCDs for N = 6, and 10% of upper bounds for N = 9, could not be computed within 2000s. The number of flows also impacts computation times, although less than the number of nodes. The center graph of Figure 11 reports computation times for random six-node tandems, with a varying percentage of flows. The added computation time when doubling the number of flows is noticeable, but not overly so, especially in the bounds. The rightmost graph of Figure 11 shows the impact of node utilization on the computations, for a six-node tandem where the number of flows F is set to 80% and U j is the same at each node. The figure shows that the computation times are almost unaffected by the utilization.

Two conclusive comments are in order regarding the computation time: first, these performance figures are obtained using a general-purpose solver such as CPLEX. We have in fact deliberately avoided any attempt at optimizing the solution process, this being outside the scope of the present paper. Devising optimized solution techniques to compute our results, e.g., exploiting the problem structure, is likely to buy us a considerable speedup. In fact, it already did for DEBORAH, itself heavily exploiting optimization, where a reduction of orders of magnitude in the solving time was achieved exactly by letting the structure of the problem guide the solution process. Second, we now show that the MP upper bounds are often so good that computing the WCD is not even necessary in most cases. Consider Figure 12, which reports the gap between the upper and lower bounds, defined as g = (V LP -v LP )/v LP . The gap is identically null for source-tree tandems (hence it is not reported), and very small in all the other cases. Notably, its average is even smaller than the MILP optimality gap. This means that V LP is a tighter estimate for the WCD than 101% of the MILP optimum in most cases, and it comes orders of magnitude faster. The average gap increases with the number of nodes and flows, and -interestingly -drops to zero when U approaches 100%: In Figure 12, right, a maximum 15% gap is achieved in one instance only with U = 1 (very likely due to numerical instability), whereas the gap is identically null in the other 49 ones. Although V LP is much cheaper to compute than the WCD, it is still in the hundreds of seconds or more for a 10-node tandem, whereas the LUDB is splitsecond in the same conditions. However, the accuracy of V LP cannot be matched by the LUDB. Figure 13 reports the gain o = V LP /V LU DB in the above-mentioned scenarios. The figures confirm an intuition which was already reported in [START_REF] Bisti | Numerical analysis of worst-case end-to-end delay bounds in FIFO tandem networks[END_REF], i.e., that the LUDB is accurate in nested tandems, and completely inaccurate in non-nested ones. In fact, for nested tandems, o is close to 1 (although always below 1, at least in our experiments), and identically equal to 1 in a sourcetree tandem (hence not reported in the figure). On the other hand, with non-nested tandems, o can be as small as 40%, and generally decreases with the number of nodes, the number of flows, and the utilization. Figures 14 report o as a function of the number of nodes and utilization for two particular cases of symmetric tandems, namely a one-hop tandem (left) and twohop tandem (right), with all flows having σ = 1000, ρ = 100, and all nodes having null latency. The figures confirm that the one-hop LUDB formula is asymptotically tight (see [START_REF] Bisti | Numerical analysis of worst-case end-to-end delay bounds in FIFO tandem networks[END_REF]), and that the overrating increases with the utilization. Interestingly, in the two-hop case the behavior of o is jaggy. This is because, in a non nested tandem, the LUDB is computed using cuts, and in this case the number of cuts increases at every odd node, hence the LUDB overrating increases accordingly.

VII. CONCLUSIONS AND FUTURE WORK

In this paper we have presented a method to compute Worstcase Delays (WCD) for flows in FIFO feed-forward networks, under the assumption that nodes exhibit piecewise-affine convex service curves, and flows are regulated by piecewise-affine concave arrival curves. This is the first work that achieves this objective, since previous works only managed to compute upper bounds on the WCD, under more restrictive hypotheses. Unlike the previous work, our method does not rely on equivalent service curves, which are definitely a source of pessimism: instead, it is based on Mathematical Programming. More specifically, it computes the WCD as the optimum of a mixed integer-linear problem (MILP), where binary (hence, integer) variables are required to enforce that cumulative functions be wide-sense increasing. The size of these MILPs grows exponentially with the number of nodes, which makes them impractical for large-scale problems: using a generalpurpose solver, it takes minutes, or tens thereof, to analyze networks of six nodes. However, the MILP formulation naturally lends itself to computing upper and lower bounds, by respectively relaxing the constraints of the MILP, and reducing the admissible region by imposing further constraints. We have thus proposed a way to compute upper and lower bounds on the WCD, both requiring only one linear program: the one for the upper bound still has an exponential size, whereas the LP for the lower bound may have a polynomial (quadratic) size, e.g. in tandem or tree networks. The upper bound (which is, of course, the most interesting of the two) can be computed faster and/or for larger-scale networks, and it is very close to the WCD, the gap with the lower bound being below 2% in most cases. Furthermore, it is considerably more accurate than the bound computed through DEBORAH, the only comparable publicly available tool.

The work described in this paper can be extended: we believe that our problems (both the MILP for the WCD and the LP for the upper bound) can be solved optimally faster by using ad-hoc solving strategies, relying on the structure of the problems, instead of general-purpose solvers. Furthermore, it stands to reason that it should be possible to obtain the WCD either in a closed form or by defining a worst-case scenario algorithmically, possibly under more restrictive hypotheses. Investigating the above is part of the ongoing work.

APPENDIX A TABLE OF SYMBOLS

We report the main symbols used throughout the paper in Table I. The sets of inequalities I j in and I j out are built respectively according to Algorithms 1 and 2. We denote with K |S the restriction of K to pairs of times belonging to set S. Algorithm 1 has two goals: first, to propagate the inherited constraints from I j out : if t ≥ t , then we necessarily have F IF O j (t) ≥ F IF O j (t ) and SC j (t) ≥ SC j (t ) and viceversa, hence the same variable b is used. Second, to define the new constraints: as there is no knowledge concerning the value of b, we have to introduce new variables to order F IF O j (t/t ) and SC j (t /t). This way, every pair of times in is now ordered. Note that if t ≥ t , then we know that F IF O j (t) ≥ F IF O j (t ) ≥ SC j (t ), so no new binary variable b is needed. In Algorithm 2, we start from the order computed for the input times of the successors, as we consider the union of the times appearing in those sets. Then, we have to set an order for the times appearing on different sets of successors. Whenever pairs of times are not in K, we have to introduce a new binary variable.

Fig. 1 .

 1 Fig. 1. Network calculus concepts: a rate-latency service curve (left), the convolution property: at time t, D(t) = A(s) + β (θ,R) (t -s) (center), backlog and delay computation for a bit arriving at time s (right).

Fig. 2 .

 2 Fig. 2. Input-output relationship at a FIFO node.

Fig. 3 .

 3 Fig. 3. A feed-forward network.

Fig. 4 .

 4 Fig.4. Some variables and constraints for two examples. The blue curve is the CAF A(t) = A 1 (t) + A 2 (t), the green the CDF D(t). The red curve represents A 1 (t). Relevant points of the plane either on the curves or included in a discontinuity are also highlighted.

Fig. 5 .

 5 Fig. 5. Tandem of two nodes and three flows.

Fig. 7 .

 7 Fig. 7. Maximum backlog and infinite service.

Fig. 8 .

 8 Fig. 8. Packetized flow and service curves.

Fig. 14 .

 14 Fig. 14. Gain V LP /V LU DB in one-hop (left) and two-hop (right) tandems with various utilizations.

1 K

 1 arrival curve for the flow traversing path p β j (t) service curve at node j β 1 (t, τ ) equivalent service curve for flow 1 A, D cumulative arrival/departure functions F j p cumulative function for flow p at the ingress of node j F IF O j (t), SC j (t) FIFO-and service-curve times of a time t which is observed at the output of node j ≤ b , ≥ b inequalities holding in the stated verse when binary variable b is equal to set of known inequalities T j in , T j out set of relevant times at the input/output of node j I j in , I j out set of time inequalities at the input/output of node j C T , C F set of time and function constraints

Algorithm 1 : 2 foreach (t ≥ b t ) ∈ I j out do 3 if b = ∅ then 4 add 7 let

 12347 Computation of I j in . Data: I j out , the ordering of the output times at node j; K, the known time orders. Result: I j in , the ordering of the input times at node j. begin 1I j in ← K |T j in ; F IF O j (t) ≥ b F IF O j (t )and 5 SC j (t) ≥ b SC j (t ) to I j in ; let b be a new binary variable; 6 add F IF O j (t) ≥ b SC j (t ) to I j in ; b be a new binary variable;

8 add

 8 SC j (t) ≥ b F IF O j (t ) to I j in ;

  but A 1 is not, then on some non trivial interval that includes t, D 1 is constant, while D 2 has the same slope as D, i.e., R. This is what happens at time t in Figure2. 2) If, instead, D is affine with slope R in the interval [t 1 , t 2 ], and on the corresponding interval [s 1 , s 2 ] (i.e., the interval when the bits that depart in [t 1 , t 2 ] arrive at the input), A i is affine with slope ρ i , i ∈ {1, 2}, then D i is affine on the interval [t 1 , t 2 ] with slope ρi ρ1+ρ2 R. This is what happens, e.g., towards the right edge of the time axis in Figure 2. 3) Finally, if both A 1 and A 2 are discontinuous, some additional care must be taken. In this case (not shown in the figure), D 1 (t) and D 2 (t) are not uniquely defined, hence any wide-sense increasing D 1 and D 2 satisfying the above equalities are possible CDFs.

	aggregate flow bits	I/O transformation
			time
		multiplexing	demultiplexing
	bits
	flow 2	ρ2
			time
	bits	A1
	flow1		ρ 1
			t	time

  [START_REF] Bauer | Improving the worst-case delay analysis of an AFDX network using an optimized trajectory approach[END_REF] ), and the related function variables according to the trajectories, i.e., F N p t 3 = F N p (t 3 ) and F p t 1 = F p (t 1 ), but with F N p t 2 = F p t 1 , in order to account for discontinuities as explained in Section IV-A. By backward induction, we can go on defining times and function variables: if t and F

	succp(j) p	t are defined, one can find t
	such that D j (t) ≥ A j (t ) + β j (t -t ) and t such that
	F j p (t ) ≤ F p succp(j) accordingly: t = F IF O j (t), t = SC j (t); for t we set t ≤ F j p (t + ). Time variables are set
	F j p t = F p succp(j)

  Fig.[START_REF] Cruz | A calculus for network delay, part I: Network elements in isolation[END_REF]. Gap (V LP -v LP )/v LP as a function of N for two topologies (left), and as a function of F (center) and U (right) for a random six-node tandem.

					LB, 1-hop	UB, 1-hop		WCD, 1-hop
	1000		LB, s.-tree LB, 2-hop	UB, s.-tree UB, 2-hop		WCD, s.-tree WCD, 2-hop		1000	LB			UB			WCD	1000	LB	UB	WCD
	avg. computation time (s)	0.1 1 10 100									avg. computation time (s)	0.1 1 10 100							avg. computation time (s)	0.1 1 10 100
		0.01	3	4	5		6	N	7	8	9	0.01 20%	30%	40%	50% F	60%	70%	80%	0.01 0.5	0.6	0.7	U	0.8	0.9	1
	Fig. 11. Computation times as a function of N for several topologies (left), and as a function of F (center) and U (right) for a random six-node tandem.
					avg, 1-hop					avg, 2-hop
		1%	max, 1-hop					max, 2-hop		0.8%	avg						max	3%		avg	max
	relative gap	0.4% 0.6% 0.8%								relative gap	0.4% 0.6%							relative gap	1% 2%
		0.2%									0.2%
		0%	3	4	5	6 N	7	8	9		0% 20%	30%	40%	F	50%	60%	70%	80%	0%	0.5	0.6	0.7	U	0.8	0.9	1
						avg, 1-hop				avg. 2-hop
		1.1				max, 1-hop				max, 2-hop			1		avg				max				1	avg	max
		1												0.9
	V LP /V LUDB	0.8 0.9										LUDB V LP /V	0.8							V LP /V	0.8 0.6
		0.7												0.7
		0.6	3	4	5	N	6		7	8	9		0.6 20%	30%	40%	F	50%	60%	70%	80%		0.4 0.5	0.6	0.7	0.8	0.9	1

LUDB U Fig.

13

. Gain V LP /V LU DB as a function of N for two topologies (left), and as a function of F (center) and U (right) for a random six-node tandem.

TABLE I TABLE OF SYMBOLS

 IOF APPENDIX B COMPLETE TWO-NODE EXAMPLEWe report in Table II the entire model for the two-node example of Section IV-B.

	APPENDIX C
	COMPUTATION OF SETS OF INEQUALITIES I j in , I j out

  max t 1 -t 4 s.t.Node 2 (Ord.)t 3 ≤ t 2 ≤ t 1 (SC) F (2) t 1 + F (1,2) t 1 ≥ F 2 (2) t 3 + F 2 (1,2) t 3 + β 2 (t 1 -t 3 ) (F IF O) F (p) t 1 = F 2 (p) t 2 t 2 -F 2 (2) t 3 ≤ α (2) (t 2 -t 3 ) Node 1 (Ord.) t 2 ≥ t 4 ≥ t 5 t 3 ≥ t 6 ≥ t 7 t 4 ≥ t 6 t 5 + (1 -b) • M ≥ t 6 (SC) F 2 (1,2) t i + F 2 (1) t i ≥ F 1 (1,2) t j + F 1 (1) t j + β 1 (t i -t j ) -F 1 p t ≤ αp(t k -t ) p∈{(1),(1,2)},(k, )∈{(4,5),[START_REF] Bisti | Deborah: A tool for worst-case analysis of FIFO tandems[END_REF][START_REF] Blake | An Architecture for Differentiated Services[END_REF],(4,7),[START_REF] Bisti | Numerical analysis of worst-case end-to-end delay bounds in FIFO tandem networks[END_REF][START_REF] Bouillard | Tight performance bounds in the worst-case analysis of feed-forward networks[END_REF],(6,7)}F 1 p t 5 -F 1 p t 6 ≤ αp(t 5 -t 6 ) + (1 -b) • M p∈{(2),(1,2)} F 1 p t 6 -F 1 p t 5 ≤ αp(t 6 -t 5 ) + b • M

			p∈{(2),(1,2)}
	(M ono.) F 2 (p) t 3 ≤ F 2 (p) t 2	p∈{(2),(1,2)}
	(Arr.)	F 2 (2) (i,j)∈{(2,5),(3,7)}
	(F IF O) F 2 p t i = F 1 p t j (M ono.) F 1 p t k ≥ F 1 p t F 1 p t 5 + (1 -b) • M ≥ F 1 p t 6 F 1 p t 5 ≤ b • M + F 1 p t 6 (Arr.) F 1 p t k p∈{(2),(1,2)} p∈{(1),(1,2)}, (i,j)∈{(2,4),(3,6)} p∈{(1),(1,2)},(k, )∈{(4,5),(4,6),(4,7),(5,7),(6,7)} p∈{(2),(1,2)} p∈{(2),(1,2)}
		Variables
		t k ∈ R +	1≤k≤7
		F j p t k ∈ R +	p∈{(1),(2),(1,2)}, j∈{1,2}, 1≤k≤7
		b ∈ {0, 1}

TABLE II COMPLETE

 II MILP FOR THE TWO-NODE EXAMPLE.

ACKNOWLEDGEMENTS

The authors would like to thank Prof. Antonio Frangioni of the University of Pisa for providing useful suggestions on modeling the WCD problem.

Algorithm 2: Computation of I j out . Data: I k in , ∀k ∈ succ(j), the ordering of the input times at successors of j; K, the known time orders. Result: I j out , the ordering of the output times at node j. Giovanni Stea has been a researcher at the Dipartimento di Ingegneria dell'Informazione of the University of Pisa since 2004. His current research interests include QoS and resource allocation in wireline and wireless networks, performance evaluation and traffic engineering. In these fields he coauthored more than 50 peer-reviewed papers and ten international patents. He has been involved in national and European research projects, as well as in projects with industrial partners. He has served as a member of the technical program committee for international conferences, including SIGCOMM, and as a Guest Editor for the Elsevier Performance Evaluation journal.