Dimensionamento e gestão de recursos em redes multi-serviço

Abstract

Esta tese visa o estudo de métodos para o dimensionamento e gestão de recursos em redes de telecomunicações de suporte a múltiplos serviços tais como as redes MPLS e ATM. Por dimensionamento de uma rede entende-se a determinação da rede física capaz de suportar o tráfego previsto. O objectivo escolhido para a tarefa de dimensionamento consiste em minimizar o custo da rede física cumprindo com os requisitos dos serviços suportados. Este objectivo visa melhorar a competitividade de um operador de telecomunicações, e como tal, deve ser uma das suas prioridades. A tarefa de dimensionamento aparece interligada com a tarefa de gestão de recursos, uma vez que a forma como os recursos são utilizados determina a rede física necessária e a qualidade de serviço que esta proporciona. São abordados dois métodos distintos de gestão de recursos: um baseado no encaminhamento de tráfego sem restrições e outro baseado no encaminhamento de tráfego por percursos de peso mínimo. São formulados os problemas de dimensionamento de redes que resultam da utilização de cada um destes métodos de gestão de recursos e são apresentadas técnicas para resolver esses problemas. Os problemas de optimização resultantes são complexos e apenas podem ser resolvidos de forma exacta para instâncias de pequena dimensão. Para estes casos, são estudados e comparados métodos de resolução baseados em programação linear inteira. Para resolver instâncias de maiores dimensões, recorre-se ao uso de técnicas heurísticas que não garantem soluções óptimas. No caso do dimensionamento com base em encaminhamento sem restrições são estudadas heurísticas baseadas na relaxação lagrangeana e em heurísticas construtivas e é proposta uma nova heurística lagrangeana. São também estudados melhoramentos para todas as heurísticas. No caso do dimensionamento com base em encaminhamento por percursos de peso mínimo são estudadas heurísticas baseadas na relaxação lagrangeana e simulated annealing e é proposta uma heurística GRASP. Em ambos os problemas, as heurísticas são comparadas entre si, verifica-se que apresentam desempenhos distintos e que as heurísticas propostas proporcionam vantagens significativas face às existentes. Além disso, para instâncias de dimensões reduzidas, verifica-se que as heurísticas propostas obtêm resultados próximos das soluções óptimas, o que leva a acreditar que os resultados para instâncias de dimensões superiores são também de boa qualidade.

This thesis aims to study methods for the task of dimensioning and resource management of multi-service telecommunication networks, such as MPLS and ATM. The task of network dimensioning consists in determining the physical network that can support the predicted traffic. The goal of the dimensioning task is to minimize the cost of the physical network while providing the required service quality. This goal aims to improve the ability of a telecommunications operator to compete with other operators, and as such, should be one of his priorities. The dimensioning task is related to the resource management task, because the way the resources are used determines the required physical network and the quality of service it provides. Two distinct methods of resource management are addressed: one based on traffic routing without constraints and another based on traffic routing through minimum weight paths. The problems of network dimensioning that result from the utilization of each of these methods are formulated and techniques to solve these problems are presented. The resulting optimization problems are complex and can only be solved exactly for small problem instances. For these case studies, several linear integer programming methods are studied and compared. To solve larger instances, heuristics techniques are used that cannot guarantee optimal solutions. In the case of network dimensioning with unconstrained traffic routing, lagrangean relaxation and greedy based heuristics are studied and a new lagrangean based heuristic is proposed. In the case of network dimensioning based on minimum weight routing, lagrangean relaxation and simulated annealing heuristics are studied and a new GRASP heuristic is proposed. In both dimensioning problems, the heuristics are compared among themselves; it is shown that they have different performances and that the proposed heuristics have significant advantages. Also, for reduced size problem instances the proposed heuristics obtain results that are close to optimal, which leads to believe that they also obtain good solutions for larger instances.