Example: 'Route traffic with ECMP getting link weights obtained from a heuristic'

Brief description

This algorithm provides two heuristic methods, presented in [Umit2009], to deal with the IGP weight setting problem with the ECMP rule (NP-hard). These heuristics are based on dual properties of multi-commodity flow (MCF) problems to obtain link metrics in a fast and efficient manner.

Algorithm description table

Algorithm inputs

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

Algorithm parameters:

  • method: Heuristic method to obtain IGP weights. Valid values are 'colGen' (column generation) and 'dv' (dual variables). Default: "colGen"
  • solverName: The solver name to be used by JOM. Default: "glpk"
  • solverLibraryName: The solver library full or relative path, to be used by JOM. Leave blank to use JOM default. Default: blank
Algorithm outputsThe routes are added to netPlan object. No protection segments/routes are defined. Any previous routes are removed.
Required librariesJOM library for solving the optimization problem
KeywordsFlow assignment (FA), JOM, LP formulation, OSPF
AuthorsPablo Pavón Mariño, José Luis Izquierdo Zaragoza
DateFebruary 2014
CodeFA_OSPF_fastIGPMetric.java

Detailed description

The first method (colGen) is a column generation heuristic, initialized with non-bifurcated min-hop routing, which adds new paths until no more profitable path can be added. A path-based form of the MCF problem is used into the Restricted Master Problem.

The second method (dv) gets link metrics as the dual variables of the link constraints of a link-based MCF problem.

See [Umit2009] for more information.

Important: Integrality of link metrics (required by real-world IGP protocols) cannot be ensured by using these methods.

[Umit2009] H. Ümit, "Techniques and Tools for Intra-domain Traffic Engineering," Ph.D. Thesis, Université catholique de Louvain (Belgium), December 2009