Análise Estatística das Topologias Virtuais para Redes Ópticas em Anéis Hierárquicos
Nome: GABRIEL LESSA DA SILVA LAVAGNOLI
Tipo: Dissertação de mestrado acadêmico
Data de publicação: 19/08/2008
Orientador:
Nome |
Papel |
|---|---|
| ELIAS SILVA DE OLIVEIRA | Co-orientador |
| MARCELO EDUARDO VIEIRA SEGATTO | Orientador |
Banca:
| Nome |
Papel |
|---|---|
| ELIANA ZANDONADE | Examinador Interno |
| ELIAS SILVA DE OLIVEIRA | Coorientador |
| MARCELO EDUARDO VIEIRA SEGATTO | Orientador |
| NANDAMUDI LANKALAPALLI VIJAYKUMAR | Examinador Externo |
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.
