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}