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.matrix.tdouble.DoubleFactory1D; 024import cern.colt.matrix.tdouble.DoubleMatrix1D; 025import cern.jet.math.tdouble.DoubleFunctions; 026 027import com.jom.OptimizationProblem; 028import com.net2plan.interfaces.networkDesign.Configuration; 029import com.net2plan.interfaces.networkDesign.IAlgorithm; 030import com.net2plan.interfaces.networkDesign.Net2PlanException; 031import com.net2plan.interfaces.networkDesign.NetPlan; 032import com.net2plan.utils.DoubleUtils; 033import com.net2plan.utils.InputParameter; 034import com.net2plan.utils.Triple; 035 036/** 037 * Solves several variants of multicast routing problems, with flow-path formulations 038 * @net2plan.description 039 * @net2plan.keywords Multicast, JOM, Flow-path formulation, Flow assignment (FA) 040 * @net2plan.ocnbooksections Section 4.6.2 041 * @net2plan.inputParameters 042 * @author Pablo Pavon-Marino 043 */ 044public class Offline_fa_xpFormulationsMulticast implements IAlgorithm 045{ 046 private InputParameter linkCostType = new InputParameter ("linkCostType", "#select# hops km" , "Criteria to compute the multicast tree cost. Valid values: 'hops' (all links cost one) or 'km' (link cost is its length in km)"); 047 private InputParameter optimizationTarget = new InputParameter ("optimizationTarget", "#select# min-consumed-bandwidth min-av-num-hops minimax-link-utilization maximin-link-idle-capacity min-av-network-blocking" , "Type of optimization target. Choose among minimize the total traffic in the links, minimize the average number of hops from ingress to different egress nodes, minimize the highest link utilization, maximize the lowest link idle capacity, and minimize the average network blocking assuming independent Erlang-B blocking in each link, load sharing model"); 048 private InputParameter nonBifurcatedRouting = new InputParameter ("nonBifurcatedRouting", false , "True if the routing is constrained to be non-bifurcated"); 049 private InputParameter k = new InputParameter ("k", (int) 5 , "Maximum number of admissible multicast trees per demand" , 1 , Integer.MAX_VALUE); 050 private InputParameter maxCopyCapability = new InputParameter ("maxCopyCapability", (int) -1 , "Maximum number of copies of the traffic a node can make (this is the maximum number of output links in a node of the same multicast tree). A non-positive value means no limit"); 051 private InputParameter maxE2ELengthInKm = new InputParameter ("maxLengthInKm", (double) -1 , "The path from an origin to any destination in any multicast tree cannot be longer than this. A non-positive number means this limit does not exist"); 052 private InputParameter maxE2ENumHops = new InputParameter ("maxE2ENumHops", (int) -1 , "The path from an origin to any destination in any multicast tree cannot have more than this number of hops. A non-positive number means this limit does not exist"); 053 private InputParameter maxE2EPropDelayInMs = new InputParameter ("maxE2EPropDelayInMs", (double) -1 , "The path from an origin to any destination in any multicast tree cannot have more than this propagation delay in miliseconds. A non-positive number means this limit does not exist"); 054 private InputParameter maxTreeCost = new InputParameter ("maxTreeCost", (double) -1 , "The trees with a cost (measured as stated by linkCostType) are considered not admissible. A non-positive number means this limit does not exist"); 055 private InputParameter maxTreeCostFactorRespectToMinimumCostTree = new InputParameter ("maxTreeCostFactorRespectToMinimumCostTree", (double) -1 , "The trees with a cost (measured as stated by linkCostType) higher than this factor multiplied by the cost of the minimum cost multicast tree for that demand, are considered not admissible. A non-positive number means this limit does not exist"); 056 private InputParameter maxTreeCostRespectToMinimumCostTree = new InputParameter ("maxTreeCostRespectToMinimumCostTree", (double) -1 , "The trees with a cost (measured as stated by linkCostType) higher than this parameter plus the cost of the minimum cost multicast tree for that demand, are considered not admissible. A non-positive number means this limit does not exist"); 057 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"); 058 private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "" , "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default."); 059 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)"); 060 061 @Override 062 public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters) 063 { 064 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 065 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 066 if (!linkCostType.getString().equalsIgnoreCase("km") && !linkCostType.getString().equalsIgnoreCase("hops")) 067 throw new Net2PlanException("Wrong linkCostType parameter"); 068 069 /* Initialize variables */ 070 final int E = netPlan.getNumberOfLinks(); 071 final int MD = netPlan.getNumberOfMulticastDemands(); 072 final double PRECISION_FACTOR = Double.parseDouble(net2planParameters.get("precisionFactor")); 073 if (E == 0 || MD == 0) throw new Net2PlanException("This algorithm requires a topology with links and a multicast demand set"); 074 075 /* Remove all multicast routed traffic. Any unicast routed traffic is kept */ 076 netPlan.removeAllMulticastTrees(); 077 078 /* Add all the k-shortest candidate routes to the netPlan object carrying no traffic */ 079 final DoubleMatrix1D linkCostVector = linkCostType.getString().equalsIgnoreCase("hops")? DoubleFactory1D.dense.make (E , 1.0) : netPlan.getVectorLinkLengthInKm(); 080 081 netPlan.addMulticastTreesFromCandidateTreeList(netPlan.computeMulticastCandidatePathList(linkCostVector , solverName.getString() , solverLibraryName.getString () , maxSolverTimeInSeconds.getDouble () , 082 "K", Integer.toString(k.getInt ()), 083 "maxCopyCapability", Integer.toString(maxCopyCapability.getInt ()) , 084 "maxE2ELengthInKm", Double.toString(maxE2ELengthInKm.getDouble ()) , 085 "maxE2ENumHops", Integer.toString(maxE2ENumHops.getInt ()) , 086 "maxE2EPropDelayInMs", Double.toString(maxE2EPropDelayInMs.getDouble ()) , 087 "maxTreeCost", Double.toString(maxTreeCost.getDouble ()) , 088 "maxTreeCostFactorRespectToMinimumCostTree", Double.toString(maxTreeCostFactorRespectToMinimumCostTree.getDouble ()) , 089 "maxTreeCostRespectToMinimumCostTree", Double.toString(maxTreeCostRespectToMinimumCostTree.getDouble ()))); 090 final int P = netPlan.getNumberOfMulticastTrees(); 091 092 System.out.println ("Number of multicast trees CPL: " + P); 093 094 /* Create the optimization problem object (JOM library) */ 095 OptimizationProblem op = new OptimizationProblem(); 096 097 /* Set some input parameters to the problem */ 098 op.setInputParameter("u_e", netPlan.getVectorLinkSpareCapacity(), "row"); /* for each link, its unused capacity (the one not used by any mulitcast trees) */ 099 op.setInputParameter("A_dp", netPlan.getMatrixMulticastDemand2MulticastTreeAssignment()); /* 1 in position (d,p) if demand d is served by tree p, 0 otherwise */ 100 op.setInputParameter("A_ep", netPlan.getMatrixLink2MulticastTreeAssignment()); /* 1 in position (e,p) if link e is traversed by tree p, 0 otherwise */ 101 op.setInputParameter("h_d", netPlan.getVectorMulticastDemandOfferedTraffic(), "row"); /* for each multicast demand, its offered traffic */ 102 op.setInputParameter("h_p", netPlan.getVectorMulticastTreeOfferedTrafficOfAssociatedMulticastDemand () , "row"); /* for each tree, the offered traffic of its demand */ 103 104 /* Write the problem formulations */ 105 106 if (optimizationTarget.getString ().equals ("min-consumed-bandwidth")) 107 { 108 op.addDecisionVariable("xx_p", nonBifurcatedRouting.getBoolean() , new int[] { 1, P }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p */ 109 op.setObjectiveFunction("minimize", "sum (h_p .* xx_p)"); /* sum of the traffic in the links, proportional to the average number of hops */ 110 op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) */ 111 op.addConstraint("A_ep * (h_p .* xx_p)' <= u_e'"); /* the traffic in each link cannot exceed its capacity */ 112 } 113 else if (optimizationTarget.getString ().equals ("min-av-num-hops")) 114 { 115 op.setInputParameter("l_p", netPlan.getVectorMulticastTreeAverageNumberOfHops() , "row"); /* for each tree, the average number of traversed from the ingress, to the different destinations */ 116 op.addDecisionVariable("xx_p", nonBifurcatedRouting.getBoolean() , new int[] { 1, P }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p */ 117 op.setObjectiveFunction("minimize", "sum (l_p .* h_p .* xx_p)"); /* sum of the traffic in the links, proportional to the average number of hops */ 118 op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) */ 119 op.addConstraint("A_ep * (h_p .* xx_p)' <= u_e'"); /* the traffic in each link cannot exceed its capacity */ 120 } 121 else if (optimizationTarget.getString ().equals ("minimax-link-utilization")) 122 { 123 op.addDecisionVariable("xx_p", nonBifurcatedRouting.getBoolean(), new int[] { 1, P }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p */ 124 op.addDecisionVariable("rho", false, new int[] { 1, 1 }, 0, 1); /* worse case link utilization */ 125 op.setObjectiveFunction("minimize", "rho"); 126 op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) */ 127 op.addConstraint("A_ep * (h_p .* xx_p)' <= rho * u_e'"); /* the traffic in each link cannot exceed its capacity. sets rho as the worse case utilization */ 128 } 129 else if (optimizationTarget.getString ().equals ("maximin-link-idle-capacity")) 130 { 131 op.addDecisionVariable("xx_p", nonBifurcatedRouting.getBoolean() , new int[] { 1, P }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p */ 132 op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* worse case link idle capacity */ 133 op.setObjectiveFunction("maximize", "u"); 134 op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) */ 135 op.addConstraint("A_ep * (h_p .* xx_p)' <= -u + u_e'"); /* the traffic in each link cannot exceed its capacity. sets u as the worse case idle capacity */ 136 } 137 else if (optimizationTarget.getString ().equals ("min-av-network-blocking")) 138 { 139 if (!solverName.getString ().equalsIgnoreCase("ipopt") || nonBifurcatedRouting.getBoolean()) throw new Net2PlanException ("This is a convex non linear model: please use IPOPT solver. The routing cannot be constrained to be non-bifurcated"); 140 op.addDecisionVariable("xx_p", false , new int[] { 1, P }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p */ 141 op.addDecisionVariable("y_e", false, new int[] { 1, E }, DoubleUtils.zeros(E), netPlan.getVectorLinkCapacity().toArray()); /* traffic in the links (already limited to the link capacity) */ 142 op.setObjectiveFunction("minimize", "sum(y_e .* erlangB(y_e, u_e))"); 143 op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) */ 144 op.addConstraint("A_ep * (h_p .* xx_p)' == y_e'"); /* sets y_e as the traffic in link e */ 145 } 146 else throw new Net2PlanException ("Unknown optimization target " + optimizationTarget.getString()); 147 148 System.out.println ("solverLibraryName: " + solverLibraryName.getString ()); 149 op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ()); 150 //op.solve(solverName.getString (), "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ()); 151 152 System.out.println ("solverLibraryName: " + solverLibraryName.getString ()); 153 154 /* If no solution is found, quit */ 155 if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution"); 156 if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found"); 157 158 /* Save the solution found in the netPlan object */ 159 final DoubleMatrix1D h_p = netPlan.getVectorMulticastTreeOfferedTrafficOfAssociatedMulticastDemand(); 160 final DoubleMatrix1D xx_p = DoubleFactory1D.dense.make (op.getPrimalSolution("xx_p").to1DArray()); 161 final DoubleMatrix1D x_p = xx_p.copy().assign (h_p , DoubleFunctions.mult); 162 netPlan.setVectorMulticastTreeCarriedTrafficAndOccupiedLinkCapacities(x_p , x_p); 163 164 netPlan.removeAllMulticastTreesUnused(PRECISION_FACTOR); // trees with zero traffic (or close to zero, with PRECISION_FACTOR tolerance) 165 166 return "Ok!: The solution found is guaranteed to be optimal (among the given candidate tree list): " + op.solutionIsOptimal() + ". Number multicast trees = " + netPlan.getNumberOfMulticastTrees(); 167 } 168 169 @Override 170 public String getDescription() 171 { 172 return "Given a network topology, the capacities in the links, and a set multicast traffic demands, this algorithm permits computing the optimum multicast routing of the traffic (that is, the set ofm multicast trees carrying the traffic of the multicast demand) solving flow-path formulations, that start computing a set of admissible multicast trees (using integer formulations), and then solve the routing problem over them. Through a set of input parameters, the user can choose among different optimization targets and constraints."; 173 } 174 175 176 @Override 177 public List<Triple<String, String, String>> getParameters() 178 { 179 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 180 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 181 } 182}