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