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 021package com.net2plan.examples.ocnbook.offline; 022 023import java.util.ArrayList; 024import java.util.Collections; 025import java.util.List; 026import java.util.Map; 027import java.util.TreeSet; 028 029import com.jom.OptimizationProblem; 030import com.net2plan.interfaces.networkDesign.Demand; 031import com.net2plan.interfaces.networkDesign.IAlgorithm; 032import com.net2plan.interfaces.networkDesign.Link; 033import com.net2plan.interfaces.networkDesign.Net2PlanException; 034import com.net2plan.interfaces.networkDesign.NetPlan; 035import com.net2plan.interfaces.networkDesign.Route; 036import com.net2plan.libraries.GraphUtils; 037import com.net2plan.utils.Constants.RoutingType; 038import com.net2plan.utils.InputParameter; 039import com.net2plan.utils.Triple; 040 041import cern.colt.matrix.tdouble.DoubleMatrix1D; 042import cern.colt.matrix.tdouble.DoubleMatrix2D; 043 044/** 045 * Solves several variants of unicast routing problems with 1+1 protection, with flow-link formulations 046 * @net2plan.description 047 * @net2plan.keywords JOM, Flow-path formulation, Flow assignment (FA), Network recovery: protection 048 * @net2plan.ocnbooksections Section 4.3, Section 4.6.6 049 * @net2plan.inputParameters 050 * @author Pablo Pavon-Marino 051 */ 052public class Offline_fa_xde11PathProtection implements IAlgorithm 053{ 054 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"); 055 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"); 056 private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "", "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default."); 057 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)"); 058 private InputParameter type11 = new InputParameter ("type11", "#select# linkDisjoint srgDisjoint" , "Type of 1+1 protection: 1+1 link disjoint (primary and backup paths have no link in common), and 1+1 srg disjoint (primary and backup paths have no SRG in common)"); 059 060 @Override 061 public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters) 062 { 063 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 064 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 065 066 /* Basic checks */ 067 final int N = netPlan.getNumberOfNodes(); 068 final int E = netPlan.getNumberOfLinks(); 069 final int D = netPlan.getNumberOfDemands(); 070 if (N == 0 || D == 0 || E == 0) throw new Net2PlanException("This algorithm requires a topology with links, and a demand set"); 071 072 /* Remove all unicast routed traffic. Any multicast routed traffic is kept */ 073 netPlan.removeAllUnicastRoutingInformation(); 074 netPlan.setRoutingTypeAllDemands(RoutingType.SOURCE_ROUTING); 075 076 /* Initialize some variables */ 077 DoubleMatrix1D u_e = netPlan.getVectorLinkSpareCapacity(); // just the unused capacity (some capacity may be used by multicast traffic) 078 DoubleMatrix1D h_d = netPlan.getVectorDemandOfferedTraffic(); 079 080 /* Create the optimization problem object (JOM library) */ 081 OptimizationProblem op = new OptimizationProblem(); 082 op.setInputParameter("u_e", u_e, "row"); 083 op.setInputParameter("h_d", h_d, "row"); 084 op.setInputParameter("A_ne", netPlan.getMatrixNodeLinkIncidence()); 085 op.setInputParameter("A_nd", netPlan.getMatrixNodeDemandIncidence()); 086 087 if (type11.getString ().equalsIgnoreCase("linkDisjoint")) 088 { 089 /* Add the decision variables to the problem */ 090 op.addDecisionVariable("x_de", true, new int[] { D, E }, 0, 1); /* 1 if the primary path of demand d, traverses link e */ 091 op.addDecisionVariable("xx_de", true, new int[] { D, E }, 0, 1); /* 1 if the backup path of demand d, traverses link e */ 092 093 /* Sets the objective function */ 094 if (optimizationTarget.getString ().equalsIgnoreCase("min-av-num-hops")) 095 { 096 op.setObjectiveFunction("minimize", "sum (h_d * (x_de + xx_de))"); 097 op.addConstraint("h_d * (x_de + xx_de) <= u_e"); /* the capacity constraints summing primary and backup paths (E constraints) */ 098 } 099 else if (optimizationTarget.getString ().equalsIgnoreCase("minimax-link-utilization")) 100 { 101 op.setInputParameter ("EPSILON" , 1e-4); 102 op.addDecisionVariable("rho", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* idle capacity in the bottleneck link */ 103 op.setObjectiveFunction("minimize", "rho + EPSILON * sum(x_de + xx_de)"); 104 op.addConstraint("h_d * (x_de + xx_de) <= rho * u_e"); /* the capacity constraints summing primary and backup paths (E constraints), make that rho becomes the worse case link utilization */ 105 } 106 else if (optimizationTarget.getString ().equalsIgnoreCase("maximin-link-idle-capacity")) 107 { 108 op.setInputParameter ("EPSILON" , 1e-4); 109 op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* idle capacity in the bottleneck link */ 110 op.setObjectiveFunction("maximize", "u - EPSILON * sum(x_de + xx_de)"); 111 op.addConstraint("h_d * (x_de + xx_de) <= u_e - u"); /* the capacity constraints summing primary and backup paths (E constraints) */ 112 } 113 else throw new Net2PlanException ("Unknown optimization target " + optimizationTarget.getString()); 114 115 /* Add constraints */ 116 op.addConstraint("A_ne * (x_de') == A_nd"); /* the flow-conservation constraints for the primary path (NxD constraints) */ 117 op.addConstraint("A_ne * (xx_de') == A_nd"); /* the flow-conservation constraints for the backup path (NxD constraints) */ 118 op.addConstraint("x_de + xx_de <= 1"); /* the primary and backup path are link disjoint (DxE constraints) */ 119 } 120 else if (type11.getString ().equalsIgnoreCase("srgDisjoint")) 121 { 122 final int S = netPlan.getNumberOfSRGs(); 123 if (S == 0) throw new Net2PlanException("No SRG was defined"); 124 125 op.setInputParameter("A_es", netPlan.getMatrixLink2SRGAssignment()); 126 op.setInputParameter("E", E); 127 128 /* Add the decision variables to the problem */ 129 op.addDecisionVariable("x_de", true, new int[] { D, E }, 0, 1); /* 1 if the primary path of demand d, traverses link e */ 130 op.addDecisionVariable("xx_de", true, new int[] { D, E }, 0, 1); /* 1 if the backup path of demand d, traverses link e */ 131 op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* idle capacity in the bottleneck link */ 132 op.addDecisionVariable("x_ds", true, new int[] { D, S }, 0, 1); /* 1 if demand d traverses SRG s in the primary */ 133 op.addDecisionVariable("xx_ds", true, new int[] { D, S }, 0, 1); /* 1 if demand d traverses SRG s in the backup */ 134 135 /* Sets the objective function */ 136 if (optimizationTarget.getString ().equalsIgnoreCase("min-av-num-hops")) 137 { 138 op.setObjectiveFunction("minimize", "sum (h_d * (x_de + xx_de))"); 139 op.addConstraint("h_d * (x_de + xx_de) <= u_e"); /* the capacity constraints summing primary and backup paths (E constraints) */ 140 } 141 else if (optimizationTarget.getString ().equalsIgnoreCase("minimax-link-utilization")) 142 { 143 op.setInputParameter ("EPSILON" , 1e-4); 144 op.addDecisionVariable("rho", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* idle capacity in the bottleneck link */ 145 op.setObjectiveFunction("minimize", "rho + EPSILON * sum(x_de + xx_de)"); 146 op.addConstraint("h_d * (x_de + xx_de) <= rho * u_e"); /* the capacity constraints summing primary and backup paths (E constraints), make that rho becomes the worse case link utilization */ 147 } 148 else if (optimizationTarget.getString ().equalsIgnoreCase("maximin-link-idle-capacity")) 149 { 150 op.setInputParameter ("EPSILON" , 1e-4); 151 op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* idle capacity in the bottleneck link */ 152 op.setObjectiveFunction("maximize", "u - EPSILON * sum (x_de + xx_de)"); 153 op.addConstraint("h_d * (x_de + xx_de) <= u_e - u"); /* the capacity constraints summing primary and backup paths (E constraints) */ 154 } 155 else throw new Net2PlanException ("Unknown optimization target " + optimizationTarget.getString()); 156 157 /* Add constraints */ 158 op.addConstraint("A_ne * (x_de') == A_nd"); /* the flow-conservation constraints for the primary path (NxD constraints) */ 159 op.addConstraint("A_ne * (xx_de') == A_nd"); /* the flow-conservation constraints for the backup path (NxD constraints) */ 160 op.addConstraint("h_d * (x_de + xx_de) <= u_e - u"); /* the capacity constraints summing primary and backup paths (E constraints) */ 161 op.addConstraint("E * x_ds >= x_de * A_es"); /* 1 if demand s traverses SRG s in the primary (DxS constraints) */ 162 op.addConstraint("E * xx_ds >= xx_de * A_es"); /* 1 if demand s traverses SRG s in the nackup (DxS constraints) */ 163 op.addConstraint("x_ds + xx_ds <= 1"); /* the primary and backup path are SRG disjoint (DxS constraints) */ 164 } 165 else throw new Net2PlanException("Wrong type of 1:1 protection"); 166 167 /* Call the solver to solve the problem */ 168 op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ()); 169 170 /* If no solution is found, quit */ 171 if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution"); 172 if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found"); 173 174 /* Retrieve the optimum solutions */ 175 DoubleMatrix2D x_de = op.getPrimalSolution("x_de").view2D(); 176 DoubleMatrix2D xx_de = op.getPrimalSolution("xx_de").view2D(); 177 178 /* Convert the x_de variables into a set of routes for each demand */ 179 List<Demand> primary_demands = new ArrayList<Demand>(); 180 List<List<Link>> primary_seqLinks = new ArrayList<List<Link>>(); 181 List<Double> primary_x_p = new ArrayList<Double>(); 182 GraphUtils.convert_xde2xp(netPlan.getNodes (), netPlan.getLinks () , new TreeSet<> (netPlan.getDemands ()) , x_de, primary_demands, primary_x_p, primary_seqLinks); 183 184 List<Demand> backup_demands = new ArrayList<Demand>(); 185 List<List<Link>> backup_seqLinks = new ArrayList<List<Link>>(); 186 List<Double> backup_x_p = new ArrayList<Double>(); 187 GraphUtils.convert_xde2xp(netPlan.getNodes (), netPlan.getLinks () , new TreeSet<> (netPlan.getDemands ()) , xx_de, backup_demands, backup_x_p, backup_seqLinks); 188 189 /* Update netPlan object adding the calculated routes */ 190 if (primary_demands.size() != D) throw new Net2PlanException("Unexpected error"); 191 if (backup_demands.size() != D) throw new Net2PlanException("Unexpected error"); 192 193 for (Demand demand : netPlan.getDemands()) 194 { 195 /* for each demand, there is one primary and one backup path*/ 196 int primary_p = primary_demands.indexOf(demand); 197 if (primary_p == -1) throw new RuntimeException("Unexpected error"); 198 199 int backup_p = backup_demands.indexOf(demand); 200 if (backup_p == -1) throw new RuntimeException("Unexpected error"); 201 202 final Route route = netPlan.addRoute(demand , demand.getOfferedTraffic() , demand.getOfferedTraffic() , primary_seqLinks.get(primary_p), null); /* add the primary route (primary path) */ 203 final Route backupRoute = netPlan.addRoute (demand , 0.0 , demand.getOfferedTraffic() , backup_seqLinks.get(backup_p), null); /* add the protection segment (backup path) */ 204 route.addBackupRoute(backupRoute); 205 } 206 207 checkSolution(netPlan, type11.getString ()); 208 209 return "Ok!"; 210 } 211 212 @Override 213 public String getDescription() 214 { 215 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 with 1+1 protection to each route, solving a variations of the flow-link formulation. Through a set of input parameters, the user can choose among different optimization targets and constraints."; 216 } 217 218 @Override 219 public List<Triple<String, String, String>> getParameters() 220 { 221 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 222 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 223 } 224 225 /** 226 * Checks if solution is valid. 227 * 228 * @param netPlan Network design 229 * @param type11 Type of 1:1 protection 230 * @since 1.1 231 */ 232 private static void checkSolution(NetPlan netPlan, String type11) 233 { 234 if (!netPlan.getLinksOversubscribed().isEmpty()) throw new Net2PlanException("Bad - Some link is oversubscribed (constraint violated)"); 235 if (!netPlan.getDemandsBlocked().isEmpty()) throw new Net2PlanException("Bad - Some demand is blocked (constraint violated)"); 236 237 for (Route route : netPlan.getRoutesAreNotBackup()) 238 { 239 if (route.getBackupRoutes().size () != 1) throw new RuntimeException("Bad"); 240 241 final Route backupRoute = route.getBackupRoutes().get(0); 242 243 if (type11.equalsIgnoreCase("srgDisjoint")) 244 if (!Collections.disjoint(route.getSRGs(), backupRoute.getSRGs())) 245 throw new RuntimeException("Bad"); 246 else if (type11.equalsIgnoreCase("linkDisjoint")) 247 if (!Collections.disjoint(route.getSeqLinks(), backupRoute.getSeqLinks())) 248 throw new RuntimeException("Bad"); 249 else 250 throw new RuntimeException ("Bad"); 251 } 252 } 253} 254