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}