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