Examples involving 'Capacity assignment (CA)'

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

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.

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.