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.Collections;
015import java.util.List;
016import java.util.Map;
017import java.util.Random;
018
019import cern.colt.matrix.tdouble.DoubleMatrix1D;
020
021import com.net2plan.interfaces.networkDesign.IAlgorithm;
022import com.net2plan.interfaces.networkDesign.Link;
023import com.net2plan.interfaces.networkDesign.Net2PlanException;
024import com.net2plan.interfaces.networkDesign.NetPlan;
025import com.net2plan.utils.Constants;
026import com.net2plan.utils.Constants.RoutingType;
027import com.net2plan.utils.DoubleUtils;
028import com.net2plan.utils.InputParameter;
029import com.net2plan.utils.Pair;
030import com.net2plan.utils.TimeTrace;
031import com.net2plan.utils.Triple;
032
033/**
034 * Searches for the OSPF link weights that minimize a measure of congestion, using a greedy heuristic
035 * @net2plan.description
036 * @net2plan.keywords IP/OSPF, Flow assignment (FA), Greedy heuristic
037 * @net2plan.ocnbooksections Section 12.6
038 * @net2plan.inputParameters 
039 * @author Pablo Pavon-Marino
040 */
041public class Offline_fa_ospfWeightOptimization_greedy implements IAlgorithm
042{
043        private TimeTrace stat_objFunction;
044        private OSPFHeuristicUtils ospfEngine;
045
046        private InputParameter greedy_initializationType = new InputParameter ("greedy_initializationType", "#select# random" , "The type of initialization of the OSPF link weights");
047        private InputParameter greedy_differenceInWeightToBeNeighbors = new InputParameter ("greedy_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");
048        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);
049        private InputParameter algorithm_randomSeed = new InputParameter ("algorithm_randomSeed", (long) 1 , "Seed of the random number generator");
050        private InputParameter algorithm_outputFileNameRoot = new InputParameter ("algorithm_outputFileNameRoot", "ospfWeghtOptimization_greedy" , "Root of the file name to be used in the output files. If blank, no output");
051        private InputParameter algorithm_numSamples = new InputParameter ("algorithm_numSamples", (int) 100 , "Number of repetitions, returns the last, but prints in file all of them" , 1 , Integer.MAX_VALUE);
052        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);
053
054        @Override
055        public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters)
056        {
057                /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */
058                InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters);
059
060                /* Basic checks */
061                final int N = netPlan.getNumberOfNodes();
062                final int E = netPlan.getNumberOfLinks();
063                if (N == 0) throw new Net2PlanException("The input design must have nodes");
064                netPlan.removeAllUnicastRoutingInformation();
065                netPlan.setRoutingType (RoutingType.HOP_BY_HOP_ROUTING);
066
067                
068                Random rng = new Random (algorithm_randomSeed.getLong());
069                this.ospfEngine = new OSPFHeuristicUtils(netPlan, ospf_maxLinkWeight.getInt (), ospf_weightOfMaxUtilizationInObjectiveFunction.getDouble(), rng);
070                
071                this.stat_objFunction = new TimeTrace ();
072
073                for (int it = 0 ; it < algorithm_numSamples.getInt () ; it ++)
074                {
075                        Pair<DoubleMatrix1D,Double> p = ospfEngine.getInitialSolution (greedy_initializationType.getString());
076                        DoubleMatrix1D currentSol = p.getFirst();
077                        double currentObjFunction = p.getSecond();
078
079                        /* Create a randomly shuffled sequence of link ids */
080                        List<Link> shuffledLinks = new ArrayList<Link> (netPlan.getLinks());
081                        Collections.shuffle(shuffledLinks);
082
083                        for (Link e : shuffledLinks)
084                        {
085                                Pair<double [],int []> pair = ospfEngine.computeSolutionsVaryingLinkWeight (e , currentSol , null , greedy_differenceInWeightToBeNeighbors.getInt ());
086                                final int indexOfBestWeight = DoubleUtils.maxIndexes (pair.getFirst() , Constants.SearchType.FIRST) [0];
087                                final int bestWeight = pair.getSecond() [indexOfBestWeight];
088                                currentObjFunction = pair.getFirst() [indexOfBestWeight];
089                                currentSol.set(e.getIndex(), (double) bestWeight);
090                        } 
091                        stat_objFunction.add(it , currentObjFunction);
092                }
093                
094                stat_objFunction.printToFile(new File (algorithm_outputFileNameRoot.getString () + "_D" + greedy_differenceInWeightToBeNeighbors.getInt () + "_cong.txt"));
095
096                double minObjectiveFunction = Double.MAX_VALUE;
097                for (Pair<Double,Object> element : stat_objFunction.getList()) minObjectiveFunction = Math.min(minObjectiveFunction, (Double) element.getSecond());
098                return "Ok! Min congestion factor: " + minObjectiveFunction;
099        }
100
101        @Override
102        public String getDescription()
103        {
104                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 greedy heuristic approach.";      
105        }
106
107        @Override
108        public List<Triple<String, String, String>> getParameters()
109        {
110                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
111                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
112        }
113}