001/*******************************************************************************
002 * Copyright (c) 2017 Pablo Pavon Marino and others.
003 * All rights reserved. This program and the accompanying materials
004 * are made available under the terms of the 2-clause BSD License 
005 * which accompanies this distribution, and is available at
006 * https://opensource.org/licenses/BSD-2-Clause
007 *
008 * Contributors:
009 *     Pablo Pavon Marino and others - initial API and implementation
010 *******************************************************************************/
011package com.net2plan.examples.ocnbook.offline;
012
013
014import cern.colt.matrix.tdouble.DoubleMatrix1D;
015import com.net2plan.interfaces.networkDesign.IAlgorithm;
016import com.net2plan.interfaces.networkDesign.Link;
017import com.net2plan.interfaces.networkDesign.Net2PlanException;
018import com.net2plan.interfaces.networkDesign.NetPlan;
019import com.net2plan.libraries.IPUtils;
020import com.net2plan.utils.Constants.RoutingType;
021import com.net2plan.utils.InputParameter;
022import com.net2plan.utils.Pair;
023import com.net2plan.utils.TimeTrace;
024import com.net2plan.utils.Triple;
025
026import java.io.File;
027import java.util.*;
028
029/**
030 * Searches for the OSPF link weights that minimize a measure of congestion, using a GRASP heuristic
031 * 
032 * The time evolution of different metrics can be stored in output files, for later processing. 
033 * 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 
034 * <a href="http://eu.wiley.com/WileyCDA/WileyTitle/productCd-1119013356.html">book</a> using this algorithm.
035 * @net2plan.description
036 * @net2plan.keywords IP/OSPF, Flow assignment (FA), GRASP
037 * @net2plan.ocnbooksections Section 12.7
038 * @net2plan.inputParameters 
039 * @author Pablo Pavon-Marino
040 */
041public class Offline_fa_ospfWeightOptimization_GRASP implements IAlgorithm
042{
043        private TimeTrace stat_objFunction;
044        private OSPFHeuristicUtils ospfEngine;
045        
046        private InputParameter grasp_initializationType = new InputParameter ("grasp_initializationType", "#select# random" , "The type of initialization of the OSPF link weights");
047        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);
048        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");
049        private InputParameter algorithm_randomSeed = new InputParameter ("algorithm_randomSeed", (long) 1 , "Seed of the random number generator");
050        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");
051        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);
052        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);
053        private InputParameter algorithm_maxExecutionTimeInSeconds = new InputParameter ("algorithm_maxExecutionTimeInSeconds", (double) 60 , "Algorithm maximum running time in seconds" , 0 , false , Double.MAX_VALUE , true);
054        private InputParameter grasp_maxNumIterations = new InputParameter ("grasp_maxNumIterations", (int) 50000 , "Maximum number of iterations" , 1 , Integer.MAX_VALUE);
055
056        @Override
057        public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters)
058        {
059                /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */
060                InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters);
061
062                /* Basic checks */
063                final int N = netPlan.getNumberOfNodes();
064                final int E = netPlan.getNumberOfLinks();
065                if (N == 0) throw new Net2PlanException("The input design must have nodes");
066                netPlan.removeAllUnicastRoutingInformation();
067                netPlan.setRoutingTypeAllDemands (RoutingType.HOP_BY_HOP_ROUTING);
068                
069                Random rng = new Random (algorithm_randomSeed.getLong());
070                this.ospfEngine = new OSPFHeuristicUtils(netPlan, ospf_maxLinkWeight.getInt (), ospf_weightOfMaxUtilizationInObjectiveFunction.getDouble(), rng);
071                final long algorithmInitialtime = System.nanoTime();
072                final long algorithmEndtime = algorithmInitialtime + (long) (algorithm_maxExecutionTimeInSeconds.getDouble() * 1E9);
073                
074                this.stat_objFunction = new TimeTrace ();
075                
076                DoubleMatrix1D bestSol = null;
077                double bestObjFunction = Double.MAX_VALUE;
078
079                int iterationCounter = 0;
080                while ((System.nanoTime() < algorithmEndtime) && (iterationCounter < grasp_maxNumIterations.getInt ()))
081                {
082                        iterationCounter ++;
083                        
084                        /* Try a greedy randomized solution */
085
086                        /* Get an initial solution */
087                        Pair<DoubleMatrix1D,Double> p = ospfEngine.getInitialSolution (grasp_initializationType.getString());
088                        DoubleMatrix1D currentSol = p.getFirst();
089                        double currentObjFunction = p.getSecond();
090                        
091                        /* Greedy approach for each link */
092                        List<Link> shuffledLinks = new ArrayList<Link> (netPlan.getLinks());
093                        Collections.shuffle(shuffledLinks , rng);
094                        for (Link e : shuffledLinks)
095                                currentObjFunction = greedyRandomizedWeightChoice (e , currentSol , ospf_maxLinkWeight.getInt () , grasp_rclRandomnessFactor.getDouble() , grasp_differenceInWeightToBeNeighbors.getInt () , ospf_weightOfMaxUtilizationInObjectiveFunction.getDouble() , netPlan , rng);
096
097                        final double greedySolutionCongestion = currentObjFunction; 
098                        
099                        /* Update the incumbent solution */
100                        if (currentObjFunction < bestObjFunction) { bestObjFunction = currentObjFunction; bestSol = currentSol.copy (); }
101
102                        /* Local search */
103                        Pair<Double,Integer> localSearchRes = ospfEngine.localSearch(currentSol, currentObjFunction, grasp_differenceInWeightToBeNeighbors.getInt (), true);
104                        currentObjFunction = localSearchRes.getFirst();
105
106                        /* Update the incumbent solution */
107                        if (currentObjFunction < bestObjFunction) { bestObjFunction = currentObjFunction; bestSol = currentSol.copy (); }
108                        
109                        stat_objFunction.add(iterationCounter, new double [] { greedySolutionCongestion , currentObjFunction } );
110                }
111                
112                stat_objFunction.printToFile(new File (algorithm_outputFileNameRoot.getString () + "_D" + grasp_differenceInWeightToBeNeighbors.getInt () + "_cong.txt"));
113
114                IPUtils.setECMPForwardingRulesFromLinkWeights(netPlan, bestSol);
115
116                System.out.println("Ok! Best solution OF: " + bestObjFunction);
117                return "Ok! Best OF: " + bestObjFunction;
118        }
119
120        @Override
121        public String getDescription()
122        {
123                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).";
124        }
125
126        @Override
127        public List<Triple<String, String, String>> getParameters()
128        {
129                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
130                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
131        }
132
133        private double greedyRandomizedWeightChoice (Link e , DoubleMatrix1D currentSol , int maxLinkWeight , double rclRandomnessFactor , int differenceInWeightToBeNeighbors , double weightOfMaxUtilizationInObjectiveFunction , NetPlan np , Random rng)
134        {
135                Pair<double [],int []> pair = ospfEngine.computeSolutionsVaryingLinkWeight (e , currentSol , null , differenceInWeightToBeNeighbors);
136                double [] objFunc_w = pair.getFirst();
137                int [] wIds_w = pair.getSecond();
138                
139                /* Here if there is some greedy information to consider also */
140                double maxObjFunc = -Double.MAX_VALUE;
141                double minObjFunc = Double.MAX_VALUE;
142                for (int cont = 0 ; cont < wIds_w.length ; cont ++)
143                {
144                        final double greedyObjFunction = objFunc_w [cont];
145                        maxObjFunc = Math.max(maxObjFunc,greedyObjFunction);
146                        minObjFunc = Math.min(minObjFunc,greedyObjFunction);
147                }
148                
149                /* Compute the obj function threshold to be a restricted candidate  */
150                final double rclThresholdObjFunc = minObjFunc + (maxObjFunc - minObjFunc) * rclRandomnessFactor;
151                ArrayList<Integer> rcl = new ArrayList<Integer> (maxLinkWeight);
152                for (int cont = 0 ; cont < wIds_w.length ; cont ++)
153                {
154                        final double greedyObjFunction = objFunc_w [cont];
155                        if (greedyObjFunction <= rclThresholdObjFunc) rcl.add (cont);
156                }
157                final int chosenIndexOfTheWeight = rcl.get(rng.nextInt(rcl.size()));
158                final int chosenWeight = wIds_w [chosenIndexOfTheWeight];
159                final double chosenObjFunc = objFunc_w [chosenIndexOfTheWeight];
160                currentSol.set(e.getIndex (), (double) chosenWeight);
161                return chosenObjFunc;
162        }
163
164}