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.Net2PlanException; 017import com.net2plan.interfaces.networkDesign.NetPlan; 018import com.net2plan.utils.Constants.RoutingType; 019import com.net2plan.utils.InputParameter; 020import com.net2plan.utils.Pair; 021import com.net2plan.utils.TimeTrace; 022import com.net2plan.utils.Triple; 023 024import java.io.File; 025import java.util.List; 026import java.util.Map; 027import java.util.Random; 028 029/** 030 * Searches for the OSPF link weights that minimize a measure of congestion, using a local-search 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_3_ospfWeightLocalSearch.m">{@code fig_sec12_3_ospfWeightLocalSearch.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), Local search (LS) heuristic 037 * @net2plan.ocnbooksections Section 12.3 038 * @net2plan.inputParameters 039 * @author Pablo Pavon-Marino 040 */ 041public class Offline_fa_ospfWeightOptimization_localSearch implements IAlgorithm 042{ 043 private OSPFHeuristicUtils ospfEngine; 044 private TimeTrace stat_objFunction; 045 private TimeTrace stat_computationTime; 046 private TimeTrace stat_numObjFuncEvaluations; 047 048 private InputParameter algorithm_randomSeed = new InputParameter ("algorithm_randomSeed", (long) 1 , "Seed of the random number generator"); 049 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); 050 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"); 051 private InputParameter localSearch_initializationType = new InputParameter ("localSearch_initializationType", "#select# random" , "The type of initialization of the OSPF link weights"); 052 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"); 053 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"); 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 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); 056 057 @Override 058 public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters) 059 { 060 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 061 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 062 063 /* Basic checks */ 064 final int N = netPlan.getNumberOfNodes(); 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 070 /* Initialize some variables */ 071 final boolean isFirstFit = localSearch_type.getString ().equals ("first-fit"); 072 073 Random rng = new Random (algorithm_randomSeed.getLong ()); 074 this.ospfEngine = new OSPFHeuristicUtils(netPlan, ospf_maxLinkWeight.getInt (), ospf_weightOfMaxUtilizationInObjectiveFunction.getDouble(), rng); 075 this.stat_objFunction = new TimeTrace (); 076 this.stat_computationTime = new TimeTrace (); 077 this.stat_numObjFuncEvaluations = new TimeTrace (); 078 079 System.out.println("isFirstFit: " + isFirstFit); 080 081 for (int it = 0 ; it < algorithm_numSamples.getInt () ; it ++) 082 { 083 final long initTime = System.nanoTime(); 084 Pair<DoubleMatrix1D,Double> p1 = ospfEngine.getInitialSolution (localSearch_initializationType.getString()); 085 DoubleMatrix1D currentSol = p1.getFirst(); 086 double currentObjFunction = p1.getSecond(); 087 088 final Pair<Double,Integer> p2 = ospfEngine.localSearch (currentSol , currentObjFunction , localSearch_differenceInWeightToBeNeighbors.getInt () , isFirstFit); 089 final double bestObjFunc = p2.getFirst(); 090 final int numObjFunctionEvaluations = p2.getSecond(); 091 final double computationTimeIbnSeconds = (System.nanoTime() - initTime)*1e-9; 092 stat_computationTime.add(it, computationTimeIbnSeconds); 093 stat_objFunction.add(it, bestObjFunc); 094 stat_numObjFuncEvaluations.add(it, numObjFunctionEvaluations); 095 } 096 097 stat_objFunction.printToFile(new File (algorithm_outputFileNameRoot.getString () + "_D" + localSearch_differenceInWeightToBeNeighbors.getInt () + ((isFirstFit)? "_FF_" : "_BF_") + "objFunc.txt")); 098 stat_computationTime.printToFile(new File (algorithm_outputFileNameRoot.getString () + "_D" + localSearch_differenceInWeightToBeNeighbors.getInt () + ((isFirstFit)? "_FF_" : "_BF_") + "time.txt")); 099 stat_numObjFuncEvaluations.printToFile(new File (algorithm_outputFileNameRoot.getString () + "_D" + localSearch_differenceInWeightToBeNeighbors.getInt () + ((isFirstFit)? "_FF_" : "_BF_") + "numEvalObjFunc.txt")); 100 101 102 double minObjectiveFunction = Double.MAX_VALUE; 103 for (Pair<Double,Object> element : stat_objFunction.getList()) 104 minObjectiveFunction = Math.min(minObjectiveFunction, (Double) element.getSecond()); 105 return "Ok! Min OF: " + minObjectiveFunction; 106 107 } 108 109 @Override 110 public String getDescription() 111 { 112 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."; 113 } 114 115 @Override 116 public List<Triple<String, String, String>> getParameters() 117 { 118 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 119 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 120 } 121}