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 017package com.net2plan.examples.ocnbook.offline; 018 019import java.io.File; 020import java.util.ArrayList; 021import java.util.List; 022import java.util.Map; 023 024import cern.colt.matrix.tdouble.DoubleFactory1D; 025import cern.colt.matrix.tdouble.DoubleFactory2D; 026import cern.colt.matrix.tdouble.DoubleMatrix1D; 027import cern.colt.matrix.tdouble.DoubleMatrix2D; 028import cern.jet.math.tdouble.DoubleFunctions; 029 030import com.jom.OptimizationProblem; 031import com.net2plan.interfaces.networkDesign.Configuration; 032import com.net2plan.interfaces.networkDesign.Demand; 033import com.net2plan.interfaces.networkDesign.IAlgorithm; 034import com.net2plan.interfaces.networkDesign.Net2PlanException; 035import com.net2plan.interfaces.networkDesign.NetPlan; 036import com.net2plan.utils.Constants.RoutingType; 037import com.net2plan.utils.InputParameter; 038import com.net2plan.utils.Triple; 039 040/** 041 * Solves a multihour routing problem with oblivious routing (common routing in all the time intervals) using a flow-path formulation 042 * @net2plan.description 043 * @net2plan.keywords Flow assignment (FA), Flow-path formulation, JOM, Multihour optimization 044 * @net2plan.ocnbooksections Section 4.6.8.1 045 * @net2plan.inputParameters 046 * @author Pablo Pavon-Marino 047 */ 048public class Offline_fa_xpMultihourObliviousRouting implements IAlgorithm 049{ 050 private InputParameter rootOfNameOfInputTrafficFiles = new InputParameter ("rootOfNameOfInputTrafficFiles", "multiHourObliviousRouting", "Root of the names of the traffic files. If the root is \"XXX\", the files are XXX_tm0.n2p, XXX_tm1.n2p, ..."); 051 private InputParameter rootOfNameOfOutputFiles = new InputParameter ("rootOfNameOfOutputFiles", "multiHourObliviousRouting", "Root of the names of the output files. One per input traffic file. If the root is \"XXX\", the files are XXX_res_tm0.n2p, XXX_res_tm1.n2p, ..."); 052 private InputParameter k = new InputParameter ("k", (int) 5 , "Maximum number of admissible paths per demand" , 1 , Integer.MAX_VALUE); 053 private InputParameter shortestPathType = new InputParameter ("shortestPathType", "#select# hops km" , "Criteria to compute the shortest path. Valid values: 'hops' or 'km'"); 054 private InputParameter nonBifurcatedRouting = new InputParameter ("nonBifurcatedRouting", false , "True if the routing is constrained to be non-bifurcated"); 055 private InputParameter optimizationTarget = new InputParameter ("optimizationTarget", "#select# min-av-num-hops minimax-link-utilization maximin-link-idle-capacity" , "Type of optimization target. Choose among minimize the average number of hops, minimize the highest link utilization, maximize the lowest link idle capacity"); 056 private InputParameter maxLengthInKm = new InputParameter ("maxLengthInKm", (double) 2000 , "Paths longer than this are considered not admissible. A non-positive number means this limit does not exist"); 057 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"); 058 private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "" , "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default."); 059 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)"); 060 061 @Override 062 public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters) 063 { 064 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 065 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 066 if (solverName.getString ().equalsIgnoreCase("ipopt") && nonBifurcatedRouting.getBoolean()) throw new Net2PlanException ("With IPOPT solver, the routing cannot be constrained to be non-bifurcated"); 067 if (!shortestPathType.getString().equalsIgnoreCase("km") && !shortestPathType.getString().equalsIgnoreCase("hops")) 068 throw new Net2PlanException("Wrong shortestPathType parameter"); 069 070 /* Initialize variables */ 071 final int N = netPlan.getNumberOfNodes (); 072 final int E = netPlan.getNumberOfLinks (); 073 final double PRECISION_FACTOR = Double.parseDouble(net2planParameters.get("precisionFactor")); 074 if (E == 0) throw new Net2PlanException("This algorithm requires a topology with links"); 075 076 /* Remove all unicast routed traffic. Any multicast routed traffic is kept */ 077 netPlan.removeAllUnicastRoutingInformation(); 078 netPlan.setRoutingType(RoutingType.SOURCE_ROUTING); 079 netPlan.setTrafficMatrix(DoubleFactory2D.dense.make (N,N,1.0)); // just to create the demands 080 081 /* Add all the k-shortest candidate routes to the netPlan object carrying no traffic */ 082 final DoubleMatrix1D linkCostVector = shortestPathType.getString().equalsIgnoreCase("hops")? DoubleFactory1D.dense.make (E , 1.0) : netPlan.getVectorLinkLengthInKm(); 083 084 netPlan.addRoutesFromCandidatePathList(linkCostVector.toArray() , "K", Integer.toString(k.getInt ()), "maxLengthInKm", Double.toString(maxLengthInKm.getDouble () > 0? maxLengthInKm.getDouble () : Double.MAX_VALUE)); 085 final int P = netPlan.getNumberOfRoutes(); 086 087 /* Create the netPlan files, one per interval */ 088 ArrayList<NetPlan> netPlanFiles = new ArrayList<NetPlan> (); 089 while (true) 090 { 091 try 092 { 093 DoubleMatrix2D thisIntervalTrafficMatrix = new NetPlan(new File (rootOfNameOfInputTrafficFiles.getString() + "_tm" + netPlanFiles.size () + ".n2p")).getMatrixNode2NodeOfferedTraffic(); 094 NetPlan netPlanToAdd = netPlan.copy (); 095 for (Demand d : netPlanToAdd.getDemands()) d.setOfferedTraffic(thisIntervalTrafficMatrix.get (d.getIngressNode().getIndex() , d.getEgressNode().getIndex())); 096 netPlanFiles.add (netPlanToAdd); 097 } catch (Exception e) { e.printStackTrace(); break; } 098 } 099 final int T = netPlanFiles.size(); 100 System.out.println ("Number of traffic matrices loaded: " + netPlanFiles.size ()); 101 102 /* Create the optimization problem object (JOM library) */ 103 OptimizationProblem op = new OptimizationProblem(); 104 105 /* Set some input parameters to the problem */ 106 op.setInputParameter("u_e", netPlan.getVectorLinkSpareCapacity(), "row"); /* for each link, its unused capacity (the one not used by any mulitcast trees) */ 107 op.setInputParameter("A_dp", netPlan.getMatrixDemand2RouteAssignment()); /* 1 in position (d,p) if demand d is served by path p, 0 otherwise */ 108 op.setInputParameter("A_ep", netPlan.getMatrixLink2RouteAssignment()); /* 1 in position (e,p) if link e is traversed by path p, 0 otherwise */ 109 DoubleMatrix2D h_dt = DoubleFactory2D.dense.make (N*(N-1),T); 110 DoubleMatrix2D h_pt = DoubleFactory2D.dense.make (P,T); 111 for (int t = 0; t < T ; t ++) 112 { 113 h_dt.viewColumn(t).assign (netPlanFiles.get(t).getVectorDemandOfferedTraffic()); 114 h_pt.viewColumn(t).assign (netPlanFiles.get(t).getVectorRouteOfferedTrafficOfAssociatedDemand()); 115 } 116 op.setInputParameter("h_dt", h_dt); /* for each demand and time interval , its offered traffic */ 117 op.setInputParameter("h_pt", h_pt); /* for each path and time interval , the offered traffic of its demand */ 118 op.setInputParameter("onesT", DoubleFactory1D.dense.make (T,1.0) , "row"); /* a vector of ones of size T */ 119 120 /* Write the problem formulations */ 121 if (optimizationTarget.getString ().equals ("min-av-num-hops")) 122 { 123 op.setInputParameter("l_p", netPlan.getVectorRouteNumberOfLinks() , "row"); /* for each path, the number of traversed links */ 124 op.addDecisionVariable("xx_p", nonBifurcatedRouting.getBoolean() , new int[] { 1 , P }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p (the same in all time intervals) */ 125 op.setObjectiveFunction("minimize", "sum (diag (l_p .* xx_p) * h_pt)"); /* sum of the traffic in the links in all the time intervals, proportional to the average number of hops */ 126 op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) */ 127 op.addConstraint("A_ep * (diag (xx_p) * h_pt) <= u_e' * onesT"); /* the traffic in each link cannot exceed its capacity in any time slot */ 128 } 129 else if (optimizationTarget.getString ().equals ("minimax-link-utilization")) 130 { 131 op.addDecisionVariable("xx_p", nonBifurcatedRouting.getBoolean() , new int[] { 1 , P }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p (the same in all time intervals) */ 132 op.addDecisionVariable("rho", false, new int[] { 1, 1 }, 0, 1); /* worse case link utilization */ 133 op.setObjectiveFunction("minimize", "rho"); 134 op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) */ 135 op.addConstraint("A_ep * (diag (xx_p) * h_pt) <= rho * u_e' * onesT"); /* the traffic in each link cannot exceed its capacity. sets rho as the worse case utilization in any time slot */ 136 } 137 else if (optimizationTarget.getString ().equals ("maximin-link-idle-capacity")) 138 { 139 op.addDecisionVariable("xx_p", nonBifurcatedRouting.getBoolean() , new int[] { 1 , P }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p (the same in all time intervals) */ 140 op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* worse case link idle capacity */ 141 op.setObjectiveFunction("maximize", "u"); 142 op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) */ 143 op.addConstraint("A_ep * (diag (xx_p) * h_pt) <= -u + (u_e' * onesT)"); /* the traffic in each link cannot exceed its capacity. sets u as the worse case idle capacity in all time intervals */ 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 DoubleMatrix1D xx_p = DoubleFactory1D.sparse.make (op.getPrimalSolution("xx_p").to1DArray()); 155 for (int t = 0 ; t < T ; t ++) 156 { 157 NetPlan thisNp = netPlanFiles.get(t); 158 final DoubleMatrix1D h_p = thisNp.getVectorRouteOfferedTrafficOfAssociatedDemand(); 159 final DoubleMatrix1D x_p = xx_p.copy().assign (h_p , DoubleFunctions.mult); 160 thisNp.setVectorRouteCarriedTrafficAndOccupiedLinkCapacities(x_p , x_p); 161 thisNp.removeAllRoutesUnused(PRECISION_FACTOR); // routes with zero traffic (or close to zero, with PRECISION_FACTOR tolerance) 162 thisNp.saveToFile(new File (rootOfNameOfOutputFiles.getString() + "_res_tm" + netPlanFiles.size () + ".n2p")); 163 if (t == 0) netPlan.assignFrom (thisNp); 164 if (!thisNp.getLinksOversubscribed().isEmpty()) throw new RuntimeException ("Bad"); 165 if (thisNp.getDemandTotalBlockedTraffic() > PRECISION_FACTOR) throw new RuntimeException ("Bad: " + thisNp.getDemandTotalBlockedTraffic()); 166 } 167 168 return "Ok!: The solution found is guaranteed to be optimal: " + op.solutionIsOptimal() + ". Number routes = " + netPlan.getNumberOfRoutes(); 169 } 170 171 @Override 172 public String getDescription() 173 { 174 return "Given a set of traffic matrices, corresponding to the offered network traffic at different times of the day, this algorithm solves a flow-path formulation for finding the oblivious routing (common routing to all the time intervals) that optimizes the selected optimization target."; 175 } 176 177 178 @Override 179 public List<Triple<String, String, String>> getParameters() 180 { 181 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 182 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 183 } 184}