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.HashSet;
021import java.util.List;
022import java.util.Map;
023import java.util.Set;
024
025import cern.colt.matrix.tdouble.DoubleFactory1D;
026import cern.colt.matrix.tdouble.DoubleMatrix2D;
027
028import com.jom.DoubleMatrixND;
029import com.jom.OptimizationProblem;
030import com.net2plan.interfaces.networkDesign.Configuration;
031import com.net2plan.interfaces.networkDesign.Demand;
032import com.net2plan.interfaces.networkDesign.IAlgorithm;
033import com.net2plan.interfaces.networkDesign.Link;
034import com.net2plan.interfaces.networkDesign.MulticastDemand;
035import com.net2plan.interfaces.networkDesign.Net2PlanException;
036import com.net2plan.interfaces.networkDesign.NetPlan;
037import com.net2plan.interfaces.networkDesign.Node;
038import com.net2plan.utils.InputParameter;
039import com.net2plan.utils.Triple;
040
041/**
042 * Solves several variants of multicast routing problems, with flow-link formulations
043 * @net2plan.description
044 * @net2plan.keywords Multicast, JOM, Flow-link formulation, Flow assignment (FA)
045 * @net2plan.ocnbooksections Section 4.6.2
046 * @net2plan.inputParameters 
047 * @author Pablo Pavon-Marino
048 */
049public class Offline_fa_xdeFormulationsMulticast implements IAlgorithm
050{
051        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)");
052        private InputParameter optimizationTarget = new InputParameter ("optimizationTarget", "#select# min-consumed-bandwidth min-av-num-hops minimax-link-utilization maximin-link-idle-capacity" , "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");
053        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");
054        private InputParameter maxE2ELengthInKm = new InputParameter ("maxE2ELengthInKm", (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");
055        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");
056        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");
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 N = netPlan.getNumberOfNodes();
072                final int MD = netPlan.getNumberOfMulticastDemands();
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                /* Create the optimization problem object (JOM library) */
079                OptimizationProblem op = new OptimizationProblem();
080
081                /* Set some input parameters to the problem */
082                op.setInputParameter("u_e", netPlan.getVectorLinkSpareCapacity(), "row"); /* for each link, its unused capacity (the one not used by any mulitcast trees) */
083                op.setInputParameter("A_nd", netPlan.getMatrixNodeMulticastDemandIncidence()); /* 1 if node n is ingress in multicast demand d, -1 if n is egress */ 
084                final DoubleMatrix2D Aout_nd = netPlan.getMatrixNodeMulticastDemandOutgoingIncidence();
085                final DoubleMatrix2D Ain_nd = netPlan.getMatrixNodeMulticastDemandIncomingIncidence();
086                op.setInputParameter("Aout_nd", Aout_nd); /* 1 if node n is ingress in multicast demand d */ 
087                op.setInputParameter("Ain_nd", Ain_nd); /* -1 if node n is egress in multicast demand d */ 
088                op.setInputParameter("A_ne", netPlan.getMatrixNodeLinkIncidence()); /* 1 in position (n,e) if link e starts in n, -1 if it ends in n, 0 otherwise */
089                op.setInputParameter("Aout_ne", netPlan.getMatrixNodeLinkOutgoingIncidence()); /* 1 in position (n,e) if link e starts in n */
090                op.setInputParameter("Ain_ne", netPlan.getMatrixNodeLinkIncomingIncidence()); /* 1 in position (n,e) if link e ends in n */
091                op.setInputParameter("h_d", netPlan.getVectorMulticastDemandOfferedTraffic(), "row"); /* for each multicast demand, its offered traffic */
092                op.setInputParameter("lengthInKm_e", netPlan.getVectorLinkLengthInKm(), "row"); /* for each link, its length in km */
093                op.setInputParameter("propDelay_e", netPlan.getVectorLinkPropagationDelayInMiliseconds(), "row"); /* for each link, its length in km */
094                op.setInputParameter("onesE", DoubleFactory1D.dense.make (E,1.0) , "row"); /* for each link, a one */
095                op.setInputParameter("K", maxCopyCapability.getInt() <= 0? N : maxCopyCapability.getInt ()); /* the maximum number of output links a node can copy the input traffic of a multicast tree (<= 0 means no limitation) */
096                
097                /* Add decision variables for the multicast demands */
098                op.addDecisionVariable("xx_de", true , new int [] {MD , E} , 0 , 1); // 1 if link e is used my the multicast tree of this demand
099                op.addDecisionVariable("xx_det", true , new int [] {MD , E , N} , 0 , 1); // 1 if link e is used my the multicast tree of this demand
100
101                /* Write the problem objective function and constraints specific to this objective function */
102                if (optimizationTarget.getString ().equals ("min-consumed-bandwidth")) 
103                {
104                        op.setObjectiveFunction("minimize", "sum (h_d * xx_de)"); /* total traffic in the links */
105                        op.addConstraint("h_d * xx_de <= u_e"); /* the traffic in each link cannot exceed its capacity */
106                }
107                else if (optimizationTarget.getString ().equals ("min-av-num-hops")) 
108                {
109                        op.setInputParameter ("EPSILON" , getMinimumNonZeroTrafficOrCapacityValue (netPlan) / 1000);
110                        op.setObjectiveFunction("minimize", "sum(diag(h_d) * xx_det) + EPSILON * sum (h_d * xx_de)"); /* proportional to the number of hops each packet makes */
111                        op.addConstraint("h_d * xx_de <= u_e"); /* the traffic in each link cannot exceed its capacity */
112                }
113                else if (optimizationTarget.getString ().equals ("minimax-link-utilization")) 
114                {
115                        op.setInputParameter ("EPSILON" , getMinimumNonZeroTrafficOrCapacityValue (netPlan) / 1000);
116                        op.addDecisionVariable("rho", false, new int[] { 1, 1 }, 0, 1); /* worse case link utilization */
117                        op.setObjectiveFunction("minimize", "rho + EPSILON * sum (h_d * xx_de)"); // to avoid loops, we sum EPSILON by the traffic carried (EPSILON very small number)
118                        op.addConstraint("h_d * xx_de <= rho * u_e"); /* the traffic in each link cannot exceed its capacity. sets rho as the worse case utilization */
119                }
120                else if (optimizationTarget.getString ().equals ("maximin-link-idle-capacity"))
121                {
122                        op.setInputParameter ("EPSILON" , getMinimumNonZeroTrafficOrCapacityValue (netPlan) / 1000);
123                        op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* worse case link idle capacity */
124                        op.setObjectiveFunction("maximize", "u - EPSILON * sum (h_d * xx_de)"); // to avoid loops, we sum EPSILON by the traffic carried (EPSILON very small number)
125                        op.addConstraint("h_d * xx_de <= -u + u_e"); /* the traffic in each link cannot exceed its capacity. sets u as the worse case idle capacity */
126                }
127                else throw new Net2PlanException ("Unknown optimization target " + optimizationTarget.getString());
128
129//              DoubleMatrix3D I_eet = DoubleFactory3D.sparse.make (E,E,N); for (int t = 0; t < N ; t ++) I_eet.viewColumn (t).assign (DoubleFactory2D.sparse.identity(E));
130//              op.setInputParameter("I_eet", new DoubleMatrixND (I_eet));
131                DoubleMatrixND I_eet = new DoubleMatrixND (new int [] {E,E,N} , "sparse"); for (int t = 0 ; t < N ; t ++) for (int e = 0 ; e < E ; e ++) I_eet.set (new int [] { e,e,t} , 1.0);
132                op.setInputParameter("I_eet", I_eet);
133                
134                DoubleMatrixND A_ndt = new DoubleMatrixND (new int [] { N , MD , N }  , "sparse"); 
135                for (MulticastDemand d : netPlan.getMulticastDemands())
136                        for (Node t : d.getEgressNodes())
137                        {
138                                A_ndt.set (new int [] { d.getIngressNode().getIndex() , d.getIndex ()  , t.getIndex () } , 1.0);
139                                A_ndt.set (new int [] { t.getIndex () , d.getIndex () , t.getIndex () } , -1.0);
140                        }
141                op.setInputParameter("A_ndt", A_ndt);
142                op.setInputParameter("onesN" , DoubleFactory1D.dense.make (N,1.0)  , "row");
143                
144                /* Add constraints for the multicast demands */
145                op.addConstraint ("Ain_ne * xx_de' >= Ain_nd"); // a destination node receives at least one input link
146                op.addConstraint ("Ain_ne * xx_de' <= 1 - Aout_nd"); // source nodes receive 0 links, destination nodes at most one (then just one)
147                op.addConstraint ("Aout_ne * xx_de' <= K * (Aout_nd + (Ain_ne * xx_de'))"); // at most K out links from ingress node and from intermediate nodes if they have one input link
148                op.addConstraint ("xx_det  <= xx_de * I_eet"); // a link belongs to a path only if it is in the tree
149                op.addConstraint ("A_ne * permute(xx_det , [2 ; 1 ; 3]) == A_ndt"); // flow conservation constraint for each path in the tree
150
151                final boolean maxE2ELengthConstraintApplies = (maxE2ELengthInKm.getDouble() > 0) && (maxE2ELengthInKm.getDouble() < netPlan.getVectorLinkLengthInKm().zSum());
152                final boolean maxE2ENumHopsConstraintApplies = (maxE2ENumHops.getInt() > 0) && (maxE2ENumHops.getInt() < E);
153                final boolean maxE2EPropDelayConstraintApplies = (maxE2EPropDelayInMs.getDouble() > 0) && (maxE2EPropDelayInMs.getDouble() < netPlan.getVectorLinkPropagationDelayInMiliseconds().zSum());
154                if (maxE2ELengthConstraintApplies) op.addConstraint ("lengthInKm_e * permute(xx_det,[2;1;3]) <= " + maxE2ELengthInKm.getDouble()); // maximum length in km from ingress node to any demand egress node is limited
155                if (maxE2ENumHopsConstraintApplies) op.addConstraint ("sum(xx_det,2) <= " + maxE2ENumHops.getInt()); // maximum number of hops from ingress node to any demand egress node is limited
156                if (maxE2EPropDelayConstraintApplies) op.addConstraint ("propDelay_e * permute(xx_det,[2;1;3])  <= " + maxE2EPropDelayInMs.getDouble()); // maximum propagation delay in ms from ingress node to any demand egress node is limited
157
158                op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ());
159
160                /* If no solution is found, quit */
161                if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution");
162                if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found");
163                
164                /* Save the solution found in the netPlan object */
165                final DoubleMatrix2D xx_de = op.getPrimalSolution("xx_de").view2D();
166                /* Check */
167                final DoubleMatrixND xx_det = op.getPrimalSolution("xx_det");
168                for (MulticastDemand d : netPlan.getMulticastDemands())
169                        for (Link e : netPlan.getLinks())
170                                for (Node n : netPlan.getNodes())
171                                        if (xx_de.get(d.getIndex () , e.getIndex ()) == 0)
172                                                if (xx_det.get(new int [] {d.getIndex() , e.getIndex () , n.getIndex() } ) != 0) throw new RuntimeException ("Bad: x_de: " + (xx_de.get(d.getIndex () , e.getIndex ())) + ", xx_det: " + (xx_det.get(new int [] {d.getIndex() , e.getIndex () , n.getIndex() } )) );
173                
174                for (MulticastDemand d : netPlan.getMulticastDemands())
175                {
176                        Set<Link> linkSet = new HashSet<Link> (); for (int e = 0 ; e < E ; e ++) if (xx_de.get(d.getIndex() , e) != 0) { linkSet.add (netPlan.getLink (e)); }
177                        netPlan.addMulticastTree(d , d.getOfferedTraffic() , d.getOfferedTraffic() , linkSet , null);
178                }
179                
180
181                
182                
183                return "Ok!: The solution found is guaranteed to be optimal: " + op.solutionIsOptimal() + ", number of multicast trees created: " + netPlan.getNumberOfMulticastTrees();
184        }
185
186        @Override
187        public String getDescription()
188        {
189                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-link formulations. Through a set of input parameters, the user can choose among different optimization targets and constraints.";
190        }
191
192        
193        @Override
194        public List<Triple<String, String, String>> getParameters()
195        {
196                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
197                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
198        }
199        
200        private double getMinimumNonZeroTrafficOrCapacityValue (NetPlan netPlan)
201        {
202                double res = Double.MAX_VALUE;
203                for (Demand d : netPlan.getDemands ()) if (d.getOfferedTraffic() > 0) res = Math.min (res , d.getOfferedTraffic());
204                for (Link e : netPlan.getLinks ()) if (e.getCapacity() > 0) res = Math.min (res , e.getCapacity());
205                if (res == Double.MAX_VALUE) throw new Net2PlanException ("Too large offered traffics and link capacities");
206                return res;
207        }
208}