Package org.networkcalculus.dnc.feedforward

Class UniqueLinearProgram

  • public class UniqueLinearProgram
extends java.lang.Object
    This code is a very direct, step-by-step implementation the the unique linear program (ULP), an optimization formulation derived from the network calculus server graph, first presented in Tight Performance Bounds in the Worst-case Analysis of Feed-forward Networks. Anne Bouillard, Laurent Jouhet, and Eric Thierry, In Proceedings of the IEEE Conference on Computer Communications (INFOCOM), 2010. and refined in (can be enabled by the flag flow_constr_hdr) Algorithms and Efficiency of Network Calculus. Anne Bouillard. Habilitation thesis, École Normale Supérieure, 2014. This code will create an internal representation of the optimization formulation. It can then be written to the file system, either in the LpSolve format or the CPLEX format. Performance of both optimization tools can be found in Quality and Cost of Deterministic Network Calculus – Design and Evaluation of an Accurate and Fast Analysis. Steffen Bondorf, Paul Nikolaus, and Jens B. Schmitt, In Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), 2017. Moreover, the following publication provides insights into the reproducibility of CPLEX results can be found in: The Deterministic Network Calculus Analysis: Reliability Insights and Performance Improvements. Alexander Scheffler, Markus Fögen, Steffen Bondorf, In Proceedings of the IEEE International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD), 2018. (TODO investigate effect of CPLEX parameter settings for integrality tolerance, optimality tolerance, etc.)

    • Field Detail

      • debug

        boolean debug

      • print_debug

        boolean print_debug

      • lp_file_output_path

        static java.lang.String lp_file_output_path

      • map__path__id

        java.util.HashMap<Path,​java.lang.Integer> map__path__id

      • map__j__jpi

        java.util.HashMap<Server,​java.util.HashSet<Path>> map__j__jpi

      • map__j__pair_jpi_pi

        java.util.HashMap<Server,​java.util.HashSet<org.apache.commons.math3.util.Pair<Path,​Path>>> map__j__pair_jpi_pi

      • pi_flow

        java.util.HashMap<Flow,​java.util.HashSet<Path>> pi_flow

      • pi_flow_server

        java.util.HashMap<org.apache.commons.math3.util.Pair<Flow,​Server>,​java.util.HashSet<Path>> pi_flow_server

      • temp_constraints_transClosed

        java.util.HashSet<TemporalConstraint> temp_constraints_transClosed

      • map__path__temp_constraints_transClosed

        java.util.HashMap<Path,​java.util.HashSet<TemporalConstraint>> map__path__temp_constraints_transClosed

      • flow_constr_hdr

        boolean flow_constr_hdr

      • nonDecreasing_constraints

        java.util.HashSet<LogicalConstraint> nonDecreasing_constraints

      • nonDecreasingAtSource_constraints

        java.util.HashSet<LogicalConstraint> nonDecreasingAtSource_constraints

      • flow_of_interest

        Flow flow_of_interest

      • sink_of_interest

        Server sink_of_interest

      • explicit_src

        Server explicit_src

      • empty_path

        Path empty_path

    • Constructor Detail

      • UniqueLinearProgram

        private UniqueLinearProgram()

      • UniqueLinearProgram

        public UniqueLinearProgram​(ServerGraph network,
                           Flow flow_of_interest)
                    throws java.lang.Exception
        Throws:
        java.lang.Exception

    • Method Detail

      • derivePi

        private void derivePi​(Flow flow_to_trace,
                      Server tracing_start,
                      Path suffix)
               throws java.lang.Exception
        Throws:
        java.lang.Exception

      • deriveConstraints

        private void deriveConstraints​(Server s,
                               Path pi)
                        throws java.lang.Exception
        Derive: temp_constraints temp_constraints_transClosed map__j__jpi map__j__pair_jpi_pi map__path__temp_constraints_transClosed
        Throws:
        java.lang.Exception

      • derivePiFlow

        private void derivePiFlow()

      • getTempConstraintRelation

        public Relation getTempConstraintRelation​(Path path1,
                                          Path path2)

      • s2cConstraints

        private void s2cConstraints()

      • backloggedPeriodsConstraints

        private void backloggedPeriodsConstraints()

      • flowConstraints

        private void flowConstraints()

      • flowConstraintsHdr

        private void flowConstraintsHdr()

      • nonDecreasingConstraints

        private void nonDecreasingConstraints()

      • nonDecreasingAtSourcesConstraints

        private void nonDecreasingAtSourcesConstraints()

      • arrivalConstraints

        private void arrivalConstraints()

      • saveDelayLPv1

        public void saveDelayLPv1​(java.lang.String output_path)
                   throws java.lang.Exception
        The LP file created by this function can be read by LpSolve.
        Throws:
        java.lang.Exception

      • saveBacklogLPv1

        public void saveBacklogLPv1​(java.lang.String output_path)
                     throws java.lang.Exception
        Backlog at the flow of interest's sink. The LP file created by this function can be read by LpSolve.
        Throws:
        java.lang.Exception

      • lpSolveConstraintsString

        private java.lang.String lpSolveConstraintsString()

      • saveDelayLPv2

        public void saveDelayLPv2​(java.lang.String output_path)
                   throws java.lang.Exception
        The LP file created by this function can be read by CPLEX and by Gurobi.
        Throws:
        java.lang.Exception

      • cplexDelay

        public static double cplexDelay​(java.io.InputStream inputStream)
                         throws java.io.IOException
        Throws:
        java.io.IOException

      • lpSolveDelay

        public static double lpSolveDelay​(java.io.InputStream inputStream)
                           throws java.io.IOException
        Throws:
        java.io.IOException