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 ******************************************************************************/
008package com.net2plan.examples.ocnbook.offline;
009
010
011
012import java.io.File;
013import java.util.ArrayList;
014import java.util.Collections;
015import java.util.List;
016import java.util.Map;
017import java.util.Random;
018
019import cern.colt.matrix.tdouble.DoubleMatrix1D;
020
021import com.net2plan.interfaces.networkDesign.IAlgorithm;
022import com.net2plan.interfaces.networkDesign.Link;
023import com.net2plan.interfaces.networkDesign.Net2PlanException;
024import com.net2plan.interfaces.networkDesign.NetPlan;
025import com.net2plan.libraries.IPUtils;
026import com.net2plan.utils.Constants.RoutingType;
027import com.net2plan.utils.InputParameter;
028import com.net2plan.utils.Pair;
029import com.net2plan.utils.TimeTrace;
030import com.net2plan.utils.Triple;
031
032/**
033 * Searches for the OSPF link weights that minimize a measure of congestion, using a GRASP heuristic
034 * 
035 * The time evolution of different metrics can be stored in output files, for later processing. 
036 * As an example, see the <a href="../../../../../../graphGeneratorFiles/fig_sec12_7_ospfWeightGRASP.m">{@code fig_sec12_7_ospfWeightGRASP.m}</a> MATLAB file used for generating the graph/s of the case study in the 
037 * <a href="http://eu.wiley.com/WileyCDA/WileyTitle/productCd-1119013356.html">book</a> using this algorithm.
038 * @net2plan.description
039 * @net2plan.keywords IP/OSPF, Flow assignment (FA), GRASP
040 * @net2plan.ocnbooksections Section 12.7
041 * @net2plan.inputParameters 
042 * @author Pablo Pavon-Marino
043 */
044public class Offline_fa_ospfWeightOptimization_GRASP implements IAlgorithm
045{
046        private TimeTrace stat_objFunction;
047        private OSPFHeuristicUtils ospfEngine;
048        
049        private InputParameter grasp_initializationType = new InputParameter ("grasp_initializationType", "#select# random" , "The type of initialization of the OSPF link weights");
050        private InputParameter ospf_maxLinkWeight = new InputParameter ("ospf_maxLinkWeight", (int) 16 , "OSPF link weights are constrained to be integers between 1 and this parameter" , 1 , Integer.MAX_VALUE);
051        private InputParameter grasp_differenceInWeightToBeNeighbors = new InputParameter ("grasp_differenceInWeightToBeNeighbors", (int) 1 , "Two solutions where all the links have the same weight, but one link where the weight differs in the quantity given by this parameter, are considered neighbors");
052        private InputParameter algorithm_randomSeed = new InputParameter ("algorithm_randomSeed", (long) 1 , "Seed of the random number generator");
053        private InputParameter algorithm_outputFileNameRoot = new InputParameter ("algorithm_outputFileNameRoot", "ospfWeghtOptimization_grasp" , "Root of the file name to be used in the output files. If blank, no output");
054        private InputParameter ospf_weightOfMaxUtilizationInObjectiveFunction = new InputParameter ("ospf_weightOfMaxUtilizationInObjectiveFunction", (double) 0.9 , "Objective function is this factor multiplied by maximum link utilization, plus 1 minus this factor by average link utilization" , 0 , true , 1 , true);
055        private InputParameter grasp_rclRandomnessFactor = new InputParameter ("grasp_rclRandomnessFactor", (double) 0.5 , "Factor to compute the Restricted Candidate List in the (RCL) in the greedy randomized part" , 0 , true , 1 , true);
056        private InputParameter algorithm_maxExecutionTimeInSeconds = new InputParameter ("algorithm_maxExecutionTimeInSeconds", (double) 60 , "Algorithm maximum running time in seconds" , 0 , false , Double.MAX_VALUE , true);
057        private InputParameter grasp_maxNumIterations = new InputParameter ("grasp_maxNumIterations", (int) 50000 , "Maximum number of iterations" , 1 , Integer.MAX_VALUE);
058
059        @Override
060        public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters)
061        {
062                /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */
063                InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters);
064
065                /* Basic checks */
066                final int N = netPlan.getNumberOfNodes();
067                final int E = netPlan.getNumberOfLinks();
068                if (N == 0) throw new Net2PlanException("The input design must have nodes");
069                netPlan.removeAllUnicastRoutingInformation();
070                netPlan.setRoutingType (RoutingType.HOP_BY_HOP_ROUTING);
071                
072                Random rng = new Random (algorithm_randomSeed.getLong());
073                this.ospfEngine = new OSPFHeuristicUtils(netPlan, ospf_maxLinkWeight.getInt (), ospf_weightOfMaxUtilizationInObjectiveFunction.getDouble(), rng);
074                final long algorithmInitialtime = System.nanoTime();
075                final long algorithmEndtime = algorithmInitialtime + (long) (algorithm_maxExecutionTimeInSeconds.getDouble() * 1E9);
076                
077                this.stat_objFunction = new TimeTrace ();
078                
079                DoubleMatrix1D bestSol = null;
080                double bestObjFunction = Double.MAX_VALUE;
081
082                int iterationCounter = 0;
083                while ((System.nanoTime() < algorithmEndtime) && (iterationCounter < grasp_maxNumIterations.getInt ()))
084                {
085                        iterationCounter ++;
086                        
087                        /* Try a greedy randomized solution */
088
089                        /* Get an initial solution */
090                        Pair<DoubleMatrix1D,Double> p = ospfEngine.getInitialSolution (grasp_initializationType.getString());
091                        DoubleMatrix1D currentSol = p.getFirst();
092                        double currentObjFunction = p.getSecond();
093                        
094                        /* Greedy approach for each link */
095                        List<Link> shuffledLinks = new ArrayList<Link> (netPlan.getLinks());
096                        Collections.shuffle(shuffledLinks , rng);
097                        for (Link e : shuffledLinks)
098                                currentObjFunction = greedyRandomizedWeightChoice (e , currentSol , ospf_maxLinkWeight.getInt () , grasp_rclRandomnessFactor.getDouble() , grasp_differenceInWeightToBeNeighbors.getInt () , ospf_weightOfMaxUtilizationInObjectiveFunction.getDouble() , netPlan , rng);
099
100                        final double greedySolutionCongestion = currentObjFunction; 
101                        
102                        /* Update the incumbent solution */
103                        if (currentObjFunction < bestObjFunction) { bestObjFunction = currentObjFunction; bestSol = currentSol.copy (); }
104
105                        /* Local search */
106                        Pair<Double,Integer> localSearchRes = ospfEngine.localSearch(currentSol, currentObjFunction, grasp_differenceInWeightToBeNeighbors.getInt (), true);
107                        currentObjFunction = localSearchRes.getFirst();
108
109                        /* Update the incumbent solution */
110                        if (currentObjFunction < bestObjFunction) { bestObjFunction = currentObjFunction; bestSol = currentSol.copy (); }
111                        
112                        stat_objFunction.add(iterationCounter, new double [] { greedySolutionCongestion , currentObjFunction } );
113                }
114                
115                stat_objFunction.printToFile(new File (algorithm_outputFileNameRoot.getString () + "_D" + grasp_differenceInWeightToBeNeighbors.getInt () + "_cong.txt"));
116
117                IPUtils.setECMPForwardingRulesFromLinkWeights(netPlan, bestSol);
118
119                System.out.println("Ok! Best solution OF: " + bestObjFunction);
120                return "Ok! Best OF: " + bestObjFunction;
121        }
122
123        @Override
124        public String getDescription()
125        {
126                return "Given a set of nodes, links and offered traffic, this algorithm assumes that the nodes are IP routers running the OSPF protocol (applying ECMP rules) for routing it. The algorithm searches for the set of link weights that optimize the routing. In particular, the target is minimizing a congestion metric computed as a function of both the worst-case link utilization and the average link utilization. The algorithm is based on applying a GRASP heuristic approach (Greedy Randomzied Adaptive Search Procedure).";
127        }
128
129        @Override
130        public List<Triple<String, String, String>> getParameters()
131        {
132                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
133                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
134        }
135
136        private double greedyRandomizedWeightChoice (Link e , DoubleMatrix1D currentSol , int maxLinkWeight , double rclRandomnessFactor , int differenceInWeightToBeNeighbors , double weightOfMaxUtilizationInObjectiveFunction , NetPlan np , Random rng)
137        {
138                Pair<double [],int []> pair = ospfEngine.computeSolutionsVaryingLinkWeight (e , currentSol , null , differenceInWeightToBeNeighbors);
139                double [] objFunc_w = pair.getFirst();
140                int [] wIds_w = pair.getSecond();
141                
142                /* Here if there is some greedy information to consider also */
143                double maxObjFunc = -Double.MAX_VALUE;
144                double minObjFunc = Double.MAX_VALUE;
145                for (int cont = 0 ; cont < wIds_w.length ; cont ++)
146                {
147                        final double greedyObjFunction = objFunc_w [cont];
148                        maxObjFunc = Math.max(maxObjFunc,greedyObjFunction);
149                        minObjFunc = Math.min(minObjFunc,greedyObjFunction);
150                }
151                
152                /* Compute the obj function threshold to be a restricted candidate  */
153                final double rclThresholdObjFunc = minObjFunc + (maxObjFunc - minObjFunc) * rclRandomnessFactor;
154                ArrayList<Integer> rcl = new ArrayList<Integer> (maxLinkWeight);
155                for (int cont = 0 ; cont < wIds_w.length ; cont ++)
156                {
157                        final double greedyObjFunction = objFunc_w [cont];
158                        if (greedyObjFunction <= rclThresholdObjFunc) rcl.add (cont);
159                }
160                final int chosenIndexOfTheWeight = rcl.get(rng.nextInt(rcl.size()));
161                final int chosenWeight = wIds_w [chosenIndexOfTheWeight];
162                final double chosenObjFunc = objFunc_w [chosenIndexOfTheWeight];
163                currentSol.set(e.getIndex (), (double) chosenWeight);
164                return chosenObjFunc;
165        }
166
167}