Example: 'OSPF routing that minimizes the average congestion between (i) the congestion when no failure occurs in the network, (ii) the worse congestion ranging the cases when one single SRG is failed. '

Brief description

This algorithm computes the OSPF routing that minimizes the average congestion between (i) the congestion when no failure occurs in the network, (ii) the worse congestion ranging the cases when one single SRG is failed. If no SRGs are defined, congestion in (i) is returned. An evolutionary algorithm is implemented. Each solution is coded as an array of as many elements as links, storing the OSPF weight in each link. Details on the particular form in which the evolutionary operators are implemented can be seen in the source code. The returning design includes the routes defined by the OSPF weights, and an attribute per link with its OSPF weight

Algorithm description table

Algorithm inputs

Requires a topology (nodes and links) and a demand set within the netPlan object.

Algorithm parameters:

  • ea_fractionParentsChosenRandomly: Fraction of the parents that are selected randomly for creating the offspring. Default: 0.5
  • ea_offSpringSize: Number of childs in the offspring every generation. Default: 500
  • ea_populationSize: Number of elements in the population. Default: 1000
  • maxExecTimeSecs: Execution time of the algorithm. The algorithm will stop after this time, returning the best solution found. Default: 10
  • maxLinkWeight: OSPF links weights are integers between one and maxLinkWeight. Default: 10
Algorithm outputsThe OSPF link weights are returned as attributes to the links, and the routes (considering Equal-Cost Multipath (ECMP)) are added to netPlan object. Any previous routes are removed.
Required librariesNone
KeywordsDestination-based routing, Evolutionary algorithm (EA), Flow assignment (FA), OSPF, Restoration algorithm
AuthorsPablo Pavón Mariño, José Luis Izquierdo Zaragoza
DateApril 2014
CodeFA_EA_minCongestionSingleFailureOSPF.java