Quality of Service constrained routing optimization using Evolutionary Computation

M. Rocha, P. Sousa, P. Cortez, M. Rio


In this work, a novel optimization framework is proposed that allows the improvement 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, working 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 network congestion and end-to-end delays. A number of experiments were performed, over a large set of network topologies, where Evolutionary Algorithms (EAs), Differential Evolution, local search methods and common heuristics were compared. EAs make the most promising alternative leading to solutions with an effective network 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.

Applied Soft. Computing Journal (2009), doi:10.1016/j.asoc.2009.11.026