Examples involving 'MILP formulation'

Find (modular) link capacities and traffic routing which minimizes the total link cost

Keywords: Capacity assignment (CA), Flow assignment (FA), JOM, MILP formulation

Given a network topology, and the offered traffic, this algorithm obtains the traffic routing and the (modular) capacities in the links that minimizes the link costs. The capacity of a link is constrained to be the aggregation of integer multiples of modules of capacities {0.15, 0.6, 2.4, 9.6} Gbps, and prices {1, 2, 4, 8} monetary units. Link utilization is limited by the user-defined parameter rhoMax

Solve the routing and wavelength assignment problem assuming no wavelength conversion capabilities

Keywords: Capacity assignment (CA), Flow assignment (FA), JOM, MILP formulation, WDM

Given a network topology of OADM optical nodes connected by WDM fiber links, and a traffic demand of lightpath requests, this algorithm optimally computes the RWA (Routing and Wavelength Assignment) that carries all the lightpaths minimizing the average propagation delay, solving an Integer Linear Program (ILP). Wavelength conversion is not allowed. Only those routes with a length below a user-defined threshold maxLightpathLengthInKm are accepted. All the channels are of the same binaryRatePerChannel_Gbps capacity. The offered traffic demand is supposed to be measured in Gbps, and is rounded up to a multiple of binaryRatePerChannel_Gbps.

Maximum idle bottleneck capacity routing, flow-link formulation, and link-disjoint backup path protection

Keywords: Flow assignment (FA), JOM, MILP formulation, Protection algorithm

Given a network topology, the capacities in the links and the offered traffic, this algorithm obtains a link-disjoint or a SRG-disjoint (depending on user's choice) primary and backup path for the traffic of each demand, that minimizes the network congestion, with the constraint of non-bifurcated routing. For that it solves an ILP flow-link formulation (more complex in the SRG-disjoint case). In this algorithm, congestion is minimized by maximizing the idle link capacity in the bottleneck (the link with less idle capacity).

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).

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

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).

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.

Minimum bottleneck utilization routing with maximum bifurcation constraints, path formulation

Keywords: Flow assignment (FA), JOM, 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 number of hops, between the demand end nodes. k is a user-defined parameter. The fraction of the demand volume that is carried by a path that carries traffic, is constrained to be higher or equal than a user-defined parameter tMin. That is, a path ( p \) can carry no traffic, or an amount of traffic equal or greater than \( tMin \cdot h_{d(p)}\), where \( d(p) \) is the demand associated to path \( p \). Finally, the user-defined parameter BIFMAX sets the maximum number of paths of a demand that can carry traffic.

Computes the optimal bidirectional ring for the network

Keywords: Capacity assignment (CA), JOM, MILP formulation, Topology assignment (TA)

Given a set of nodes \( N \), this algorithm computes the bidirectional ring with the minimum length (in km) in all its nodes, solving with an ILP (Integer Linear Program) the associated Traveling Salesman Problem (TSP) instance. All the links are set to have the capacity passed as input parameter.

Computes the optimal minimum cost access-to-core network

Keywords: Capacity assignment (CA), JOM, MILP formulation, Topology assignment (TA)

Given a set of access nodes, this algorithm computes the subset of access nodes which have a core node located next to it (in the same place), and the links access-to-core nodes, so that the network cost is minimized. This cost is given by a cost per core node (always 1) plus a cost per link, given by the product of link distance and the user-defined parameter linkCostPerKm. Access-core link capacities are fixed to the user-defined parameter linkCapacities. A core node cannot be connected to more than K_max access nodes, a user-defined parameter. This problem is modeled as a ILP and optimally solved using a solver.

Computes a minimum cost network with optimized capacities and traffic routing, path-link formulation

Keywords: Capacity assignment (CA), Flow assignment (FA), JOM, MILP formulation, Topology assignment (TA)

Given a set of nodes \( N \), and a traffic demand, this algorithm computes the set of links, their capacities and the routing of traffic that optimally minimizes the network cost given by a fixed cost per link, plus a variable cost with link capacities. Between two nodes, at most one link can exist. The maximum link capacity is U_max, a user-defined parameter. Link fixed cost is given by link distance by fixedCostFactorPerKm, a user-defined parameter. Link variable cost is given by link distance, by link capacity, by variableCostFactorPerKmAndTrafficUnit, a user-defined parameter. The problem is modeled with JOM as a MILP, and optimally solved by a external solver.