FIFO
====

This repository contains modules for the analysis of FIFO networks. It contains both the classical modules for the
analysis of networks, such as TFA (Total Flow analysis) and SFA(Separated flow analysis), that are both easy to
implement and fast to compute, and more recent methods based on linear programming, relying on the papers [1] and [2].
More precisely, the modules are:

- :mod:`admTFA`, for computing bounds  using the TFA analysis. This implementation also relies on linear programming,
  that may not be a fast as optimized implementations, but that can apply in more general settings (in particular, [3]
  is focused on rate-latency arrival curves and has some restriction on the greedy-shapers after the servers that we do
  not need with LP). It also implements recent result [4] by propagating some shaping constraints. This method also
  considers the different regulators (per-flow and interleaved) that exist, as described in [3].

- :mod:`sfaLP`, implements the SFA method, also using a linear program implementation. For each server, we compute a
  residual service curve for each flow using the classical result in ref [5], and do a greedy optimization (for the
  backlog computation), we then compute the overall service curve for each flow, by convolving all the elementary
  service curves on its path.

- :mod:`fifo` implements the LP method, with the choice of using the unique lp from [1] (exponential size LP). of the
  simplified  LP from [2] (polynomial-size LP). Basically,the analysis of one network is done as follows:
    - decomposition of the network into trees (we obtain a forest).
    - analysis of each flow for each tree of the forest by

      a) generating a linear program
      b) solving the linear program (hence the calling of the program LP-solve)

    - reconstructing the bound for each flow of the network (for example by summing the delay of each obtained subflow)

- :mod:`treeLP` implement the above solving for trees.

References:
-----------

[1] Anne Bouillard and Giovanni Stea. Exact Worst-case Delay for FIFO-multiplexing tandems.
Sixth International Conference on Performance Evaluation Methodologies and Tools (ValueTools 2012)

[2] Anne Bouillard. Trade-off between accuracy and tractability of Network Calculus in FIFO networks.
Perform. Evaluation 153: 102250, 2022

[3] Ludovic Thomas, Jean-Yves Le Boudec, Ahlem Mifdaoui. On Cyclic Dependencies and Regulators in Time-Sensitive
Networks. RTSS 2019: 299-311

[4] Anne Bouillard.  Admission Shaping With Network Calculus. IEEE Netw. Lett. 6(2): 115-118 (2024)

[5] Jean-Yves Le Boudec and P. Thiran, Network Calculus: A Theory of Deterministic Queuing Systems for the Internet.
Lecture Notes in Computer Science, Lectures Notes Computer, 2001



.. toctree::
   :maxdepth: 4

   admTFA
   sfaLP
   fifoLP
   treeLP