Autor(es):
Lopes, Carlos Miguel Ferreira Soares Borges 
Data: 2007
Identificador Persistente: http://hdl.handle.net/10773/2215
Origem: RIA - Repositório Institucional da Universidade de Aveiro
Assunto(s): Engenharia electrotécnica; Redes de telecomunicações; Gestão de redes de telecomunicações; Programação linear
Descrição
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.
ABSTRACT: 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. Doutoramento em Engenharia Electrotécnica
