Brief description
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.
Algorithm description table
| Algorithm inputs | Requires a topology (nodes and links) and a demand set within the netPlan object. Algorithm parameters:
|
|---|---|
| Algorithm outputs | The routes and path protection segments are added to netPlan object. Any previous routes are removed |
| Required libraries | None |
| Keywords | Evolutionary algorithm (EA), Flow assignment (FA), Restoration algorithm |
| Authors | Pablo Pavón Mariño, José Luis Izquierdo Zaragoza |
| Date | May 2013 |
| Code | FA_EA_minCongestionPrecomputedRestoration.java |
Detailed description
For each demand, the candidate link-disjoint candidate pairs are computed as all the link disjoint pairs p1, p2, such that p1 and p2 are admissible paths. Two solutions are considered neighbors if they differ in the routing of one demand (either primary path, backup path or both). A solution is codified as in int vector, with one coordinate per demand, containing the identifier of the link-disjoint route pair for that demand. The population size, the number of generations and the offspring size are used-defined parameters.
In each generation, a user-defined fraction of the parents are selected randomly, while the rest are the top ones. Cross-over is uniform: for each demand the routing of a randomly chosen parent passes to the child. Children are mutated in one demand randomly chosen. The top solutions among parents and offspring make it to the next generation. The evolutionary core is implemented in a separated internal class, for didactic purposes.
