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}