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