EA for the design of multi-overlay robust networks
Abstract
Nowadays, overlay networks are an essential tool in telecommunications. However, few works have addressed the optimization of overlay and multi-overlay networks. This work focuses on solving the problem of designing a minimum-cost and fault-tolerant multi-overlay network. The problem is NP-hard, and exact techniques are not appropriate to compute accurate solutions efficiently. This work explores the application of a sequential and a parallel genetic algorithm to solve the problem. The experimental analysis is performed on real-world scenarios built from a MPLS data network mounted over a multiple technology (SDH/DWDM) transport network. The analysis show that the studied genetic algorithms are able to obtain promising results, while the parallel model significantly speeds up the problem resolution.
Introduction
Telecommunications have grown at a fast pace. The rapid development of network infrastructures has been driven by the growing demand for data communication over the last 20 years. As a consequence, the research community has shown a renewed interest in network design problems. Overlay and multi-overlay networks are an essential tool in telecommunication. An overlay network is built on top of another network, and their nodes can be seen as connected by virtual links, built using many physical links in the underlying network. Overlay networks are nowadays present in telephony and data communication, such as broadband Internet access, voice over IP, etc; and distributed computing systems such as cloud computing, peer-to-peer networks, and client-server applications.
The multi-overlay robust network design problem (MORNDP) is NP-hard, since the Minimum Weight 2- Connected Network Problem is reducible to it. Therefore, classic exact techniques are only applicable to solve very small instances of MORNDP. Among a broad set of modern heuristics and metaheuristics methods for optimization, evolutionary algorithms (EAs) have emerged as promising tools for solving network design problems, as they are able to compute accurate approximate solutions in acceptable execution times. In this line of work, this post explores the application of sequential and parallel Genetic Algorithms (GA) to solve the MORNDP.
The experimental analysis of the proposed GAs is performed on real-world scenarios. In these scenarios, the MORNDP proposes to find the optimum design of an MPLS network mounted over a multi-technology transport network (DWDM/SDH). The company wishes to design a robust MPLS data network, which can meet certain estimations of the future commercial demands, at the lowest cost possible. The transport layer is considered as fixed. As the transport network is an expensive and limited resource, the maintenance costs of the transport network are transferred to the MPLS network. In fact, all other costs are considered as negligible in comparison. Therefore, the problem proposes to minimize the use of the transport layer by the designed MPLS network. In addition, the proposed network must fulfill some reliability constraints to be considered as a robust design: the network must support the routing of certain traffic demands between nodes, even in the case that a single link failure arises in the transport network.
The main contributions of this article are the proposal of a sequential and a parallel GA for solving the MORNDP and the experimental evaluation on real-world network scenarios. The GAs have been designed using simple operators, that allows the proposed methods to be used to solve realistic MORNDP scenarios. Promising results are reported for the sequential and the parallel version of the GA studied in this work, while the parallel model significantly speeds up the problem resolution. The proposed GAs are implemented using a well-known library of algorithms for optimization, which allows designing reusable algorithms that can be easily extended to solve other specific variants of the problem.
Problem formulation
The MORNDP proposes to find a reliable design of an MPLS multi-overlay network over a fixed transport infrastructure, with minimum cost.
In the studied MORNDP, two different networks are present: the data network and the transport network. The data network is a MPLS virtual network built over a multiple technology (SDH/DWDM) transport network. An example is presented in Fig. 1, where the black lines represent the physical links (transport links), the continuous colored lines represent the virtual links (data links) and the dotted lines represent physical paths used by the data links. The transport network is considered fixed in the model, i.e. the topology of the transport network is part of the problem input.
In contrast to the transport network, the design of the data network is part of the problem. Since MPLS networks are overlay networks, a second overlay is given by the MPLS network. This situation is shown in Fig. 2. As before, thin colored lines represent the data links. The continuous wide red line represents a MPLS virtual circuit. The path associated to this circuit is shown as a dotted red line.
Solving the MORNDP implies the following:
- • Design the data network, which implies defining the links that will finally be included in the network and the capacity values assigned to each one.
- • Define the transport paths of each data link included in the data network.
- • The designed data network should be tolerant to single failures on the transport network. This means that the data network should be able of routing all the traffic demand, even in case of single failures of the transport links.
- • The maintenance cost of the designed data network should be minimized.
- • Define the routing on MPLS circuits for each failure scenario. In this work, a simple approach based on primary/alternative paths is used to solve this issue.
Solution representation
Using traditional encodings to represent MORNDP solutions will require to design specific evolutionary operators to maintain the solutions feasibility, thus a problem-dependant encoding was used.
A solution is implicitly encoded by the routings of its terminal nodes. Two logical sub-encodings are used: the routing encoding and the mapping encoding. Fig. 3 (routing encoding) and Fig 4. (mapping encoding) present a graphical representation of the two proposed sub-encodings to represent MORNDP solutions.
The routing encoding is divided in “routing genes” (see Fig. 3). Each routing gene is associated with a pair of terminal nodes with a non-null demand between them. A routing gene is composed by the primary path (i.e., the default routing) and the alternative path (i.e., the routing applied when any of the transport links associated to the primary path fail). Both paths are represented as lists of data nodes. The data network is implicitly defined by the paths in the routing genes. Each data link present in any path should be also present in the data network. The capacity of each link is calculated taking the minimum bandwidth available that supports the maximum data rate achieved for all failure scenarios.
The mapping encoding defines the transport mapping of each data edge present in the solution (see Fig. 4). Each gene in the mapping encoding is associated to a data link present in the solution. The gene contains a list of transport nodes that represents the transport path associated to the data link.
The proposed two-vector encoding defines all attributes of a MORNDP solution:
- • Data links and their capacity are implicitly defined by the routing encoding
- • Data routings are defined by the routing encoding
- • Transport routings are defined by the mapping encoding
Initialization
A specific procedure was proposed to generate feasible initial solutions in the GA. It is a kind of greedy randomized algorithm that can delete (previously incorporated) elements in the solution, if the construction process gets stuck.
The algorithm follows a cyclic procedure that tries to generate a routing gene in each step. The construction of the mapping genes is subordinated to the construction of the routing genes. Each routing gene is built in an iterative process: at each step the algorithm randomly selects a new data link to append to the existing routing gene. The selection is performed using the roulette wheel technique: data links that add high costs to the network are rated with low probability, and data links that add low costs or are already present on the solution are rated with high probability. If a selected data link is not mapped, the mapping gene generation is applied. It is also an iterative process that selects transport links using the roulette wheel technique. The aptitude function that is used to rate transport links is inversely proportional to the kilometers of a transport link.
The routing gene generation can fail, mainly by capacity overflow issues or primary-alternative path collision. If the routing gene construction fails after twenty attempts, a selected routing gene already incorporated to the solution is deleted and re-built in a different way. This process is repeated until the routing gene that is being constructed is completed.
The described greedy constructor is also used to repair unfeasible solutions after applying the evolutionary operators.
Crossover
Traditional crossover operators do not assure to generate feasible solutions when applied to the MORNDP. To deal with this problem, an ad-hoc crossover operator was designed.
The child is generated step by step, by copying a routing gene and all dependant mapping genes from a randomly selected parent. The crossover verifies that the primary and the alternative paths are independent in the child (they could intersect in the child, as some transport mappings in the child can be different to the original ones in the parent). The capacity restrictions are also checked and corrected if necessary. This process is repeated until the routing gene is successfully copied or no more parents are left. If the routing gene insertion fails, the routing encoding will remain incomplete and the new solution will not be feasible. The greedy randomized solution generator/corrector is then applied to complete the missing parts of the individual.
The behavior of the crossover operator is shown in Fig. 5. The routing gene [2,4] is marked with orange because it could not be inserted from any of the parent individuals. The routing genes[0,4] and [2,4] were created using the generator/corrector greedy algorithm described in the previous subsection.
Mutation
Five mutation operators were proposed to introduce diversity and improve the solutions in the GA:
- • Data layer mutation: it rebuilds a random gene of the routing encoding, mainly modifying the paths in the data layer. This mutation can change the mapping of a data link if this link is used only by one routing gene. The gene rebuilding task is delegated to the greedy randomized solution generator/corrector.
- • Transport layer mutation: it changes the mapping of data links by randomly selecting a set of mapping genes and modifying a portion of the path in each selected gene.
- • Tabu link mutation: it randomly selects a “tabu” data link which is eliminated along with its associated genes from the solution. The randomized solution generator/corrector is then used to rebuild the missing parts of the solution, without using the tabu link.
- • Best data layer mutation: it is a local search operator that uses the data layer mutation as a base for searching in the neighborhood of a solution. The operator modifies the current solution 30 times and the best result is returned.
- • Best transport layer mutation: it is another local search operator that uses the transport layer mutation for the neighborhood search. Like the previous operator, it performs 20 changes and returns the best result found.
Parallel GA
The parallel GA follows the distributed subpopulation model, using the same encoding and operators than the sequential GA. A migration operator exchanges individuals between subpopulations, considering them connected in a unidirectional ring. Four subpopulations were used in the PGA.
Conclusions
The GA and the parallel GA proposed in this work were designed using simple and intuitive evolutionary operators, without including much problem-specific information or sophisticated optimization methods for the search.
The algorithms were evaluated over a set of three real world network design scenarios. The experimental analysis allowed us to conclude that promising results were obtained with the proposed GAs, especially with the parallel GA, despite the simple approach followed to design the evolutionary operators.
Regarding the computational efficiency, the parallel version of the proposed GA significantly improved over the execution times of the sequential GA. The speedup and computational efficiency values were almost-linear for two out of the three problem instances solved. In addition, the fitness evolution analysis showed that the parallel GA was able to compute more accurate solutions than the sequential GA in significantly lower execution times. These two previous results suggest that the use of parallel implementations of GA is a promising idea to efficiently solve the MORNDP.