Deterministic Network Calculus

11 Tight Worst-case Performances

In the previous chapter, we described several algorithms to compute performances in feed-forward networks. All these algorithms share some common characteristics: first, they are based on an exploration of the servers from the sources of the flows to their destination. Second, residual service curves and output arrival curves are computed for each flow (or group of flows) and each server.

In section 10.3.1, examples are given showing that the bounds computed with these methods cannot be tight, because they are based on computing residual curves.

The aim of this chapter is to present methods to compute tight performance bounds, by using a different paradigm from that in the previous chapter: we describe the network by a linear program that (1) mimics the exploration of the network from the destination (of the flow of interest) to the sources and (2) describes the characteristics of an admissible trajectory (i.e. the possible cumulative functions given arrival and service curves). As a result, no residual service curve or additional arrival curve is computed.

This technique can be interpreted as an alternative and more precise generalization of the pay multiplexing only once phenomenon than Theorem 10.1: in section 10.3.1 an example is provided where, depending on the parameters, PMOO leads to better or worse performances. Here, in a sense, the linear problem can make the decision on what will lead to the best computation.

In this chapter, we ...