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}