Deterministic Network Calculus

12 Stability in Networks with Cyclic Dependencies

Until now, we have focused on feed-forward networks, whose underlying graphs are acyclic. In those networks, as soon as the arrival rate to each server is lower than the service rate, the network is stable and worst-case performances can be computed, using, for example, the results of the previous two chapters. The computations can be made by exploring the servers of the networks in a topological order.

When the underlying graph has cycles, it is not possible anymore to analyze the servers in a topological order, and the same techniques cannot be used directly. In fact, computing worst-case performances becomes much more complex, and even the problem of stability becomes difficult and is still open in the network calculus theory.

Very few methods and general results are known for cyclic networks, and this chapter aims to present some of them.

In section 12.1, we define the notion of stability that we call global stability to distinguish it from the local stability that is defined for each server.

In section 12.2, we describe the most classical technique to obtain sufficient conditions for the stability as the existence of a fix point of an equation. The idea is to decompose the network into acyclic networks, and the fix-point equation relates the performance of each sub-system. This method was first developed by Cruz in [CRU 91b], and then with more detail in [CHA 00, LEB 01].

Section 12.3 focuses on service policies where the ...