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