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 cern.colt.matrix.tdouble.DoubleFactory1D; 024import cern.colt.matrix.tdouble.DoubleMatrix1D; 025import com.jom.OptimizationProblem; 026import com.net2plan.interfaces.networkDesign.*; 027import com.net2plan.utils.Constants.RoutingType; 028import com.net2plan.utils.InputParameter; 029import com.net2plan.utils.Triple; 030 031import java.util.Collections; 032import java.util.List; 033import java.util.Map; 034 035/** 036 * Solves several variants of unicast routing problems with 1+1 protection, with flow-path formulations 037 * @net2plan.description 038 * @net2plan.keywords JOM, Flow-path formulation, Flow assignment (FA), Network recovery: protection 039 * @net2plan.ocnbooksections Section 4.2, Section 4.6.6 040 * @net2plan.inputParameters 041 * @author Pablo Pavon-Marino 042 */ 043public class Offline_fa_xp11PathProtection implements IAlgorithm 044{ 045 private InputParameter k = new InputParameter ("k", (int) 5 , "Maximum number of admissible paths per demand" , 1 , Integer.MAX_VALUE); 046 private InputParameter shortestPathType = new InputParameter ("shortestPathType", "#select# hops km" , "Criteria to compute the shortest path. Valid values: 'hops' or 'km'"); 047 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"); 048 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"); 049 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"); 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 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)"); 053 054 @Override 055 public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters) 056 { 057 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 058 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 059 if (!shortestPathType.getString().equalsIgnoreCase("km") && !shortestPathType.getString().equalsIgnoreCase("hops")) 060 throw new Net2PlanException("Wrong shortestPathType parameter"); 061 if (type11.getString ().equalsIgnoreCase("srgDisjoint") && (netPlan.getNumberOfSRGs() == 0)) throw new Net2PlanException("No SRG was defined"); 062 063 /* Basic checks */ 064 final int N = netPlan.getNumberOfNodes(); 065 final int E = netPlan.getNumberOfLinks(); 066 final int D = netPlan.getNumberOfDemands(); 067 final int S = netPlan.getNumberOfSRGs(); 068 final double PRECISION_FACTOR = Double.parseDouble(net2planParameters.get("precisionFactor")); 069 if (N == 0 || D == 0 || E == 0) throw new Net2PlanException("This algorithm requires a topology with links, and a demand set"); 070 071 /* Remove all unicast routed traffic. Any multicast routed traffic is kept */ 072 netPlan.removeAllUnicastRoutingInformation(); 073 netPlan.setRoutingTypeAllDemands(RoutingType.SOURCE_ROUTING); 074 075 /* Add all the k-shortest candidate routes to the netPlan object carrying no traffic */ 076 final DoubleMatrix1D linkCostVector = shortestPathType.getString().equalsIgnoreCase("hops")? DoubleFactory1D.dense.make (E , 1.0) : netPlan.getVectorLinkLengthInKm(); 077 netPlan.addRoutesFromCandidatePathList(netPlan.computeUnicastCandidatePathList(linkCostVector , k.getInt(), maxLengthInKm.getDouble(), -1, -1, -1, -1, -1 , null)); 078 final int P = netPlan.getNumberOfRoutes(); 079 080 /* Create the optimization problem object (JOM library) */ 081 OptimizationProblem op = new OptimizationProblem(); 082 op.setInputParameter("u_e", netPlan.getVectorLinkSpareCapacity(), "row"); /* for each link, its unused capacity (the one not used by any mulitcast trees) */ 083 op.setInputParameter("A_ep", netPlan.getMatrixLink2RouteAssignment()); /* 1 in position (e,p) if link e is traversed by path p, 0 otherwise */ 084 op.setInputParameter("A_dp", netPlan.getMatrixDemand2RouteAssignment()); /* 1 in position (d,p) if demand d is served by path p, 0 otherwise */ 085 op.setInputParameter("h_d", netPlan.getVectorDemandOfferedTraffic(), "row"); /* for each demand, its offered traffic */ 086 op.setInputParameter("h_p", netPlan.getVectorRouteOfferedTrafficOfAssociatedDemand () , "row"); /* for each path, the offered traffic of its demand */ 087 088 if (type11.getString ().equalsIgnoreCase("linkDisjoint")) 089 op.setInputParameter("A_ps", netPlan.getMatrixLink2RouteAssignment().viewDice ()); /* 1 in position (p,s) if link s is traversed by path p, 0 otherwise */ 090 else if (type11.getString ().equalsIgnoreCase("srgDisjoint")) 091 op.setInputParameter("A_ps", netPlan.getMatrixRoute2SRGAffecting()); /* 1 in position (p,s) if srg s is affecting path p, 0 otherwise */ 092 093 /* Common decision variables */ 094 op.addDecisionVariable("xx_p", true , new int[] { 1, P }, 0, 1); /* 1 if primary path of demand d(p) that is carried by p */ 095 op.addDecisionVariable("bb_p", true , new int[] { 1, P }, 0, 1); /* 1 if backup path of demand d(p) that is carried by p */ 096 097 if (optimizationTarget.getString ().equals ("min-av-num-hops")) 098 { 099 op.setInputParameter("l_p", netPlan.getVectorRouteNumberOfLinks() , "row"); /* for each path, the number of traversed links */ 100 op.setObjectiveFunction("minimize", "sum (l_p .* h_p .* (xx_p + bb_p))"); /* sum of the traffic in the links, proportional to the average number of hops */ 101 op.addConstraint("A_ep * (h_p .* (xx_p + bb_p))' <= u_e'"); /* the traffic in each link cannot exceed its capacity */ 102 } 103 else if (optimizationTarget.getString ().equals ("minimax-link-utilization")) 104 { 105 op.addDecisionVariable("rho", false, new int[] { 1, 1 }, 0, 1); /* worse case link utilization */ 106 op.setObjectiveFunction("minimize", "rho"); 107 op.addConstraint("A_ep * (h_p .* (xx_p + bb_p))' <= rho * u_e'"); /* the traffic in each link cannot exceed its capacity. sets rho as the worse case utilization */ 108 } 109 else if (optimizationTarget.getString ().equals ("maximin-link-idle-capacity")) 110 { 111 op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* worse case link idle capacity */ 112 op.setObjectiveFunction("maximize", "u"); 113 op.addConstraint("A_ep * (h_p .* (xx_p + bb_p))' <= -u + u_e'"); /* the traffic in each link cannot exceed its capacity. sets u as the worse case idle capacity */ 114 } 115 else throw new Net2PlanException ("Unknown optimization target " + optimizationTarget.getString()); 116 117 op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, one primary path exists */ 118 op.addConstraint("A_dp * bb_p' == 1"); /* for each demand, one backup path exists */ 119 op.addConstraint("A_dp * diag(xx_p + bb_p) * A_ps <= 1"); /* primary and backup are link or srg disjoint (depending on what is needed) */ 120 121 /* Call the solver to solve the problem */ 122 op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ()); 123 124 /* If no solution is found, quit */ 125 if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution"); 126 if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found"); 127 128 /* Retrieve the optimum solutions */ 129 double [] xx_p = op.getPrimalSolution("xx_p").to1DArray(); 130 double [] bb_p = op.getPrimalSolution("bb_p").to1DArray(); 131 132 for (Demand d : netPlan.getDemands ()) 133 { 134 Route primary = null; Route backup = null; 135 for (Route r : d.getRoutes()) { if (xx_p [r.getIndex ()] == 1) primary = r; if (bb_p [r.getIndex ()] == 1) backup = r; } 136 if (primary == null) throw new RuntimeException ("Bad"); 137 if (backup == null) throw new RuntimeException ("Bad"); 138 primary.setCarriedTraffic(d.getOfferedTraffic() , d.getOfferedTraffic()); 139 backup.setCarriedTraffic(0 , d.getOfferedTraffic()); 140 primary.addBackupRoute(backup); 141 } 142 143 netPlan.removeAllRoutesUnused(PRECISION_FACTOR); // routes with zero traffic (or close to zero, with PRECISION_FACTOR tolerance) 144 145 checkSolution(netPlan, type11.getString ()); 146 147 return "Ok!"; 148 } 149 150 @Override 151 public String getDescription() 152 { 153 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-path formulation. Initially, a set of admissible candidate paths are computed for each demand, which can be used as either primary or backup paths. Through a set of input parameters, the user can choose among different optimization targets and constraints."; 154 } 155 156 @Override 157 public List<Triple<String, String, String>> getParameters() 158 { 159 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 160 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 161 } 162 163 private static void checkSolution(NetPlan netPlan, String type11) 164 { 165 if (!netPlan.getLinksOversubscribed().isEmpty()) throw new Net2PlanException("Bad - Some link is oversubscribed (constraint violated)"); 166 if (!netPlan.getDemandsBlocked().isEmpty()) throw new Net2PlanException("Bad - Some demand is blocked (constraint violated)"); 167 168 for (Route route : netPlan.getRoutesAreNotBackup()) 169 { 170 if (route.getBackupRoutes().size () != 1) throw new RuntimeException("Bad"); 171 172 final Route backupRoute = route.getBackupRoutes().get(0); 173 174 if (type11.equalsIgnoreCase("srgDisjoint")) 175 if (!Collections.disjoint(route.getSRGs(), backupRoute.getSRGs())) 176 throw new RuntimeException("Bad"); 177 else if (type11.equalsIgnoreCase("linkDisjoint")) 178 if (!Collections.disjoint(route.getSeqLinks(), backupRoute.getSeqLinks())) 179 throw new RuntimeException("Bad"); 180 else 181 throw new RuntimeException ("Bad"); 182 } 183 } 184} 185