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}