001/*******************************************************************************
002 * Copyright (c) 2016 Pablo Pavon Mariņo.
003 * All rights reserved. This program and the accompanying materials
004 * are made available under the terms of the GNU Lesser Public License v2.1
005 * which accompanies this distribution, and is available at
006 * http://www.gnu.org/licenses/lgpl.html
007 ******************************************************************************/
008
009
010
011
012
013 
014
015
016
017
018package com.net2plan.examples.ocnbook.offline;
019
020import java.util.List;
021import java.util.Map;
022
023import cern.colt.matrix.tdouble.DoubleFactory2D;
024import cern.colt.matrix.tdouble.DoubleMatrix1D;
025import cern.colt.matrix.tdouble.DoubleMatrix2D;
026import cern.jet.math.tdouble.DoubleFunctions;
027
028import com.jom.OptimizationProblem;
029import com.net2plan.interfaces.networkDesign.Demand;
030import com.net2plan.interfaces.networkDesign.IAlgorithm;
031import com.net2plan.interfaces.networkDesign.Link;
032import com.net2plan.interfaces.networkDesign.Net2PlanException;
033import com.net2plan.interfaces.networkDesign.NetPlan;
034import com.net2plan.utils.DoubleUtils;
035import com.net2plan.utils.InputParameter;
036import com.net2plan.utils.Triple;
037
038/**
039 * Solves severals variants of routing problems in the form of destination-link formulations.
040 * @net2plan.description
041 * @net2plan.keywords JOM, Destination-link formulation, Flow assignment (FA)
042 * @net2plan.ocnbooksections Section 4.4, Section 4.6.3
043 * @net2plan.inputParameters 
044 * @author Pablo Pavon-Marino
045 */
046public class Offline_fa_xteFormulations implements IAlgorithm
047{
048        private InputParameter optimizationTarget = new InputParameter ("optimizationTarget", "#select# min-av-num-hops minimax-link-utilization maximin-link-idle-capacity min-av-network-delay min-av-network-blocking" , "Type of optimization target. Choose among minimize the average number of hops, minimize the highest link utilization, maximize the lowest link idle capacity, minimize the average end-to-end network delay including queueing (M/M/1 estimation) and propagation delays, and minimize the average network blocking assuming independent Erlang-B blocking in each link, load sharing model");
049        private InputParameter solverName = new InputParameter ("solverName", "#select# glpk cplex ipopt", "The solver name to be used by JOM. GLPK and IPOPT are free, CPLEX commercial. GLPK and CPLEX solve linear problems w/w.o integer contraints. IPOPT is can solve nonlinear problems (if convex, returns global optimum), but cannot handle integer constraints");
050        private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "", "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default.");
051        private InputParameter maxSolverTimeInSeconds = new InputParameter ("maxSolverTimeInSeconds", (double) -1 , "Maximum time granted to the solver to solve the problem. If this time expires, the solver returns the best solution found so far (if a feasible solution is found)");
052        private InputParameter binaryRatePerTrafficUnit_bps = new InputParameter ("binaryRatePerTrafficUnit_bps", (double) 1E6 , "Binary rate equivalent to one traffic unit (used only in average network delay minimization formulation)." , 0 , false , Double.MAX_VALUE , true);
053        private InputParameter averagePacketLengthInBytes = new InputParameter ("averagePacketLengthInBytes", (double) 500 , "Average packet length in bytes (used only in average network delay minimization formulation)." , 0 , false , Double.MAX_VALUE , true);
054        private InputParameter nonBifurcatedRouting = new InputParameter ("nonBifurcatedRouting", false , "True if the routing is constrained to be non-bifurcated");
055
056        @Override
057        public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters)
058        {
059                /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */
060                InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters);
061                
062                /* Initialize variables */
063                final int N = netPlan.getNumberOfNodes ();
064                final int E = netPlan.getNumberOfLinks();
065                final int D = netPlan.getNumberOfDemands();
066                if (E == 0 || D == 0) throw new Net2PlanException("This algorithm requires a topology with links and a demand set");
067
068                /* Remove all routes in current netPlan object, and set routing type to SOURCE ROUTING */
069                netPlan.removeAllUnicastRoutingInformation ();
070
071                /* Create the optimization problem object (JOM library) */
072                OptimizationProblem op = new OptimizationProblem();
073
074                /* Set some input parameters to the problem */
075                op.setInputParameter("u_e", netPlan.getVectorLinkSpareCapacity(), "row"); /* for each link, its unused capacity (the one not used by any mulitcast trees) */
076                op.setInputParameter("A_ne", netPlan.getMatrixNodeLinkIncidence()); /* 1 in position (n,e) if link e starts in n, -1 if it ends in n, 0 otherwise */
077                final DoubleMatrix1D egressTraffic_t = netPlan.getVectorNodeEgressUnicastTraffic();
078                final DoubleMatrix2D trafficMatrixDiagonalNegative = netPlan.getMatrixNode2NodeOfferedTraffic();
079                trafficMatrixDiagonalNegative.assign (DoubleFactory2D.sparse.diagonal(egressTraffic_t) , DoubleFunctions.minus);
080                op.setInputParameter("TM", trafficMatrixDiagonalNegative);
081                
082                /* Write the problem formulations */
083                if (optimizationTarget.getString ().equals ("min-av-num-hops")) 
084                {
085                        op.addDecisionVariable("x_te", false , new int[] { N, E }, 0, Double.MAX_VALUE); /* the amount of traffic targeted to node t, that is carried by link e */
086                        if (nonBifurcatedRouting.getBoolean()) op.addDecisionVariable("f_te", true, new int [] {N,E} , 0 , 1);
087                        op.setObjectiveFunction("minimize", "sum (x_te)"); /* sum of the traffic in the links, proportional to the average number of hops  */
088                        op.addConstraint("A_ne * (x_te') == TM"); /* the flow-conservation constraints (NxD constraints) */
089                        op.addConstraint("sum(x_te,1) <= u_e"); /* the capacity constraints (E constraints) */
090                }
091                else if (optimizationTarget.getString ().equals ("minimax-link-utilization")) 
092                {
093                        op.setInputParameter ("EPSILON" , getMinimumNonZeroTrafficOrCapacityValue (netPlan) / 1000);
094                        op.addDecisionVariable("x_te", false , new int[] { N, E }, 0, Double.MAX_VALUE); /* the amount of traffic targeted to node t, that is carried by link e */
095                        op.addDecisionVariable("rho", false, new int[] { 1, 1 }, 0, 1); /* worse case link utilization */
096                        if (nonBifurcatedRouting.getBoolean()) op.addDecisionVariable("f_te", true, new int [] {N,E} , 0 , 1);
097                        op.setObjectiveFunction("minimize", "rho + EPSILON * sum(x_te)"); // to avoid loops, we sum EPSILON by the traffic carried (EPSILON very small number)
098                        op.addConstraint("A_ne * (x_te') == TM"); /* the flow-conservation constraints (NxD constraints) */
099                        op.addConstraint("sum(x_te,1) <= rho * u_e"); /* the traffic in each link cannot exceed its capacity. sets rho as the worse case utilization */
100                }
101                else if (optimizationTarget.getString ().equals ("maximin-link-idle-capacity"))
102                {
103                        op.setInputParameter ("EPSILON" , getMinimumNonZeroTrafficOrCapacityValue (netPlan) / 1000);
104                        op.addDecisionVariable("x_te", false , new int[] { N, E }, 0, Double.MAX_VALUE); /* the amount of traffic targeted to node t, that is carried by link e */
105                        op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* worse case link idle capacity */
106                        if (nonBifurcatedRouting.getBoolean()) op.addDecisionVariable("f_te", true, new int [] {N,E} , 0 , 1);
107                        op.setObjectiveFunction("maximize", "u - EPSILON * sum(x_te)"); // to avoid loops, we sum EPSILON by the traffic carried (EPSILON very small number)
108                        op.addConstraint("A_ne * (x_te') == TM"); /* the flow-conservation constraints (NxD constraints) */
109                        op.addConstraint("sum(x_te,1) <= -u + u_e"); /* the traffic in each link cannot exceed its capacity. sets u as the worse case idle capacity */
110                }
111                else if (optimizationTarget.getString ().equals ("min-av-network-delay"))
112                {
113                        op.setInputParameter("d_e_secs", netPlan.getVectorLinkPropagationDelayInMiliseconds().assign (DoubleFunctions.mult (0.001)) , "row");
114                        op.setInputParameter("L", averagePacketLengthInBytes.getDouble() * 8); /* average packet length in bits */
115                        op.setInputParameter("R", binaryRatePerTrafficUnit_bps.getDouble()); /* binary rate per traffic unit */
116                        op.addDecisionVariable("x_te", false , new int[] { N, E }, 0, Double.MAX_VALUE); /* the amount of traffic targeted to node t, that is carried by link e */
117                        op.addDecisionVariable("y_e", false, new int[] { 1, E }, DoubleUtils.zeros(E), netPlan.getVectorLinkCapacity().toArray()); /* traffic in the links (already limited to the link capacity) */
118                        if (nonBifurcatedRouting.getBoolean()) op.addDecisionVariable("f_te", true, new int [] {N,E} , 0 , 1);
119                        op.setObjectiveFunction("minimize", "sum( y_e .* (d_e_secs + (L./R) * (1 ./ (u_e - y_e)))  )");
120                        op.addConstraint("A_ne * (x_te') == TM"); /* the flow-conservation constraints (NxD constraints) */
121                        op.addConstraint("sum(x_te,1) == y_e"); /* sets y_e as the total traffic in each link */
122                }
123                else if (optimizationTarget.getString ().equals ("min-av-network-blocking"))
124                {
125                        op.addDecisionVariable("x_te", false , new int[] { N, E }, 0, Double.MAX_VALUE); /* the amount of traffic targeted to node t, that is carried by link e */
126                        op.addDecisionVariable("y_e", false, new int[] { 1, E }, DoubleUtils.zeros(E), netPlan.getVectorLinkCapacity().toArray()); /* traffic in the links (already limited to the link capacity) */
127                        if (nonBifurcatedRouting.getBoolean()) op.addDecisionVariable("f_te", true, new int [] {N,E} , 0 , 1);
128                        op.setObjectiveFunction("minimize", "sum(y_e .* erlangB(y_e, u_e))");
129                        op.addConstraint("A_ne * (x_te') == TM"); /* the flow-conservation constraints (NxD constraints) */
130                        op.addConstraint("sum(x_te,1) == y_e"); /* sets y_e as the total traffic in each link */
131                }
132                else throw new Net2PlanException ("Unknown optimization target " + optimizationTarget.getString());
133
134                /* Constraints for non-bifurcated traffic */
135                if (nonBifurcatedRouting.getBoolean())
136                {
137                        DoubleMatrix2D maxNumOutLinksCarryingTraffic_nt = DoubleFactory2D.dense.make(N,N,1.0);
138                        for (int n = 0 ; n < N ; n ++) maxNumOutLinksCarryingTraffic_nt.set(n, n, 0);
139                        op.setInputParameter("U", netPlan.getVectorLinkCapacity().getMaxLocation() [0]);
140                        op.setInputParameter("Aout_ne", netPlan.getMatrixNodeLinkOutgoingIncidence());
141                        op.setInputParameter("outMax_nt", maxNumOutLinksCarryingTraffic_nt);
142                        op.addConstraint("x_te <= U * f_te"); /* f_te takes value 1 for non zero x_te */
143                        op.addConstraint ("Aout_ne * f_te' <= outMax_nt"); /* number of out links of node n carrying traffic to t is always below 1, and if n=t, it is zero */
144                }
145
146                op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ());
147
148                /* If no solution is found, quit */
149                if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution");
150                if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found");
151                
152                /* Save the solution found in the netPlan object */
153                final DoubleMatrix2D x_te = op.getPrimalSolution("x_te").view2D();
154                netPlan.setRoutingFromDestinationLinkCarriedTraffic(x_te , true); // remove the cycles if any
155
156                return "Ok!: The solution found is guaranteed to be optimal: " + op.solutionIsOptimal();
157        }
158
159        @Override
160        public String getDescription()
161        {
162                return "Given a network topology, the capacities in the links, and a set unicast traffic demands, this algorithm permits computing the optimum destination-based routing of the traffic solving destination-link formulations (x_{te} variables). Recall that in destination-based routing, the nodes can only forward the traffic depending on its destination node, whatever its demand is (e.g. a node routes all the demands with the same egress node in the same form, whatever its ingress node is). Through a set of input parameters, the user can choose among different optimization targets and constraints.";
163        }
164
165        
166        @Override
167        public List<Triple<String, String, String>> getParameters()
168        {
169                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
170                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
171        }
172
173        private double getMinimumNonZeroTrafficOrCapacityValue (NetPlan netPlan)
174        {
175                double res = Double.MAX_VALUE;
176                for (Demand d : netPlan.getDemands ()) if (d.getOfferedTraffic() > 0) res = Math.min (res , d.getOfferedTraffic());
177                for (Link e : netPlan.getLinks ()) if (e.getCapacity() > 0) res = Math.min (res , e.getCapacity());
178                if (res == Double.MAX_VALUE) throw new Net2PlanException ("Too large offered traffics and link capacities");
179                return res;
180        }
181}