QoS Constrained Internet Routing with Evolutionary Algorithms

Miguel Rocha, Pedro Sousa, Miguel Rio, Paulo Cortez

Universidade do Minho
Departamento de Informática
P-4710-057 Braga, Portugal

Tel.: +351 253 604430
Fax.: +351 253 604471
E-mail: pns (at) di.uminho.pt


Abstract

OSPF is the most common intra-domain routing protocol in Wide Area Networks. Thus, optimising OSPF weight will produce tools for traffic engineering with Quality of Service constraints, without changing the network management model. Evolutionary Algorithms (EAs) provide a valuable tool to face this NF-hard problem, allowing flexible cost functions with sweml metrics of the network behavior: A novel framework is proposed that enriches current models for network congestion with delay constraints, setting the basis for EAs that allocate OSPF weights, guided by a bi-objective cost function. The results show that EAs make an eflcient method, outperfoming common heuristics and achieving effective network behavior under unfavorable scenarios.


Proc of 2006 IEEE Congress on Evolutionary Computation, pp 9270-9277, Vancouver, Canada, Jul 16-21, 2006