com.net2plan.examples.ocnbook.offline

Class Offline_fa_ospfWeightOptimization_localSearch

Object

com.net2plan.examples.ocnbook.offline.Offline_fa_ospfWeightOptimization_localSearch

All Implemented Interfaces:

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

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

Searches for the OSPF link weights that minimize a measure of congestion, using a local-search heuristic The time evolution of different metrics can be stored in output files, for later processing. As an example, see the fig_sec12_3_ospfWeightLocalSearch.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 local-search heuristic approach.

Keywords:

• IP/OSPF, Flow assignment (FA), Local search (LS) heuristic

Input parameters:

algorithm_randomSeed: Default: 1 Seed of the random number generator algorithm_numSamples: Default: 100 Number of repetitions, returns the last, but saves in file all of them algorithm_outputFileNameRoot: Default: ospfWeghtOptimization_ls Root of the file name to be used in the output files. If blank, no output localSearch_initializationType: Value to select within {random} The type of initialization of the OSPF link weights localSearch_type: Value to select within {first-fit, best-fit} The tpe of local search algorithm. First-fit, jumps to the first improving neighbor solution found, best-fit to the best improving neighbor localSearch_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 ospf_maxLinkWeight: Default: 16 OSPF link weights are constrained to be integers between 1 and this parameter ospf_weightOfMaxUtilizationInObjectiveFunction: Default: 0.9 Objective function is this factor multiplied by maximum link utilization, plus 1 minus this factor by average link utilization

For more information see:

• Section 12.3, 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_localSearch()

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_localSearch

public Offline_fa_ospfWeightOptimization_localSearch()

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