Encaminhamento Multiobjectivo em Redes MPLS com Optimização Global da Rede

Abstract

A presente tese tem por objectivo central a abordagem de um problema de encaminhamento multiobjectivo em redes MultiProtocol Label Switching com optimização global da rede e o desenvolvimento de um método de resolução exacta. Neste problema os objectivos considerados são a minimização do custo de encaminhamento e uma distribuição do tráfego tão equilibrada quanto possível. Pretende-se garantir protecção dedicada para cada uxo, pelo que deve atribuir-se a cada um deles um par de caminhos disjuntos nos nós e, se tal não fôr possível, um par de caminhos disjuntos nos arcos. O modelo de optimização será formulado numa perspectiva global da rede, isto é, pretende-se melhorar o desempenho da rede como um todo e não privilegiar determinados uxos relativamente a outros. O modelo é resolvido de forma exacta utilizando como algoritmo auxiliar um software de resolução de problemas de optimização mono-objectivo, em particular, o CPLEX 12.6. Neste texto apresenta-se o problema que se pretende resolver utilizando uma formulação matemática de uxos em redes e descreve-se o método utilizado para a sua resolução. Realizou-se um estudo experimental com aplicação do modelo a redes com topologia gerada aleatoriamente e dimensionadas de acordo com um algoritmo também aqui descrito.

The purpose of the present work is to tackle a multiobjective routing problem in MultiProtocol Label Switching networks, considering a network-wide optimization approach and the development of an exact resolution method. In this problem, the objectives are the minimization of the routing cost and an adequate balancing of the load. For each tra c trunk, dedicated protection must be provided. As a consequence, a pair of node-disjoint paths must be associated with each trunk. If a pair of node-disjoint paths is not available, a pair of edge-disjoint paths must be found. The model will be formulated in a network-wide optimization sense, that is, the purpose is to improve the overall network performance rather than nding the best path for some tra c trunks while ignoring others. The model will be solved exactly by using as auxiliary algorithm CPLEX 12.6. In this work, the problem in question will be presented using a network ow mathematical formulation and the algorithm used to solve it will be described. An experimental study was performed using random generated network topologies. A dimensioning algorithm used to obtain the features of the networks considered in the experiments is also described in this work.