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}