# Network Calculus with Flow Prolongation -- A Feedforward FIFO Analysis enabled by ML

arXiv: https://arxiv.org/abs/2202.03004 · HTML: https://mlsanity.com/paper/2202.03004/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 70 references that are in the map.
- First posted on arXiv 7 Feb 2022.

## Builds on (most cited first, 16 of 16)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Recurrent Relational Networks](https://mlsanity.com/paper/1711.08028/) (2017)
- [Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking](https://mlsanity.com/paper/2005.11081/) (2020)
- [Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSP](https://mlsanity.com/paper/1809.02721/) (2018)
- [RouteNet: Leveraging Graph Neural Networks for network modeling and optimization in SDN](https://mlsanity.com/paper/1910.01508/) (2019)
- [Graph-based Deep Learning for Communication Networks: A Survey](https://mlsanity.com/paper/2106.02533/) (2021)
- [Improving Policy Gradient by Exploring Under-appreciated Rewards](https://mlsanity.com/paper/1611.09321/) (2016)
- [On the Robustness of Deep Learning-predicted Contention Models for Network Calculus](https://mlsanity.com/paper/1911.10522/) (2019)
- [Quality and Cost of Deterministic Network Calculus - Design and Evaluation of an Accurate and Fast Analysis](https://mlsanity.com/paper/1603.02094/) (2016)

## Abstract (arXiv)

The derivation of upper bounds on data flows' worst-case traversal times is an important task in many application areas. For accurate bounds, model simplifications should be avoided even in large networks. Network Calculus (NC) provides a modeling framework and different analyses for delay bounding. We investigate the analysis of feedforward networks where all queues implement First-In First-Out (FIFO) service. Correctly considering the effect of data flows onto each other under FIFO is already a challenging task. Yet, the fastest available NC FIFO analysis suffers from limitations resulting in unnecessarily loose bounds. A feature called Flow Prolongation (FP) has been shown to improve delay bound accuracy significantly. Unfortunately, FP needs to be executed within the NC FIFO analysis very often and each time it creates an exponentially growing set of alternative networks with prolongations. FP therefore does not scale and has been out of reach for the exhaustive analysis of large networks. We introduce DeepFP, an approach to make FP scale by predicting prolongations using machine learning. In our evaluation, we show that DeepFP can improve results in FIFO networks considerably. Compared to the standard NC FIFO analysis, DeepFP reduces delay bounds by 12.1% on average at negligible additional computational cost.