An example where a Linear Programming (LP) formulation is solved using a solver.
Network design - Algorithms
| Example name | Description |
|---|---|
| FA_maxBottleneckIdleCapacity_xde.java | Maximum idle bottleneck capacity routing, flow-link formulation Keywords: Flow assignment (FA), JOM, LP formulation, MILP formulation Given a network topology, the capacities in the links and the offered traffic, this algorithm obtains the traffic routing that minimizes the network congestion, with or without the constraint of non-bifurcated routing. In this algorithm, congestion is minimized by maximizing the idle link capacity in the bottleneck (the link with less idle capacity). |
| FA_minAvNumHops_xp.java | Minimum average hop count routing, path formulation Keywords: Flow assignment (FA), JOM, LP formulation, MILP formulation Given a network topology, the capacities in the links and the offered traffic, this algorithm obtains the traffic routing that minimizes the average number of hops using a flow-path formulation. For each demand, the set of admissible paths is composed of the ranking of (at most) k-shortest paths in km, between the demand end nodes. k is a user-defined parameter. Paths for which its propagation time sums more than maxPropDelayMs, a user-defined parameter, are considered not admissible. The routing may be constrained to be non-bifurcated setting the user-defined parameter nonBifurcated to true |
| FA_minAvNumHops_xte.java | Minimum average hop count routing, destination-based routing Keywords: Destination-based routing, Flow assignment (FA), JOM, LP formulation Given a network topology, the capacities in the links and the offered traffic, this algorithm obtains the destination-based traffic routing that minimizes the average number of hops. Destination-based routing means that the routing could be implemented i.e. in an IP network. |
| FA_minBottleneckUtilization_xde.java | Minimum bottleneck utilization routing, flow-link formulation Keywords: Flow assignment (FA), JOM, LP formulation, MILP formulation Given a network topology, the capacities in the links and the offered traffic, this algorithm obtains the traffic routing that minimizes the network congestion, with or without the constraint of non-bifurcated routing. In this algorithm, congestion is minimized by minimizing the utilization in the bottleneck (the link with highest utilization). |
| FA_minBottleneckUtilization_xp.java | Minimum bottleneck utilization routing, path formulation Keywords: Flow assignment (FA), JOM, LP formulation, MILP formulation Given a network topology, the capacities in the links and the offered traffic, this algorithm obtains the traffic routing that minimizes the worst link utilization using a flow-path formulation. For each demand, the set of admissible paths is composed of the ranking of (at most) k-shortest paths in km, between the demand end nodes. k is a user-defined parameter. Paths for which its propagation time sums more than maxPropDelayMs, a user-defined parameter, are considered not admissible. The routing may be constrained to be non-bifurcated setting the user-defined parameter nonBifurcated to true. |
| FA_OSPF_fastIGPMetric.java | Route traffic with ECMP getting link weights obtained from a heuristic Keywords: Flow assignment (FA), JOM, LP formulation, OSPF 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. |
