Examples from category 'Network design - Algorithms'

Algorithms which receive some of information as input parameters (e.g. traffic demand, and network topology) and try optimize the rest (e.g. capacities in the links and traffic routing) according to a performance merit of interest

Example nameDescription
CA_minDelayConcaveCost.java

Find link capacities which minimizes the average network delay under a given budget

Keywords: Capacity assignment (CA), Convex formulation, JOM

Given a network topology, a known amount of traffic carried in each link, and an available budget, this algorithm computes the capacities in the links that minimize the average network delay (considering only queuing and transmission delays in the links, using the M/M/1 model), with the constraint that the cost does not exceeds the available budget. The total network cost is given by the sum of the costs of the links, where the cost in each link is given by \( u_e ^ \alpha \), being \( \alpha \) a positive parameter. If \( \alpha \) is between 0 and 1, the link cost function is concave respect to the capacities.

We solve the problem using a convex formulation, where the decision variables are the utilizations \( \rho_e \) in the links. Note that thanks to this change of variable, the problem is convex (in the variables \( \rho_e \) ) even if it was not originally convex (in the variables \( u_e \) ).

CFA_minCostModularCapacities_xde.java

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

CFA_OSPF_fixedWeight.java

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.

CFA_shortestPathFixedUtilization.java

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

CFA_WDM_basicRWA.java

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.

FA_EA_minCongestionPrecomputedRestoration.java

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.

FA_EA_minCongestionSingleFailureOSPF.java

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

FA_maxBottleneckIdleCapacity_xde_11pathProtection.java

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

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

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)

FA_minAvNetDelay_xde.java

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.

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

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.

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.

FA_SAN_minCongestion.java

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

FA_shortestPath_11pathProtection.java

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

FA_shortestPath.java

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

FA_TS_minCongestion11.java

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.

FBA_maxAlphaFairness.java

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

FBA_projectedGradient.java

Assign routes and a proportionally fair bandwidth to each demand, using a distributed algorithm based on projected gradient

Keywords: Bandwidth assignment (BA), Projected gradient/subgradient algorithm

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 km or in number of hops, and obtains the offered traffic for each demand (that is, assigns bandwidth to each demand), using a projected gradient algorithm, that permits a distributed implementation (per demand). The optimization problem to solve is: min sum_e F_e - sum_d log h_d, subject to h_d >= h^{min} e is the index for the links, d the index for the demands. The h^{min} value is set to the minimum link capacity divided by the number of demands. Then, it is guaranteed that if all the demands are set to this value, the resulting traffic does not oversubscribe any link. This means: h^{min} = min_e u_e / |D|, where u_e are the link capacities. The F_e functions are F_e = M_e / (u_e-y_e), if link utilization is below 99% and its linear projection if not. M_e is set so that if the link utilization is 99%, any demand traversing the link will have a gradient coordinate which makes it reduce its rate h_d. We use M_e = u_e^2 / (h^{min} 1E4) According to [1], the logarithmic functions tend to enforce a bandwidth distribution that approximates (not exactly, given the noise added by F_e penalizations) the proportionally-fair bandwidth sharing. The algorithm permits testing several projected gradient flavors: constant step, 1/k diminishing rule, w/o diagonal scaling. In this latter case, each demand multiplies its movement by the inverse of the associated diagonal value in the hessian matrix. [1] 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

TCA_ACO_TSP.java

This algorithm computes the bidirectional ring which minimizes the total ring length, using an ACO (Ant Colony Optimization) heuristic, described as Ant System in the literature

Keywords: Ant Colony Optimization (ACO), Capacity assignment (CA), Topology assignment (TA)

This algorithm computes the bidirectional ring which minimizes the total ring length, using an ACO (Ant Colony Optimization) heuristic, described as Ant System in the literature: M. Dorigo, V. Maniezzo, A. Colorni, "Ant system: optimization by a colony of cooperating agents", IEEE T on Cybernetics, 1996. The cost of a link equals the euclidean distance between link end nodes. The algorithm executes ACO iterations until the maxExecTime is reached. In each ACO iteration, a loop for each ant is executed. Each ant, creates a greedy-randomized solution using the pheromones information of each potential link, and each link length, as follows. Each ant starts in a node chosen randomly. At each iteration, an ant in node n decides the next node to visit randomly among the non-visited nodes, being the probability of choosing node n' proportional to ph_nn'^alpha b_nn'^beta. ph_nn' is the amount of pheromones associated to link nn', b_nn' is the inverse of the distance between both nodes. alpha and beta are parameters tuning the importance of pheromones and link distances respectively. After all ants have finished, an evaporation strategy is executed, where each link nn' looses pheromones multiplicatively (pheromones are multiplied by 1-r, where r is a 0...1 evaporation factor). After evaporation phase, a reinforcement step is completed, where each ant a adds a quantity 1/La to the pheromones of all links traversed, being La the total distance of its ring.

TCA_GRASP_TSP.java

This algorithm computes the bidirectional ring which minimizes the total ring length, using a GRASP heuristic.

Keywords: Capacity assignment (CA), Greedy-Randomized Adaptive Search Procedure (GRASP), Topology assignment (TA)

This algorithm computes the bidirectional ring which minimizes the total ring length, using a GRASP heuristic. The cost of a link equals the euclidean distance between link end nodes. The algorithm executes GRASP iterations until the maxExecTime is reached. In each GRASP iteration, a solution is first created using a greedy-randomized approach. Then, this solution is the starting point of a local search (first-fit) heuristic, where two rings are considered neighbors when they have all but 2 bidirectional links in common. The greedy randomized approach is based on the concept of restricted candidate list (RCL). The ring starts with one single node chosen randomly. In each greedy iteration one node is added to the ring, randomly chosen from a RCL created in this iteration. The RCL contains the non-visited nodes which are closer to current node. In particular, the nodes in the RCL are those which are at a distance from c_min to c_min + alpha * (c_max - c_min). c_min and c_max are the distances from last added node, to closest and furthest non-visited nodes. alpha is an algroithm parameter between 0 and 1, tuning the size of the RCL. When alpha=0, the algorithm is equal to pure greedy nearest neighbor heuristic. If alpha = 1, randomness is maximum: a non-visited node is chosen randomly.

TCA_LS_nodeLocation.java

Compute a minimum cost access-to-core network

Keywords: Capacity assignment (CA), Local search (LS) heuristic, 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. This problem is solved using a local-search heuristic.

TCA_minLengthBidirectionalRingILP.java

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.

TCA_nearestNeighborTSP.java

Computes a bidirectional ring for the network using a nearest-neighbor heuristic

Keywords: Capacity assignment (CA), Greedy heuristic, Topology assignment (TA)

Given a set of nodes, this heuristic tries to find a (possibly sub-optimal) minimum cost bidirectional ring (where the cost of a link is given by its length in km) using the nearest-neighbor greedy heuristic.

TCA_nodeLocationILP.java

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.

TCA_PrimMST.java

Compute the bidirectional minimum spanning tree for the network

Keywords: Capacity assignment (CA), Topology assignment (TA)

This algorithm computes the bidirectional minimum spanning tree (MST) for the given set of nodes, using the node distance as the cost measure for each link.

For a network of \(N\) nodes, the returned topology is a tree of \(N-1\) bidirectional links, so that no other topology is able to connect the \(N\) nodes with bidirectional links, at a lower cost (being the cost the sum of the lengths of the links). To compute the MST, the Prim algorithm is implemented.

TCA_WaxmanGenerator.java

Waxman generator

Keywords: Capacity assignment (CA), Topology assignment (TA)

Generates a topology using the Waxman random model

TCFA_minLinkCost.java

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.