August 27, 2019
Stability and performance bounds in cyclic networks using newtork calculus
- Bouillard A.
With the development of real-time systems and of new wire less communication technologies having strong requirements on latencies and reliability, there is a need to compute deterministic performance bounds in networks. This paper focuses on the performance guarantees and stability conditions of networks with cyclic dependencies in the net work calculus framework. Two kinds of techniques exist: backlog-based techniques compute backlog bounds for each server, and obtain good stability bounds to the detriment of the performance bounds; ow-based techniques compute performance bounds for each flow and obtain better performance bounds for low bandwidth usage, but poor stability conditions. In this article, we propose a unified framework that combines the two techniques and improve at the same time stability conditions and performance bounds. To do this, we first propose an algorithm that computes tight backlog bounds in trees for a set of flows at a server, and then develop a linear program based on this algorithm that computes performance bounds for cyclic networks. An implementation of these algorithms is provided in the Python package NCBounds and is used for numerical experiments showing the efficiency of the approach.View Original Article