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.HashMap; 015import java.util.LinkedList; 016import java.util.List; 017import java.util.Map; 018import java.util.Random; 019 020import cern.colt.matrix.tdouble.DoubleMatrix1D; 021 022import com.net2plan.interfaces.networkDesign.IAlgorithm; 023import com.net2plan.interfaces.networkDesign.Link; 024import com.net2plan.interfaces.networkDesign.Net2PlanException; 025import com.net2plan.interfaces.networkDesign.NetPlan; 026import com.net2plan.libraries.IPUtils; 027import com.net2plan.utils.Constants.OrderingType; 028import com.net2plan.utils.Constants.RoutingType; 029import com.net2plan.utils.DoubleUtils; 030import com.net2plan.utils.InputParameter; 031import com.net2plan.utils.Pair; 032import com.net2plan.utils.TimeTrace; 033import com.net2plan.utils.Triple; 034 035/** 036 * Searches for the OSPF link weights that minimize a measure of congestion, using a tabu search heuristic 037 * 038 * The time evolution of different metrics can be stored in output files, for later processing. 039 * As an example, see the <a href="../../../../../../graphGeneratorFiles/fig_sec12_5_ospfWeightTabuSearch.m">{@code fig_sec12_5_ospfWeightTabuSearch.m}</a> MATLAB file used for generating the graph/s of the case study in the 040 * <a href="http://eu.wiley.com/WileyCDA/WileyTitle/productCd-1119013356.html">book</a> using this algorithm. 041 * @net2plan.description 042 * @net2plan.keywords IP/OSPF, Flow assignment (FA), Tabu search (TS) 043 * @net2plan.ocnbooksections Section 12.5 044 * @net2plan.inputParameters 045 * @author Pablo Pavon-Marino 046 */ 047public class Offline_fa_ospfWeightOptimization_tabuSearch implements IAlgorithm 048{ 049 private int numIterations; 050 private int numIterationsNonImprovingBestSolutionSinceLastRandomization; 051 private TimeTrace stat_objFunction; 052 private OSPFHeuristicUtils ospfEngine; 053 private double [][] numberOccurrencies_ew; 054 055 private InputParameter ts_initializationType = new InputParameter ("ts_initializationType", "#select# random" , "The type of initialization of the OSPF link weights"); 056 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); 057 private InputParameter algorithm_randomSeed = new InputParameter ("algorithm_randomSeed", (long) 1 , "Seed of the random number generator"); 058 private InputParameter algorithm_outputFileNameRoot = new InputParameter ("algorithm_outputFileNameRoot", "ospfWeghtOptimization_tabu" , "Root of the file name to be used in the output files. If blank, no output"); 059 private InputParameter ts_differenceInWeightToBeNeighbors = new InputParameter ("ts_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 ts_tabuListSizeAsFractionOfLinks = new InputParameter ("ts_tabuListSizeAsFractionOfLinks", (double) 0.5 , "Size of the tabe list, given as a fraction of the total number of links" , 0 , true , 1 , true); 061 private InputParameter algorithm_maxExecutionTimeInSeconds = new InputParameter ("algorithm_maxExecutionTimeInSeconds", (double) 60 , "Algorithm maximum running time in seconds" , 0 , false , Double.MAX_VALUE , true); 062 private InputParameter ts_maxNumIterations = new InputParameter ("ts_maxNumIterations", (int) 50000 , "Maximum number of iterations" , 1 , Integer.MAX_VALUE); 063 private InputParameter ts_maxNumIterationsNonImprovingIncumbentSolution = new InputParameter ("ts_maxNumIterationsNonImprovingIncumbentSolution", (int) 15 , "Num iterations non improving the incumbent solution, to restart the search in a randomized solution" , 1 , Integer.MAX_VALUE); 064 private InputParameter ts_aspirationCriterion = new InputParameter ("ts_aspirationCriterion", true , "Apply aspiration criterion in tabu search"); 065 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); 066 067 @Override 068 public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters) 069 { 070 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 071 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 072 073 /* Basic checks */ 074 final int N = netPlan.getNumberOfNodes(); 075 final int E = netPlan.getNumberOfLinks(); 076 if (N == 0) throw new Net2PlanException("The input design must have nodes"); 077 netPlan.removeAllUnicastRoutingInformation(); 078 netPlan.setRoutingType (RoutingType.HOP_BY_HOP_ROUTING); 079 080 /* Initialize some variables */ 081 final long algorithmInitialtime = System.nanoTime(); 082 final long algorithmEndtime = algorithmInitialtime + (long) (algorithm_maxExecutionTimeInSeconds.getDouble() * 1E9); 083 final int tabuListSize = (int) Math.ceil(E * ts_tabuListSizeAsFractionOfLinks.getDouble()); 084 if (tabuListSize >= E) throw new Net2PlanException ("The tabu list size is larger or equal than the number of links: all jumps would be tabu"); 085 086 Random rng = new Random (algorithm_randomSeed.getLong()); 087 this.ospfEngine = new OSPFHeuristicUtils(netPlan, ospf_maxLinkWeight.getInt (), ospf_weightOfMaxUtilizationInObjectiveFunction.getDouble(), rng); 088 this.numberOccurrencies_ew = new double [E][ospf_maxLinkWeight.getInt ()]; 089 090 /* Tabu list info. Because of aspiration criterion, a link can appear more than once in the tabu list */ 091 Map<Link,Integer> numEntriesTabuList_e = new HashMap<Link,Integer> (); for (Link e : netPlan.getLinks()) numEntriesTabuList_e.put(e, 0); 092 LinkedList<Link> tabuList_e = new LinkedList<Link> (); 093 094 Pair<DoubleMatrix1D,Double> p = ospfEngine.getInitialSolution (ts_initializationType.getString()); 095 DoubleMatrix1D currentSol = p.getFirst(); 096 double currentObjFunction = p.getSecond(); 097 098 DoubleMatrix1D bestSol = currentSol.copy (); 099 double bestObjFunction = currentObjFunction; 100 double bestObjFunctionSinceLastRandomization = currentObjFunction; 101 102 this.numIterations= 0; 103 this.numIterationsNonImprovingBestSolutionSinceLastRandomization = 0; 104 this.stat_objFunction = new TimeTrace (); 105 106 stat_objFunction.add(0.0, currentObjFunction); 107 108 /* update the long-term memory*/ 109 for (int eIndex = 0 ; eIndex < E ; eIndex ++) this.numberOccurrencies_ew [eIndex][(int) (currentSol.get(eIndex)) - 1] ++; 110 111 System.out.println("Initial objFunction: " + bestObjFunction + ", tabu list tenure: " + tabuListSize); 112 113 while ((System.nanoTime() < algorithmEndtime) && (numIterations < ts_maxNumIterations.getInt ())) 114 { 115 this.numIterations ++; 116 Link bestNeighborLink = null; 117 int bestNeighborWeight = -1; 118 double bestNeighborObjFunction = Double.MAX_VALUE; 119 120 /* Neighbors differing in one link */ 121 for (Link e1 : netPlan.getLinks()) 122 { 123 final boolean isTabu = (numEntriesTabuList_e.get(e1) > 0); 124 if (!ts_aspirationCriterion.getBoolean() && isTabu) continue; 125 126 final int currentWeight1 = (int) currentSol.get(e1.getIndex ()); 127 for (int w1 = 1 ; w1 <= ospf_maxLinkWeight.getInt () ; w1 ++) 128 { 129 if (w1 == currentWeight1) continue; 130 if (Math.abs(w1 - currentWeight1) > ts_differenceInWeightToBeNeighbors.getInt ()) continue; 131 currentSol.set(e1.getIndex (), (double) w1); 132 final double neighborObjFunction = ospfEngine.computeObjectiveFunction(currentSol).getFirst(); 133 currentSol.set(e1.getIndex (), (double) currentWeight1); 134 135 /* Update best neighbor if (i) not tabu and improves best neighbor, (ii) tabu, but aspiration criterion is active and improves incumbent solution */ 136 if ( (!isTabu && (neighborObjFunction < bestNeighborObjFunction)) || (isTabu && ts_aspirationCriterion.getBoolean() && (neighborObjFunction < bestObjFunction)) ) 137 { 138 if (isTabu) System.out.println ("Aspiration criterion applied"); 139 bestNeighborLink = e1; bestNeighborWeight = w1; bestNeighborObjFunction = neighborObjFunction; 140 } 141 } 142 } 143 144 if (bestNeighborLink == null) { throw new RuntimeException ("This should not happen: it means a too large tabu list"); } 145 146 /* Jump to the neighbor solution */ 147 currentSol.set(bestNeighborLink.getIndex (), (double) bestNeighborWeight); currentObjFunction = bestNeighborObjFunction; 148 149 /* update tabu list */ 150 if (tabuList_e.size() == tabuListSize) { Link eToRemove = tabuList_e.removeFirst(); numEntriesTabuList_e.put(eToRemove, numEntriesTabuList_e.get(eToRemove) - 1); if (numEntriesTabuList_e.get(eToRemove) < 0) throw new RuntimeException ("Bad"); } 151 tabuList_e.addLast(bestNeighborLink); numEntriesTabuList_e.put(bestNeighborLink , numEntriesTabuList_e.get(bestNeighborLink) + 1); 152 153 /* update the incumbent solution */ 154 if (currentObjFunction < bestObjFunctionSinceLastRandomization) 155 { 156 this.numIterationsNonImprovingBestSolutionSinceLastRandomization = 0; 157 bestObjFunctionSinceLastRandomization = currentObjFunction; 158 System.out.println("Improving best objFunction since last randomization: " + currentObjFunction); 159 if (currentObjFunction < bestObjFunction) { bestObjFunction = currentObjFunction; bestSol = currentSol.copy (); System.out.println("Improving best objFunction: " + bestObjFunction); } 160 } 161 else 162 this.numIterationsNonImprovingBestSolutionSinceLastRandomization ++; 163 164 /* update the long-term memory*/ 165 for (int eIndex = 0 ; eIndex < E ; eIndex ++) this.numberOccurrencies_ew [eIndex][(int) (currentSol.get(eIndex)) - 1] ++; 166 167 /* Check if too many iterations without improving the incumbent solution */ 168 if (numIterationsNonImprovingBestSolutionSinceLastRandomization > ts_maxNumIterationsNonImprovingIncumbentSolution.getInt ()) 169 { 170 System.out.println("Randomization!!"); 171 172 /* Initialize tabu list */ 173 tabuList_e.clear(); for (Link e : netPlan.getLinks()) numEntriesTabuList_e.put(e, 0); 174 175 /* Make a diversification jump: incumbent solution, then each link with prob 0.5 randomizes its weight */ 176 currentSol = bestSol.copy(); 177 for (Link e : netPlan.getLinks()) 178 { 179 if (rng.nextBoolean()) continue; 180 final int [] leastUtilizedWeightsMinus1 = DoubleUtils.sortIndexes(this.numberOccurrencies_ew [e.getIndex ()], OrderingType.ASCENDING); 181 final int randomlyChosenWeight = leastUtilizedWeightsMinus1 [rng.nextInt(ospf_maxLinkWeight.getInt ()/2)] + 1; 182 currentSol.set(e.getIndex (), (double) randomlyChosenWeight); 183 } 184 currentObjFunction = ospfEngine.computeObjectiveFunction(currentSol).getFirst(); 185 bestObjFunctionSinceLastRandomization = currentObjFunction; 186 this.numIterationsNonImprovingBestSolutionSinceLastRandomization = 0; 187 } 188 189 final double currentTimeInSecs = (System.nanoTime() - algorithmInitialtime) * 1e-9; 190 stat_objFunction.add(currentTimeInSecs , currentObjFunction); 191 } 192 193 IPUtils.setECMPForwardingRulesFromLinkWeights(netPlan, bestSol); 194 195 final String completeFileName = algorithm_outputFileNameRoot.getString () + "_0" + ((int) (10*ts_tabuListSizeAsFractionOfLinks.getDouble())) + ((ts_aspirationCriterion.getBoolean())? "_asp" : "_noasp"); 196 stat_objFunction.printToFile(new File (completeFileName + "_cong.txt")); 197 198 System.out.println("Ok! ObjFunction: " + bestObjFunction + ", num it: " + numIterations + ", Best solution: " + bestSol); 199 return "Ok! ObjFunction: " + bestObjFunction + ", num it: " + numIterations; 200 } 201 202 @Override 203 public String getDescription() 204 { 205 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 tabu search heuristic approach."; 206 } 207 208 @Override 209 public List<Triple<String, String, String>> getParameters() 210 { 211 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 212 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 213 } 214 215}