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
011package com.net2plan.examples.ocnbook.offline;
012
013import java.io.File;
014import java.util.List;
015import java.util.Map;
016import java.util.Random;
017
018import cern.colt.matrix.tdouble.DoubleMatrix1D;
019
020import com.net2plan.interfaces.networkDesign.IAlgorithm;
021import com.net2plan.interfaces.networkDesign.Link;
022import com.net2plan.interfaces.networkDesign.Net2PlanException;
023import com.net2plan.interfaces.networkDesign.NetPlan;
024import com.net2plan.libraries.IPUtils;
025import com.net2plan.utils.InputParameter;
026import com.net2plan.utils.Pair;
027import com.net2plan.utils.TimeTrace;
028import com.net2plan.utils.Triple;
029import com.net2plan.utils.Constants.RoutingType;
030
031/**
032 * Searches for the OSPF link weights that minimize a measure of congestion, using a simulated annealing (SAN) heuristic
033 * 
034 * The time evolution of different metrics can be stored in output files, for later processing. 
035 * As an example, see the <a href="../../../../../../graphGeneratorFiles/fig_sec12_4_ospfWeightLocalSAN.m">{@code fig_sec12_4_ospfWeightSAN.m}</a> MATLAB file used for generating the graph/s of the case study in the 
036 * <a href="http://eu.wiley.com/WileyCDA/WileyTitle/productCd-1119013356.html">book</a> using this algorithm.
037 * @net2plan.description
038 * @net2plan.keywords IP/OSPF, Flow assignment (FA), Simulated annealing (SAN)
039 * @net2plan.ocnbooksections Section 12.4
040 * @net2plan.inputParameters 
041 * @author Pablo Pavon-Marino
042 */
043public class Offline_fa_ospfWeightOptimization_SAN implements IAlgorithm
044{
045        private int numIterOuterLoop;
046
047        private TimeTrace stat_objFunction;
048        private TimeTrace stat_bestObjFunction;
049        private TimeTrace stat_temperature;
050        private OSPFHeuristicUtils ospfEngine;
051
052        private InputParameter san_initializationType = new InputParameter ("san_initializationType", "#select# random" , "The type of initialization of the OSPF link weights");
053        private InputParameter san_worseCaseObjFunctionWorsening = new InputParameter ("san_worseCaseObjFunctionWorsening", (double) 0.25 , "Objective function worsening in a transition considered as worse case for initial temperature computation" , 0 , false , Double.MAX_VALUE , true);
054        private InputParameter san_geometricTemperatureReductionFactor = new InputParameter ("san_geometricTemperatureReductionFactor", (double) 0.8 , "Geometric decrease factor of the temperature" , 0 , true , 1 , true);
055        private InputParameter san_freezingProbabilityThreshold = new InputParameter ("san_freezingProbabilityThreshold", (double) 0.01 , "If the fraction of iterations with a jump, in the inner loop, is below this, the system is reheated (temperature to the initial value). If not, decreased geometrically" , 0 , true , 1 , true);
056        private InputParameter san_initialAcceptanceProbability = new InputParameter ("san_initialAcceptanceProbability", (double) 0.5 , "Acceptance probability of the worst case transition: to compute the initial temperature" , 0 , false , Double.MAX_VALUE , true);
057        private InputParameter san_maxNumIterationsInnerLoop = new InputParameter ("san_maxNumIterationsInnerLoop", (int) 1000 , "Number of iterations of the inner loop (all with the same temperature)" , 1 , Integer.MAX_VALUE);
058        private InputParameter san_maxNumIterationsOuterLoop = new InputParameter ("san_maxNumIterationsOuterLoop", (int) 50 , "Number of iterations of the outer loop" , 1 , Integer.MAX_VALUE);
059        private InputParameter san_differenceInWeightToBeNeighbors = new InputParameter ("san_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");
060        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);
061        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);
062        private InputParameter algorithm_randomSeed = new InputParameter ("algorithm_randomSeed", (long) 1 , "Seed of the random number generator");
063        private InputParameter algorithm_outputFileNameRoot = new InputParameter ("algorithm_outputFileNameRoot", "ospfWeghtOptimization_san" , "Root of the file name to be used in the output files. If blank, no output");
064        private InputParameter algorithm_maxExecutionTimeInSeconds = new InputParameter ("algorithm_maxExecutionTimeInSeconds", (double) 60 , "Algorithm maximum running time in seconds" , 0 , false , Double.MAX_VALUE , true);
065
066        
067        
068        @Override
069        public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters)
070        {
071                /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */
072                InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters);
073
074                /* Basic checks */
075                final int N = netPlan.getNumberOfNodes();
076                final int E = netPlan.getNumberOfLinks ();
077                if (N == 0) throw new Net2PlanException("The input design must have nodes");
078                netPlan.removeAllUnicastRoutingInformation();
079                netPlan.setRoutingType (RoutingType.HOP_BY_HOP_ROUTING);
080
081                final long algorithmInitialtime = System.nanoTime();
082                final long algorithmEndtime = algorithmInitialtime + (long) (algorithm_maxExecutionTimeInSeconds.getDouble() * 1E9);
083                
084                /* Compute initial solution */ 
085                Random rng = new Random (algorithm_randomSeed.getLong ());
086                this.ospfEngine = new OSPFHeuristicUtils(netPlan, ospf_maxLinkWeight.getInt (), ospf_weightOfMaxUtilizationInObjectiveFunction.getDouble (), rng);
087                this.stat_bestObjFunction = new TimeTrace ();
088                this.stat_objFunction = new TimeTrace ();
089                this.stat_temperature = new TimeTrace ();
090                this.numIterOuterLoop = 0;
091
092                Pair<DoubleMatrix1D,Double> p = ospfEngine.getInitialSolution (san_initializationType.getString ());
093                DoubleMatrix1D currentSol = p.getFirst();
094                double currentObjFunction = p.getSecond();
095                
096                /* Compute the initial and end temperatures, and the geometric temperature reduction factor */
097                final double initialTemperature = -san_worseCaseObjFunctionWorsening.getDouble () / Math.log(san_initialAcceptanceProbability.getDouble ());
098
099                System.out.println("initialTemperature: " + initialTemperature + ", geometricReductionFactor: " + san_geometricTemperatureReductionFactor.getDouble ());
100                
101                double currentTemperature = initialTemperature;
102                DoubleMatrix1D bestSol = currentSol.copy ();
103                double bestObjFunction = currentObjFunction;
104
105                stat_objFunction.add(0.0 , currentObjFunction);
106                stat_bestObjFunction.add(0.0 , bestObjFunction);
107                stat_temperature.add(0.0 , currentTemperature);
108                while ((System.nanoTime() < algorithmEndtime) && (numIterOuterLoop < san_maxNumIterationsOuterLoop.getInt ()))
109                {
110                        numIterOuterLoop ++;
111                        int numFrozenJumps = 0;
112                        for (int innerIt = 0 ; innerIt < san_maxNumIterationsInnerLoop.getInt () ; innerIt ++)
113                        {
114                                final Link neighborDifferentLink = netPlan.getLink (rng.nextInt(E));
115                                final double oldWeight = currentSol.get(neighborDifferentLink.getIndex ());
116                                double newWeight = 1;
117                                do 
118                                { newWeight = oldWeight + rng.nextInt(2*san_differenceInWeightToBeNeighbors.getInt ()+1) - san_differenceInWeightToBeNeighbors.getInt (); } 
119                                while ((oldWeight == newWeight) || (newWeight < 1) || (newWeight > ospf_maxLinkWeight.getInt ()));
120
121                                currentSol.set(neighborDifferentLink.getIndex (), newWeight);
122                                final double neighborObjFunction = ospfEngine.computeObjectiveFunction(currentSol).getFirst();
123                                
124                                if ((neighborObjFunction < currentObjFunction) || (rng.nextDouble() < Math.exp(-(neighborObjFunction - currentObjFunction)/currentTemperature)))
125                                {
126                                        /* If this jump does not change objFunction, consider it a frozen one */
127                                        if (currentObjFunction == neighborObjFunction) numFrozenJumps ++;
128                                        /* jump to the neighbor solution */
129                                        currentObjFunction = neighborObjFunction;
130                                        if (neighborObjFunction < bestObjFunction) { bestObjFunction = neighborObjFunction; bestSol = currentSol.copy (); System.out.println("Improving solution (temp: " + currentTemperature + ", objFunction: "+  bestObjFunction); }
131                                }
132                                else
133                                {
134                                        currentSol.set(neighborDifferentLink.getIndex (), oldWeight);
135                                        numFrozenJumps ++;
136                                }
137                                final double currentTimeInSecs = (System.nanoTime() - algorithmInitialtime) * 1e-9;
138                                stat_objFunction.add(currentTimeInSecs , currentObjFunction);
139                                stat_bestObjFunction.add(currentTimeInSecs , bestObjFunction);
140                                stat_temperature.add(currentTimeInSecs , currentTemperature);
141                        }
142                        if (((double) numFrozenJumps)/san_maxNumIterationsInnerLoop.getInt () > 1-san_freezingProbabilityThreshold.getDouble ())
143                                { currentTemperature = initialTemperature; System.out.println("Reheat the system."); } // reheat the system  
144                        else
145                                { currentTemperature *= san_geometricTemperatureReductionFactor.getDouble(); System.out.println("Decrease temperature."); } // decrease temperature
146                }
147                
148                IPUtils.setECMPForwardingRulesFromLinkWeights(netPlan, bestSol);
149
150                stat_bestObjFunction.printToFile(new File (algorithm_outputFileNameRoot.getString () + "_bestObjFunc.txt"));
151                stat_objFunction.printToFile(new File (algorithm_outputFileNameRoot.getString () + "_objFunc.txt"));
152                stat_temperature.printToFile(new File (algorithm_outputFileNameRoot.getString () + "_temp.txt"));
153                System.out.println("Ok! ObjFunction: " + bestObjFunction );
154                return "Ok! ObjFunction: " + bestObjFunction;
155        }
156
157        @Override
158        public String getDescription()
159        {
160                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 simulated annealign (SAN) heuristic approach.";
161        }
162
163        @Override
164        public List<Triple<String, String, String>> getParameters()
165        {
166                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
167                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
168        }
169
170}