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.ArrayList;
021import java.util.Collections;
022import java.util.List;
023import java.util.Map;
024
025import cern.colt.matrix.tdouble.DoubleMatrix1D;
026import cern.colt.matrix.tdouble.DoubleMatrix2D;
027
028import com.jom.OptimizationProblem;
029import com.net2plan.interfaces.networkDesign.Demand;
030import com.net2plan.interfaces.networkDesign.IAlgorithm;
031import com.net2plan.interfaces.networkDesign.Link;
032import com.net2plan.interfaces.networkDesign.Net2PlanException;
033import com.net2plan.interfaces.networkDesign.NetPlan;
034import com.net2plan.interfaces.networkDesign.ProtectionSegment;
035import com.net2plan.interfaces.networkDesign.Route;
036import com.net2plan.libraries.GraphUtils;
037import com.net2plan.utils.Constants.RoutingType;
038import com.net2plan.utils.InputParameter;
039import com.net2plan.utils.Triple;
040
041/**
042 * Solves several variants of unicast routing problems with 1+1 protection, with flow-link formulations
043 * @net2plan.description
044 * @net2plan.keywords JOM, Flow-path formulation, Flow assignment (FA), Network recovery: protection
045 * @net2plan.ocnbooksections Section 4.3, Section 4.6.6
046 * @net2plan.inputParameters 
047 * @author Pablo Pavon-Marino
048 */
049public class Offline_fa_xde11PathProtection implements IAlgorithm
050{
051        private InputParameter optimizationTarget = new InputParameter ("optimizationTarget", "#select# min-av-num-hops minimax-link-utilization maximin-link-idle-capacity" , "Type of optimization target. Choose among minimize the average number of hops, minimize the highest link utilization, maximize the lowest link idle capacity");
052        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");
053        private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "", "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default.");
054        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)");
055        private InputParameter type11 = new InputParameter ("type11", "#select# linkDisjoint srgDisjoint" , "Type of 1+1 protection: 1+1 link disjoint (primary and backup paths have no link in common), and 1+1 srg disjoint (primary and backup paths have no SRG in common)");
056
057        @Override
058        public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters)
059        {
060                /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */
061                InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters);
062
063                /* Basic checks */
064                final int N = netPlan.getNumberOfNodes();
065                final int E = netPlan.getNumberOfLinks();
066                final int D = netPlan.getNumberOfDemands();
067                if (N == 0 || D == 0 || E == 0) throw new Net2PlanException("This algorithm requires a topology with links, and a demand set");
068
069                /* Remove all unicast routed traffic. Any multicast routed traffic is kept */
070                netPlan.removeAllUnicastRoutingInformation();
071                netPlan.setRoutingType(RoutingType.SOURCE_ROUTING);
072                
073                /* Initialize some variables */
074                DoubleMatrix1D u_e = netPlan.getVectorLinkSpareCapacity(); // just the unused capacity (some capacity may be used by multicast traffic)
075                DoubleMatrix1D h_d = netPlan.getVectorDemandOfferedTraffic();
076                
077                /* Create the optimization problem object (JOM library) */
078                OptimizationProblem op = new OptimizationProblem();
079                op.setInputParameter("u_e", u_e, "row");
080                op.setInputParameter("h_d", h_d, "row");
081                op.setInputParameter("A_ne", netPlan.getMatrixNodeLinkIncidence());
082                op.setInputParameter("A_nd", netPlan.getMatrixNodeDemandIncidence());
083
084                if (type11.getString ().equalsIgnoreCase("linkDisjoint"))
085                {
086                        /* Add the decision variables to the problem */
087                        op.addDecisionVariable("x_de", true, new int[] { D, E }, 0, 1); /* 1 if the primary path of demand d, traverses link e */
088                        op.addDecisionVariable("xx_de", true, new int[] { D, E }, 0, 1);  /* 1 if the backup path of demand d, traverses link e */
089                        
090                        /* Sets the objective function */
091                        if (optimizationTarget.getString ().equalsIgnoreCase("min-av-num-hops"))
092                        {
093                                op.setObjectiveFunction("minimize", "sum (h_d * (x_de + xx_de))");
094                                op.addConstraint("h_d * (x_de + xx_de) <= u_e"); /* the capacity constraints summing primary and backup paths (E constraints) */
095                        }
096                        else if (optimizationTarget.getString ().equalsIgnoreCase("minimax-link-utilization"))
097                        {
098                                op.setInputParameter ("EPSILON" , 1e-4);
099                                op.addDecisionVariable("rho", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* idle capacity in the bottleneck link */
100                                op.setObjectiveFunction("minimize", "rho + EPSILON * sum(x_de + xx_de)");
101                                op.addConstraint("h_d * (x_de + xx_de) <= rho * u_e"); /* the capacity constraints summing primary and backup paths (E constraints), make that rho becomes the worse case link utilization */
102                        }
103                        else if (optimizationTarget.getString ().equalsIgnoreCase("maximin-link-idle-capacity"))
104                        {
105                                op.setInputParameter ("EPSILON" , 1e-4);
106                                op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* idle capacity in the bottleneck link */
107                                op.setObjectiveFunction("maximize", "u - EPSILON * sum(x_de + xx_de)");
108                                op.addConstraint("h_d * (x_de + xx_de) <= u_e - u"); /* the capacity constraints summing primary and backup paths (E constraints) */
109                        }
110                        else throw new Net2PlanException ("Unknown optimization target " + optimizationTarget.getString());
111                        
112                        /* Add constraints */
113                        op.addConstraint("A_ne * (x_de') == A_nd"); /* the flow-conservation constraints for the primary path (NxD constraints) */
114                        op.addConstraint("A_ne * (xx_de') == A_nd"); /* the flow-conservation constraints for the backup path (NxD constraints) */
115                        op.addConstraint("x_de + xx_de <= 1"); /* the primary and backup path are link disjoint (DxE constraints) */
116                }       
117                else if (type11.getString ().equalsIgnoreCase("srgDisjoint"))
118                {
119                        final int S = netPlan.getNumberOfSRGs();
120                        if (S == 0) throw new Net2PlanException("No SRG was defined");
121                        
122                        op.setInputParameter("A_es", netPlan.getMatrixLink2SRGAssignment());
123                        op.setInputParameter("E", E);
124                        
125                        /* Add the decision variables to the problem */
126                        op.addDecisionVariable("x_de", true, new int[] { D, E }, 0, 1); /* 1 if the primary path of demand d, traverses link e */
127                        op.addDecisionVariable("xx_de", true, new int[] { D, E }, 0, 1);  /* 1 if the backup path of demand d, traverses link e */
128                        op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* idle capacity in the bottleneck link */
129                        op.addDecisionVariable("x_ds", true, new int[] { D, S }, 0, 1); /* 1 if demand d traverses SRG s in the primary  */
130                        op.addDecisionVariable("xx_ds", true, new int[] { D, S }, 0, 1); /* 1 if demand d traverses SRG s in the backup */
131                        
132                        /* Sets the objective function */
133                        if (optimizationTarget.getString ().equalsIgnoreCase("min-av-num-hops"))
134                        {
135                                op.setObjectiveFunction("minimize", "sum (h_d * (x_de + xx_de))");
136                                op.addConstraint("h_d * (x_de + xx_de) <= u_e"); /* the capacity constraints summing primary and backup paths (E constraints) */
137                        }
138                        else if (optimizationTarget.getString ().equalsIgnoreCase("minimax-link-utilization"))
139                        {
140                                op.setInputParameter ("EPSILON" , 1e-4);
141                                op.addDecisionVariable("rho", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* idle capacity in the bottleneck link */
142                                op.setObjectiveFunction("minimize", "rho + EPSILON * sum(x_de + xx_de)");
143                                op.addConstraint("h_d * (x_de + xx_de) <= rho * u_e"); /* the capacity constraints summing primary and backup paths (E constraints), make that rho becomes the worse case link utilization */
144                        }
145                        else if (optimizationTarget.getString ().equalsIgnoreCase("maximin-link-idle-capacity"))
146                        {
147                                op.setInputParameter ("EPSILON" , 1e-4);
148                                op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* idle capacity in the bottleneck link */
149                                op.setObjectiveFunction("maximize", "u - EPSILON * sum (x_de + xx_de)"); 
150                                op.addConstraint("h_d * (x_de + xx_de) <= u_e - u"); /* the capacity constraints summing primary and backup paths (E constraints) */
151                        }
152                        else throw new Net2PlanException ("Unknown optimization target " + optimizationTarget.getString());
153
154                        /* Add constraints */
155                        op.addConstraint("A_ne * (x_de') == A_nd"); /* the flow-conservation constraints for the primary path (NxD constraints) */
156                        op.addConstraint("A_ne * (xx_de') == A_nd"); /* the flow-conservation constraints for the backup path (NxD constraints) */
157                        op.addConstraint("h_d * (x_de + xx_de) <= u_e - u"); /* the capacity constraints summing primary and backup paths (E constraints) */
158                        op.addConstraint("E * x_ds >= x_de * A_es"); /* 1 if demand s traverses SRG s in the primary (DxS constraints) */
159                        op.addConstraint("E * xx_ds >= xx_de * A_es"); /* 1 if demand s traverses SRG s in the nackup (DxS constraints) */
160                        op.addConstraint("x_ds + xx_ds <= 1"); /* the primary and backup path are SRG disjoint (DxS constraints) */
161                }
162                else throw new Net2PlanException("Wrong type of 1:1 protection");
163                
164                /* Call the solver to solve the problem */
165                op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ());
166
167                /* If no solution is found, quit */
168                if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution");
169                if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found");
170
171                /* Retrieve the optimum solutions */
172                DoubleMatrix2D x_de = op.getPrimalSolution("x_de").view2D();
173                DoubleMatrix2D xx_de = op.getPrimalSolution("xx_de").view2D();
174
175                /* Convert the x_de variables into a set of routes for each demand */
176                List<Demand> primary_demands = new ArrayList<Demand>();
177                List<List<Link>> primary_seqLinks = new ArrayList<List<Link>>();
178                List<Double> primary_x_p = new ArrayList<Double>();
179                GraphUtils.convert_xde2xp(netPlan.getNodes (), netPlan.getLinks () , netPlan.getDemands () , x_de, primary_demands, primary_x_p, primary_seqLinks);
180                
181                List<Demand> backup_demands = new ArrayList<Demand>();
182                List<List<Link>> backup_seqLinks = new ArrayList<List<Link>>();
183                List<Double> backup_x_p = new ArrayList<Double>();
184                GraphUtils.convert_xde2xp(netPlan.getNodes (), netPlan.getLinks () , netPlan.getDemands () , xx_de, backup_demands, backup_x_p, backup_seqLinks);
185
186                /* Update netPlan object adding the calculated routes */
187                if (primary_demands.size() != D) throw new Net2PlanException("Unexpected error");
188                if (backup_demands.size() != D) throw new Net2PlanException("Unexpected error");
189                
190                for (Demand demand : netPlan.getDemands())
191                {
192                        /* for each demand, there is one primary and one backup path*/
193                        int primary_p = primary_demands.indexOf(demand);
194                        if (primary_p == -1) throw new RuntimeException("Unexpected error");
195
196                        int backup_p = backup_demands.indexOf(demand);
197                        if (backup_p == -1) throw new RuntimeException("Unexpected error");
198                        
199                        Route route = netPlan.addRoute(demand , demand.getOfferedTraffic() , demand.getOfferedTraffic() , primary_seqLinks.get(primary_p), null); /* add the primary route (primary path) */
200                        ProtectionSegment segment = netPlan.addProtectionSegment(backup_seqLinks.get(backup_p), demand.getOfferedTraffic(), null); /* add the protection segment (backup path) */
201                        route.addProtectionSegment(segment);
202                }
203
204                checkSolution(netPlan, type11.getString ());
205
206                return "Ok!";
207        }
208
209        @Override
210        public String getDescription()
211        {
212                return "Given a network topology, the capacities in the links, and a set unicast traffic demands, this algorithm permits computing the optimum routing of the traffic with 1+1 protection to each route, solving a variations of the flow-link formulation. Through a set of input parameters, the user can choose among different optimization targets and constraints.";
213        }
214
215        @Override
216        public List<Triple<String, String, String>> getParameters()
217        {
218                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
219                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
220        }
221        
222        /**
223         * Checks if solution is valid.
224         * 
225         * @param netPlan Network design
226         * @param type11 Type of 1:1 protection
227         * @since 1.1
228         */
229        private static void checkSolution(NetPlan netPlan, String type11)
230        {
231                if (!netPlan.getLinksOversubscribed().isEmpty()) throw new Net2PlanException("Bad - Some link is oversubscribed (constraint violated)");
232                if (!netPlan.getDemandsBlocked().isEmpty()) throw new Net2PlanException("Bad - Some demand is blocked (constraint violated)");
233
234                for (Route route : netPlan.getRoutes())
235                {
236                        if (route.getPotentialBackupProtectionSegments().size () != 1) throw new RuntimeException("Bad");
237                        
238                        final ProtectionSegment segment = route.getPotentialBackupProtectionSegments().iterator().next();
239                        if (route.getIngressNode() != segment.getOriginNode()) throw new RuntimeException("Bad");
240                        if (route.getEgressNode() != segment.getDestinationNode()) throw new RuntimeException("Bad");
241                        
242                        if (type11.equalsIgnoreCase("srgDisjoint"))
243                                if (!Collections.disjoint(route.getSRGs(), segment.getSRGs()))
244                                        throw new RuntimeException("Bad");
245                        else if (type11.equalsIgnoreCase("linkDisjoint"))
246                                if (!Collections.disjoint(route.getSeqLinksRealPath(), segment.getSeqLinks()))
247                                        throw new RuntimeException("Bad");
248                        else
249                                throw new RuntimeException ("Bad");
250                }
251        }
252}
253