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