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.List; 014import java.util.Map; 015import java.util.Random; 016 017import cern.colt.matrix.tdouble.DoubleMatrix1D; 018 019import com.net2plan.interfaces.networkDesign.IAlgorithm; 020import com.net2plan.interfaces.networkDesign.Net2PlanException; 021import com.net2plan.interfaces.networkDesign.NetPlan; 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 028/** 029 * Searches for the OSPF link weights that minimize a measure of congestion, using a local-search heuristic 030 * 031 * The time evolution of different metrics can be stored in output files, for later processing. 032 * As an example, see the <a href="../../../../../../graphGeneratorFiles/fig_sec12_3_ospfWeightLocalSearch.m">{@code fig_sec12_3_ospfWeightLocalSearch.m}</a> MATLAB file used for generating the graph/s of the case study in the 033 * <a href="http://eu.wiley.com/WileyCDA/WileyTitle/productCd-1119013356.html">book</a> using this algorithm. 034 * @net2plan.description 035 * @net2plan.keywords IP/OSPF, Flow assignment (FA), Local search (LS) heuristic 036 * @net2plan.ocnbooksections Section 12.3 037 * @net2plan.inputParameters 038 * @author Pablo Pavon-Marino 039 */ 040public class Offline_fa_ospfWeightOptimization_localSearch implements IAlgorithm 041{ 042 private OSPFHeuristicUtils ospfEngine; 043 private TimeTrace stat_objFunction; 044 private TimeTrace stat_computationTime; 045 private TimeTrace stat_numObjFuncEvaluations; 046 047 private InputParameter algorithm_randomSeed = new InputParameter ("algorithm_randomSeed", (long) 1 , "Seed of the random number generator"); 048 private InputParameter algorithm_numSamples = new InputParameter ("algorithm_numSamples", (int) 100 , "Number of repetitions, returns the last, but saves in file all of them" , 1 , Integer.MAX_VALUE); 049 private InputParameter algorithm_outputFileNameRoot = new InputParameter ("algorithm_outputFileNameRoot", "ospfWeghtOptimization_ls" , "Root of the file name to be used in the output files. If blank, no output"); 050 private InputParameter localSearch_initializationType = new InputParameter ("localSearch_initializationType", "#select# random" , "The type of initialization of the OSPF link weights"); 051 private InputParameter localSearch_type = new InputParameter ("localSearch_type", "#select# first-fit best-fit" , "The tpe of local search algorithm. First-fit, jumps to the first improving neighbor solution found, best-fit to the best improving neighbor"); 052 private InputParameter localSearch_differenceInWeightToBeNeighbors = new InputParameter ("localSearch_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"); 053 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); 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 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 if (N == 0) throw new Net2PlanException("The input design must have nodes"); 065 netPlan.removeAllUnicastRoutingInformation(); 066 netPlan.setRoutingType (RoutingType.HOP_BY_HOP_ROUTING); 067 068 069 /* Initialize some variables */ 070 final boolean isFirstFit = localSearch_type.getString ().equals ("first-fit"); 071 072 Random rng = new Random (algorithm_randomSeed.getLong ()); 073 this.ospfEngine = new OSPFHeuristicUtils(netPlan, ospf_maxLinkWeight.getInt (), ospf_weightOfMaxUtilizationInObjectiveFunction.getDouble(), rng); 074 this.stat_objFunction = new TimeTrace (); 075 this.stat_computationTime = new TimeTrace (); 076 this.stat_numObjFuncEvaluations = new TimeTrace (); 077 078 System.out.println("isFirstFit: " + isFirstFit); 079 080 for (int it = 0 ; it < algorithm_numSamples.getInt () ; it ++) 081 { 082 final long initTime = System.nanoTime(); 083 Pair<DoubleMatrix1D,Double> p1 = ospfEngine.getInitialSolution (localSearch_initializationType.getString()); 084 DoubleMatrix1D currentSol = p1.getFirst(); 085 double currentObjFunction = p1.getSecond(); 086 087 final Pair<Double,Integer> p2 = ospfEngine.localSearch (currentSol , currentObjFunction , localSearch_differenceInWeightToBeNeighbors.getInt () , isFirstFit); 088 final double bestObjFunc = p2.getFirst(); 089 final int numObjFunctionEvaluations = p2.getSecond(); 090 final double computationTimeIbnSeconds = (System.nanoTime() - initTime)*1e-9; 091 stat_computationTime.add(it, computationTimeIbnSeconds); 092 stat_objFunction.add(it, bestObjFunc); 093 stat_numObjFuncEvaluations.add(it, numObjFunctionEvaluations); 094 } 095 096 stat_objFunction.printToFile(new File (algorithm_outputFileNameRoot.getString () + "_D" + localSearch_differenceInWeightToBeNeighbors.getInt () + ((isFirstFit)? "_FF_" : "_BF_") + "objFunc.txt")); 097 stat_computationTime.printToFile(new File (algorithm_outputFileNameRoot.getString () + "_D" + localSearch_differenceInWeightToBeNeighbors.getInt () + ((isFirstFit)? "_FF_" : "_BF_") + "time.txt")); 098 stat_numObjFuncEvaluations.printToFile(new File (algorithm_outputFileNameRoot.getString () + "_D" + localSearch_differenceInWeightToBeNeighbors.getInt () + ((isFirstFit)? "_FF_" : "_BF_") + "numEvalObjFunc.txt")); 099 100 101 double minObjectiveFunction = Double.MAX_VALUE; 102 for (Pair<Double,Object> element : stat_objFunction.getList()) 103 minObjectiveFunction = Math.min(minObjectiveFunction, (Double) element.getSecond()); 104 return "Ok! Min OF: " + minObjectiveFunction; 105 106 } 107 108 @Override 109 public String getDescription() 110 { 111 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 local-search heuristic approach."; 112 } 113 114 @Override 115 public List<Triple<String, String, String>> getParameters() 116 { 117 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 118 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 119 } 120}