Quality of service constrained routing optimization using evolutionary computation

Abstract

In this work, a novel optimization framework is proposed that allows the im- provement of Quality of Service levels in TCP/IP based networks, by configuring the routing weights of link-state protocols such as OSPF. Since this is a NP-hard problem, some algorithms from Evolutionary Computation were considered, work- ing over a mathematical model that allows the definition of flexible cost functions that can take into account several measures of the network behaviour, such as net- work congestion and end-to-end delays. A number of experiments were performed, over a large set of network topologies, where Evolutionary Algorithms (EAs), Dif- ferential Evolution, local search methods and common heuristics were compared. EAs make the most promising alternative leading to solutions with an effective net- work performance, even under unfavourable scenarios. A number of state of the art multiobjective optimization algorithms were also tested, but the proposed EAs still hold as the most consistent method for network optimization.