Full example set

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

CAC algorithm based on shortest path routing

Keywords: None

Basic CAC algorithm which tries to route each connection request in the shortest path. Since it is an uncapacitated algorithm, links may become over-subscribed

CAC algorithm based on capacitated shortest path routing

Keywords: None

CAC algorithm which tries to route each connection request in the shortest path for which there is enough bandwidth. If no route satisfies this, the connection is blocked

RWA-CAC algorithm based on k-shortest path routing

Keywords: WDM

This algorithm receives lightpath connection requests and releases. For each lightpath release, wavelength resources are liberated. For each lightpath request, it determines how many lightpaths are actually required. Then, it tries to allocate them over a set of precomputed k-shortest paths (maximum path length in km equal to maxLightpathLengthInKm) using first-fit wavelength assignment (wavelength continuity is enforced).

Connection generator based on exponential interarrival and holding times

Keywords: None

Connection generator in which connection requests from traffic demands arrive according to a Poisson process and are independent of each other

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

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

Do not react to failures

Keywords: None

Algorithm which implements a 'do nothing' resilience mechanism. Under failure, takes no action; while for reparations tries to restore to the primary path, provided that resources are available

Generic provisioning algorithm using protection segments

Keywords: Protection algorithm

Algorithm which implements a generic protection mechanism using pre-defined protection segments in the network design.

Generic provisioning algorithm based on restoration

Keywords: MPLS, Restoration algorithm

Algorithm which implements several restoration mechanisms: path/subpath/link restoration, and fast restoration.

Reroute all traffic according to the ECMP rule

Keywords: OSPF, Restoration algorithm

This algorithm reacts to any resilience event (failure/restoration) trying to routing all the traffic according to the ECMP rule, using link IGP weights. These weights are not modified by the algorithm.

WDM Fast Reroute

Keywords: Regenerator placement, Restoration algorithm, WDM

This algorithm implements a local lightpath restoration mechanism. Since it assumes that the WDM network requires regenerators/wavelength converters, if the input design does not contain them, the algorithm computes the requirements of regeneration/conversion for each lightpath.

Failure/reparation event generator based on shared-risk groups (SRGs) and mean time to fail/repair (MTTF/MTTR) figures

Keywords: None

Generates random failures in SRGs according to a random process with an exponential distribution with MTTF and MTTR mean values

Availability report

Keywords: None

This report analyzes a network design in terms of average availability under a set of failures

Blocking report

Keywords: None

This report analyzes a network design in terms of blocking probability

Disaster-vulnerability report

Keywords: None

This report analyzes a network design in terms of average traffic survivability under a set of disaster failures

Network design report

Keywords: None

This report shows basic information about the network plan

Robustness report

Keywords: None

This report analyses a network design in terms of robustness under different multiple-failures scenarios

Point-to-point WDM line engineering report

Keywords: WDM

This report checks the correctness of the line engineering design of the point-to-point WDM links in an optical network, following the guidelines described in ITU-T Manual 2009 "Optical fibres, cables and systems" (chapter 7, section 2 Worst case design for system with optical line amplifiers).

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.

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.

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.

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

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.

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.

Waxman generator

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

Generates a topology using the Waxman random model

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.

Allocate demands over existing routes

Keywords: None

This algorithm allocates the traffic over the existing routes. Link over-subscription may happen.

Adjust dynamically the number of lightpaths of end-to-end lightpath demands

Keywords: WDM

At each time interval, this algorithm adjusts dynamically the number of lightpaths for each demand with respect to the ones in the previous period.

In case that new lightpaths are required, it performs an RWA using first-fit (wavelength continuity is enforced) over a set of precomputed k-shortest paths (maximum path length in km equal to maxLightpathLengthInKm). These paths are evaluated in order. Once a feasible RWA is found, then the lightpath is allocated, and no other candidate solution is checked.

Vary a peak demand set according to an activity function depending on the time and timezone

Keywords: None

This generator modifies the peak offered-traffic volume per demand according to an activity function, according to the current time and the node timezone

Vary an average demand set according to a Gaussian distribution

Keywords: None

This generator modifies the average offered-traffic volume per demand according to a Gaussian distribution, with mean the initial value of the offered traffic, and standard deviation obtained from the coefficient of variation (input parameter)