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.Collections;
021import java.util.List;
022import java.util.Map;
023
024import cern.colt.matrix.tdouble.DoubleFactory1D;
025import cern.colt.matrix.tdouble.DoubleMatrix1D;
026
027import com.jom.OptimizationProblem;
028import com.net2plan.interfaces.networkDesign.Demand;
029import com.net2plan.interfaces.networkDesign.IAlgorithm;
030import com.net2plan.interfaces.networkDesign.Net2PlanException;
031import com.net2plan.interfaces.networkDesign.NetPlan;
032import com.net2plan.interfaces.networkDesign.ProtectionSegment;
033import com.net2plan.interfaces.networkDesign.Route;
034import com.net2plan.utils.Constants.RoutingType;
035import com.net2plan.utils.InputParameter;
036import com.net2plan.utils.Triple;
037
038/**
039 * Solves several variants of unicast routing problems with 1+1 protection, with flow-path formulations
040 * @net2plan.description
041 * @net2plan.keywords JOM, Flow-path formulation, Flow assignment (FA), Network recovery: protection
042 * @net2plan.ocnbooksections Section 4.2, Section 4.6.6 
043 * @net2plan.inputParameters 
044 * @author Pablo Pavon-Marino
045 */
046public class Offline_fa_xp11PathProtection implements IAlgorithm
047{
048        private InputParameter k = new InputParameter ("k", (int) 5 , "Maximum number of admissible paths per demand" , 1 , Integer.MAX_VALUE);
049        private InputParameter shortestPathType = new InputParameter ("shortestPathType", "#select# hops km" , "Criteria to compute the shortest path. Valid values: 'hops' or 'km'");
050        private InputParameter maxLengthInKm = new InputParameter ("maxLengthInKm", (double) 2000 , "Paths longer than this are considered not admissible. A non-positive number means this limit does not exist");
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                if (!shortestPathType.getString().equalsIgnoreCase("km") && !shortestPathType.getString().equalsIgnoreCase("hops"))
063                        throw new Net2PlanException("Wrong shortestPathType parameter");
064                if (type11.getString ().equalsIgnoreCase("srgDisjoint") && (netPlan.getNumberOfSRGs() == 0)) throw new Net2PlanException("No SRG was defined"); 
065
066                /* Basic checks */
067                final int N = netPlan.getNumberOfNodes();
068                final int E = netPlan.getNumberOfLinks();
069                final int D = netPlan.getNumberOfDemands();
070                final int S = netPlan.getNumberOfSRGs();
071                final double PRECISION_FACTOR = Double.parseDouble(net2planParameters.get("precisionFactor"));
072                if (N == 0 || D == 0 || E == 0) throw new Net2PlanException("This algorithm requires a topology with links, and a demand set");
073
074                /* Remove all unicast routed traffic. Any multicast routed traffic is kept */
075                netPlan.removeAllUnicastRoutingInformation();
076                netPlan.setRoutingType(RoutingType.SOURCE_ROUTING);
077
078                /* Add all the k-shortest candidate routes to the netPlan object carrying no traffic */
079                final DoubleMatrix1D linkCostVector = shortestPathType.getString().equalsIgnoreCase("hops")? DoubleFactory1D.dense.make (E , 1.0) : netPlan.getVectorLinkLengthInKm();
080
081                netPlan.addRoutesFromCandidatePathList(linkCostVector.toArray() , "K", Integer.toString(k.getInt ()), "maxLengthInKm", Double.toString(maxLengthInKm.getDouble () > 0? maxLengthInKm.getDouble () : Double.MAX_VALUE));
082                final int P = netPlan.getNumberOfRoutes(); 
083                
084                /* Create the optimization problem object (JOM library) */
085                OptimizationProblem op = new OptimizationProblem();
086                op.setInputParameter("u_e", netPlan.getVectorLinkSpareCapacity(), "row"); /* for each link, its unused capacity (the one not used by any mulitcast trees) */
087                op.setInputParameter("A_ep", netPlan.getMatrixLink2RouteAssignment()); /* 1 in position (e,p) if link e is traversed by path p, 0 otherwise */
088                op.setInputParameter("A_dp", netPlan.getMatrixDemand2RouteAssignment()); /* 1 in position (d,p) if demand d is served by path p, 0 otherwise */ 
089                op.setInputParameter("h_d", netPlan.getVectorDemandOfferedTraffic(), "row"); /* for each demand, its offered traffic */
090                op.setInputParameter("h_p", netPlan.getVectorRouteOfferedTrafficOfAssociatedDemand () , "row"); /* for each path, the offered traffic of its demand */
091
092                if (type11.getString ().equalsIgnoreCase("linkDisjoint"))
093                        op.setInputParameter("A_ps", netPlan.getMatrixLink2RouteAssignment().viewDice ()); /* 1 in position (p,s) if link s is traversed by path p, 0 otherwise */
094                else if (type11.getString ().equalsIgnoreCase("srgDisjoint"))
095                        op.setInputParameter("A_ps", netPlan.getMatrixRoute2SRGAffecting()); /* 1 in position (p,s) if srg s is affecting path p, 0 otherwise */
096                
097                /* Common decision variables */
098                op.addDecisionVariable("xx_p", true , new int[] { 1, P }, 0, 1); /* 1 if primary path of demand d(p) that is carried by p */
099                op.addDecisionVariable("bb_p", true , new int[] { 1, P }, 0, 1); /* 1 if backup path of demand d(p) that is carried by p */
100
101                if (optimizationTarget.getString ().equals ("min-av-num-hops")) 
102                {
103                        op.setInputParameter("l_p", netPlan.getVectorRouteNumberOfLinks() , "row"); /* for each path, the number of traversed links */
104                        op.setObjectiveFunction("minimize", "sum (l_p .* h_p .* (xx_p + bb_p))"); /* sum of the traffic in the links, proportional to the average number of hops  */
105                        op.addConstraint("A_ep * (h_p .* (xx_p + bb_p))' <= u_e'"); /* the traffic in each link cannot exceed its capacity  */
106                }
107                else if (optimizationTarget.getString ().equals ("minimax-link-utilization")) 
108                {
109                        op.addDecisionVariable("rho", false, new int[] { 1, 1 }, 0, 1); /* worse case link utilization */
110                        op.setObjectiveFunction("minimize", "rho");
111                        op.addConstraint("A_ep * (h_p .* (xx_p + bb_p))' <= rho * u_e'"); /* the traffic in each link cannot exceed its capacity. sets rho as the worse case utilization */
112                }
113                else if (optimizationTarget.getString ().equals ("maximin-link-idle-capacity"))
114                {
115                        op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* worse case link idle capacity */
116                        op.setObjectiveFunction("maximize", "u");
117                        op.addConstraint("A_ep * (h_p .* (xx_p + bb_p))' <= -u + u_e'"); /* the traffic in each link cannot exceed its capacity. sets u as the worse case idle capacity */
118                }
119                else throw new Net2PlanException ("Unknown optimization target " + optimizationTarget.getString());
120                
121                op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, one primary path exists  */
122                op.addConstraint("A_dp * bb_p' == 1"); /* for each demand, one backup path exists  */
123                op.addConstraint("A_dp * diag(xx_p + bb_p) * A_ps  <= 1"); /* primary and backup are link or srg disjoint (depending on what is needed) */
124
125                /* Call the solver to solve the problem */
126                op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ());
127
128                /* If no solution is found, quit */
129                if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution");
130                if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found");
131
132                /* Retrieve the optimum solutions */
133                double [] xx_p = op.getPrimalSolution("xx_p").to1DArray();
134                double [] bb_p = op.getPrimalSolution("bb_p").to1DArray();
135
136                for (Demand d : netPlan.getDemands ())
137                {
138                        Route primary = null; Route backup = null;
139                        for (Route r : d.getRoutes()) { if (xx_p [r.getIndex ()] == 1) primary = r; if (bb_p [r.getIndex ()] == 1) backup = r; }
140                        ProtectionSegment segment = netPlan.addProtectionSegment(backup.getSeqLinksRealPath() , d.getOfferedTraffic() , null);
141                        if (primary == null) throw new RuntimeException ("Bad");
142                        if (backup == null) throw new RuntimeException ("Bad");
143                        primary.setCarriedTraffic(d.getOfferedTraffic() , d.getOfferedTraffic());
144                        primary.addProtectionSegment(segment);
145                }
146
147                netPlan.removeAllRoutesUnused(PRECISION_FACTOR); // routes with zero traffic (or close to zero, with PRECISION_FACTOR tolerance)
148                
149                checkSolution(netPlan, type11.getString ());
150
151                return "Ok!";
152        }
153
154        @Override
155        public String getDescription()
156        {
157                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-path formulation. Initially, a set of admissible candidate paths are computed for each demand, which can be used as either primary or backup paths. Through a set of input parameters, the user can choose among different optimization targets and constraints.";
158        }
159
160        @Override
161        public List<Triple<String, String, String>> getParameters()
162        {
163                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
164                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
165        }
166        
167        private static void checkSolution(NetPlan netPlan, String type11)
168        {
169                if (!netPlan.getLinksOversubscribed().isEmpty()) throw new Net2PlanException("Bad - Some link is oversubscribed (constraint violated)");
170                if (!netPlan.getDemandsBlocked().isEmpty()) throw new Net2PlanException("Bad - Some demand is blocked (constraint violated)");
171
172                for (Route route : netPlan.getRoutes())
173                {
174                        if (route.getPotentialBackupProtectionSegments().size () != 1) throw new RuntimeException("Bad");
175                        
176                        final ProtectionSegment segment = route.getPotentialBackupProtectionSegments().iterator().next();
177                        if (route.getIngressNode() != segment.getOriginNode()) throw new RuntimeException("Bad");
178                        if (route.getEgressNode() != segment.getDestinationNode()) throw new RuntimeException("Bad");
179                        
180                        if (type11.equalsIgnoreCase("srgDisjoint"))
181                                if (!Collections.disjoint(route.getSRGs(), segment.getSRGs()))
182                                        throw new RuntimeException("Bad");
183                        else if (type11.equalsIgnoreCase("linkDisjoint"))
184                                if (!Collections.disjoint(route.getSeqLinksRealPath(), segment.getSeqLinks()))
185                                        throw new RuntimeException("Bad");
186                        else
187                                throw new RuntimeException ("Bad");
188                }
189        }
190}
191