Robust optimization of intradomain routing using evolutionary algorithms

Abstract

Open Shortest Path First (OSPF) is a widely used routing protocol that depends on weights assigned to each link to make routing decisions. If traffic demands are known, the OSPF weight setting (OSPFWS) problem can be defined to seek a set of weights that optimize network performance, typically by minimizing a congestion measure. The OSPFWS problem is NP-hard and, thus, meta-heuristics such as Evolutionary Algorithms (EAs) have been used in previous work to obtain near optimal solutions. However, the dynamic nature of this problem leads to the necessity of addressing these problems in a more robust manner that can deal with changes in the conditions of the network. Here, we present EAs for two of those tasks, defining objective functions that take into account, on the one hand, changes in the traffic demand matrices and, on the other, single link failures. Those functions use weighting schemes to provide trade-offs between the behaviour of the network in distinct conditions, thus providing robust sets of OSPF weights.The algorithms are implemented in the open-source software NetOpt framework.