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.List; 014import java.util.Map; 015 016import cern.colt.matrix.tdouble.DoubleFactory1D; 017import cern.colt.matrix.tdouble.DoubleMatrix1D; 018import cern.jet.math.tdouble.DoubleFunctions; 019 020import com.jom.OptimizationProblem; 021import com.net2plan.interfaces.networkDesign.Demand; 022import com.net2plan.interfaces.networkDesign.IAlgorithm; 023import com.net2plan.interfaces.networkDesign.Net2PlanException; 024import com.net2plan.interfaces.networkDesign.NetPlan; 025import com.net2plan.utils.Constants.RoutingType; 026import com.net2plan.utils.InputParameter; 027import com.net2plan.utils.Triple; 028 029/** 030 * Solves the congestion control problem using a NUM formulation. 031 * @net2plan.description 032 * @net2plan.keywords Bandwidth assignment (BA), JOM, NUM, TCP 033 * @net2plan.ocnbooksections Section 6.2, Section 6.3 034 * @net2plan.inputParameters 035 * @author Pablo Pavon-Marino 036 */ 037public class Offline_ba_numFormulations implements IAlgorithm 038{ 039 private InputParameter shortestPathType = new InputParameter ("shortestPathType", "#select# hops km" , "Criteria to compute the shortest path. Valid values: 'hops' or 'km'"); 040 private InputParameter alphaFairnessFactor = new InputParameter ("alphaFairnessFactor", (double) 2 , "Fairness alpha factor" , 0 , true , Double.MAX_VALUE , true); 041 private InputParameter utilityFunctionType = new InputParameter ("utilityFunctionType", "#select# alphaFairness TCP-Reno TCP-Vegas", "The type of utility function of each demand, in the NUM problem to solve: standard alpha-fairness (alpha parameter is given by alphaFairnessFactor), an utility function suitable for TCP-Reno NUM model (each demand is a TCP connection) and the same for TCP-Vegas"); 042 private InputParameter solverName = new InputParameter ("solverName", "#select# ipopt glpk cplex", "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 can solve nonlinear problems (if convex, returns global optimum), but cannot handle integer constraints"); 043 private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "" , "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default."); 044 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)"); 045 046 @Override 047 public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters) 048 { 049 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 050 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 051 if (!shortestPathType.getString().equalsIgnoreCase("km") && !shortestPathType.getString().equalsIgnoreCase("hops")) 052 throw new Net2PlanException("Wrong shortestPathType parameter"); 053 054 /* Initialize variables */ 055 final int E = netPlan.getNumberOfLinks(); 056 final int D = netPlan.getNumberOfDemands(); 057 final double PRECISION_FACTOR = Double.parseDouble(net2planParameters.get("precisionFactor")); 058 if (E == 0 || D == 0) throw new Net2PlanException("This algorithm requires a topology with links and a demand set"); 059 060 /* Remove all unicast routed traffic. Any multicast routed traffic is kept */ 061 netPlan.removeAllUnicastRoutingInformation(); 062 netPlan.setRoutingType(RoutingType.SOURCE_ROUTING); 063 064 /* Add all the k-shortest candidate routes to the netPlan object carrying no traffic */ 065 final DoubleMatrix1D linkCostVector = shortestPathType.getString().equalsIgnoreCase("hops")? DoubleFactory1D.dense.make (E , 1.0) : netPlan.getVectorLinkLengthInKm(); 066 netPlan.addRoutesFromCandidatePathList(linkCostVector.toArray() , "K", "1"); // one route per demand, so P equals D 067 final int P = netPlan.getNumberOfRoutes(); 068 069 /* Create the optimization problem object (JOM library) */ 070 OptimizationProblem op = new OptimizationProblem(); 071 072 /* Set some input parameters to the problem */ 073 op.setInputParameter("u_e", netPlan.getVectorLinkSpareCapacity(), "row"); /* for each link, its unused capacity (the one not used by any mulitcast trees) */ 074 op.setInputParameter("A_ep", netPlan.getMatrixLink2RouteAssignment()); /* 1 in position (e,p) if link e is traversed by path p, 0 otherwise */ 075 op.addDecisionVariable("h_p", false , new int[] { 1, P }, 0, Double.MAX_VALUE); /* the traffic carried by the demand in the macroscopic equilibrium */ 076 op.addConstraint("A_ep * h_p' <= u_e'" , "pi_e"); // the capacity constraints (E constraints) 077 078 /* Write the problem formulations */ 079 if (utilityFunctionType.getString ().equals ("alphaFairness")) 080 { 081 op.setInputParameter("oneMinusAlpha", 1-alphaFairnessFactor.getDouble()); 082 if (alphaFairnessFactor.getDouble() == 1) 083 op.setObjectiveFunction("maximize", "sum(ln(h_p))"); 084 else if (alphaFairnessFactor.getDouble() == 0) 085 op.setObjectiveFunction("maximize", "sum(h_p)"); 086 else 087 op.setObjectiveFunction("maximize", "(1/oneMinusAlpha) * sum(h_p ^ oneMinusAlpha)"); 088 089 } 090 else if (utilityFunctionType.getString ().equals ("TCP-Reno")) 091 { 092 op.setInputParameter("rtt_p", netPlan.getVectorRoutePropagationDelayInMiliseconds().assign (DoubleFunctions.mult (2)) , "row"); /* round-trip-time in miliseconds for each connection */ 093 op.setObjectiveFunction("maximize", "sum (-1.5 / (rtt_p .* h_p))"); 094 } 095 else if (utilityFunctionType.getString ().equals ("TCP-Vegas")) 096 { 097 op.setObjectiveFunction("maximize", "sum(ln(h_p))"); 098 } 099 else throw new Net2PlanException ("Unknown optimization target " + utilityFunctionType.getString()); 100 101 /* Call the solver to solve the problem */ 102 op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ()); 103 104 /* If no solution is found, quit */ 105 if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution"); 106 if (op.foundUnboundedSolution()) throw new Net2PlanException ("Found an unbounded solution"); 107 if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found"); 108 109 /* Save the solution found in the netPlan object */ 110 final DoubleMatrix1D h_p = op.getPrimalSolution("h_p").view1D(); 111 netPlan.setVectorRouteCarriedTrafficAndOccupiedLinkCapacities(h_p , h_p); 112 for (Demand d : netPlan.getDemands ()) d.setOfferedTraffic(d.getCarriedTraffic()); // make the offered traffic equal to the carried traffic 113 114 System.out.println ("Total carried traffic: " + netPlan.getVectorDemandOfferedTraffic().zSum()); 115 System.out.println ("Network utility: " + op.getOptimalCost()); 116 117 return "Ok!: The solution found is guaranteed to be optimal: " + op.solutionIsOptimal() + ". Total carried traffic: " + netPlan.getVectorDemandOfferedTraffic().zSum() + ", Network utility: " + op.getOptimalCost(); 118 } 119 120 @Override 121 public String getDescription() 122 { 123 return "Given a network topology, the capacities in the links, and the set of unicast demands, this algorithm assigns the shortest path route to each demand, then optimizes the traffic to inject by each demand (that is, assigns bandwidth), with different optimization targets based on some form of fairness in resource allocation"; 124 } 125 126 127 @Override 128 public List<Triple<String, String, String>> getParameters() 129 { 130 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 131 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 132 } 133}