com.net2plan.examples.ocnbook.offline

Class Offline_fa_ospfWeightOptimization_GRASP

Object

com.net2plan.examples.ocnbook.offline.Offline_fa_ospfWeightOptimization_GRASP

All Implemented Interfaces:

com.net2plan.interfaces.networkDesign.IAlgorithm, com.net2plan.internal.IExternal

public class Offline_fa_ospfWeightOptimization_GRASP
extends Object
implements com.net2plan.interfaces.networkDesign.IAlgorithm

Searches for the OSPF link weights that minimize a measure of congestion, using a GRASP heuristic The time evolution of different metrics can be stored in output files, for later processing. As an example, see the fig_sec12_7_ospfWeightGRASP.m MATLAB file used for generating the graph/s of the case study in the book using this algorithm.

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 GRASP heuristic approach (Greedy Randomzied Adaptive Search Procedure).

Keywords:

• IP/OSPF, Flow assignment (FA), GRASP

Input parameters:

grasp_initializationType: Value to select within {random} The type of initialization of the OSPF link weights ospf_maxLinkWeight: Default: 16 OSPF link weights are constrained to be integers between 1 and this parameter grasp_differenceInWeightToBeNeighbors: Default: 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 algorithm_randomSeed: Default: 1 Seed of the random number generator algorithm_outputFileNameRoot: Default: ospfWeghtOptimization_grasp Root of the file name to be used in the output files. If blank, no output ospf_weightOfMaxUtilizationInObjectiveFunction: Default: 0.9 Objective function is this factor multiplied by maximum link utilization, plus 1 minus this factor by average link utilization grasp_rclRandomnessFactor: Default: 0.5 Factor to compute the Restricted Candidate List in the (RCL) in the greedy randomized part algorithm_maxExecutionTimeInSeconds: Default: 60.0 Algorithm maximum running time in seconds grasp_maxNumIterations: Default: 50000 Maximum number of iterations

For more information see:

• Section 12.7, of the book: P. Pavon-Marino, Optimization of computer networks. Modeling and algorithms. A hands-on approach, Wiley 2016.

Constructor Summary

Constructors

Constructor and Description
Offline_fa_ospfWeightOptimization_GRASP()

Method Summary

Modifier and Type	Method and Description
String	executeAlgorithm(com.net2plan.interfaces.networkDesign.NetPlan netPlan, Map<String,String> algorithmParameters, Map<String,String> net2planParameters)
String	getDescription()
List<com.net2plan.utils.Triple<String,String,String>>	getParameters()

Methods inherited from class Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Offline_fa_ospfWeightOptimization_GRASP

public Offline_fa_ospfWeightOptimization_GRASP()

Method Detail

executeAlgorithm

public String executeAlgorithm(com.net2plan.interfaces.networkDesign.NetPlan netPlan,
                               Map<String,String> algorithmParameters,
                               Map<String,String> net2planParameters)

Specified by:

executeAlgorithm in interface com.net2plan.interfaces.networkDesign.IAlgorithm

getDescription

public String getDescription()

Specified by:

getDescription in interface com.net2plan.interfaces.networkDesign.IAlgorithm

Specified by:

getDescription in interface com.net2plan.internal.IExternal

getParameters

public List<com.net2plan.utils.Triple<String,String,String>> getParameters()

Specified by:

getParameters in interface com.net2plan.interfaces.networkDesign.IAlgorithm

Specified by:

getParameters in interface com.net2plan.internal.IExternal