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 ******************************************************************************/
008
009
010
011package com.net2plan.examples.ocnbook.offline;
012
013import java.io.File;
014import java.util.HashMap;
015import java.util.LinkedList;
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 a tabu search 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_5_ospfWeightTabuSearch.m">{@code fig_sec12_5_ospfWeightTabuSearch.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), Tabu search (TS)
043 * @net2plan.ocnbooksections Section 12.5
044 * @net2plan.inputParameters 
045 * @author Pablo Pavon-Marino
046 */
047public class Offline_fa_ospfWeightOptimization_tabuSearch implements IAlgorithm
048{
049        private int numIterations;
050        private int numIterationsNonImprovingBestSolutionSinceLastRandomization;
051        private TimeTrace stat_objFunction;
052        private OSPFHeuristicUtils ospfEngine;
053        private double [][] numberOccurrencies_ew;
054        
055        private InputParameter ts_initializationType = new InputParameter ("ts_initializationType", "#select# random" , "The type of initialization of the OSPF link weights");
056        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);
057        private InputParameter algorithm_randomSeed = new InputParameter ("algorithm_randomSeed", (long) 1 , "Seed of the random number generator");
058        private InputParameter algorithm_outputFileNameRoot = new InputParameter ("algorithm_outputFileNameRoot", "ospfWeghtOptimization_tabu" , "Root of the file name to be used in the output files. If blank, no output");
059        private InputParameter ts_differenceInWeightToBeNeighbors = new InputParameter ("ts_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");
060        private InputParameter ts_tabuListSizeAsFractionOfLinks = new InputParameter ("ts_tabuListSizeAsFractionOfLinks", (double) 0.5 , "Size of the tabe list, given as a fraction of the total number of links" , 0 , true , 1 , true);
061        private InputParameter algorithm_maxExecutionTimeInSeconds = new InputParameter ("algorithm_maxExecutionTimeInSeconds", (double) 60 , "Algorithm maximum running time in seconds" , 0 , false , Double.MAX_VALUE , true);
062        private InputParameter ts_maxNumIterations = new InputParameter ("ts_maxNumIterations", (int) 50000 , "Maximum number of iterations" , 1 , Integer.MAX_VALUE);
063        private InputParameter ts_maxNumIterationsNonImprovingIncumbentSolution = new InputParameter ("ts_maxNumIterationsNonImprovingIncumbentSolution", (int) 15 , "Num iterations non improving the incumbent solution, to restart the search in a randomized solution" , 1 , Integer.MAX_VALUE);
064        private InputParameter ts_aspirationCriterion = new InputParameter ("ts_aspirationCriterion", true , "Apply aspiration criterion in tabu search");
065        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);
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                /* Initialize some variables */
081                final long algorithmInitialtime = System.nanoTime();
082                final long algorithmEndtime = algorithmInitialtime + (long) (algorithm_maxExecutionTimeInSeconds.getDouble() * 1E9);
083                final int tabuListSize = (int) Math.ceil(E * ts_tabuListSizeAsFractionOfLinks.getDouble());
084                if (tabuListSize >= E) throw new Net2PlanException ("The tabu list size is larger or equal than the number of links: all jumps would be tabu");
085
086                Random rng = new Random (algorithm_randomSeed.getLong());
087                this.ospfEngine = new OSPFHeuristicUtils(netPlan, ospf_maxLinkWeight.getInt (), ospf_weightOfMaxUtilizationInObjectiveFunction.getDouble(), rng);
088                this.numberOccurrencies_ew = new double [E][ospf_maxLinkWeight.getInt ()];
089                
090                /* Tabu list info. Because of aspiration criterion, a link can appear more than once in the tabu list */
091                Map<Link,Integer> numEntriesTabuList_e = new HashMap<Link,Integer> (); for (Link e : netPlan.getLinks()) numEntriesTabuList_e.put(e, 0); 
092                LinkedList<Link> tabuList_e = new LinkedList<Link> ();
093                
094                Pair<DoubleMatrix1D,Double> p = ospfEngine.getInitialSolution (ts_initializationType.getString());
095                DoubleMatrix1D currentSol = p.getFirst();
096                double currentObjFunction = p.getSecond();
097
098                DoubleMatrix1D bestSol = currentSol.copy ();
099                double bestObjFunction = currentObjFunction;
100                double bestObjFunctionSinceLastRandomization = currentObjFunction;
101                
102                this.numIterations= 0;
103                this.numIterationsNonImprovingBestSolutionSinceLastRandomization = 0;
104                this.stat_objFunction = new TimeTrace ();
105
106                stat_objFunction.add(0.0, currentObjFunction);
107                
108                /* update the long-term memory*/
109                for (int eIndex = 0 ; eIndex < E ; eIndex ++) this.numberOccurrencies_ew [eIndex][(int) (currentSol.get(eIndex)) - 1] ++;
110                
111                System.out.println("Initial objFunction: " + bestObjFunction + ", tabu list tenure: " + tabuListSize);
112
113                while ((System.nanoTime() < algorithmEndtime) && (numIterations < ts_maxNumIterations.getInt ()))
114                {
115                        this.numIterations ++;
116                        Link bestNeighborLink = null;
117                        int bestNeighborWeight = -1;
118                        double bestNeighborObjFunction = Double.MAX_VALUE;
119                        
120                        /* Neighbors differing in one link */
121                        for (Link e1 : netPlan.getLinks())
122                        {
123                                final boolean isTabu = (numEntriesTabuList_e.get(e1) > 0);
124                                if (!ts_aspirationCriterion.getBoolean() && isTabu) continue;
125                                
126                                final int currentWeight1 = (int) currentSol.get(e1.getIndex ());
127                                for (int w1 = 1 ; w1 <= ospf_maxLinkWeight.getInt () ; w1 ++)
128                                {
129                                        if (w1 == currentWeight1) continue;
130                                        if (Math.abs(w1 - currentWeight1) > ts_differenceInWeightToBeNeighbors.getInt ()) continue;
131                                        currentSol.set(e1.getIndex (), (double) w1);
132                                        final double neighborObjFunction = ospfEngine.computeObjectiveFunction(currentSol).getFirst();
133                                        currentSol.set(e1.getIndex (), (double) currentWeight1);
134                                        
135                                        /* Update best neighbor if (i) not tabu and improves best neighbor, (ii) tabu, but aspiration criterion is active and improves incumbent solution */
136                                        if ( (!isTabu && (neighborObjFunction < bestNeighborObjFunction)) || (isTabu && ts_aspirationCriterion.getBoolean() && (neighborObjFunction < bestObjFunction)) ) 
137                                        {
138                                                if (isTabu) System.out.println ("Aspiration criterion applied");
139                                                bestNeighborLink = e1; bestNeighborWeight = w1; bestNeighborObjFunction = neighborObjFunction;
140                                        }
141                                }
142                        }
143
144                        if (bestNeighborLink == null) { throw new RuntimeException ("This should not happen: it means a too large tabu list");  }
145                        
146                        /* Jump to the neighbor solution */
147                        currentSol.set(bestNeighborLink.getIndex (), (double) bestNeighborWeight); currentObjFunction = bestNeighborObjFunction;
148
149                        /* update tabu list */
150                        if (tabuList_e.size() == tabuListSize) { Link eToRemove = tabuList_e.removeFirst(); numEntriesTabuList_e.put(eToRemove, numEntriesTabuList_e.get(eToRemove) - 1); if (numEntriesTabuList_e.get(eToRemove) < 0) throw new RuntimeException ("Bad"); }
151                        tabuList_e.addLast(bestNeighborLink); numEntriesTabuList_e.put(bestNeighborLink , numEntriesTabuList_e.get(bestNeighborLink) + 1);
152
153                        /* update the incumbent solution */
154                        if (currentObjFunction < bestObjFunctionSinceLastRandomization)
155                        {
156                                this.numIterationsNonImprovingBestSolutionSinceLastRandomization = 0;
157                                bestObjFunctionSinceLastRandomization = currentObjFunction; 
158                                System.out.println("Improving best objFunction since last randomization: " + currentObjFunction);
159                                if (currentObjFunction < bestObjFunction) { bestObjFunction = currentObjFunction; bestSol = currentSol.copy (); System.out.println("Improving best objFunction: " + bestObjFunction); }
160                        }
161                        else
162                                this.numIterationsNonImprovingBestSolutionSinceLastRandomization ++;
163                        
164                        /* update the long-term memory*/
165                        for (int eIndex = 0 ; eIndex < E ; eIndex ++) this.numberOccurrencies_ew [eIndex][(int) (currentSol.get(eIndex)) - 1] ++;
166
167                        /* Check if too many iterations without improving the incumbent solution */
168                        if (numIterationsNonImprovingBestSolutionSinceLastRandomization > ts_maxNumIterationsNonImprovingIncumbentSolution.getInt ())
169                        {
170                                System.out.println("Randomization!!");
171                                
172                                /* Initialize tabu list */
173                                tabuList_e.clear(); for (Link e : netPlan.getLinks()) numEntriesTabuList_e.put(e, 0); 
174
175                                /* Make a diversification jump: incumbent solution, then each link with prob 0.5 randomizes its weight */
176                                currentSol = bestSol.copy();
177                                for (Link e : netPlan.getLinks())
178                                {
179                                        if (rng.nextBoolean()) continue; 
180                                        final int [] leastUtilizedWeightsMinus1 = DoubleUtils.sortIndexes(this.numberOccurrencies_ew [e.getIndex ()], OrderingType.ASCENDING);
181                                        final int randomlyChosenWeight = leastUtilizedWeightsMinus1 [rng.nextInt(ospf_maxLinkWeight.getInt ()/2)] + 1;
182                                        currentSol.set(e.getIndex (), (double) randomlyChosenWeight);
183                                }
184                                currentObjFunction = ospfEngine.computeObjectiveFunction(currentSol).getFirst();
185                                bestObjFunctionSinceLastRandomization = currentObjFunction;
186                                this.numIterationsNonImprovingBestSolutionSinceLastRandomization = 0;
187                        }
188                        
189                        final double currentTimeInSecs = (System.nanoTime() - algorithmInitialtime) * 1e-9;
190                        stat_objFunction.add(currentTimeInSecs , currentObjFunction);
191                } 
192
193                IPUtils.setECMPForwardingRulesFromLinkWeights(netPlan, bestSol);
194
195                final String completeFileName = algorithm_outputFileNameRoot.getString () + "_0" + ((int) (10*ts_tabuListSizeAsFractionOfLinks.getDouble())) + ((ts_aspirationCriterion.getBoolean())? "_asp" : "_noasp"); 
196                stat_objFunction.printToFile(new File (completeFileName + "_cong.txt"));
197
198                System.out.println("Ok! ObjFunction: " + bestObjFunction + ", num it: " + numIterations + ", Best solution: " + bestSol);
199                return "Ok! ObjFunction: " + bestObjFunction + ", num it: " + numIterations;
200        }
201
202        @Override
203        public String getDescription()
204        {
205                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 tabu search heuristic approach.";
206        }
207
208        @Override
209        public List<Triple<String, String, String>> getParameters()
210        {
211                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
212                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
213        }
214
215}