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.Arrays; 015import java.util.Collections; 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 an ant-colony optimization (ACO) 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_8_ospfWeightACO.m">{@code fig_sec12_8_ospfWeightACO.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), Ant Colony Optimization (ACO) 043 * @net2plan.ocnbooksections Section 12.8 044 * @net2plan.inputParameters 045 * @author Pablo Pavon-Marino 046 */ 047public class Offline_fa_ospfWeightOptimization_ACO implements IAlgorithm 048{ 049 private TimeTrace stat_objFunction; 050 private TimeTrace stat_pheromone_ew; 051 private OSPFHeuristicUtils ospfEngine; 052 053 private InputParameter aco_initializationType = new InputParameter ("aco_initializationType", "#select# random" , "The type of initialization of the OSPF link weights"); 054 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); 055 private InputParameter aco_differenceInWeightToBeNeighbors = new InputParameter ("aco_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"); 056 private InputParameter algorithm_randomSeed = new InputParameter ("algorithm_randomSeed", (long) 1 , "Seed of the random number generator"); 057 private InputParameter algorithm_outputFileNameRoot = new InputParameter ("algorithm_outputFileNameRoot", "ospfWeghtOptimization_aco" , "Root of the file name to be used in the output files. If blank, no output"); 058 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); 059 private InputParameter algorithm_maxExecutionTimeInSeconds = new InputParameter ("algorithm_maxExecutionTimeInSeconds", (double) 5 , "Algorithm maximum running time in seconds" , 0 , false , Double.MAX_VALUE , true); 060 private InputParameter aco_maxNumIterations = new InputParameter ("aco_maxNumIterations", (int) 100 , "Maximum number of iterations" , 1 , Integer.MAX_VALUE); 061 private InputParameter aco_pheromoneEvaporationRate = new InputParameter ("aco_pheromoneEvaporationRate", (double) 0.5 , "Evaporation factor of the pheromones in the ACO model" , 0 , true , 1 , true); 062 private InputParameter aco_factorImportanceOfPheromones = new InputParameter ("aco_factorImportanceOfPheromones", (double) 1 , "Importance of pheromones vs greedy step for the ants" , 0 , true , 1 , true); 063 private InputParameter aco_numAnts = new InputParameter ("aco_numAnts", (int) 10 , "Number of ants in the system" , 1 , Integer.MAX_VALUE); 064 private InputParameter aco_fractionOfEliteAntsContributingToPheromones = new InputParameter ("aco_fractionOfEliteAntsContributingToPheromones", (double) 0.5 , "Only the best fraction of the ants (round up) contributes to pheromone reinforcement" , 0 , true , 1 , true); 065 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 Random rng = new Random (algorithm_randomSeed.getLong()); 081 this.ospfEngine = new OSPFHeuristicUtils(netPlan, ospf_maxLinkWeight.getInt (), ospf_weightOfMaxUtilizationInObjectiveFunction.getDouble(), rng); 082 final long algorithmInitialtime = System.nanoTime(); 083 final long algorithmEndtime = algorithmInitialtime + (long) (algorithm_maxExecutionTimeInSeconds.getDouble() * 1E9); 084 085 this.stat_objFunction = new TimeTrace (); 086 this.stat_pheromone_ew = new TimeTrace (); 087 DoubleMatrix1D bestSol = null; 088 double bestObjFunction = Double.MAX_VALUE; 089 090 /* Initialize all pheromones to zero */ 091 double [][] pheromones_ew = new double [E][ospf_maxLinkWeight.getInt ()]; for (int e = 0 ; e < E ; e ++) Arrays.fill (pheromones_ew [e] , 1.0); 092 093 int iterationCounter = 0; 094 while ((System.nanoTime() < algorithmEndtime) && (iterationCounter < aco_maxNumIterations.getInt ())) 095 { 096 iterationCounter ++; 097 098 /* To store each ant solution and objective function */ 099 double [] objFunc_a = new double [aco_numAnts.getInt ()]; 100 ArrayList<DoubleMatrix1D> sol_a = new ArrayList<DoubleMatrix1D> (aco_numAnts.getInt ()); 101 for (int contAnt = 0 ; contAnt < aco_numAnts.getInt () ; contAnt ++) 102 { 103 Pair<DoubleMatrix1D,Double> p = ospfEngine.getInitialSolution (aco_initializationType.getString ()); 104 DoubleMatrix1D currentSol = p.getFirst(); 105 106 /* Create a randomly shuffled sequence of link ids */ 107 List<Link> shuffledLinks = new ArrayList<Link> (netPlan.getLinks()); 108 Collections.shuffle(shuffledLinks , rng); 109 110 /* The ant movements */ 111 for (Link e : shuffledLinks) 112 antWeightChoice (e , currentSol , ospf_maxLinkWeight.getInt () , aco_differenceInWeightToBeNeighbors.getInt () , pheromones_ew [e.getIndex ()] , aco_factorImportanceOfPheromones.getDouble() , rng); 113 114 double objFunc = ospfEngine.computeObjectiveFunction(currentSol).getFirst(); 115 objFunc_a [contAnt] = objFunc; 116 sol_a.add(currentSol); 117 118 /* Update the incumbent solution */ 119 if (objFunc < bestObjFunction) { bestObjFunction = objFunc; bestSol = currentSol.copy (); } 120 121 } 122 123 /* Truncate it in case we end the algorithm ahead of time */ 124 objFunc_a = Arrays.copyOf(objFunc_a, sol_a.size()); 125 126 System.out.println("sol_a: "); 127 128 /* Increase the pheromones */ 129 int [] orderedAntIndexes = DoubleUtils.sortIndexes(objFunc_a, OrderingType.ASCENDING); 130 final int numEliteAnts = (int) Math.ceil(sol_a.size() * aco_fractionOfEliteAntsContributingToPheromones.getDouble()); 131 for (int cont = 0 ; cont < numEliteAnts ; cont ++) 132 { 133 final int a = orderedAntIndexes [cont]; 134 final double objFuncAnt = objFunc_a [a]; 135 for (Link e : netPlan.getLinks()) 136 { 137 final int linkWeightAnt = (int) sol_a.get(a).get(e.getIndex ()); 138 pheromones_ew[e.getIndex ()][linkWeightAnt-1] += 1.0 / objFuncAnt; 139 } 140 } 141 142 /* Evaporate pheromones */ 143 for (Link e : netPlan.getLinks()) 144 { 145 double [] pheromone_w = pheromones_ew [e.getIndex ()]; 146 for (int w = 0; w < pheromone_w.length ; w ++) pheromone_w[w] *= 1 - aco_pheromoneEvaporationRate.getDouble(); 147 } 148 149 /* Update the stats */ 150 //this.stat_objFunction.add(iterationCounter , Arrays.copyOf (objFunc_a , numAnts)); 151 this.stat_objFunction.add(iterationCounter , copyOf (objFunc_a , sol_a.size() , aco_numAnts.getInt ())); 152 this.stat_pheromone_ew.add (iterationCounter , copyOf(pheromones_ew)); 153 } 154 155 final String baseFileName = algorithm_outputFileNameRoot.getString () + "_a" + aco_numAnts.getInt () + "_rho" + ((int) (aco_pheromoneEvaporationRate.getDouble()*100)) + "_g" + ((int) (100*aco_factorImportanceOfPheromones.getDouble())); 156 stat_objFunction.printToFile(new File (baseFileName + "_objFunc.txt")); 157 stat_pheromone_ew.printToFile(new File (baseFileName + "_pheromones_ew.txt")); 158 159 IPUtils.setECMPForwardingRulesFromLinkWeights(netPlan, bestSol); 160 161 System.out.println("Ok! Best solution OF: " + bestObjFunction); 162 return "Ok! Best OF: " + bestObjFunction; 163 } 164 165 @Override 166 public String getDescription() 167 { 168 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 an ant-colony optimization (ACO) heuristic approach."; 169 } 170 171 @Override 172 public List<Triple<String, String, String>> getParameters() 173 { 174 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 175 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 176 } 177 178 private void antWeightChoice (Link e , DoubleMatrix1D currentSol , int maxLinkWeight , int differenceInWeightToBeNeighbors , double [] pheromone_w , double factorImportanceOfPheromones , Random rng) 179 { 180 /* Sum the probabilities coming from the pheromones */ 181 double [] accumProbabilities = new double [pheromone_w.length]; 182 double accumProbabilitySum = 0; 183 for (int w = 0 ; w < accumProbabilities.length ; w ++) { accumProbabilities [w] = pheromone_w [w] * factorImportanceOfPheromones; accumProbabilitySum += accumProbabilities [w]; } 184 185 if (factorImportanceOfPheromones != 1) 186 { 187 Pair<double [],int []> pair = ospfEngine.computeSolutionsVaryingLinkWeight (e , currentSol , null , differenceInWeightToBeNeighbors); 188 final double [] objFunctions = pair.getFirst(); 189 final int [] weights = pair.getSecond(); 190 191 for (int cont = 0 ; cont < objFunctions.length ; cont ++) 192 { 193 final int w = weights [cont]; 194 final double greedyObjFunction = objFunctions [cont]; 195 final double importanceToSum = (1/greedyObjFunction) * (1-factorImportanceOfPheromones); 196 accumProbabilities [w-1] += importanceToSum; 197 accumProbabilitySum += importanceToSum; 198 } 199 } 200 currentSol.set(e.getIndex (), 1.0 + (double) sampleUniformDistribution (accumProbabilities , accumProbabilitySum , rng)); 201 return ; 202 } 203 204 /* Receives a vector with values proportional to the probabilities p[s] of each option s. Returns the index of the sample chosen. 205 * Each sample s has a probability to be chosen proportional to p[s] */ 206 private int sampleUniformDistribution (double [] p , double totalSumProbabilities , Random r) 207 { 208 final double comp = r.nextDouble() * totalSumProbabilities; 209 double accumValue = 0; 210 211 double checkTotalSum = 0; for (int cont = 0 ; cont < p.length ; cont ++) checkTotalSum += p [cont]; 212 if (Math.abs(checkTotalSum - totalSumProbabilities) > 1E-3) throw new RuntimeException ("Bad"); 213 for (int cont = 0 ; cont < p.length ; cont ++) 214 { accumValue += p [cont]; if (accumValue >= comp) return cont; } 215 return p.length-1; 216 } 217 218 private double [][] copyOf (double [][] x) 219 { 220 double [][] res = new double [x.length][]; for (int c1 = 0 ; c1 < x.length ; c1 ++) res [c1] = Arrays.copyOf(x[c1], x[c1].length); return res; 221 } 222 private double [] copyOf (double [] x , int numValuesCopy , int finalSize) 223 { 224 double [] res = new double [finalSize]; for (int c1 = 0 ; c1 < numValuesCopy ; c1 ++) res [c1] = x [c1]; return res; 225 } 226}