11.1.1. Example of two servers in tandem

Consider the network shown in Figure 10.2 with , leaky buckets arrival curves and rate-latency strict service curves . Before making any approximation, let us write the equations that are used to compute a worst-case delay upper bound. We assume that t is the time at which a bit of data of flow 2 suffering the worst-case delay exits the network for this flow. We call this bit of data the bit of interest. We have

Remember that the functions are non-decreasing and that .

As in the previous chapters, we can specify those equations by choosing s, u and v. A natural choice is and , so that and and the first two equations share a common date.

The equations then become, when we replace the service and arrival curves by their expression,

Note that the first two lines can be replaced by

We can also translate the monotony and the causality at dates v, s, t into the following inequalities (we only need to define at s and at t):

Let us denote by the arrival date of the bit of data of interest. We must have (the bit of interest could arrive in a burst or, more specifically here, be the last bit of data of a burst).

In order to compute a bound for the worst-case delay of flow 2, it then suffices to solve those equations. It should be noted that if we accept replacing , all of the inequalities are linear and thus can be solved by a linear program. This linear program is given in Table 11.1. Here and in the rest of the chapter, we differentiate the variables from the quantity they represent (which can be a date or the value of a function at a date) by writing the variables in bold font and forgetting the parenthesis. For example, variable t is the variable representing date t and variable A₁t is the variable representing .

Objective	Maximize t — v
Under the constraints
Dates
Monotonicity
Causality
Arrival
Service

In fact, this linear program gives the exact worst-case delay of the network, as we will prove in the following section.

11.1.2. A linear program for tandem networks

We first present the general scheme of transformation of a tandem network into a linear program before proving that its optimal solution is the exact worst-case delay of the network. Note that these results can be generalized at no cost to tree networks and adapted to the computation of the maximum backlog at a server.

Worst-case performance bounds can be computed using the linear program under the following assumptions on the arrival and service curves:

• – arrival curves are concave and piecewise linear (we can write );
• – strict service curves are convex and piecewise linear ().

We assume without loss of generality that flow 1 is the flow of interest and that this flow departs the network at server n.

11.1.3. The equivalence theorem

THEOREM 11.1.– Let be a tandem network with n servers and m flows. Then, given a flow i (respectively a server j), the linear program described above has variables and constraints and the optimum is the worst end-to-end delay for flow i (respectively the worst backlog at server j).

PROOF.– There are n + 2 time variables; the number of variable indices by flow i is linear in the length of its path, then in . Hence, the number of variables is in . The number of constraints of each type is in (this order is achieved for the arrival curve constraints).

Let D be the optimal solution of the linear program for a tandem network.

There are two steps in the rest of the proof: first, we prove that for any admissible trajectory with maximum delay d, we can set variables satisfying all the constraints (hence d ≤ D), and the problem has value d; second, we prove that from a solution to the linear problem, we can reconstruct an admissible trajectory (hence d ≥ D).

First, consider an admissible trajectory and then set t_n the departure time of the bit of data and u its arrival time. Set t_n = t_n; from the value assigned to t_n and the interpretation of the variables, we can deduce the assignment of any other variable except those involving u. Set u = u and . As the trajectory is admissible and the constraints only encode network calculus constraints, it should be clear to the reader that every linear constraint is satisfied, and the delay of the bit of data is t_n − u.

Second, consider a solution to the linear program:

• – the arrival cumulative process of flow i, , is defined by taking the largest non-decreasing function that is α_i-constrained and takes values at time (note the special case for flow 1), and we only consider dates and u;
• – the departure cumulative process is defined by having for all , for all and the linear interpolation otherwise.

We now prove that the trajectory defined by these processes is admissible. By construction, these functions are non-decreasing, we have and the arrival processes are constrained by their arrival curves. Then, it remains to show that is a strict service curve for server h. Let F be the aggregated departure process from server h. The strict service property has to be checked only on as it is the only backlogged period. In this interval, the processes are linear, so there exists H such that . But as is convex and , we have , hence the result.

□

11.2. Tandem networks under the FIFO policy

In this section, we specialize the results with FIFO servers. Unfortunately, the linear program that we will obtain will not be solvable in polynomial time: the number of variables becomes exponential in the size of the network, and some of these variables are Boolean. However, this linear program will allow us to derive upper and lower bounds for the worst-case delay.

11.2.1. Single node

Let us first focus on the simple yet meaningful example of one server offering a min-plus service curve β crossed by two flows, whose respective arrival and departure processes are denoted by A₁, A₂ and D₁, D₂. For each departure date t₁ of a bit, there exists another date t₂ when that bit arrived. From Definition 7.7, if functions A_i are continuous at t₂, then . Moreover, from Definition 5.3, (D₁ + D₂)(t₁) β ∗ (A₁ + A₂)(t₁₎. If β is convex, it is continuous, and then, there exists t₃ such that D₁(t₁) + D₂(t₁) (A₁(t₃) + A₂(t₃)) + β(t₁ − t₃). As β 0, we can set t₃ t₂. Then, the worst-case delay, with a rate-latency service curves and token-buckets arrival curves, is computed by solving the problem of Table 11.2. We use the same convention as in the previous section, and bold letters represent variables of the linear program.

Objective	Maximize t1 − t2
Under the constraints
Dates
Monotonicity
Arrival
Service
FIFO

In Table 11.2, we use very simple curves, but these can be generalized to piecewise linear concave arrival curves and piecewise linear convex service curves by writing several arrival and service constraints.

11.2.2. Tandem networks

We now consider a tandem of n servers, with flow 1 as the flow of interest, traversing every server. Let us first focus on server n. Most of the constraints of Table 11.2 can be written down, generalized to the set of all flows crossing server n. However, arrival constraints cannot be formulated for flows starting before server n. Therefore, given a departure date at server n, t₁ , we can compute two input dates, related to the FIFO and service curve constraints at server n, t₂ and t₃. Those dates also describe the output of server n − 1. Thus, we can iterate the previous reasoning at server n − 1, for each of the two dates: the bit that exits server n − 1 at time t₂ entered that server at time t₄, and t₅ is a time instant in the past that verifies the service curve constraint formulated at time t₂. Similarly, for date t₃ at server n − 1, we can identify dates t₆ and t₇, respectively. It is easy to see that we can go backwards until server 1, doubling the number of dates and constraints at each node and adding arrival constraints whenever we hit the ingress node of a flow. In this way, we eventually set up a set of constraints that relate the dates of departure (at server n) and arrival of a bit of the tagged flow. Thus, we compute its worst-case delay by solving the linear problem that maximizes the above difference under these constraints.

More formally, the variables of our problem are the following:

• – time variables: t₁,…, , where t_2k and t_2k+1 correspond to the FIFO and the service curve constraints with regard to t_k;
• – function values: for fst(i) — 1 h end(i) and k ∈ [2^n+1−h 2^n+2−h – 1].

The number of dates (hence of variables) grows exponentially with the tandem length, since it doubles at each node as we go backwards. Unfortunately, in a multi-server scenario, these dates are only partially ordered. Following the argument for the single server case and the network calculus constraints, we have:

• – (*) for k < 2ⁿ, t_2k+1 t_2k t_k;
• – (**) if 2^h k, < 2^h+1 and if t_k , then t_2k (cumulative functions are non-decreasing) and t_2k+1 (same as above, plus β^{( h)} is convex).

These relations and the transitivity only lead to a partial order of . For example, for a two-node tandem, we have t₁ t₂ t₃, and t₄ t₅, t₄ t₆, t₅ t₇ and t₆ t₇. However, t₅ and t₆ cannot be ordered. A partial order creates a problem. Given a partial order of dates, we can enforce the same partial order on the corresponding function values, but this is not sufficient to ensure the monotonicity of the cumulative arrival and departure processes. In fact, it may well happen that, in the above example, the optimal solution to the linear program is for t₅ < t₆ and , for some i, h, which violates monotonicity. In this case, the solution does not correspond to any feasible scenario and hence it is not the worst-case delay. To ensure monotonicity in a linear programming approach, we need to introduce Boolean variables.

LEMMA 11.1.– Consider the following constraints:

Then, x₁ < x₂ y₁ y₂ and x₂ < x₁ y₂ y₁.

PROOF.– The inequality x₁ < x₂ imposes that b = 0 and then that y₂ y₁. Similarly, x₂ < x₂ imposes that b = 1 and that y₁ y₂.

□

This lemma can be used on all dates t_k , on which cumulative processes are defined. Since a date corresponds to a unique node in the tandem, for a date t_k, there exists a unique h such that (t_k) is defined; hence, it is sufficient to generate total orders on for each h ∈ [1,n + 1].

Using the results of Chapter 10, the constant M is easy to find: it suffices to find an upper bound of the delay and of the cumulative arrival functions. We will not comment further on this value, but assume for every variable x the constraint 0 x M.

We are now ready to define the constraints of a mixed-integer linear program (MILP) in order to compute the worst-case delay of flow 1. In the following, the expression stands for .

For all h ∈ {1,…,n + 1}, for all k, and for all i ∈ {1,…,m} such that h ∈ p_i:

• – time constraints: ;
• – partial order constraints: and ;
• – monotonicity: ;
• – FIFO hypothesis: h > ;
• – service constraint: ;
• – arrival constraints: if h = fst(i), .

The objective of the linear program is then max t₁ − .

THEOREM 11.2.– The worst-case delay for flow 1 is the optimal solution of the mixed-integer linear program just described.

PROOF.– Set d the worst-case delay for an admissible trajectory of the network and D the optimal solution of the MILP. The proof is in two steps: we first prove that every admissible trajectory is a solution of the MIPL, so that d D. Then, we show that from any solution of the MILP, we can construct an admissible trajectory, so that D d.

First, consider an admissible trajectory and set t₁ the departure time of the bit of data of interest. Set t₁ = t₁. By definition, cumulative functions are left-continuous. Then, by Proposition 3.10, we can find a date t₃ such that and a date t₂ such that for all flow i crossing server n, . We can then set the variables as t_k = t_k and but for .

By induction, we can go on assigning dates and variables if variables t_k and are assigned, we can assign and if the same way as with k = 1. Remark that .

The reason why we cannot define t_2k directly by is that the functions are not necessarily continuous. As a result, it may be the case that several dates defined have the same value, with different values for the functions. This is not a problem for mathematical programs. Also note that this assignment of variables also defines a total order of the dates, which allows us to assign variables , so that the monotonic and arrival constraints are satisfied. As a result, the assignment of the variables respects all the constraints and they are a solution to the problem and .

On the other hand, consider a solution of the MILP. We will define a scenario that verifies all the constraints. Assign dates for all k, fix i and h and consider the variables of the form and t_k for which is defined. Let We set and . If , then from those values, we extrapolate as the largest non-decreasing function that is -constrained and takes values at time t_k. If , then we extrapolate

We can check that:

• – those functions are wide-sense increasing (because of the Boolean variables);
• – arrival functions are α-constrained (by construction);
• – the FIFO order is preserved: it is preserved for the dates defined by the linear program, and outside of those dates, the traffic is only made up of bursts;
• – the service constraints are met by construction.

We have then built a scenario that verifies all the constraints and that has the same delay as the solution of the linear program. Then, .

□

We remark that Theorem 11.2 can be generalized to compute the worst-case delay of any flow i by only modifying the objective function to maximize .

11.2.3. Bounds on the worst-case delay

As already pointed out, computing the worst-case delay in a tandem network requires an exponential number of (potentially Boolean) variables, which makes this solution intractable for large networks.

One solution to simplify the problem (which will remain exponential) is to relax some constraints, especially the Boolean ones. An upper bound can be found by giving up total ordering. We only keep the partial date and function value ordering and solve one linear program, forgetting all the Boolean variables.

Similarly, any solution of the MILP can be extrapolated into an admissible trajectory and hence is a lower bound on the worst-case delay. An algorithmically efficient way to obtain a lower bound is to reduce the number of dates, by imposing further constraints on the latter. We can do this by setting for . In this way, the number of different dates is quadratic in the number of nodes, and this induces a complete order on the dates for every h. Therefore, this lower bound can be obtained in polynomial time.