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 011package com.net2plan.examples.ocnbook.offline; 012 013import java.util.LinkedList; 014import java.util.List; 015import java.util.Map; 016 017import cern.colt.matrix.tdouble.DoubleFactory1D; 018import cern.colt.matrix.tdouble.DoubleMatrix1D; 019import cern.jet.math.tdouble.DoubleFunctions; 020 021import com.jom.OptimizationProblem; 022import com.net2plan.interfaces.networkDesign.Demand; 023import com.net2plan.interfaces.networkDesign.IAlgorithm; 024import com.net2plan.interfaces.networkDesign.Link; 025import com.net2plan.interfaces.networkDesign.Net2PlanException; 026import com.net2plan.interfaces.networkDesign.NetPlan; 027import com.net2plan.interfaces.networkDesign.Node; 028import com.net2plan.interfaces.networkDesign.Route; 029import com.net2plan.utils.Constants.RoutingType; 030import com.net2plan.utils.InputParameter; 031import com.net2plan.utils.Triple; 032 033/** 034 * In a network with demands of two QoS, jointly optimizes the demand injected traffic and link capacity assigned to each solving a formulation. 035 * @net2plan.description 036 * @net2plan.keywords Bandwidth assignment (BA), Capacity assignment (CA), JOM, NUM 037 * @net2plan.ocnbooksections Section 11.3, Section 6.2 038 * @net2plan.inputParameters 039 * @author Pablo Pavon-Marino 040 */ 041public class Offline_cba_congControLinkBwSplitTwolQoS implements IAlgorithm 042{ 043 private double PRECISIONFACTOR; 044 private InputParameter solverName = new InputParameter ("solverName", "#select# ipopt", "The solver name to be used by JOM. "); 045 private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "" , "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default."); 046 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)"); 047 private InputParameter cc_control_minHd = new InputParameter ("cc_control_minHd", 0.1 , "Minimum traffic assigned to each demand" , 0 , true , Double.MAX_VALUE , true); 048 private InputParameter cc_control_maxHd = new InputParameter ("cc_control_maxHd", 1e6 , "Maximum traffic assigned to each demand" , 0 , true , Double.MAX_VALUE , true); 049 050 private InputParameter cc_control_fairnessFactor_1 = new InputParameter ("cc_control_fairnessFactor_1", 1.0 , "Fairness factor in utility function of congestion control for demands of class 1" , 0 , true , Double.MAX_VALUE , true); 051 private InputParameter cc_control_fairnessFactor_2 = new InputParameter ("cc_control_fairnessFactor_2", 1.0 , "Fairness factor in utility function of congestion control for demands of class 2" , 0 , true , Double.MAX_VALUE , true); 052 private InputParameter cc_control_weightFairness_1 = new InputParameter ("cc_control_weightFairness_1", 1.0 , "Weight factor in utility function demands type 1" , 0 , true , Double.MAX_VALUE , true); 053 private InputParameter cc_control_weightFairness_2 = new InputParameter ("cc_control_weightFairness_2", 2.0 , "Weight factor in utility function demands type 2" , 0 , true , Double.MAX_VALUE , true); 054 private InputParameter mac_minCapacity_1 = new InputParameter ("mac_minCapacity_1", 0.1 , "Minimum capacity in each link, allocated to traffic of type 1" , 0 , true , Double.MAX_VALUE , true); 055 private InputParameter mac_minCapacity_2 = new InputParameter ("mac_minCapacity_2", 0.1 , "Minimum capacity in each link, allocated to traffic of type 2" , 0 , true , Double.MAX_VALUE , true); 056 057 private int N,E,D; 058 private DoubleMatrix1D demandType; 059 060 @Override 061 public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters) 062 { 063 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 064 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 065 066 if (netPlan.getNumberOfLayers() != 1) throw new Net2PlanException ("This algorithm works in single layer networks"); 067 068 this.PRECISIONFACTOR = Double.parseDouble(net2planParameters.get("precisionFactor")); 069 this.N = netPlan.getNumberOfNodes(); 070 this.E = netPlan.getNumberOfLinks(); 071 this.D = 2*N*(N-1); 072 073 /* Remove all demands, then create a demand per input output node pair. One route for it */ 074 netPlan.removeAllDemands(); 075 netPlan.setRoutingType(RoutingType.SOURCE_ROUTING); 076 List<Integer> arrayIndexesOfDemand1 = new LinkedList<Integer> (); 077 List<Integer> arrayIndexesOfDemand2 = new LinkedList<Integer> (); 078 this.demandType = DoubleFactory1D.dense.make (D); 079 for (Node n1 : netPlan.getNodes()) 080 for (Node n2 : netPlan.getNodes()) 081 if (n1 != n2) 082 { 083 final Demand d1 = netPlan.addDemand(n1, n2, 0.0, null); d1.setAttribute("type" , "1"); demandType.set(d1.getIndex (), 1); 084 final Demand d2 = netPlan.addDemand(n1, n2, 0.0, null); d2.setAttribute("type" , "2"); demandType.set(d2.getIndex (), 2); 085 arrayIndexesOfDemand1.add (d1.getIndex ()); 086 arrayIndexesOfDemand2.add (d2.getIndex ()); 087 } 088 089 /* Remove all routes, and create one with the shortest path in km for each demand */ 090 netPlan.removeAllUnicastRoutingInformation(); 091 netPlan.setRoutingType(RoutingType.SOURCE_ROUTING); 092 netPlan.addRoutesFromCandidatePathList(netPlan.getVectorLinkLengthInKm().toArray() , "K" , "1"); 093 094 /* Make the formulation */ 095 final int E = netPlan.getNumberOfLinks(); 096 final int D = netPlan.getNumberOfDemands(); 097 final DoubleMatrix1D u_e = netPlan.getVectorLinkCapacity(); 098 OptimizationProblem op = new OptimizationProblem(); 099 100 op.setInputParameter("b1", 1-cc_control_fairnessFactor_1.getDouble()); 101 op.setInputParameter("b2", 1-cc_control_fairnessFactor_2.getDouble()); 102 op.setInputParameter("w1", cc_control_weightFairness_1.getDouble()); 103 op.setInputParameter("w2", cc_control_weightFairness_2.getDouble()); 104 op.setInputParameter("R_de", netPlan.getMatrixDemand2LinkAssignment()); 105 op.setInputParameter("u_e", u_e , "row"); 106 op.setInputParameter("D1", arrayIndexesOfDemand1 , "row"); 107 op.setInputParameter("D2", arrayIndexesOfDemand2 , "row"); 108 109 op.addDecisionVariable("h_d", false , new int[] { 1 , D }, cc_control_minHd.getDouble() , cc_control_maxHd.getDouble()); 110 op.addDecisionVariable("u_1", false , new int[] { 1 , E }, DoubleFactory1D.dense.make (E , mac_minCapacity_1.getDouble()) , u_e); 111 op.addDecisionVariable("u_2", false , new int[] { 1 , E }, DoubleFactory1D.dense.make (E , mac_minCapacity_2.getDouble()) , u_e); 112 113 String objFunc = ""; 114 if (cc_control_fairnessFactor_1.getDouble() == 1) 115 objFunc += "w1*sum(ln(h_d(D1)))"; 116 else 117 objFunc += "(w1/b1) * sum ( h_d(D1)^b1 ) "; 118 if (cc_control_fairnessFactor_2.getDouble() == 1) 119 objFunc += " + w2*sum(ln(h_d(D2)))"; 120 else 121 objFunc += " + (w2/b2) * sum ( h_d(D2)^b2 ) "; 122 123 op.setObjectiveFunction("maximize", objFunc); 124 125 op.addConstraint("h_d(D1) * R_de(D1,all) <= u_1" , "pie_1"); 126 op.addConstraint("h_d(D2) * R_de(D2,all) <= u_2" , "pie_2"); 127 op.addConstraint("u_1 + u_2 <= u_e"); 128 129 /* Call the solver to solve the problem */ 130 op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ()); 131 132 /* If no solution is found, quit */ 133 if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution"); 134 if (op.foundUnboundedSolution()) throw new Net2PlanException ("Found an unbounded solution"); 135 if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found"); 136 137 /* Retrieve the optimum solutions. Convert the bps into Erlangs */ 138 DoubleMatrix1D h_d = op.getPrimalSolution("h_d").view1D (); 139 DoubleMatrix1D u_1 = op.getPrimalSolution("u_1").view1D (); 140 DoubleMatrix1D u_2 = op.getPrimalSolution("u_2").view1D (); 141 DoubleMatrix1D pie_1 = op.getMultipliersOfConstraint("pie_1").assign(DoubleFunctions.abs).view1D (); 142 DoubleMatrix1D pie_2 = op.getMultipliersOfConstraint("pie_2").assign(DoubleFunctions.abs).view1D (); 143 144 /* Set the demand offered and carried traffic */ 145 for (Demand d : netPlan.getDemands ()) 146 { 147 final double thisDemand_hd = h_d.get(d.getIndex ()); 148 d.setOfferedTraffic(thisDemand_hd); 149 d.getRoutes().iterator().next().setCarriedTraffic(thisDemand_hd , thisDemand_hd); 150 } 151 /* Set the link capacity split and multipliers */ 152 for (Link e : netPlan.getLinks()) 153 { 154 e.setAttribute("u_1", "" + u_1.get(e.getIndex ())); 155 e.setAttribute("u_2", "" + u_2.get(e.getIndex ())); 156 e.setAttribute("pie_1", "" + pie_1.get(e.getIndex ())); 157 e.setAttribute("pie_2", "" + pie_2.get(e.getIndex ())); 158 } 159 160 /* Check link capacities */ 161 for (Link e : netPlan.getLinks()) 162 { 163 double traf1 = 0 ; double traf2 = 0; 164 for (Route r : e.getTraversingRoutes()) 165 if (demandType.get(r.getDemand().getIndex ()) == 1) traf1 += r.getCarriedTraffic(); else traf2 += r.getCarriedTraffic(); 166 if (traf1 > u_1.get (e.getIndex ()) + PRECISIONFACTOR) throw new RuntimeException ("Bad"); 167 if (traf2 > u_2.get (e.getIndex ()) + PRECISIONFACTOR) throw new RuntimeException ("Bad"); 168 if (u_1.get(e.getIndex ()) + u_2.get(e.getIndex ()) > e.getCapacity() + PRECISIONFACTOR) throw new RuntimeException ("Bad"); 169 } 170 171 /* Compute the network utility */ 172 double netUtil = 0; 173 for (Demand d : netPlan.getDemands()) 174 { 175 final double thisDemand_hd = h_d.get(d.getIndex ()); 176 if (d.getRoutes ().size() != 1) throw new RuntimeException ("Bad"); 177 if (Math.abs (d.getCarriedTraffic() - d.getOfferedTraffic()) > 1e-3) throw new RuntimeException ("Bad"); 178 if (demandType.get(d.getIndex ()) == 1) 179 netUtil += cc_control_weightFairness_1.getDouble () * ((cc_control_fairnessFactor_1.getDouble () == 1)? Math.log(thisDemand_hd) : 1/(1-cc_control_fairnessFactor_1.getDouble ()) * Math.pow(thisDemand_hd, 1-cc_control_fairnessFactor_1.getDouble ())); 180 else 181 netUtil += cc_control_weightFairness_2.getDouble () * ((cc_control_fairnessFactor_2.getDouble () == 1)? Math.log(thisDemand_hd) : 1/(1-cc_control_fairnessFactor_2.getDouble ()) * Math.pow(thisDemand_hd, 1-cc_control_fairnessFactor_2.getDouble ())); 182 } 183 184 netPlan.setAttribute("netUtility" , "" + netUtil); 185 186 return "Ok! Optimal net utility: " + netUtil; 187 } 188 189 @Override 190 public String getDescription() 191 { 192 return "Given a network with a set of given nodes. The algorithm first creates two demands for each node pair, one of traffic type 1 and one of traffic type 2. The routing of each demand is known. A shortest-path route is assigned to each demand. We assume that, in order to enforce a strict QoS to the two types of traffic, the capacity in each link is split into two parts, one for each traffic type. Then, this algorithm will jointly optimize: (i) the traffic to inject by each demand, and (ii) the capacity in each link assigned to traffic of class 1 and class 2. The solution is found solving a problem formulation with JOM. The optimization target is finding a fair allocation using the NUM model, where the utility functions of demands of type 1 and type 2 are different."; 193 } 194 195 @Override 196 public List<Triple<String, String, String>> getParameters() 197 { 198 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 199 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 200 } 201}