001/******************************************************************************* 002 * Copyright (c) 2017 Pablo Pavon Marino and others. 003 * All rights reserved. This program and the accompanying materials 004 * are made available under the terms of the 2-clause BSD License 005 * which accompanies this distribution, and is available at 006 * https://opensource.org/licenses/BSD-2-Clause 007 * 008 * Contributors: 009 * Pablo Pavon Marino and others - initial API and implementation 010 *******************************************************************************/ 011 012 013 014 015 016 017 018 019 020 021 022package com.net2plan.examples.ocnbook.offline; 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; 029import com.jom.OptimizationProblem; 030import com.net2plan.interfaces.networkDesign.Demand; 031import com.net2plan.interfaces.networkDesign.IAlgorithm; 032import com.net2plan.interfaces.networkDesign.Net2PlanException; 033import com.net2plan.interfaces.networkDesign.NetPlan; 034import com.net2plan.utils.Constants.RoutingType; 035import com.net2plan.utils.InputParameter; 036import com.net2plan.utils.Triple; 037 038import java.io.File; 039import java.util.ArrayList; 040import java.util.List; 041import java.util.Map; 042 043/** 044 * Solves a multihour routing problem with dynamic routing (routing may be different at different time intervals) using a flow-path formulation 045 * @net2plan.description 046 * @net2plan.keywords Flow assignment (FA), Flow-path formulation, JOM, Multihour optimization 047 * @net2plan.ocnbooksections Section 4.6.8.2 048 * @net2plan.inputParameters 049 * @author Pablo Pavon-Marino 050 */ 051public class Offline_fa_xpMultihourDynamicRouting implements IAlgorithm 052{ 053 private InputParameter rootOfNameOfInputTrafficFiles = new InputParameter ("rootOfNameOfInputTrafficFiles", "multiHourDynamicRouting", "Root of the names of the traffic files. If the root is \"XXX\", the files are XXX_tm0.n2p, XXX_tm1.n2p, ..."); 054 private InputParameter rootOfNameOfOutputFiles = new InputParameter ("rootOfNameOfOutputFiles", "multiHourDynamicRouting", "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, ..."); 055 private InputParameter k = new InputParameter ("k", (int) 5 , "Maximum number of admissible paths per demand" , 1 , Integer.MAX_VALUE); 056 private InputParameter shortestPathType = new InputParameter ("shortestPathType", "#select# hops km" , "Criteria to compute the shortest path. Valid values: 'hops' or 'km'"); 057 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"); 058 private InputParameter gammaFactor = new InputParameter ("gammaFactor", (double) 1e-5 , "Penalization factor to changing the routing of traffic"); 059 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"); 060 private InputParameter solverName = new InputParameter ("solverName", "#select# glpk ipopt xpress cplex", "The solver name to be used by JOM. GLPK and IPOPT are free, XPRESS and CPLEX commercial. GLPK, XPRESS 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"); 061 private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "" , "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default."); 062 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)"); 063 064 @Override 065 public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters) 066 { 067 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 068 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 069 if (!shortestPathType.getString().equalsIgnoreCase("km") && !shortestPathType.getString().equalsIgnoreCase("hops")) 070 throw new Net2PlanException("Wrong shortestPathType parameter"); 071 072 /* Initialize variables */ 073 final int N = netPlan.getNumberOfNodes (); 074 final int E = netPlan.getNumberOfLinks (); 075 final double PRECISION_FACTOR = Double.parseDouble(net2planParameters.get("precisionFactor")); 076 if (E == 0) throw new Net2PlanException("This algorithm requires a topology with links"); 077 078 /* Remove all unicast routed traffic. Any multicast routed traffic is kept */ 079 netPlan.removeAllUnicastRoutingInformation(); 080 netPlan.setRoutingTypeAllDemands (RoutingType.SOURCE_ROUTING); 081 netPlan.setTrafficMatrix(DoubleFactory2D.dense.make (N,N,1.0) , RoutingType.SOURCE_ROUTING); // just to create the demands 082 083 /* Add all the k-shortest candidate routes to the netPlan object carrying no traffic */ 084 final DoubleMatrix1D linkCostVector = shortestPathType.getString().equalsIgnoreCase("hops")? DoubleFactory1D.dense.make (E , 1.0) : netPlan.getVectorLinkLengthInKm(); 085 netPlan.addRoutesFromCandidatePathList(netPlan.computeUnicastCandidatePathList(linkCostVector , k.getInt(), maxLengthInKm.getDouble(), -1, -1, -1, -1, -1 , null)); 086 final int P = netPlan.getNumberOfRoutes(); 087 088 /* Create the netPlan files, one per interval */ 089 ArrayList<NetPlan> netPlanFiles = new ArrayList<NetPlan> (); 090 while (true) 091 { 092 try 093 { 094 DoubleMatrix2D thisIntervalTrafficMatrix = new NetPlan(new File (rootOfNameOfInputTrafficFiles.getString() + "_tm" + netPlanFiles.size () + ".n2p")).getMatrixNode2NodeOfferedTraffic(); 095 if (thisIntervalTrafficMatrix.rows () != N) throw new Net2PlanException ("The number of nodes in traffic matrix: " + rootOfNameOfInputTrafficFiles.getString() + "_tm" + netPlanFiles.size () + ".n2p (" + thisIntervalTrafficMatrix.rows() + ") is not correct (" + N + ")"); 096 NetPlan netPlanToAdd = netPlan.copy (); 097 for (Demand d : netPlanToAdd.getDemands()) d.setOfferedTraffic(thisIntervalTrafficMatrix.get (d.getIngressNode().getIndex() , d.getEgressNode().getIndex())); 098 netPlanFiles.add (netPlanToAdd); 099 } catch (Exception e) { break; } 100 } 101 final int T = netPlanFiles.size(); 102 103 104 /* Create the optimization problem object (JOM library) */ 105 OptimizationProblem op = new OptimizationProblem(); 106 107 /* Set some input parameters to the problem */ 108 op.setInputParameter("u_e", netPlan.getVectorLinkSpareCapacity(), "row"); /* for each link, its unused capacity (the one not used by any mulitcast trees) */ 109 op.setInputParameter("A_dp", netPlan.getMatrixDemand2RouteAssignment()); /* 1 in position (d,p) if demand d is served by path p, 0 otherwise */ 110 op.setInputParameter("A_ep", netPlan.getMatrixLink2RouteAssignment()); /* 1 in position (e,p) if link e is traversed by path p, 0 otherwise */ 111 DoubleMatrix2D h_dt = DoubleFactory2D.dense.make (N*(N-1),T); 112 DoubleMatrix2D h_pt = DoubleFactory2D.dense.make (P,T); 113 DoubleMatrix2D P_ttminus1 = DoubleFactory2D.dense.make (T,T); 114 for (int t = 0; t < T ; t ++) 115 { 116 h_dt.viewColumn(t).assign (netPlanFiles.get(t).getVectorDemandOfferedTraffic()); 117 h_pt.viewColumn(t).assign (netPlanFiles.get(t).getVectorRouteOfferedTrafficOfAssociatedDemand()); 118 P_ttminus1.set(t,t,1.0); P_ttminus1.set(t,(t-1+T)%T,-1.0); 119 } 120 op.setInputParameter("h_dt", h_dt); /* for each demand and time interval , its offered traffic */ 121 op.setInputParameter("h_pt", h_pt); /* for each path and time interval , the offered traffic of its demand */ 122 op.setInputParameter("P_ttminus1", P_ttminus1); /* Each column t has a one in t and a mins one in t-1. Used to compute xx_pt - xx_p{t-1) easily as matrix multiplication */ 123 op.setInputParameter("gamma", gammaFactor.getDouble() / Math.pow (h_dt.zSum() , 2)); /* Gamma factor is normalized dividing by the maximum traffic that can be moved in all time slots, to the square. Then, gamma becomes the maximum value that the penalization summatory can take */ 124 op.setInputParameter("onesT", DoubleFactory1D.dense.make (T,1.0) , "row"); /* a vector of ones of size T */ 125 126 /* Write the problem formulations */ 127 if (optimizationTarget.getString ().equals ("min-av-num-hops")) 128 { 129 op.setInputParameter("l_p", netPlan.getVectorRouteNumberOfLinks() , "row"); /* for each path, the number of traversed links */ 130 op.addDecisionVariable("xx_pt", false , new int[] { P , T }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p in each time interval */ 131 if (gammaFactor.getDouble() == 0) 132 op.setObjectiveFunction("minimize", "sum (diag (l_p) * xx_pt .* h_pt)"); /* sum of the traffic in the links in all the time intervals, proportional to the average number of hops */ 133 else 134 op.setObjectiveFunction("minimize", "sum (diag (l_p) * xx_pt .* h_pt) + gamma * sum ((h_pt .* (xx_pt*P_ttminus1)) ^ 2)"); /* sum of the traffic in the links in all the time intervals, proportional to the average number of hops */ 135 op.addConstraint("A_dp * xx_pt == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) in any time interval */ 136 op.addConstraint("A_ep * (xx_pt .* h_pt) <= u_e' * onesT"); /* the traffic in each link cannot exceed its capacity in any time slot */ 137 } 138 else if (optimizationTarget.getString ().equals ("minimax-link-utilization")) 139 { 140 op.addDecisionVariable("xx_pt", false , new int[] { P , T }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p in each time interval */ 141 op.addDecisionVariable("rho", false, new int[] { 1, 1 }, 0, 1); /* worse case link utilization in all time slots */ 142 if (gammaFactor.getDouble() == 0) 143 op.setObjectiveFunction("minimize", "rho"); 144 else 145 op.setObjectiveFunction("minimize", "rho + gamma * sum ((h_pt .* (xx_pt*P_ttminus1)) ^ 2)"); 146 op.addConstraint("A_dp * xx_pt == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) in any time interval */ 147 op.addConstraint("A_ep * (xx_pt .* 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 */ 148 } 149 else if (optimizationTarget.getString ().equals ("maximin-link-idle-capacity")) 150 { 151 op.addDecisionVariable("xx_pt", false , new int[] { P , T }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p in each time interval */ 152 op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* worse case link idle capacity in all time slots */ 153 if (gammaFactor.getDouble() == 0) 154 op.setObjectiveFunction("maximize", "u"); 155 else 156 op.setObjectiveFunction("maximize", "u - gamma * sum ((h_pt .* (xx_pt*P_ttminus1)) ^ 2)"); 157 op.addConstraint("A_dp * xx_pt == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) in any time interval */ 158 op.addConstraint("A_ep * (xx_pt .* 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 */ 159 } 160 else throw new Net2PlanException ("Unknown optimization target " + optimizationTarget.getString()); 161 162 op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ()); 163 164 /* If no solution is found, quit */ 165 if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution"); 166 if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found"); 167 168 /* Save the solution found in the netPlan object */ 169 final DoubleMatrix2D xx_pt = op.getPrimalSolution("xx_pt").view2D (); 170 for (int t = 0 ; t < T ; t ++) 171 { 172 NetPlan thisNp = netPlanFiles.get(t); 173 final DoubleMatrix1D h_p = thisNp.getVectorRouteOfferedTrafficOfAssociatedDemand(); 174 final DoubleMatrix1D x_p = xx_pt.viewColumn(t).copy().assign (h_p , DoubleFunctions.mult); 175 thisNp.setVectorRouteCarriedTrafficAndOccupiedLinkCapacities(x_p , x_p); 176 thisNp.removeAllRoutesUnused(PRECISION_FACTOR); // routes with zero traffic (or close to zero, with PRECISION_FACTOR tolerance) 177 thisNp.saveToFile(new File (rootOfNameOfOutputFiles.getString() + "_res_tm" + netPlanFiles.size () + ".n2p")); 178 if (t == 0) netPlan.assignFrom (thisNp); 179 if (thisNp.getVectorLinkOversubscribedTraffic().zSum () > PRECISION_FACTOR) throw new RuntimeException ("Bad: " + thisNp.getVectorLinkOversubscribedTraffic().zSum ()); 180 if (thisNp.getVectorDemandBlockedTraffic().zSum() > PRECISION_FACTOR) throw new RuntimeException ("Bad: " + thisNp.getVectorDemandBlockedTraffic().zSum()); 181 } 182 183 DoubleMatrix2D reroutedTraffic_pt = xx_pt.zMult (P_ttminus1 , null).assign (h_pt, DoubleFunctions.mult).assign (DoubleFunctions.abs); 184 185 return "Ok!: The solution found is guaranteed to be optimal: " + op.solutionIsOptimal() + ". Sum rerouted traffic all time slots = " + reroutedTraffic_pt.zSum(); 186 } 187 188 @Override 189 public String getDescription() 190 { 191 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 set of routings (one per time interval) that optimizes the selected optimization target. The objective function includes a penalization factor to avoid excessive reroutings along the day."; 192 } 193 194 195 @Override 196 public List<Triple<String, String, String>> getParameters() 197 { 198 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 199 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 200 } 201}