Blind

This repository contains some modules to perform the analysis of performance for the blind multiplexing. It mainly implements the linear programming approach developed in [1], and compute tight performance bounds in tree networks, given piecewise linear and concave arrival curves, and piecewise linear snd convex service curves. Using the techniques developed in[2] for FIFO networks, it can be adapted to any network topology (feed-forward and with cyclic dependencies). Basically,the analysis of one network is done as follows:

Please note that while the general problem in NP-hard, this method computes worst-case delay bounds in polynomial time for tree topologies (only one LP program of polynomial size has to be generated)

More precisely, the module bLindLP proposes the analysis in the general case, where some restrictions need to be done in the case of a cyclic network, by assuming that some flows only admit a Token-Buket arrival curve (although more complex curves can be consider using the admission shaping attribute. 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

  1. generating a linear program

  2. 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)

In contrast, the module treeOnlyBlindLP proposes a more complete analysis when only tree topologies are considered. This should allow tighter bounds, without having to resort to any kind of simplification. For this analysis, no decomposition is needed, anad only one linear program is enough (hence the LP generation and solving in linear time.

References

[1] Anne Bouillard, Laurent Jouhet and Eric Thierry. Tight Performance Bounds in the Worst-Case Analysis of Feed-Forward Networks, 29th IEEE International Conference on Computer Communications (INFOCOM 2010), p. 1316-1324

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

• BlindLP module
  • BlindLP
    • BlindLP.all_delays
    • BlindLP.backlog()
    • BlindLP.delay()
    • BlindLP.ff_analysis()
    • BlindLP.ff_equiv
    • BlindLP.lp_constraint_flow()
    • BlindLP.lp_constraints()
    • BlindLP.lp_program
    • BlindLP.update_sigma()
• treeBlindLP module
  • TreeBlindLP
    • TreeBlindLP.backlog
    • TreeBlindLP.backlog_objective()
    • TreeBlindLP.backlog_set_objective()
    • TreeBlindLP.backlog_set_of_flows()
    • TreeBlindLP.burst_constraints()
    • TreeBlindLP.delay
    • TreeBlindLP.delay_objective()
• TreeOnlyBlindLP module
  • TreeOnlyBlindLP
    • TreeOnlyBlindLP.arrival_constraints()
    • TreeOnlyBlindLP.arrival_shaping_constraints()
    • TreeOnlyBlindLP.backlog
    • TreeOnlyBlindLP.backlog_objective()
    • TreeOnlyBlindLP.causality_constraints()
    • TreeOnlyBlindLP.delay
    • TreeOnlyBlindLP.delay_objective()
    • TreeOnlyBlindLP.greedy_shaping_constraints()
    • TreeOnlyBlindLP.monotony_constraints()
    • TreeOnlyBlindLP.service_constraints()
    • TreeOnlyBlindLP.time_constraints()
    • TreeOnlyBlindLP.time_horizon
    • TreeOnlyBlindLP.time_horizon_objective()
    • TreeOnlyBlindLP.write_constraints()