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.list.tdouble.DoubleArrayList; 024import cern.colt.list.tint.IntArrayList; 025import cern.colt.matrix.tdouble.DoubleFactory1D; 026import cern.colt.matrix.tdouble.DoubleMatrix1D; 027import cern.colt.matrix.tdouble.DoubleMatrix2D; 028import cern.colt.matrix.tdouble.DoubleMatrix3D; 029import com.jom.DoubleMatrixND; 030import com.jom.OptimizationProblem; 031import com.net2plan.interfaces.networkDesign.*; 032import com.net2plan.utils.Constants.RoutingType; 033import com.net2plan.utils.InputParameter; 034import com.net2plan.utils.Triple; 035 036import java.util.List; 037import java.util.Map; 038 039/** 040 * Solves several variants of unicast routing problems with flow-link formulations, so that designs are fault tolerant to a set of failure states, using shared restoration 041 * @net2plan.description 042 * @net2plan.keywords JOM, Flow-link formulation, Flow assignment (FA), Network recovery: restoration 043 * @net2plan.ocnbooksections Section 4.3, Section 4.6.7 044 * @net2plan.inputParameters 045 * @author Pablo Pavon-Marino 046 */ 047public class Offline_fa_xdeSharedRestoration implements IAlgorithm 048{ 049 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"); 050 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"); 051 private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "", "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default."); 052 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)"); 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 (netPlan.getNumberOfSRGs() == 0) throw new Net2PlanException("No SRG was defined"); 060 061 /* Basic checks */ 062 final int N = netPlan.getNumberOfNodes(); 063 final int E = netPlan.getNumberOfLinks(); 064 final int D = netPlan.getNumberOfDemands(); 065 final int S = netPlan.getNumberOfSRGs(); 066 if (N == 0 || D == 0 || E == 0) throw new Net2PlanException("This algorithm requires a topology with links, and a demand set"); 067 068 /* Remove all unicast routed traffic. Any multicast routed traffic is kept */ 069 netPlan.removeAllUnicastRoutingInformation(); 070 netPlan.setRoutingTypeAllDemands(RoutingType.SOURCE_ROUTING); 071 072 /* Initialize some variables */ 073 DoubleMatrix1D u_e = netPlan.getVectorLinkSpareCapacity(); // just the unused capacity (some capacity may be used by multicast traffic) 074 DoubleMatrix1D h_d = netPlan.getVectorDemandOfferedTraffic(); 075 076 /* Create the optimization problem object (JOM library) */ 077 OptimizationProblem op = new OptimizationProblem(); 078 op.setInputParameter("E", E); 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("onesS", DoubleFactory1D.dense.make (S , 1.0) , "row"); 083 op.setInputParameter("A_nd", netPlan.getMatrixNodeDemandIncidence()); 084 op.setInputParameter("A_es", netPlan.getMatrixLink2SRGAssignment()); 085 DoubleMatrixND A_des = new DoubleMatrixND (new int []{D,E,S} , "sparse"); for (SharedRiskGroup srg : netPlan.getSRGs()) for (Link e : srg.getAffectedLinksAllLayers()) for (int d = 0; d < D ; d ++) A_des.set(new int [] {d,e.getIndex (),srg.getIndex()} , 1.0); 086 DoubleMatrixND A_nds = new DoubleMatrixND (new int []{N,D,S} , "sparse"); for (Demand d : netPlan.getDemands()) for (int s = 0; s < S ; s ++) { A_nds.set(new int [] {d.getIngressNode().getIndex(),d.getIndex(),s}, 1.0); A_nds.set(new int [] {d.getEgressNode().getIndex(),d.getIndex(),s}, -1.0); } 087 op.setInputParameter("A_des", A_des); 088 op.setInputParameter("A_nds", A_nds); 089 090 /* Add the decision variables to the problem */ 091 op.addDecisionVariable("xx_de", true, new int[] { D, E }, 0, 1); /* 1 if the primary path of demand d, traverses link e */ 092 op.addDecisionVariable("xx_des", true, new int[] { D, E , S }, 0, 1); /* 1 if the primary path of demand d, traverses link e */ 093 094 /* Sets the objective function */ 095 if (optimizationTarget.getString ().equalsIgnoreCase("min-av-num-hops")) 096 { 097 op.setObjectiveFunction("minimize", "sum (h_d * xx_de)"); 098 op.addConstraint("h_d * xx_de <= u_e"); /* the capacity constraints in the no-failure state */ 099 op.addConstraint("sum (diag(h_d) * xx_des , 1) <= u_e' * onesS"); /* the capacity constraints summing primary and backup paths (E constraints), make that rho becomes the worse case link utilization */ 100 } 101 else if (optimizationTarget.getString ().equalsIgnoreCase("minimax-link-utilization")) 102 { 103 op.setInputParameter ("EPSILON" , 1e-4); 104 op.addDecisionVariable("rho", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* idle capacity in the bottleneck link in any failure state */ 105 op.setObjectiveFunction("minimize", "rho + EPSILON * sum(xx_de) + EPSILON * sum(xx_des) "); 106 op.addConstraint("h_d * xx_de <= rho * u_e"); /* the capacity constraints in the no-failure state */ 107 op.addConstraint("sum (diag(h_d) * xx_des , 1) <= rho * u_e' * onesS"); /* the capacity constraints summing primary and backup paths (E constraints), make that rho becomes the worse case link utilization */ 108 } 109 else if (optimizationTarget.getString ().equalsIgnoreCase("maximin-link-idle-capacity")) 110 { 111 op.setInputParameter ("EPSILON" , 1e-4); 112 op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* idle capacity in the bottleneck link */ 113 op.setObjectiveFunction("maximize", "u - EPSILON * sum(xx_de) - EPSILON * sum(xx_des)"); 114 op.addConstraint("h_d * xx_de <= -u + u_e"); /* the capacity constraints in the no-failure state */ 115 op.addConstraint("sum (diag(h_d) * xx_des , 1) <= -u + u_e' * onesS"); /* the capacity constraints summing primary and backup paths (E constraints), make that rho becomes the worse case link utilization */ 116 } 117 else throw new Net2PlanException ("Unknown optimization target " + optimizationTarget.getString()); 118 119 /* Add constraints */ 120 op.addConstraint("A_ne * xx_de' == A_nd"); /* flow conservation constraints for the non-failure state */ 121 op.addConstraint("A_ne * permute(xx_des,[2;1;3]) == A_nds"); /* flow conservation constraints in all the failure states */ 122 op.addConstraint("xx_des <= 1 - A_des"); /* failing links do not carry traffic */ 123 124 DoubleMatrixND I_sse = new DoubleMatrixND (new int [] {S,S,E}); 125 DoubleMatrixND I_ees = new DoubleMatrixND (new int [] {E,E,S}); 126 for (int e = 0 ; e < E ; e ++) for (int s = 0 ; s < S ; s ++) { I_sse.set (new int [] { s,s,e } ,1.0); I_ees.set (new int [] { e,e,s } ,1.0); } 127 op.setInputParameter("I_sse" , I_sse); 128 op.setInputParameter("I_ees" , I_ees); 129 op.setInputParameter("onesE" , DoubleFactory1D.dense.make(E,1) , "row"); 130 131 /* If a demand does not traverse a changing link in failure state s, keep the same routing as in no-failure state */ 132 op.addConstraint("- permute((xx_de * A_es) * I_sse , [1;3;2]) <= xx_des - xx_de * I_ees "); 133 op.addConstraint(" permute((xx_de * A_es) * I_sse , [1;3;2]) >= xx_des - xx_de * I_ees "); 134 135 /* Call the solver to solve the problem */ 136 op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ()); 137 138 /* If no solution is found, quit */ 139 if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution"); 140 if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found"); 141 142 /* Retrieve the optimum solutions */ 143 DoubleMatrix2D xx_de = op.getPrimalSolution("xx_de").view2D(); 144 DoubleMatrix3D xx_des = op.getPrimalSolution("xx_des").view3D("sparse"); 145 146 netPlan.setRoutingFromDemandLinkCarriedTraffic(xx_de , true , false , null); 147 148 checkSolution(netPlan, xx_de , xx_des); 149 150 return "Ok!"; 151 } 152 153 @Override 154 public String getDescription() 155 { 156 return "Given a network topology, the capacities in the links and the offered traffic, this algorithm obtains a link-disjoint or a SRG-disjoint (depending on user's choice) primary and backup path for the traffic of each demand, that minimizes the network congestion, with the constraint of non-bifurcated routing. For that it solves an ILP flow-link formulation (more complex in the SRG-disjoint case). In this algorithm, congestion is minimized by maximizing the idle link capacity in the bottleneck (the link with less idle capacity)."; 157 } 158 159 @Override 160 public List<Triple<String, String, String>> getParameters() 161 { 162 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 163 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 164 } 165 166 private static void checkSolution(NetPlan netPlan, DoubleMatrix2D xx_de , DoubleMatrix3D xx_des) 167 { 168 if (!netPlan.getLinksOversubscribed().isEmpty()) throw new Net2PlanException("Bad - Some link is oversubscribed (constraint violated)"); 169 if (!netPlan.getDemandsBlocked().isEmpty()) throw new Net2PlanException("Bad - Some demand is blocked (constraint violated)"); 170 171 for (SharedRiskGroup srg : netPlan.getSRGs()) 172 { 173 NetPlan npThis = netPlan.copy (); 174 npThis.removeAllUnicastRoutingInformation(); 175 DoubleMatrix2D this_xxde = xx_des.viewColumn (srg.getIndex ()).copy (); 176 for (Link e : srg.getAffectedLinksAllLayers()) if (this_xxde.viewColumn(e.getIndex ()).zSum () != 0) throw new Net2PlanException("Bad - some failing links carry traffic"); 177 npThis.setRoutingFromDemandLinkCarriedTraffic(this_xxde , true , false , null); 178 if (!npThis.getLinksOversubscribed().isEmpty()) throw new Net2PlanException("Bad - Some link is oversubscribed (constraint violated) in a failure"); 179 if (!npThis.getDemandsBlocked().isEmpty()) throw new Net2PlanException("Bad - Some demand is blocked (constraint violated) in a failure"); 180 for (Demand d : netPlan.getDemands ()) 181 { 182 IntArrayList es_noFailure = new IntArrayList (); xx_de.viewRow (d.getIndex ()).getNonZeros(es_noFailure , new DoubleArrayList ()); 183 boolean affectedByThisFailure = false; for (Link e : srg.getAffectedLinksAllLayers()) if (xx_de.get(d.getIndex() , e.getIndex ()) != 0) { affectedByThisFailure = true; break; } 184 if (!affectedByThisFailure) 185 { 186 IntArrayList es_thisFailure = new IntArrayList (); this_xxde.viewRow (d.getIndex ()).getNonZeros(es_thisFailure , new DoubleArrayList ()); 187 if (!es_noFailure.equals(es_thisFailure)) throw new Net2PlanException("Routing cannot change when a demand is not affected by the failure"); 188 } 189 } 190 } 191 } 192} 193