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.List;
021import java.util.Map;
022
023import cern.colt.list.tdouble.DoubleArrayList;
024import cern.colt.list.tint.IntArrayList;
025import cern.colt.matrix.tdouble.DoubleFactory1D;
026import cern.colt.matrix.tdouble.DoubleMatrix1D;
027import cern.colt.matrix.tdouble.DoubleMatrix2D;
028import cern.colt.matrix.tdouble.DoubleMatrix3D;
029
030import com.jom.DoubleMatrixND;
031import com.jom.OptimizationProblem;
032import com.net2plan.interfaces.networkDesign.Demand;
033import com.net2plan.interfaces.networkDesign.IAlgorithm;
034import com.net2plan.interfaces.networkDesign.Link;
035import com.net2plan.interfaces.networkDesign.Net2PlanException;
036import com.net2plan.interfaces.networkDesign.NetPlan;
037import com.net2plan.interfaces.networkDesign.SharedRiskGroup;
038import com.net2plan.utils.Constants.RoutingType;
039import com.net2plan.utils.InputParameter;
040import com.net2plan.utils.Triple;
041
042/**
043 * Solves several variants of unicast routing problems with flow-link formulations, so that designs are fault tolerant to a set of failure states, using shared restoration
044 * @net2plan.description
045 * @net2plan.keywords JOM, Flow-link formulation, Flow assignment (FA), Network recovery: restoration
046 * @net2plan.ocnbooksections Section 4.3, Section 4.6.7
047 * @net2plan.inputParameters 
048 * @author Pablo Pavon-Marino
049 */
050public class Offline_fa_xdeSharedRestoration implements IAlgorithm
051{
052        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");
053        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");
054        private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "", "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default.");
055        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)");
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 (netPlan.getNumberOfSRGs() == 0) throw new Net2PlanException("No SRG was defined"); 
063
064                /* Basic checks */
065                final int N = netPlan.getNumberOfNodes();
066                final int E = netPlan.getNumberOfLinks();
067                final int D = netPlan.getNumberOfDemands();
068                final int S = netPlan.getNumberOfSRGs();
069                if (N == 0 || D == 0 || E == 0) throw new Net2PlanException("This algorithm requires a topology with links, and a demand set");
070
071                /* Remove all unicast routed traffic. Any multicast routed traffic is kept */
072                netPlan.removeAllUnicastRoutingInformation();
073                netPlan.setRoutingType(RoutingType.SOURCE_ROUTING);
074                
075                /* Initialize some variables */
076                DoubleMatrix1D u_e = netPlan.getVectorLinkSpareCapacity(); // just the unused capacity (some capacity may be used by multicast traffic)
077                DoubleMatrix1D h_d = netPlan.getVectorDemandOfferedTraffic();
078                
079                /* Create the optimization problem object (JOM library) */
080                OptimizationProblem op = new OptimizationProblem();
081                op.setInputParameter("E", E);
082                op.setInputParameter("u_e", u_e, "row");
083                op.setInputParameter("h_d", h_d, "row");
084                op.setInputParameter("A_ne", netPlan.getMatrixNodeLinkIncidence());
085                op.setInputParameter("onesS", DoubleFactory1D.dense.make (S , 1.0) , "row");
086                op.setInputParameter("A_nd", netPlan.getMatrixNodeDemandIncidence());
087                op.setInputParameter("A_es", netPlan.getMatrixLink2SRGAssignment());
088                DoubleMatrixND A_des = new DoubleMatrixND (new int []{D,E,S} , "sparse"); for (SharedRiskGroup srg : netPlan.getSRGs()) for (Link e : srg.getAffectedLinks()) for (int d = 0; d < D ; d ++) A_des.set(new int [] {d,e.getIndex (),srg.getIndex()} , 1.0);
089                DoubleMatrixND A_nds = new DoubleMatrixND (new int []{N,D,S} , "sparse"); for (Demand d : netPlan.getDemands()) for (int s = 0; s < S ; s ++) { A_nds.set(new int [] {d.getIngressNode().getIndex(),d.getIndex(),s}, 1.0); A_nds.set(new int [] {d.getEgressNode().getIndex(),d.getIndex(),s}, -1.0); }
090                op.setInputParameter("A_des", A_des);
091                op.setInputParameter("A_nds", A_nds);
092                
093                /* Add the decision variables to the problem */
094                op.addDecisionVariable("xx_de", true, new int[] { D, E }, 0, 1); /* 1 if the primary path of demand d, traverses link e */
095                op.addDecisionVariable("xx_des", true, new int[] { D, E , S }, 0, 1); /* 1 if the primary path of demand d, traverses link e */
096
097                /* Sets the objective function */
098                if (optimizationTarget.getString ().equalsIgnoreCase("min-av-num-hops"))
099                {
100                        op.setObjectiveFunction("minimize", "sum (h_d * xx_de)");
101                        op.addConstraint("h_d * xx_de <= u_e"); /* the capacity constraints in the no-failure state */
102                        op.addConstraint("sum (diag(h_d) * xx_des , 1) <=  u_e' * onesS"); /* the capacity constraints summing primary and backup paths (E constraints), make that rho becomes the worse case link utilization */
103                }
104                else if (optimizationTarget.getString ().equalsIgnoreCase("minimax-link-utilization"))
105                {
106                        op.setInputParameter ("EPSILON" , 1e-4);
107                        op.addDecisionVariable("rho", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* idle capacity in the bottleneck link in any failure state */
108                        op.setObjectiveFunction("minimize", "rho + EPSILON * sum(xx_de) + EPSILON * sum(xx_des) ");
109                        op.addConstraint("h_d * xx_de <= rho * u_e"); /* the capacity constraints in the no-failure state */
110                        op.addConstraint("sum (diag(h_d) * xx_des , 1) <=  rho * u_e' * onesS"); /* the capacity constraints summing primary and backup paths (E constraints), make that rho becomes the worse case link utilization */
111                }
112                else if (optimizationTarget.getString ().equalsIgnoreCase("maximin-link-idle-capacity"))
113                {
114                        op.setInputParameter ("EPSILON" , 1e-4);
115                        op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* idle capacity in the bottleneck link */
116                        op.setObjectiveFunction("maximize", "u - EPSILON * sum(xx_de) - EPSILON * sum(xx_des)");
117                        op.addConstraint("h_d * xx_de <= -u + u_e"); /* the capacity constraints in the no-failure state */
118                        op.addConstraint("sum (diag(h_d) * xx_des , 1) <=  -u + u_e' * onesS"); /* the capacity constraints summing primary and backup paths (E constraints), make that rho becomes the worse case link utilization */
119                }
120                else throw new Net2PlanException ("Unknown optimization target " + optimizationTarget.getString());
121                
122                /* Add constraints */
123                op.addConstraint("A_ne * xx_de' == A_nd"); /* flow conservation constraints for the non-failure state */
124                op.addConstraint("A_ne * permute(xx_des,[2;1;3]) == A_nds"); /* flow conservation constraints in all the failure states */
125                op.addConstraint("xx_des <= 1 - A_des"); /* failing links do not carry traffic */
126
127                DoubleMatrixND I_sse = new DoubleMatrixND (new int [] {S,S,E}); 
128                DoubleMatrixND I_ees = new DoubleMatrixND (new int [] {E,E,S}); 
129                for (int e = 0 ; e < E ; e ++) for (int s = 0 ; s < S ; s ++) { I_sse.set (new int [] { s,s,e } ,1.0); I_ees.set (new int [] { e,e,s } ,1.0); }
130                op.setInputParameter("I_sse" , I_sse);
131                op.setInputParameter("I_ees" , I_ees);
132                op.setInputParameter("onesE" , DoubleFactory1D.dense.make(E,1) , "row");
133
134                /* If a demand does not traverse a changing link in failure state s, keep the same routing as in no-failure state */
135                op.addConstraint("- permute((xx_de * A_es) * I_sse , [1;3;2]) <= xx_des - xx_de * I_ees "); 
136                op.addConstraint("  permute((xx_de * A_es) * I_sse , [1;3;2]) >= xx_des - xx_de * I_ees "); 
137
138                /* Call the solver to solve the problem */
139                op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ());
140
141                /* If no solution is found, quit */
142                if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution");
143                if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found");
144
145                /* Retrieve the optimum solutions */
146                DoubleMatrix2D xx_de = op.getPrimalSolution("xx_de").view2D();
147                DoubleMatrix3D xx_des = op.getPrimalSolution("xx_des").view3D("sparse");
148
149                netPlan.setRoutingFromDemandLinkCarriedTraffic(xx_de , true , false);
150
151                checkSolution(netPlan, xx_de , xx_des);
152
153                return "Ok!";
154        }
155
156        @Override
157        public String getDescription()
158        {
159                return "Given a network topology, the capacities in the links and the offered traffic, this algorithm obtains a link-disjoint or a SRG-disjoint (depending on user's choice) primary and backup path for the traffic of each demand, that minimizes the network congestion, with the constraint of non-bifurcated routing. For that it solves an ILP flow-link formulation (more complex in the SRG-disjoint case). In this algorithm, congestion is minimized by maximizing the idle link capacity in the bottleneck (the link with less idle capacity).";
160        }
161
162        @Override
163        public List<Triple<String, String, String>> getParameters()
164        {
165                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
166                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
167        }
168        
169        private static void checkSolution(NetPlan netPlan, DoubleMatrix2D xx_de , DoubleMatrix3D xx_des)
170        {
171                if (!netPlan.getLinksOversubscribed().isEmpty()) throw new Net2PlanException("Bad - Some link is oversubscribed (constraint violated)");
172                if (!netPlan.getDemandsBlocked().isEmpty()) throw new Net2PlanException("Bad - Some demand is blocked (constraint violated)");
173
174                for (SharedRiskGroup srg : netPlan.getSRGs())
175                {
176                        NetPlan npThis = netPlan.copy ();
177                        npThis.removeAllUnicastRoutingInformation();
178                        DoubleMatrix2D this_xxde = xx_des.viewColumn (srg.getIndex ()).copy ();
179                        for (Link e : srg.getAffectedLinks()) if (this_xxde.viewColumn(e.getIndex ()).zSum () != 0) throw new Net2PlanException("Bad - some failing links carry traffic");
180                        npThis.setRoutingFromDemandLinkCarriedTraffic(this_xxde , true , false);
181                        if (!npThis.getLinksOversubscribed().isEmpty()) throw new Net2PlanException("Bad - Some link is oversubscribed (constraint violated) in a failure");
182                        if (!npThis.getDemandsBlocked().isEmpty()) throw new Net2PlanException("Bad - Some demand is blocked (constraint violated) in a failure");
183                        for (Demand d : netPlan.getDemands ())
184                        {
185                                IntArrayList es_noFailure = new IntArrayList (); xx_de.viewRow (d.getIndex ()).getNonZeros(es_noFailure , new DoubleArrayList ());
186                                boolean affectedByThisFailure = false; for (Link e : srg.getAffectedLinks()) if (xx_de.get(d.getIndex() , e.getIndex ()) != 0) { affectedByThisFailure = true; break; }
187                                if (!affectedByThisFailure)
188                                {
189                                        IntArrayList es_thisFailure = new IntArrayList (); this_xxde.viewRow (d.getIndex ()).getNonZeros(es_thisFailure , new DoubleArrayList ());
190                                        if (!es_noFailure.equals(es_thisFailure)) throw new Net2PlanException("Routing cannot change when a demand is not affected by the failure");
191                                }
192                        }
193                }
194        }
195}
196