Use este identificador para citar ou linkar para este item: http://repositorio.ufes.br/handle/10/4064
Título: Análise estatística de projeto de topologias virtuais para redes ópticas em anéis hierárquicos
Autor(es): Lavagnoli, Gabriel Lessa da Silva
Orientador: Segatto, Marcelo Eduardo Vieira
Coorientador: Oliveira, Elias Silva de
Data do documento: 19-Ago-2008
Editor: Universidade Federal do Espírito Santo
Resumo: O problema do projeto de topologias virtuais consiste em encontrar uma topologia na camada óptica para o roteamento de tráfego em uma rede óptica de forma que alguma métrica de avaliação de desempenho de rede seja otimizado, em nosso caso, o congestionamento. Este problema é classicamente modelado como um problema de programação linear inteira mista e é classificado como NP-Hard, isto é, a busca pela solução ótima é intratável a medida que o número de nós aumenta. Com isso, desde 1996, quando foi proposto o problema, busca-se aplicar métodos heurísticos que encontrem uma boa solução (n˜ão necessariamente a soluçã˜o ótima). Tais métodos, em geral, possuem elevado custo computacional e normalmente n˜ão é estudado o t˜ão quanto é boa a solução encontrada. Esta dissertação estuda a dificuldade de encontrar uma solução satisfatória para o caso de redes com arquitetura em anéis hierárquicos. Optou-se o estudo em anéis hierárquicos devido suas vantagens de tolerˆância a falhas e facilidades de implementação computacional. Para realizar as análises utilizamos teoria básica de estatística, descrevendo a distribuição do conjunto das soluç˜ões e avaliando o valor mínimo encontrado. Concluímos que, fazendo uma análise exaustiva com pequenas amostras aleatórias simples encontram-se soluções que pertencem ao seleto grupo dos 2% melhores.
The Virtual Topology Design (VTD) problem in optical networks which consists of finding a good set of ligthpaths that minimizes, or maximizes, a given parameter. It is usually modeled as a mixed-integer linear programming problems and is well known as NP-Hard. However most of those methods present high computational cost. Therefore, since the problem was proposed in 1996, many research groups have tried to develop both new exacts and heuristics methods to find good solutions to the VTD problem. This work presents an empirical study of how difficult is to find a good solution of the VTD problem to hierarchical ring optical networks. In order to better analyze the results we have used basic statistic theory to describe the set of solutions in their distributions. We have analyzed networks with 9, 24, 36, 60 and 120 nodes and compared the results obtained whith the optimal soluction, whenever possible, otherwise with the lowerbound. the results show that the problem we have been dealing is not that hard as we thought it would be
URI: http://repositorio.ufes.br/handle/10/4064
Aparece nas coleções:PPGEE - Dissertações de mestrado

Arquivos associados a este item:
Arquivo TamanhoFormato 
tese_2736_DissertacaoMestradoGabrielLessadaSilvaLavagnoli.pdf476.94 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.