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.DoubleMatrix2D; 024import cern.jet.math.tdouble.DoubleFunctions; 025 026import com.jom.OptimizationProblem; 027import com.net2plan.interfaces.networkDesign.Demand; 028import com.net2plan.interfaces.networkDesign.IAlgorithm; 029import com.net2plan.interfaces.networkDesign.Link; 030import com.net2plan.interfaces.networkDesign.Net2PlanException; 031import com.net2plan.interfaces.networkDesign.NetPlan; 032import com.net2plan.utils.DoubleUtils; 033import com.net2plan.utils.InputParameter; 034import com.net2plan.utils.Triple; 035 036/** 037 * Solves several variants of unicast routing problems, with flow-link formulations 038 * @net2plan.description 039 * @net2plan.keywords JOM, Flow-link formulation, Flow assignment (FA) 040 * @net2plan.ocnbooksections Section 4.3, Section 4.6.3 041 * @net2plan.inputParameters 042 * @author Pablo Pavon-Marino 043 */ 044public class Offline_fa_xdeFormulations implements IAlgorithm 045{ 046 private InputParameter nonBifurcatedRouting = new InputParameter ("nonBifurcatedRouting", false , "True if the routing is constrained to be non-bifurcated"); 047 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"); 048 private InputParameter maxLengthInKm = new InputParameter ("maxLengthInKm", (double) -1 , "Paths longer than this are considered not admissible. A non-positive number means this limit does not exist"); 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 055 @Override 056 public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters) 057 { 058 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 059 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 060 if (solverName.getString ().equalsIgnoreCase("ipopt") && nonBifurcatedRouting.getBoolean()) throw new Net2PlanException ("With IPOPT solver, the routing cannot be constrained to be non-bifurcated"); 061 062 /* Initialize variables */ 063 final int E = netPlan.getNumberOfLinks(); 064 final int D = netPlan.getNumberOfDemands(); 065 if (E == 0 || D == 0) throw new Net2PlanException("This algorithm requires a topology with links and a demand set"); 066 067 /* Remove all unicast routed traffic. Any multicast routed traffic is kept */ 068 netPlan.removeAllUnicastRoutingInformation(); 069 070 /* Create the optimization problem object (JOM library) */ 071 OptimizationProblem op = new OptimizationProblem(); 072 073 /* Set some input parameters to the problem */ 074 op.setInputParameter("u_e", netPlan.getVectorLinkSpareCapacity(), "row"); /* for each link, its unused capacity (the one not used by any mulitcast trees) */ 075 op.setInputParameter("A_nd", netPlan.getMatrixNodeDemandIncidence()); /* 1 in position (n,d) if demand d starts in n, -1 if it ends in n, 0 otherwise */ 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 op.setInputParameter("h_d", netPlan.getVectorDemandOfferedTraffic(), "row"); /* for each demand, its offered traffic */ 078 op.setInputParameter("l_e", netPlan.getVectorLinkLengthInKm(), "row"); /* for each link, its length in km */ 079 op.setInputParameter("Lmax", maxLengthInKm.getDouble()); /* for each link, its length in km */ 080 081 /* Write the problem formulations */ 082 if (optimizationTarget.getString ().equals ("min-av-num-hops")) 083 { 084 op.addDecisionVariable("xx_de", nonBifurcatedRouting.getBoolean() , new int[] { D, E }, 0, 1); /* the FRACTION of traffic of demand d that is carried by link e */ 085 op.setObjectiveFunction("minimize", "sum (h_d * xx_de)"); /* sum of the traffic in the links, proportional to the average number of hops */ 086 op.addConstraint("A_ne * (xx_de') == A_nd"); /* the flow-conservation constraints (NxD constraints) */ 087 op.addConstraint("h_d * xx_de <= u_e"); /* the capacity constraints (E constraints) */ 088 if (maxLengthInKm.getDouble() > 0) 089 { 090 if (nonBifurcatedRouting.getBoolean()) throw new Net2PlanException ("The maximum length constraint can only be applied in this formulation with non-bifurcated routing"); 091 op.addConstraint("xx_de * l_e' <= Lmax"); /* the path traversed by a demand cannot exceed the maximum length in km */ 092 } 093 } 094 else if (optimizationTarget.getString ().equals ("minimax-link-utilization")) 095 { 096 op.setInputParameter ("EPSILON" , getMinimumNonZeroTrafficOrCapacityValue (netPlan) / 1000); 097 op.addDecisionVariable("xx_de", nonBifurcatedRouting.getBoolean() , new int[] { D, E }, 0, 1); /* the FRACTION of traffic of demand d that is carried by link e */ 098 op.addDecisionVariable("rho", false, new int[] { 1, 1 }, 0, 1); /* worse case link utilization */ 099 op.setObjectiveFunction("minimize", "rho + EPSILON * sum (h_d * xx_de)"); // to avoid loops, we sum EPSILON by the traffic carried (EPSILON very small number) 100 op.addConstraint("A_ne * (xx_de') == A_nd"); /* the flow-conservation constraints (NxD constraints) */ 101 op.addConstraint("h_d * xx_de <= rho * u_e"); /* the traffic in each link cannot exceed its capacity. sets rho as the worse case utilization */ 102 if (maxLengthInKm.getDouble() > 0) 103 { 104 if (nonBifurcatedRouting.getBoolean()) throw new Net2PlanException ("The maximum length constraint can only be applied in this formulation with non-bifurcated routing"); 105 op.addConstraint("xx_de * l_e' <= Lmax"); /* the path traversed by a demand cannot exceed the maximum length in km */ 106 } 107 } 108 else if (optimizationTarget.getString ().equals ("maximin-link-idle-capacity")) 109 { 110 op.setInputParameter ("EPSILON" , getMinimumNonZeroTrafficOrCapacityValue (netPlan) / 1000); 111 op.addDecisionVariable("xx_de", nonBifurcatedRouting.getBoolean() , new int[] { D, E }, 0, 1); /* the FRACTION of traffic of demand d that is carried by link e */ 112 op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* worse case link idle capacity */ 113 op.setObjectiveFunction("maximize", "u - (EPSILON * sum (h_d * xx_de))"); // to avoid loops, we sum EPSILON by the traffic carried (EPSILON very small number) 114 op.addConstraint("A_ne * (xx_de') == A_nd"); /* the flow-conservation constraints (NxD constraints) */ 115 op.addConstraint("h_d * xx_de <= -u + u_e"); /* the traffic in each link cannot exceed its capacity. sets u as the worse case idle capacity */ 116 if (maxLengthInKm.getDouble() > 0) 117 { 118 if (nonBifurcatedRouting.getBoolean()) throw new Net2PlanException ("The maximum length constraint can only be applied in this formulation with non-bifurcated routing"); 119 op.addConstraint("xx_de * l_e' <= Lmax"); /* the path traversed by a demand cannot exceed the maximum length in km */ 120 } 121 } 122 else if (optimizationTarget.getString ().equals ("min-av-network-delay")) 123 { 124 if (!solverName.getString ().equalsIgnoreCase("ipopt") || nonBifurcatedRouting.getBoolean()) throw new Net2PlanException ("This is a convex non linear model: please use IPOPT solver. The routing cannot be constrained to be non-bifurcated"); 125 if (maxLengthInKm.getDouble() > 0) throw new Net2PlanException ("The maximum length constraint can not be applied in this objective function"); 126 op.setInputParameter("d_e_secs", netPlan.getVectorLinkPropagationDelayInMiliseconds().assign (DoubleFunctions.mult (0.001)) , "row"); 127 op.setInputParameter("L", averagePacketLengthInBytes.getDouble() * 8); /* average packet length in bits */ 128 op.setInputParameter("R", binaryRatePerTrafficUnit_bps.getDouble()); /* binary rate per traffic unit */ 129 op.addDecisionVariable("xx_de", nonBifurcatedRouting.getBoolean() , new int[] { D, E }, 0, 1); /* the FRACTION of traffic of demand d that is carried by link e */ 130 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) */ 131 op.setObjectiveFunction("minimize", "sum( y_e .* (d_e_secs + (L./R) * (1 ./ (u_e - y_e))) )"); 132 op.addConstraint("A_ne * (xx_de') == A_nd"); /* the flow-conservation constraints (NxD constraints) */ 133 op.addConstraint("h_d * xx_de == y_e"); /* sets y_e as the total traffic in each link */ 134 } 135 else if (optimizationTarget.getString ().equals ("min-av-network-blocking")) 136 { 137 if (!solverName.getString ().equalsIgnoreCase("ipopt") || nonBifurcatedRouting.getBoolean()) throw new Net2PlanException ("This is a convex non linear model: please use IPOPT solver. The routing cannot be constrained to be non-bifurcated"); 138 if (maxLengthInKm.getDouble() > 0) throw new Net2PlanException ("The maximum length constraint can not be applied in this objective function"); 139 op.addDecisionVariable("xx_de", nonBifurcatedRouting.getBoolean() , new int[] { D, E }, 0, 1); /* the FRACTION of traffic of demand d that is carried by link e */ 140 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) */ 141 op.setObjectiveFunction("minimize", "sum(y_e .* erlangB(y_e, u_e))"); 142 op.addConstraint("A_ne * (xx_de') == A_nd"); /* the flow-conservation constraints (NxD constraints) */ 143 op.addConstraint("h_d * xx_de == y_e"); /* sets y_e as the total traffic in each link */ 144 } 145 else throw new Net2PlanException ("Unknown optimization target " + optimizationTarget.getString()); 146 147 op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ()); 148 149 /* If no solution is found, quit */ 150 if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution"); 151 if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found"); 152 153 /* Save the solution found in the netPlan object */ 154 final DoubleMatrix2D xx_de = op.getPrimalSolution("xx_de").view2D(); 155 netPlan.setRoutingFromDemandLinkCarriedTraffic(xx_de , true , true); 156 157 return "Ok!: The solution found is guaranteed to be optimal: " + op.solutionIsOptimal(); 158 } 159 160 @Override 161 public String getDescription() 162 { 163 return "Given a network topology, the capacities in the links, and a set unicast traffic demands, this algorithm permits computing the optimum routing of the traffic (that is, the set of routes carrying the traffic of the demands) solving flow-link formulations (x_{de} variables). Through a set of input parameters, the user can choose among different optimization targets and constraints."; 164 } 165 166 167 @Override 168 public List<Triple<String, String, String>> getParameters() 169 { 170 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 171 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 172 } 173 174 private double getMinimumNonZeroTrafficOrCapacityValue (NetPlan netPlan) 175 { 176 double res = Double.MAX_VALUE; 177 for (Demand d : netPlan.getDemands ()) if (d.getOfferedTraffic() > 0) res = Math.min (res , d.getOfferedTraffic()); 178 for (Link e : netPlan.getLinks ()) if (e.getCapacity() > 0) res = Math.min (res , e.getCapacity()); 179 if (res == Double.MAX_VALUE) throw new Net2PlanException ("Too large offered traffics and link capacities"); 180 return res; 181 } 182}