Examples involving 'Flow assignment (FA)'

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

Minimimize number of IP links so that traffic is carried using OSPF routing

Keywords: Capacity assignment (CA), Destination-based routing, Flow assignment (FA), Greedy heuristic, OSPF

This algorithm computes the number of IP links between two nodes, and the OSPF routing (with ECMP), so that all the traffic is carried, while all the links have an utilization not exceeding a given threshold (maximumUtilization). All IP links have the same given fixedOSPFWeight weight, and the same given fixedIPLinkCapacity capacity.

Find link capacities to allocate shortest path (uncapacitated) routing

Keywords: Capacity assignment (CA), Flow assignment (FA)

Given a network topology, and the offered traffic, this algorithm first routes the traffic according to the shortest path (in number of traversed links or in number of traversed km), and then fixes the capacities so that the utilization in all the links is equal to a user-defined given value

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.

Find traffic routing which minimizes the average between the network congestion in the non-failure state, and the worst network congestion among any single link failure

Keywords: Evolutionary algorithm (EA), Flow assignment (FA), Restoration algorithm

Given a set of nodes and links, with their capacities, an offered traffic, and a set of admissible paths for each demand (given by the k-shortest paths in km for each demand, being k an user-defined parameter), this algorithm uses an evolutionary algorithm metaheuristic to find for each demand two link-disjoint routes: a primary route, and a backup route used for restoration. That is, the backup route is pre-computed, but it carries not traffic unless the primary route fails. The optimization target is minimizing the average between the network congestion in the non-failure state, and the worst network congestion among the single link failures.

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.

Keywords: Destination-based routing, Evolutionary algorithm (EA), Flow assignment (FA), OSPF, Restoration algorithm

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

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 network blocking probability routing, flow-link formulation

Keywords: Convex formulation, Flow assignment (FA), JOM

Given a network topology, the capacities in the links and the offered traffic, this algorithm obtains the traffic routing that minimizes the average network blocking \(B\), estimated according to the formula: \(B = \frac{1}{\sum_d h_d} \sum_e y_e B_e\), where \( h_d \) is the traffic offered by demand \( d \) (in Erlangs), and \(B_e\) is the Erlang-B blocking for link \(e\), assuming that the offered traffic in the link \( y_e \) is all the traffic routed to \( e \) (traffic does not shrink because of the blockings in the rest of the links)

Minimum average network delay routing, flow-link formulation

Keywords: Convex formulation, Flow assignment (FA), JOM

Given a network topology, the capacities in the links and the offered traffic, this algorithm obtains the traffic routing that minimizes the average network delay T, estimated according to the formula: \( T = \frac{1}{\sum_d h_d} \sum_e y_e T_e \), where \( h_d \) is the offered traffic by demand \( d \) (in bps), and \( T_e \) is the average link delay estimated for link \( e \), given by \( d_e + \frac{L}{u_e - y_e} \). For each link \( e \), \( d_e \) is the propagation delay, \( y_e \) is the average traffic in the link and \( u_e \) is the link capacity (both in bps). \(L\) is the average packet length in bits.

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

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.

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.

Minimum bottleneck utilization routing using a simulated annealing heuristic

Keywords: Flow assignment (FA), Simulated annealing (SAN)

Given a set of nodes and links, gith their capacities, an offered traffic, and a set of admissible paths for each demand (given by the k-shortest paths in km for each demand, being k a user-defined parameter), this algorithm uses a simulated annealing metaheuristic to find the non-bifurcated routing solution that minimizes the network congestion. Two solutions are considered neighbors if they differ the routing of one demand. The number of iterations in the inner (all with the same temperature) and outer loop (decreasing the temperature) are user-defined parameters

Shortest path (uncapacitated) routing, and link-disjoint backup path protection

Keywords: Flow assignment (FA), Protection algorithm

Algorithm for flow assignment problems which routes all traffic of each demand, through the shortest path, and then creates a backup path, measured in number of hops or in km, being this an user-defined parameter

Shortest path (uncapacitated) routing

Keywords: Flow assignment (FA)

Algorithm for flow assignment problems which routes all traffic of each demand, through the shortest path, measured in number of hops or in km, being this an user-defined parameter

Minimum bottleneck utilization routing using a tabu search heuristic

Keywords: Flow assignment (FA), Protection algorithm, Tabu search (TS)

Given a set of nodes and links, gith their capacities, an offered traffic, and a set of admissible paths for each demand (given by the k-shortest paths in km for each demand, being k a user-defined parameter), this algorithm uses a tabu search metaheuristic to find for each demand a link-disjoint 1+1 routes, so that the network congestion is minimized. For each demand, the candidate 1+1 pairs are computed as all the link disjoint pairs p1,p2, such that p1 and p2 are admissible paths.

Solve the Network Utility Maximization (NUM) problem

Keywords: Bandwidth assignment (BA), Convex formulation, Flow assignment (FA), JOM

Given a network topology and the capacities in the links, this algorithm creates one demand of traffic for each input-output node pair, routes the traffic of each demand through the shortest path in number of hops, and obtains the offered traffic for each demand (that is, assigns bandwidth) to each demand, so that global assignment is \(\alpha\)-fair, with the constraint that no network link is over-congested.

According to the Mo & Walrand paper (see reference below), the \(\alpha\)-fairness assignment is obtained by solving the NUM model (Network Utility Maximization) where the utility of a demand \(d\) which is assigned a bandwidth \(h_d\) is given by: \((r^{(1-\alpha)} / (1-\alpha))\), and the target is to maximize the sum of the utilities in all the demands in the network.

Reference: J. Mo, J. Walrand, "Fair end-to-end window-based congestion control," IEEE/ACM Transactions on Networking, vol. 8, no. 5, pp. 556–567, October 2000

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.