( PDF ) Algoritmos de Otimização Dinâmica Aplicados ao Projeto de Redes Ópticas

Download PDF

ads:

Francisco de Assis Boldt

Algoritmos de Otimização Dinâmica Aplicados ao

Projeto de Redes Ópticas

Vitória - ES, Brasil

Agosto de 2008

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

Francisco de Assis Boldt

Algoritmos de Otimização Dinâmica Aplicados ao

Projeto de Redes Ópticas

Dissertação apresentada à Coordenação do

Mestrado em Informática para obtenção do

Grau de Mestre em Informática pela Universi-

dade Federal do Espírito Santo.

Orientador:

Ph.D. Elias Silva de Oliveira

Co-orientador:

D.Sc. Renato Tannure Rotta de Almeida

DEPARTAMENTO DE INFORMÁTICA

CENTRO TECNOLÓGICO

UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO

Vitória - ES, Brasil

Agosto de 2008

ads:

Dissertação de Mestrado sob o título “Algoritmos de Otimização Dinâmica Aplicados ao

Projeto de Redes Ópticas”, defendida por Francisco de Assis Boldt e aprovada em Agosto de

2008, em Vitória, Estado do Espírito Santo, pela banca examinadora constituída pelos profes-

sores:

Prof. Ph.D. Elias Silva de Oliveira

Orientador

Prof. D.Sc. Renato Tannure Rotta de Almeida

Co-orientador

Prof. D.Sc. Maria Cristina Rangel

Universidade Federal do Espírito Santo

Prof. D.Sc. Luciano Lessa Lorenzoni

Centro Federal de Educação Tecnológica do

Espírito Santo

Resumo

O tráfego de dados em rede de comunicação é variável e pouco previsível. Este trabalho

apresenta um estudo empírico que compara o desempenho entre conﬁguração estática e conﬁ-

gurações dinâmicas no que diz respeito ao projeto de topologia virtual em redes ópticas com

tecnologia WDM. Para encontrar estes resultados desenvolvemos uma série de algoritmos que

possibilitam esta comparação. Estes algoritmos também podem ser úteis na avaliação de novas

heurísticas e novos modelos de otimização.

Foram feitos experimentos com redes de 6 nós e redes de 14 nós. Para as redes com 6 nós

utilizamos um algoritmo exato para encontrar uma topologia virtual ótima para cada matriz de

tráfego. Para as rede com 14 nós utilizamos a meta-heurística Algoritmo Genético para calcular

uma topologia virtual sub-ótima para as matrizes de tráfego, pois o modelo de otimização uti-

lizado neste trabalho não pode ser resolvido de forma exata para redes com grande quantidade

de nós.

Os resultados encontrados pelos experimentos mostram que a reconﬁguração dinâmica de

uma rede óptica pode melhorar o desempenho desta. Também mostram que a distribuição das

demandas grandes e pequenas inﬂuencia na optimização da rede, assim como, na qualidade dos

limites inferiores e das soluções encontradas pela heurística Algoritmo Genético.

Abstract

The data trafﬁc on a network of communication is variable and somewhat predictable. This

work presents an empirical study that compares the performance conﬁguration between static

and dynamic settings applied to the design of virtual topology in optical networks with WDM

technology. To ﬁnd these results we developed a lot of algorithms that allow this compari-

son. These algorithms can also be useful in evaluation of new heuristics and new optimization

models.

We made experiments with networks of 6 nodes and networks of 14 nodes. For networks

of 6 nodes we used an exact algorithm to ﬁnd an optimal virtual topology for each array of

trafﬁc. For networks of 14 nodes used the meta-heuristic Genetic Algorithm to compute a sub-

optimal virtual topology, because the optimization model used in this work hardly can be solved

accurately for networks with large amounts of nodes.

The results found by experiments show that the dynamic reconﬁguration of an optical

network can improve the performance of this. They also show that the distribution of large

and small demands inﬂuence on the optimization of the network, as the quality of the lower

bounds and the solutions found by heuristic genetic algorithm.

Dedicatória

Dedico este trabalho à minha sempre amiga, companheira e incentivadora Gisela.

Agradecimentos

Agradeço a Deus por me guiar e acompanhar todos os dias.

Ao professor Elias Silva de Oliveira pela oportunidade e orientação.

Ao amigo e Co-orientador Renato Tannure Rotta de Almeida pela conﬁança, paciência e

indispensáveis idéias.

Ao amigo e colega de trabalho Sérgio Nery Simões por toda ajuda direta e indireta, pelas

dicas, sugestões e incentivos.

Aos colegas de trabalho por sempre me incentivar.

Aos colegas da UFES, especialmente os colegas do LCAD, por estarem sempre dispostos a

me ajudar.

Aos amigos e família por compreenderem minha ausência e torcerem para que eu concluísse

este trabalho.

Sumário

Lista de Figuras

Lista de Tabelas

1 Introdução p. 15

1.1 Revisão Bibliográﬁca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 17

1.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 19

1.2.1 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 20

1.3 Estrutura da dissertação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 21

2 Redes Ópticas p. 22

2.1 Evolução dos Dispositivos Ópticos . . . . . . . . . . . . . . . . . . . . . . . p. 22

2.2 Topologias Reconﬁguráveis . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 26

3 Projeto de Topologia Virtual p. 27

3.1 Modelo MILP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 27

3.1.1 Função Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 27

3.1.2 Restrições de Conservação de Tráfego . . . . . . . . . . . . . . . . . p. 28

3.1.3 Restrições de Fluxo . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 28

3.1.4 Restrições de grau lógico . . . . . . . . . . . . . . . . . . . . . . . . p. 29

3.1.5 Restrições ao valor das variáveis . . . . . . . . . . . . . . . . . . . . p. 29

3.2 Algoritmo Genético . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 29

3.2.1 Representação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 30

3.2.2 Seleção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 31

3.2.3 Operadores Genéticos . . . . . . . . . . . . . . . . . . . . . . . . . p. 32

3.2.4 Parâmetros Genéticos . . . . . . . . . . . . . . . . . . . . . . . . . . p. 33

3.2.5 Implementação do Algoritmo Genético . . . . . . . . . . . . . . . . p. 34

4 Experimentos Computacionais p. 35

4.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 35

4.2 Soluções Ótimas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 38

4.3 Comparação com a Conﬁguração Estática . . . . . . . . . . . . . . . . . . . p. 39

4.4 Método das Matrizes Principais . . . . . . . . . . . . . . . . . . . . . . . . . p. 41

4.5 Método das Matrizes Anteriores . . . . . . . . . . . . . . . . . . . . . . . . p. 43

4.5.1 Método da Matriz t − 3 . . . . . . . . . . . . . . . . . . . . . . . . . p. 44

4.5.2 Método da Matriz t − 2 . . . . . . . . . . . . . . . . . . . . . . . . . p. 46

4.5.3 Método da Matriz t − 1 . . . . . . . . . . . . . . . . . . . . . . . . . p. 47

4.6 Método da Média Anterior . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 49

4.6.1 Método da Média das Duas Matrizes Anteriores . . . . . . . . . . . . p. 49

4.6.2 Método da Média das Três Matrizes Anteriores . . . . . . . . . . . . p. 51

4.7 Método Preditivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 52

4.8 Experimentos com Algoritmo Genético . . . . . . . . . . . . . . . . . . . . p. 54

5 Análise dos Resultados p. 56

5.1 Experimentos com redes de 6 nós . . . . . . . . . . . . . . . . . . . . . . . p. 56

5.1.1 Soluções Ótimas . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 56

5.1.2 Comparação com a Conﬁguração Estática . . . . . . . . . . . . . . . p. 56

5.1.3 Método das Matrizes Principais . . . . . . . . . . . . . . . . . . . . p. 58

5.1.4 Método das Matrizes Anteriores . . . . . . . . . . . . . . . . . . . . p. 60

5.1.4.1 Método da Matriz t − 3 . . . . . . . . . . . . . . . . . . . p. 60

5.1.4.2 Método da Matriz t − 2 . . . . . . . . . . . . . . . . . . . p. 61

5.1.4.3 Método da Matriz t − 1 . . . . . . . . . . . . . . . . . . . p. 62

5.1.5 Método da Média Anterior . . . . . . . . . . . . . . . . . . . . . . . p. 63

5.1.5.1 Método da Média das Duas Matrizes Anteriores . . . . . . p. 63

5.1.5.2 Método da Média das Três Matrizes Anteriores . . . . . . p. 64

5.1.6 Método Preditivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 66

5.1.7 Experimentos com AG . . . . . . . . . . . . . . . . . . . . . . . . . p. 66

5.2 Experimentos com redes de 14 nós . . . . . . . . . . . . . . . . . . . . . . . p. 68

5.2.1 Soluções com Lower Bound Determinístico . . . . . . . . . . . . . . p. 69

5.2.2 Soluções Genéticas . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 71

5.2.3 Método Estático . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 74

5.2.4 Método das Matrizes Anteriores . . . . . . . . . . . . . . . . . . . . p. 77

5.2.4.1 Método da Matriz t − 3 . . . . . . . . . . . . . . . . . . . p. 78

5.2.4.2 Método da Matriz t − 2 . . . . . . . . . . . . . . . . . . . p. 81

5.2.4.3 Método da Matriz t − 1 . . . . . . . . . . . . . . . . . . . p. 84

6 Conclusões e trabalhos futuros p. 88

6.1 Conclusões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 88

6.2 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 89

Referências Bibliográﬁcas p. 90

Anexo A -- Modelo MILP em Linguagem MathProg p. 95

Lista de Figuras

2.1 Conexão WDM ponto a ponto. . . . . . . . . . . . . . . . . . . . . . . . . . p. 22

2.2 Conexão WDM em uma topologia física em barramento. . . . . . . . . . . . p. 23

2.3 Conﬁguração dos roteadores que possibilita a topologia virtual apresentada

na Figura 2.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 23

2.4 WDM com proteção. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 24

2.5 Conﬁguração dos roteadores que possibilita a proteção apresentada na Figura

2.4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 24

2.6 Dispositivo WSS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 25

4.1 Tráfego do link RJ-SP na RNP. . . . . . . . . . . . . . . . . . . . . . . . . . p. 35

4.2 Uma demanda λ (s,d) hipotética do instante t

ao instante t

. . . . . . . . . . p. 37

4.3 Gráﬁco do tempo versus congestionamento das soluções ótimas para matrizes

com 30% de super demandas, calculadas com as restrições de Grau Lógico

1, 2, 3, 4 e 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 38

4.4 Método Estático. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 39

4.5 Comparação entre soluções ótimas e a solução estática para matrizes com

30% de super demandas com restrição de grau lógico igual a 1. . . . . . . . . p. 40

4.6 Método das Matrizes Principais. . . . . . . . . . . . . . . . . . . . . . . . . p. 42

4.7 Comparação entre soluções ótimas, método estático e método das matrizes

principais para matrizes com 30% de super demandas e grau lógico 1. . . . . p. 42

4.8 Método da Matriz t-3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 44

4.9 Comparação entre soluções ótimas, método estático e método da matriz t − 3

para matrizes com 30% de super demandas e grau lógico 1. . . . . . . . . . . p. 45

4.10 Método da Matriz t-2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 46

4.11 Comparação entre soluções ótimas, método estático e método da matriz t − 2

para matrizes com 30% de super demandas e grau lógico 1. . . . . . . . . . . p. 47

4.12 Método da Matriz t-1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 48

4.13 Comparação entre soluções ótimas, método estático e método da matriz t − 1

para matrizes com 30% de super demandas e grau lógico 1. . . . . . . . . . . p. 48

4.14 Comparação entre soluções ótimas, método estático, método da média das

duas matrizes anteriores e método da matriz t − 1 para matrizes com 30% de

super demandas e grau lógico 1. . . . . . . . . . . . . . . . . . . . . . . . . p. 50

4.15 Comparação entre soluções ótimas, método estático, método da média das

três matrizes anteriores e método da matriz t − 2 para matrizes com 30% de

super demandas e grau lógico 1. . . . . . . . . . . . . . . . . . . . . . . . . p. 52

4.16 Método Preditivo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 53

4.17 Congestionamento das soluções ótimas, método estático e método preditivo

para matrizes com 30% de super demandas e grau lógico 1. . . . . . . . . . . p. 54

5.1 Gráﬁco do tempo versus congestionamento do Lower Bound Determinístico

para matrizes com 30% de super demandas, calculadas com as restrições de

Grau Lógico 2, 4, 6 e 8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 70

5.2 Comparação entre LBD e soluções genéticas para matrizes com 30% de super

demandas com restrição de grau lógico igual a 2. . . . . . . . . . . . . . . . p. 71

5.3 Distribuição do custo encontrado com o Método Genético. . . . . . . . . . . p. 74

5.4 Comparação entre LBD, soluções genéticas e soluções estáticas para matrizes

com 30% de super demandas com restrição de grau lógico igual a 2. . . . . . p. 75

5.5 Distribuição do custo encontrado com o Método Estático. . . . . . . . . . . . p. 77

5.6 Comparação entre LBD, soluções genéticas, método estático e Método da

Matriz t − 3 para matrizes com 30% de super demandas com restrição de

grau lógico 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 78

5.7 Distribuição do custo encontrado com o Método da Matriz t-3. . . . . . . . . p. 80

5.8 Comparação entre LBD, soluções genéticas, soluções estáticas e soluções da

Matriz t −2 para matrizes com 30% de super demandas com restrição de grau

lógico igual a 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 81

5.9 Distribuição do custo encontrado com o Método da Matriz t-2. . . . . . . . . p. 83

5.10 Comparação entre LBD, soluções genéticas, soluções estáticas e soluções da

Matriz t −1 para matrizes com 30% de super demandas com restrição de grau

lógico igual a 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 84

5.11 Distribuição do custo encontrado com o Método da Matriz t-1. . . . . . . . . p. 87

Lista de Tabelas

4.1 Proporção do congestionamento em relação ao grau lógico 1 das matrizes

utilizadas para gerar o gráﬁco da Figura 4.3. . . . . . . . . . . . . . . . . . . p. 39

4.2 ∆λ

max

(MatEstatica) das matrizes utilizadas para gerar o gráﬁco da Figura 4.5. p. 41

4.3 ∆λ

max

(MatPrincipal) das matrizes utilizadas na geração do gráﬁco da Figura

4.7. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 43

4.4 ∆λ

max

(MatAnterior3) das matrizes utilizadas na Figura 4.9. . . . . . . . . . p. 45

4.5 ∆λ

max

(MatAnterior2) das matrizes utilizadas na Figura 4.11. . . . . . . . . . p. 46

4.6 ∆λ

max

(MatAnterior1) das matrizes utilizadas no gráﬁco da Figura 4.13. . . . p. 49

4.7 ∆λ

max

(Media2) das matrizes utilizadas no gráﬁco da Figura 4.14. . . . . . . p. 51

4.8 ∆λ

max

(Media3) das matrizes utilizadas no gráﬁco da Figura 4.15. . . . . . . p. 52

4.9 ∆λ

max

(Preditivo) das matrizes utilizadas no gráﬁco da Figura 4.17. . . . . . . p. 54

5.1 ∆λ

max

(MatEstatica) em 16 experimentos. . . . . . . . . . . . . . . . . . . . p. 57

5.2 ∆λ

max

(MatPrincipal) em 16 experimentos. . . . . . . . . . . . . . . . . . . p. 59

5.3 ∆λ

max

(MatAnterior3) em 16 experimentos. . . . . . . . . . . . . . . . . . . p. 60

5.4 ∆λ

max

(MatAnterior2) em 16 experimentos. . . . . . . . . . . . . . . . . . . p. 61

5.5 ∆λ

max

(MatAnterior1) em 16 experimentos . . . . . . . . . . . . . . . . . . p. 62

5.6 ∆λ

max

(Media2) em 16 experimentos. . . . . . . . . . . . . . . . . . . . . . p. 64

5.7 ∆λ

max

(Media3) em 16 experimentos. . . . . . . . . . . . . . . . . . . . . . p. 65

5.8 ∆λ

max

(Preditivo) em 16 experimentos. . . . . . . . . . . . . . . . . . . . . . p. 67

5.9 ∆λ

max

(Genetico200G) em 16 experimentos. . . . . . . . . . . . . . . . . . . p. 68

5.10 ∆λ

max

(Genetico200G) e ∆λ

max

(Genetico300G) em 16 experimentos. . . . . p. 68

5.11 Comparação entre o LBD e as Soluções Ótimas para redes de 6 nós. . . . . . p. 70

5.12 ∆λ

max

(Genetico) das matrizes utilizadas para gerar o gráﬁco da Figura 5.2. . p. 72

5.13 ∆λ

max

(Genetico) em 20 experimentos. . . . . . . . . . . . . . . . . . . . . . p. 72

5.14 ∆λ

max

(Genetico) e ∆λ

max

(MatEstatica) das matrizes utilizadas para gerar o

gráﬁco da Figura 5.4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 75

5.15 ∆λ

max

(MatEstatica) em 20 experimentos. . . . . . . . . . . . . . . . . . . . p. 76

5.16 ∆λ

max

(MatAnterior3) e ∆λ

max

(MatEstatica) das matrizes utilizadas para ge-

rar o gráﬁco da Figura 5.6. . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 79

5.17 ∆λ

max

(MatAnterior3) em 20 experimentos. . . . . . . . . . . . . . . . . . . p. 79

5.18 ∆λ

max

(MatAnterior2) e ∆λ

max

(MatEstatica) das matrizes utilizadas para ge-

rar o gráﬁco da Figura 5.8. . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 82

5.19 ∆λ

max

(MatAnterior2) em 20 experimentos. . . . . . . . . . . . . . . . . . . p. 82

5.20 ∆λ

max

(MatAnterior1) e ∆λ

max

(MatEstatica) das matrizes utilizadas para ge-

rar o gráﬁco da Figura 5.10. . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 84

5.21 ∆λ

max

(MatAnterior1) em 20 experimentos. . . . . . . . . . . . . . . . . . . p. 85

5.22 ∆λ

max

(MatAnterior1), ∆λ

max

(MatAnterior1) e ∆λ

max

(MatEstatica) em 20

experimentos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 86

5.23 Proporção do custo médio do Método Estático e Método da Matriz t − 1 em

relação ao custo do Método Genético. . . . . . . . . . . . . . . . . . . . . . p. 86

1 Introdução

O tamanho e a complexidade das redes de telecomunicações, bem como a velocidade da

troca de informação têm crescido nas últimas décadas a uma taxa sem precedentes [1]. Não

há sinal de que este crescimento seja uma anomalia, e é provável que tanto o tráfego quanto

a capacidade dos backbones continuem crescendo rapidamente em um futuro próximo [2]. A

ﬁbra óptica pode suprir essas necessidades por suas capacidades potencialmente ilimitadas [3,

4]: enorme largura de banda (quase 50 terabits por segundo (Tpbs)), baixa atenuação de sinal

(tão baixa quanto 0.2 dB/km), baixa distorção de sinal, baixa necessidade de energia, baixa

utilização de material, pequeno espaço requerido e baixo custo [5].

As arquiteturas de redes tradicionais usam switches eletrônicos e a ﬁbra óptica como um

simples substituto do ﬁo de cobre e outros meios de transmissão, limitando-se pelo gargalo

da velocidade dos dispositivos eletrônicos e apresentando limitações signiﬁcativas em redes de

telecomunicações que possuem uma crescente demanda para aplicações de Gbps [1]. A tecno-

logia de multiplexação de comprimentos de onda (WDM - wavelength division multiplexing)

permitiu que vários canais, transmitidos em comprimentos de onda diferentes, compartilhassem

a mesma ﬁbra óptica [6], aumentando a capacidade de transmissão de enlaces ponto a ponto,

característicos desse tipo de arquitetura.

Com a evolução dos dispositivos ópticos que permitem a manipulação direta dos compri-

mentos de onda, como ampliﬁcadores, multiplexadores, demultiplexadores e notadamente, as

chaves ópticas reconﬁguráveis, surgiram as redes com roteamento de tráfego por comprimentos

de onda (WRON - wavelength routed optical networks) [7]. Em tais redes, há comprimentos

de onda que correspondem a caminhos ópticos, interligando nós que não são adjacentes na

topologia física, esta última formada por enlaces de ﬁbra óptica [1, 6, 8].

Um caminho óptico é a ligação de um nó da rede a outro sem que essa transmissão precise

passar pela camada de rede, ou seja, podem ser roteados na camada física, ou óptica, da rede [1].

Para oferecer esta funcionalidade, é necessário que os nós de uma rede contenham dispositivos

ópticos arranjados de forma a constituir cross-connects ópticos (OXC - Optical Cross-Connect)

1 Introdução 16

ou multiplexadores ópticos add-drop (OADM - Optical Add-Drop Multiplexer) [6].

Assim surgiu um novo paradigma em que a camada da topologia física pôde ser sobreposta

por outra camada de rede denominada topologia lógica, ou topologia virtual, que é o conjunto

de caminhos ópticos interligando os nós diretamente, ou seja, de maneira transparente [9, 10].

Uma rede óptica é considerada totalmente transparente quando existem caminhos ópticos

entre cada par de nós da rede [1], o que geralmente não é solução eﬁciente em termos da

quantidade de recursos demandados [8]. Isto signiﬁca que, devido à limitação do número de

comprimentos de ondas que podem ser utilizados e restrições dos equipamentos nos nós da rede,

é problemático criar um canal para cada par de nós fonte e destino para uma rede a partir de

um determinado tamanho [11]. Por exemplo, uma rede com 14 nós precisaria de 14 x 13 = 182

caminhos ópticos para ser totalmente transparente. Para uma rede de 17 nós seria necessário

272 caminhos ópticos. Quase 50% a mais de canais do que a rede de 14 nós [8].

Quando uma rede óptica não possui caminhos ópticos entre todos os pares de nós da rede

ela é considerada semi-transparente [8] ou translúcida [1] . Isso requer que apenas uma parte

do tráfego seja roteada de maneira transparente dos nós de origem aos nós destinatários, sendo

a outra parte transportada por uma seqüência de caminhos ópticos com roteamento eletrônico

em alguns nós intermediários [12].

O problema encontrado nesse tipo de rede é saber qual a melhor topologia virtual. Esse é um

problema de otimização que busca melhor aproveitar os recursos ópticos e eletrônicos da rede,

minimizando variáveis como número médio de saltos, processamento de tráfego em roteadores

eletrônicos de pacotes de dados, capacidade requerida de transmissão por comprimento de onda

e outras variáveis que possam ser otimizadas [10, 8]. Como as demandas de tráfego entre os

nós da rede, organizadas em uma matriz de tráfego, mudam constantemente, essa conﬁguração

deve ser refeita para atender aos requisitos formulados no problema de otimização, sendo este,

então, um problema intrinsecamente dinâmico.

Este problema é conhecido por Projeto de Topologia Virtual (VTD - Virtual Topology De-

sign) e é considerado um problema de ﬂuxo. A complexidade de tais problemas é polinomial

quando utiliza apenas variáveis contínuas, como por exemplo, no caso de uma relaxação [10].

Quando são consideradas variáveis inteiras este problema se torna NP-difícil (NP-hard) [13].

Sendo assim, o VTD é um problema NP-difícil [11, 14] e computacionalmente intratável para

redes com muitos nós [15, 16].

Para resolver o VTD de forma exata pode-se utilizar uma formulação Programação Linear

Inteira Mista (MILP - Mixted Integer Linear Programming) [10, 8, 17, 18]. Devido a comple-

1.1 Revisão Bibliográﬁca 17

xidade do problema, alguns estudos utilizam heurísticas criadas especiﬁcamente para ele [10]

ou, ainda, meta-heurísticas [14, 19]. Em ambos os casos são encontradas soluções sub-ótimas

satisfatórias, isto é, não existe garantia de que a solução encontrada seja ótima.

O grupo de pesquisa em telecomunicações (GPTEL) do LABTEL, Laboratório de Teleco-

municações da UFES, utiliza heurísticas [10] para o estudo da conﬁguração das redes ópticas

semi-transparentes. O GPTEL também utiliza meta-heurísticas como Algoritmos Genéticos

(GA - Genetic Algoritm) [20], Simulated Annealing (SA) [21], Busca Tabu (Tabu Search) [22]

e Random Walk [23]. O grupo utiliza, ainda, alguns softwares, preferencialmente livres, para

produzir resultados. Um exemplo é o GLPK (GNU Linear Programming Kit) [24].

A maioria dos estudos feitos até agora pelo GPTEL envolve matrizes de tráfego estáticas.

Isto é uma limitação importante para a análise de soluções, pois o projeto de redes ópticas deve

possuir mecanismos de reconﬁguração que respondam a variações nas demandas de tráfego,

pois determinada solução para a topologia virtual não é adequada para qualquer cenário de

tráfego.

Este trabalho apresenta um estudo empírico do Projeto de Topologia Virtual levando em

conta a mudança no tráfego das redes de comunicação durante seu funcionamento.

1.1 Revisão Bibliográﬁca

Um dos trabalhos mais citados na pesquisa em redes ópticas é [10]. Este artigo apresenta

o modelo MILP que utilizamos nesta Dissertação. Também apresenta um método iterativo para

calcular limites inferiores. Este método iterativo precisa solucionar um modelo linear pelo me-

nos 25 vezes, o que faz dele um método muito lento. Este método é incapaz de encontrar limites

inferiores para grau lógico 1. Nós utilizamos um método para encontrar limites inferiores de

forma determinística e o chamamos de LBD (Lower Bond Determinístico). Enquanto o método

para encontrar limites inferiores apresentado em [10] demora minutos para encontrar o limite

inferior de uma matriz, o LBD precisa de menos de 1 segundo para encontrar o limite inferior

de centenas de matrizes.

O mesmo artigo apresenta algumas heurísticas para encontrar a topologia virtual de uma

rede, minimizando o congestionamento. Em nosso trabalho, utilizamos o Algoritmo Genético

para encontrar a topologia virtual das redes analisadas. Os resultados que obtivemos com o

Algoritmo Genético foram bem melhores do que os obtidos com as heurísticas apresentadas em

[10].

1.1 Revisão Bibliográﬁca 18

Os resultados apresentados em [10] foram encontrados a partir de experimentos feitos com

apenas duas matrizes de tráfego de uma rede de 14 nós, representando a média do tráfego de

uma rede. Ou seja, estes experimentos utilizaram duas matrizes estáticas. Nosso trabalho, além

analisar o tráfego de forma dinâmica, chegou a utilizar 1680 matrizes de tráfego para redes de

6 nós e 2100 matrizes de tráfego para redes de 14 nós, para tipo de experimento, sendo que

foram feitos até de 10 tipos de experimentos diferentes para cada tamanho de rede para pelo

menos 4 graus lógicos. Nosso trabalho apresenta a análise dos resultados de mais de 134.400

experimentos computacionais.

Em [25] é apresentado um estudo em que os comprimentos de onda são adicionados ou

excluídos conforme a leitura instantânea do tráfego. Os experimentos deste trabalho usam uma

formulação MILP, mas não utiliza matrizes de tráfego. Ao invés disso, utiliza padrões de tráfego

que são passados como parâmetros para os experimentos. Nosso trabalho apresenta metodolo-

gias capazes de ler o tráfego de uma rede e calcular uma nova topologia virtual levando em

conta o tempo necessário para que reconﬁguração da rede seja feita.

Os autores de [26] propõem uma atualização automática de uma rede óptica, de forma que

esta se adapte às mudanças das demandas de tráfego, decidindo a política de reconﬁguração,

selecionando a nova conﬁguração e trocando a conﬁguração antiga pela nova. Este trabalho não

apresenta resultados de experimentos computacionais. Todos nossos resultados são baseados

em muitos experimentos computacionais.

Em [27] os autores apresentam um estudo de dois algoritmos para re-otimização em redes

ópticas resilientes em malha. Trata-se de um algoritmo de re-optimização completa que reor-

ganiza tanto caminhos ópticos primários quanto os de reserva e um algoritmo de re-otimização

parcial que reorganiza apenas os caminhos ópticos de reserva. Nosso trabalho procura veriﬁ-

car como a mudança da topologia virtual durante o funcionamento de uma rede óptica pode

melhorar o desempenho desta.

Tendo em vista a complexidade do modelo MILP utilizado em [28], utiliza-se a meta-

heurística simulated annealing para solucioná-lo. Este artigo também propõe a mudança da

topologia virtual de acordo com as mudanças de tráfego. Esta dissertação apresenta experimen-

tos feitos com Algoritmo Genético, para redes de 14 nós, como também, experimentos com um

algoritmo exato, para redes de 6 nós.

O projeto de reconﬁguração da topologia virtual de uma rede óptica com topologia física em

anel é apresentado em [29]. O problema apresentado neste trabalho é a troca de uma topologia

por outra G

de forma resiliente. Isto é, durante a troca de topologia virtual a rede deverá

sempre ter um caminho de reserva para todos caminhos primários, de forma que nenhum nó

1.2 Objetivos 19

ﬁque desconectado do restante da rede em caso de falha de um único link físico. No artigo antes

citado, é apresentado, ainda, um algoritmo de custo mínimo que adiciona e remove o mínimo

de caminhos ópticos necessários para a reconﬁguração resiliente da rede. O foco deste artigo é

a mudança resiliente de topologia virtual. O nosso trabalho foca a otimização do desempenho

da rede.

Utilizando o algoritmo de custo mínimo apresentado em [29] é possível re-otimizar a topo-

logia virtual de uma rede óptica minimizando os custos da troca de topologia virtual. Isto só

reforça a possibilidade de troca de topologia virtual durante o funcionamento da rede. É o que

propomos para que a rede se otimize dinamicamente.

Muitos outros trabalhos são citados nesta dissertação, mas nenhum utiliza matrizes de trá-

fego para representar o comportamento dinâmico da rede. Os trabalho que utilizam matrizes

de tráfego apresentam resultados encontrados com experimentos para redes estáticas e utilizam

menos de 5 matrizes. Nenhum trabalho apresentou resultados de experimentos que utilizavam

uma quantidade tão grande de matrizes quanto a que nós utilizamos.

Outra inovação que este trabalho apresenta é a análise dos resultados segundo a caracteriza-

ção do tráfego da rede. Neste trabalho, mostramos que a forma com que as demandas grandes

e pequenas se distribuem na rede inﬂuenciam em sua otimização.

1.2 Objetivos

O tráfego de dados em rede de comunicação é variável e pouco previsível. Em uma rede

óptica não é diferente.

Para representar este comportamento, desenvolvemos um programa capaz de gerar seqüên-

cias de matrizes que representam a mudança do tráfego de uma rede hipotética. Chamamos este

programa de Gerador de Matrizes. Com o Gerador de Matrizes criamos várias seqüências de

matrizes com diferentes distribuições de demandas grandes e pequenas, assim como, diferentes

tamanhos de redes.

Também criamos um algoritmo que procura imitar o comportamento de uma conﬁgura-

ção estática em uma rede óptica e aplicamos este algoritmo nas várias seqüências criadas pelo

Gerador de Matrizes.

Além dos algoritmo já citados, desenvolvemos outros algoritmos que permitem o estudo de

várias formas de se conﬁgurar uma rede dinamicamente.

Utilizando estes algoritmos podemos descobrir quais a situações em que a conﬁguração

1.2 Objetivos 20

dinâmica é melhor otimizada do que a conﬁguração estática, e também, saber quão melhor é

uma conﬁguração em relação a outra.

Além da comparação entre conﬁguração estática de dinâmica, este algoritmos também per-

mitem comparações entre métodos dinâmicos de conﬁguração. Com isso, podemos veriﬁcar

qual a melhor forma de se conﬁgurar uma rede óptica.

Como veriﬁcamos várias distribuições de demandas diferentes, descobrimos que a forma

como as demandas se distribuem inﬂuenciam na otimização da rede.

1.2.1 Metodologia

A maioria dos estudos do grupo de pesquisa em telecomunicações do LABTEL (GPTEL)

são obtidos através de experimentos [8, 17, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42,

43, 44]. Estes experimentos utilizam principalmente matrizes de tráfego, que representam as

demandas da rede de comunicação de dados a ser estudada. Estas matrizes de tráfego podem

ser geradas aleatoriamente ou capturadas de uma rede real.

Matrizes de tráfego foram criadas computacionalmente seguindo algumas regras deﬁnidas

em um arquivo de conﬁguração, que deﬁne os tamanhos de matrizes que devem ser criadas,

quantas matrizes de cada tamanho, quais os tipos de matrizes e outros parâmetros. O programa

gera três tipos de matrizes: Matrizes uniformes, super demandas e super nós [41].

As matrizes uniformes apresentam um tráfego com demandas que variam aleatoriamente,

com distribuição uniforme, entre um valor mínimo e um valor máximo pré-deﬁnidos.

Nas matrizes com super demandas algumas demandas possuem valores em um intervalo

diferente do intervalo de valores das demais demandas da mesma matriz. Pode-se deﬁnir o

valor mínimo e máximo das super demandas, o valor mínimo e máximo das demais demandas,

assim como a porcentagem de super demandas que as matrizes terão.

Nas matrizes com super nós, alguns nós possuem demandas com intervalo de valores di-

ferentes dos demais nós. Analogamente ao que acontece com matrizes com super demandas,

pode-se deﬁnir o valor mínimo e máximo das demandas dos super nós, o valor mínimo e má-

ximo das demandas dos nós que não são super nós e a porcentagem de super nós que as matrizes

terão.

O programa gerador de matrizes também gera uma determinada quantidade de matrizes in-

termediárias, ou seja, o programa gera matrizes com demandas que são uma interpolação linear

das demandas de uma instância de matriz e a próxima. Desta forma, as matrizes apresentam

1.3 Estrutura da dissertação 21

uma variação gradativa, representando assim, o comportamento dinâmico que as demandas de

tráfego de uma rede óptica possui.

Os algoritmos utilizados para a comparação dos métodos de conﬁguração foram integrados

em uma biblioteca que chamamos de Biblioteca de Experimentos do GPTEL (EGPTEL). Esta

biblioteca foi implementada em linguagem C e também utiliza funções do GLPK para resolver

modelos programação linear e de programação linear inteira mixta.

1.3 Estrutura da dissertação

O Capítulo 2 fala sobre as redes ópticas e a evolução de seus dispositivos. Este capítulo

também explica como as redes ópticas podem se reconﬁgurar dinamicamente.

O Capítulo 3 apresenta o modelo MILP utilizado nos experimentos e alguns conceitos bási-

cos sobre Algoritmos Genéticos. Também apresenta alguns parâmetros do Algoritmo Genético

que utilizamos nos experimentos deste trabalho.

No Capítulo 4 apresentamos a nossa motivação e o funcionamento geral dos algoritmos.

O Capítulo 5 apresenta uma análise dos resultados obtidos com os experimentos com redes

de 6 e 14 nós.

O Capítulo 6 apresenta nossas conclusões e perspectivas de trabalhos futuros.

2 Redes Ópticas

2.1 Evolução dos Dispositivos Ópticos

Uma rede puramente óptica pode eliminar a necessidade de terminar um caminho óptico

em nós intermediários quando um grande número de comprimentos de onda passam por cada

ﬁbra. Outra vantagem é a transparência de redes puramente ópticas que realizam roteamento na

camada física, independente das características de quadros e protocolos utilizados no transporte

dos dados [45].

A nova geração de dispositivos ópticos permitem o chaveamento de cada comprimento de

onda no domínio óptico, bem como a reconﬁguração das matrizes de chaveamento com tecno-

logias como Micro sistemas eletro-mecânicos (MEMS - Micro-Eletrical Mechanical Systems).

Os multiplexadores Add-Drop (ADM - Add Drop Multiplexers) são muito conhecidos no

contexto das redes SDH/SONET. Os OADMs (Optical Add Drop Multiplexers) fazem parte

das soluções WDM que permitem a seleção e inserção de comprimentos de onda nos nós e,

conseqüentemente, a constituição de uma topologia virtual.

O caso mais simples de uma aplicação WDM seria uma ligação ponto a ponto entre dois

sites. A Figura 2.1 mostra primeiro a conexão física entre o Site A e o Site B. Depois, a conexão

lógica separando os canais por comprimentos de ondas.

Figura 2.1: Conexão WDM ponto a ponto.

Neste caso, os OADM’s não seriam necessários, já que seriam usados como simples multi-

plexadores.

2.1 Evolução dos Dispositivos Ópticos 23

A Figura 2.2 mostra uma topologia física em barramento. A topologia virtual apresentada

na ﬁgura é possível porque o OADM permite que, por exemplo, o Site D possua um canal, ou

comprimento de onda, ligado diretamente ao Site A, ou seja, os dados são transmitidos entre A

e D, passando por B e C, sem serem convertidos para o meio eletrônico nos nós intermediários.

Figura 2.2: Conexão WDM em uma topologia física em barramento.

A Figura 2.3 mostra como seria uma conﬁguração dos roteadores que possibilitaria esta

capacidade. As linhas vermelha e azul representam os canais que ligam o Site A ao Site B. A

linha verde representa a ligação entre o Site A e o Site C, que passa pelo Site B sem que os

dados sejam convertidos para o meio eletrônico. A linha amarela representa o canal que liga o

Site A ao Site D, que passa pelos Sites B e C sem que os dados transmitidos sejam convertidos

para o meio eletrônico.

Figura 2.3: Conﬁguração dos roteadores que possibilita a topologia virtual apresentada na Fi-

gura 2.2.

Outro recurso importante em redes de telecomunicações é a proteção dos enlaces de trans-

missão dos dados. A Figura 2.4 mostra a topologia física que liga 3 sites e uma possível topo-

logia virtual em que as linhas contínuas são os canais primários e as linhas pontilhadas são os

canais de reserva. Estes últimos são ativados no caso de uma falha no link físico, permitindo

assim, o contínuo funcionamento da rede.

Uma conﬁguração que permitiria esta proteção é apresentada na Figura 2.5.

2.1 Evolução dos Dispositivos Ópticos 24

Figura 2.4: WDM com proteção.

Figura 2.5: Conﬁguração dos roteadores que possibilita a proteção apresentada na Figura 2.4.

Os OADM reconﬁguráveis (ROADM - Reconﬁgurable Optical Add Drop Multiplexer) per-

mitem que o transporte óptico totalmente automatizado, acelerando a entrega dos dados e redu-

zindo custos [46].

Existem algumas variações de ROADM. A primeira geração é a arquitetura bloqueadora de

comprimentos de onda (WB - Wavelength Blocker) [47]. A segunda geração é a arquitetura de

chaveamento seletivo de comprimento de onda (WSS - Wavelength Selective Switch) [47]. Esta

última permite que o ROADM seja totalmente reconﬁgurável. Um sinal óptico com múltiplos

comprimentos de onda multiplexados chega diretamente ao WSS, que é capaz de redirecionar

um determinado comprimento de onda para uma ou mais portas, como mostra a Figura 2.6.

Para adicionar, remover e rotear um canal em um nó era necessário inicialmente separar

todos os comprimentos de ondas de um nó usando um demultiplexador, rearranjar os compri-

mentos de ondas em um painel de conexões ópticas, combinando-os na ﬁbra desejada em um

2.1 Evolução dos Dispositivos Ópticos 25

Figura 2.6: Dispositivo WSS.

multiplexador para transmissão para o próximo nó. Os ROADMs simpliﬁcaram estas operações

e, no futuro, irá eliminá-las completamente [48].

Os multiplexadores add/drop ópticos reconﬁguráveis (ROADMs) dispensam a necessi-

dade de conversão O-E-O (Óptico-Eletrônico-Óptico), permitindo que sistemas O-O-O (Óptico-

Óptico-Óptico) usem o chaveamento óptico, que possui vantagens signiﬁcativas para os prove-

dores de serviço e de transporte. O chaveamento óptico envolve baixo custo (CAPEX - CAPital

EXpenditures), já que não precisa de muitos dispositivos eletrônicos de alta velocidade. Além

disso, as despesas operacionais (OPEX - OPerational EXpenditures) são diminuídas e a conﬁ-

abilidade aumenta porque necessita de menos elementos de rede. A redução da complexidade

também reduz o tamanho físico dos dispositivos [49].

Atualmente a maioria dos fabricantes de dispositivos para redes ópticas oferecem ROADMs

baseados em várias tecnologias. Redes ópticas reconﬁguráveis necessitam de vários tipos de

ROADMs [49].

Algumas tecnologias são [49]:

Wavelength Blocker (WB) O WB foi o primeiro módulo de chaveamento de canais comerci-

almente disponível, por isso foi usado nos primeiros sistemas ROADM. O módulo WB é

essencialmente um equalizador de canal dinâmico. O preço relativamente alto do módulo

WB, devido suas limitadas capacidades, deu a ele uma baixa competitividade no mercado

atual, limitando-o a sistemas antigos, desenvolvidos antes da disponibilidade de soluções

mais competitivas.

Planar Lightwave Circuit (PLC) O PLC ROADM consiste em um par de módulos, onde um

módulo é utilizado para adicionar os enlaces lógicos e o outro módulo para remover os

enlaces lógicos. Um nó de uma rede que possui dois pares de módulos tem conectividade

física de grau 2. Uma rede que possui todos seus nós com conectividade física de grau 2

forma um anel bidirecional. Esta tecnologia possui um custo-benefício melhor do que a

2.2 Topologias Reconﬁguráveis 26

anterior.

Wavelength Selective Switch (WSS) Um WSS 1 × N pode ser usado para grau de conectivi-

dade N ou para adicionar e remover canais. Um WSS possui portas que permitem que

qualquer subconjunto do número total de canais saia por qualquer porta.

Wavelength Cross-Connect (WXC) Os WXCs fornecem soluções completas de conectividade

N × N para redes em malha. A topologia em malha aumenta a capacidade, eﬁciência

e conﬁabilidade da rede através do aumento do número de conexões e do alto nível de

redundância. Do ponto de vista operacional, esta é uma topologia altamente desejável,

porém, seu inconveniente é o CAPEX, devido a quantidade de hardware exigida. Embora

o OPEX economize o suﬁciente para que o investimento seja rapidamente recuperado, o

custo foi uma barreira signiﬁcativa para sua implantação nas redes em malha. Soluções

baseadas em PLC são uma alternativa, pois reduzem o custo de circuitos ópticos com-

plexos. Além disso, a solução PLC WXC fornece um desempenho ótico elevado, baixo

consumo de energia, conﬁabilidade sólida e alta escalabilidade.

2.2 Topologias Reconﬁguráveis

As demandas de uma rede de comunicação são distribuídas de acordo com seu estado mo-

mentâneo. Como a rede e o tráfego mudam ao longo do tempo, uma determinada topologia

virtual, otimizada inicialmente, pode passar a não atender plenamente os requisitos de conecti-

vidade óptica necessários para um determinado cenário [27]. Desde a primeira geração de redes

ópticas, elas estão se tornando cada vez mais dinâmicas [50].

Redes ópticas em malha inteligentes, baseadas na tecnologia de Multiplexação Densa por

Comprimento de Onda (DWDM - Dense Wavelength Division Multiplexed), possuem a habili-

dade de distribuir e restaurar serviços rapidamente. Além disso, com a proteção (1+1) em malha

dedicada ﬁm-a-ﬁm, quando uma conexão falha, os OCXs de entrada e de saída tentam restaurar

o sinal por um caminho de reserva pré-deﬁnido diferente do caminho primário. A diversidade

de caminhos garante que o caminho primário e o de reserva não caiam simultaneamente devido

a mesma falha [27].

A evolução dos dispositivos de redes ópticas e a característica dinâmica do tráfego das

redes de comunicação motivou a publicação de inúmeros trabalhos envolvendo reconﬁguração

e re-otimização dinâmica de redes ópticas [29, 51, 25, 52, 53, 13, 28, 26, 54, 55, 56, 57].

3 Projeto de Topologia Virtual

Problemas de programação linear visam maximizar ou minimizar um objetivo represen-

tado por uma função linear de certas variáveis, cujas restrições concorrentes especiﬁcadas por

igualdades e desigualdades, indicam a limitação de recursos do problema [58, 59, 60].

Quando o modelo de programação linear possui algumas variáveis inteiras e outras reais ele

é conhecido como modelo MILP (Mixed Integer Linear Programming - Programação Linear

Inteira Mista) [61].

Geralmente o projeto da topologia virtual de redes ópticas translúcidas é deﬁnido por um

modelo MILP [62, 3, 6, 8]. Neste tipo de problema existe uma matriz B, composta por variáveis

binárias de decisão b

i j

. Estas variáveis de decisão representam a existência de um caminho

óptico entre os nós (i, j) quando possui valor unitário, e não existência de caminho óptico

quando seu valor é zero [8].

3.1 Modelo MILP

O modelo MILP utilizado nos experimentos deste trabalho foi proposto em [10]. Este

modelo foi escolhido por ter servido de base para vários outros trabalhos [63, 53, 64, 25, 65, 66].

Uma matriz de tráfego Λ com elementos reais λ (s,d) é um dado de entrada. As principais

variáveis do problema, além das variáveis b

i j

que compõem a matriz de topologia virtual B,

são:

• λ

i j

: tráfego transportado pelo caminho óptico b

i j

• λ

i jsd

: parcela da demanda de tráfego λ (s,d) que é transportada pelo caminho óptico b

i j

3.1.1 Função Objetivo

O objetivo deste modelo é a minimização do congestionamento.

3.1 Modelo MILP 28

Função Objetivo

Minimize[λ

max

] (3.1)

3.1.2 Restrições de Conservação de Tráfego

Neste modelo existem dois tipos de restrição de tráfego. O primeiro tipo deﬁne que:

1. A soma dos componentes λ

i jsd

que saem do nó s é igual a demanda λ (s,d).

2. A soma dos componentes λ

i jsd

que chegam no nó d é igual a demanda λ (s,d).

3. A soma dos componentes λ

i jsd

que saem de um nó intermediário k = {s, d} é igual a soma

dos componentes λ

i jsd

que chegam neste nó.

∑

i jsd

−

∑

jisd











λ (s,d);s = i

−λ (s,d);d = i, ∀(s, d)

0;s = i,d = i

(3.2)

O segundo tipo de restrição de tráfego deﬁne que o carregamento de um caminho óptico λ

i j

é igual a soma dos componentes λ

i jsd

que o atravessam.

i j

∑

s,d

i jsd

, ∀(i, j) (3.3)

3.1.3 Restrições de Fluxo

O primeiro tipo de restrição de ﬂuxo deﬁne que uma componente λ

i jsd

não pode ser maior

do que a demanda de tráfego original λ (s,d), quando existe o caminho óptico b

i j

. O valor da

componente λ

i jsd

é zero quando não existe o caminho óptico b

i j

i jsd

≤ b

i j

× λ (s,d) (3.4)

O segundo tipo deﬁne o congestionamento. Nenhum ﬂuxo de tráfego λ

i j

pode ser maior do

que o congestionamento da rede λ

max

. Isto faz com que o valor de λ

max

coincida com o valor

do caminho óptico mais carregado.

i j

≤ λ

max

(3.5)

3.2 Algoritmo Genético 29

3.1.4 Restrições de grau lógico

As restrições de grau lógico deﬁnem que o grau lógico de entrada e de saída dos nós deve

ser menor ou igual ao grau lógico da rede ∆ dado como entrada.

∑

i j

≤ ∆;∀ j (3.6)

∑

i j

≤ ∆;∀i (3.7)

3.1.5 Restrições ao valor das variáveis

Este modelo não admite tráfego negativo, portanto, λ

i j

, λ

i jsd

e λ

max

devem ser maiores ou

iguais a zero.

i j

≥ 0 (3.8)

i jsd

≥ 0 (3.9)

max

≥ 0 (3.10)

As variáveis b

i j

são binárias.

i j

≥ 0 (3.11)

i j

≤ 1 (3.12)

i j

∈ I (3.13)

É possível utilizar este modelo para obter a solução exata para redes de até 8 nós, de-

pendendo do computador, programa e algoritmo utilizado para encontrar a solução. Para re-

des com muitos nós, por exemplo 14 nós, não é possível solucionar este problema de forma

exata. Neste caso, precisamos utilizar heurísticas e meta-heurísticas para encontrar soluções

sub-ótimas [10, 8].

3.2 Algoritmo Genético

As tarefas de busca e otimização possuem componentes como espaço de busca e função de

avaliação [67]. Enquanto as técnicas de busca e optimização tradicionais processam um único

3.2 Algoritmo Genético 30

candidato que é iterativamente manipulado, as técnicas de Computação Evolutiva operam sobre

uma população de candidatos fazendo sua busca em diferentes espaços de solução [68].

Baseado na Teoria da seleção natural de Darwin [69], o Algoritmo Genético (GA - Genetic

Algorithm), desenvolvido por Holland [70], é um dos melhores algoritmos conhecidos dentre

os pertencentes a Computação Evolutiva [71].

O GA utilizado nos experimentos apresentados nesta Dissertação é o resultado do trabalhos

de Iniciação Cientíﬁca dos estudantes Gustavo Coutinho Fernandes [72] e Gabriel Grillo Rosa

do CEFETES-Serra (Centro Federal de Educação Tecnológica - Unidade Serra).

Os GAs criam uma população inicial formada por um conjunto aleatório de indivíduos

vistos como possíveis soluções do problema. Depois, a população é avaliada e cada indivíduo

é avaliado de acordo com a qualidade da solução que ele representa. Uma parte dos indivíduos

com melhores avaliações é mantida e os demais são descartados. Os indivíduos mantidos podem

ser modiﬁcados por meio de mutações e cruzamento gerando descendentes para a próxima

geração [68]. Este processo é repetido até que o critério de parada seja satisfeito. Os critérios

de parada podem ser o tempo de execução do algoritmo, um determinado número de gerações,

a perda da diversidade e a convergência dos resultados [72].

O Algoritmo 1 apresenta um pseudo-código genérico do ciclo de vida de um Algoritmo

Genético [68].

t ←− 0;1

Gerar População Inicial P(0);2

para cada indivíduo i da população atual P(t) faça3

Avaliar aptidão do indivíduo i;4

ﬁm para5

enquanto Critério de para não for satisfeito faça6

t ←− t + 1;7

Selecionar população P(t) a partir de P(t − 1);8

Aplicar operadores de cruzamento sobre P(t);9

Aplicar operadores de mutação sobre P(t);10

Avaliar P(t);11

ﬁm enquanto12

Algoritmo 1: Algoritmo Genético

3.2.1 Representação

Antes de utilizar um GA, é necessário representar o problema de busca ou otimização de

uma forma que o GA possa trabalhar sobre ele [68]. Para isso, devemos conhecer a terminologia

3.2 Algoritmo Genético 31

utilizada pelos algoritmos genéticos [67, 68, 72]:

Indivíduo ou Cromossomo: estrutura de dados que representa uma possível solução do pro-

blema a ser optimizado.

Espaço de busca: conjunto de todas as conﬁgurações que o cromossomo pode assumir.

Gene: característica do problema.

Alelo: possíveis valores que um gene pode assumir.

Locus ou Loco: posição do gene dentro do cromossomo.

Genótipo: características do problema contidas no cromossomo.

Fenótipo: genótipo submetido ao problema.

População: conjunto de indivíduos.

Geração: uma população em um dado estágio de evolução.

Fitness ou Função de Aptidão: aptidão de cada indivíduo em relação função objetivo.

3.2.2 Seleção

O critério de seleção faz com que o conjunto de indivíduos iniciais gere indivíduos mais

aptos. Este é o princípio básico do funcionamento dos GAs. A população inicial é formada por

indivíduos aleatórios quando não se tem nenhum conhecimento prévio sobre a região do espaço

de busca onde se encontra a solução do problema.

Para privilegiar os indivíduos mais aptos, a função de aptidão ( f

apt

) avalia cada indivíduo

em cada geração. O resultado da função de aptidão, que tem como entrada os genes do cromos-

somo, pode ser visto como a nota daquele indivíduo e é baseada na função objetivo do problema

que se quer solucionar.

Alguns métodos de seleção utilizam a aptidão relativa ( f

rel

). A soma dos valores da aptidão

relativa é igual a 1 (

∑

rel

= 1). A aptidão relativa de um indivíduo pode ser obtida dividindo

sua aptidão absoluta pela soma da aptidão absoluta de todos os indivíduos de uma população

(Equação 3.14).

rel

(n) =

apt

(n)

∑

apt

(i)

(3.14)

3.2 Algoritmo Genético 32

A maioria dos métodos de seleção procura favorecer indivíduos com maiores notas de ap-

tidão, mas não exclusivamente, para manter a diversidade da população. Alguns métodos de

seleção conhecidos são:

Método da Roleta: é o método de seleção mais simples e mais utilizado. Nele, cada indivíduo

da população é representado na roleta por uma fatia proporcional à sua aptidão. A roleta

é girada um determinado número de vezes e cada vez que ela é girada um indivíduo é

escolhido para pertencer a população intermediária.

Método do Torneio: neste método n indivíduos são escolhidos aleatoriamente com a mesma

probabilidade. O indivíduo com maior aptidão entre estes n sorteados é selecionado para

pertencer a população intermediária.

Método da Amostragem Universal Estocástica: é uma variação do Método da Roleta que

utiliza n agulhas ao invés de uma, onde n é o número de indivíduos que pertencerão a

população intermediária.

3.2.3 Operadores Genéticos

Cada geração deve ter uma população totalmente nova mas com características adaptativas

adquiridas nas gerações anteriores. Para que isto aconteça, são utilizados os operadores de

cruzamento (crossover) e mutação. Para impedir que os melhores indivíduos desapareçam,

estes são colocados automaticamente na próxima geração, por meio de uma política elitista.

O operador de mutação altera arbitrariamente um indivíduo com o objetivo de diversiﬁcar

a população. O operador de mutação é considerado um operador secundário e, por isso, só é

aplicado em indivíduos que possuam uma probabilidade de mutação.

O cruzamento é o operador que cria um novo indivíduo a partir de características de outros

dois. É considerado o operador genético predominante e possui probabilidade maior do que a

mutação.

Existem várias maneiras de se utilizar o operador de cruzamento. As mais utilizadas são:

Cruzamento de Um-ponto É escolhido um ponto de cruzamento e as informações anteriores

a este ponto são trocadas entre os pais.

Cruzamento Multipontos Vários pontos de cruzamento são utilizados.

Cruzamento Uniforme Uma máscara determina quais genes dos cromossomos serão trocados.

3.2 Algoritmo Genético 33

3.2.4 Parâmetros Genéticos

A deﬁnição dos parâmetros utilizados inﬂuenciam fortemente no desempenho de um GA,

sendo importante a análise destes levando em conta as necessidades do problema e os recursos

disponíveis [73].

Os principais parâmetros a serem discutidos são:

Tamanho da População Quanto maior o tamanho da população, maior a cobertura do espaço

de busca do problema e maior é a necessidade de recursos computacionais.

Taxa de Cruzamento Quanto maior a taxa de cruzamento, maior a velocidade que novas estru-

turas são introduzidas na população. Uma taxa muito alta pode retirar estruturas capazes

de gerar estruturas melhores. Uma taxa muito baixa pode estagnar o GA.

Taxa de Mutação Uma taxa de mutação muito alta faz com que a busca se torne essencial-

mente aleatória. Uma taxa de mutação baixa evita que a busca estagne em máximos ou

mínimos locais.

Intervalo de Geração Quanto maior o intervalo de geração, maior a parte da geração subs-

tituída na nova geração. Um intervalo de geração muito alto pode provocar a retirada

prematura de bons indivíduos. Um intervalo de geração muito baixo pode tornar o GA

muito lento.

Critério de Parada Os critérios de parada podem ser o tempo de execução do algoritmo, um

determinado número de gerações, a perda da diversidade e a convergência dos resultados.

Se o valor ótimo for conhecido, ele pode ser usado como critério de parada. Entretanto,

se este valor não ﬁzer parte do espaço de busca representado, o algoritmo nunca chegará

ao ﬁm.

Os resultados apresentados em [72] foram de grande importância para a decisão do valor

destes parâmetros nos experimentos apresentados nesta dissertação.

Um destes parâmetros é o tamanho da população. Os resultados apresentados em [72]

mostraram que, para este Algoritmo Genético, uma população maior do que 20 indivíduos

não apresentava melhoria signiﬁcativa na solução do VTD. Sendo assim, qualquer tamanho de

população maior do que 20 aumentaria o tempo de execução do algoritmo sem melhoria na

qualidade dos resultados.

3.2 Algoritmo Genético 34

Outro parâmetro foi o critério de parada. O critério de parada escolhido foi a quantidade de

gerações. Os resultados mostraram que para o grau lógico 2 qualquer valor acima de 100 ge-

rações não apresenta melhoria na qualidade da solução e apenas aumenta o tempo de execução

do algoritmo. Para o grau lógico 4 a quantidade de gerações necessárias para que o algoritmo

genético não mais melhorasse foi 50. Esta proporção foi mantida para os graus lógicos 6 e 8,

necessitando estes de 34 e 25 gerações respectivamente.

Esta observação nos levou a fazer uma pequena alteração no critério de parada deste al-

goritmo genético. Esta alteração consiste em uma quantidade de gerações que varia de acordo

com o grau lógico. Esta quantidade de gerações é encontrada dividindo-se uma quantidade de

gerações base xG = 200 pelo grau lógico (GL). Sendo assim, a quantidade de gerações qG

utilizada como critério de parada é qG = xG/GL.

3.2.5 Implementação do Algoritmo Genético

O AG utilizado neste trabalho foi implementado pelo G3PD (Grupo de Pesquisa em Pro-

cessamento Paralelo e Distribuído) do CEFETES - Unidade Serra. Todo o código foi feito em

linguagem C e utiliza a API do GLPK para avaliar os indivíduos.

Este AG utiliza um TAD (Tipo Abstrato de Dados) matriz que foi implementado por nós

para construir o Gerador de Matrizes.

Outro TAD utilizado por este AG é o TAD indivíduo. O indivíduo é uma estrutura que

contém uma matriz que representa a topologia virtual. Seu TAD possui funções que alocam,

liberam e avaliam indivíduos. A avaliação do indivíduo é feita seguindo o modelo MILP escrito

em linguagem Mathprog e apresentado no Anexo A, que é dado como parâmetro de entrada

para o AG. Este TAD utiliza as funções do GLPK para avaliar o indivíduo.

O TAD indivíduo é utilizado por outro TAD chamado população. O TAD população possui

todas as funções necessárias para se construir o AG. Esta funções são utilizadas no programa

principal.

4 Experimentos Computacionais

4.1 Introdução

O tráfego de qualquer rede de comunicação de dados muda constantemente, enquanto a rede

estiver funcionando. A Figura 4.1 mostra o tráfego do link RJ-SP da RNP em um dia. Podemos

observar que esse link possui maior tráfego das 9 horas até as 18 horas. Mas o aumento de

tráfego não é instantâneo, é gradativo. Às 7 horas o tráfego está perto do mínimo. Às 9 horas

está perto do máximo. Às 8 horas o tráfego está próximo da média entre o tráfego das 7 horas e o

tráfego das 9 horas. Este comportamento gradativo acontece em qualquer link de um backbone,

exceto quando este link falha ou está em processo de reconﬁguração.

Figura 4.1: Tráfego do link RJ-SP na RNP.

Com base nessas observações, criamos uma seqüência de matrizes para representar o trá-

fego de várias redes durante um período de tempo. Para criar estas matrizes desenvolvemos um

programa gerador de matrizes [41] que cria matrizes para representar o tráfego de uma rede de

acordo com conﬁgurações deﬁnidas pelo usuário.

Conﬁguramos o gerador de matrizes para criar matrizes aleatórias, que chamamos de matri-

zes principais. As matrizes principais são aleatórias mas seguem algumas regras, de acordo com

seu tipo [41]. Algumas destas regras deﬁnem demandas pequenas, que variam aleatoriamente

entre 0 e 2, e demandas grandes, que variam aleatoriamente entre 0 e 200, para os experimentos

apresentados aqui. Os valores das demandas pequenas e grandes podem ser alterados em um

arquivo de conﬁguração do gerador de matrizes. Para os nossos experimentos deﬁnimos cinco

4.1 Introdução 36

tipos de matrizes principais:

1. Matrizes com 30% de super demandas. Neste tipo de matriz no máximo 30% de suas

demandas serão grandes e as demais serão pequenas.

2. Matrizes com 40% de super demandas. Neste tipo de matriz no máximo 40% de suas

demandas serão grandes e as demais serão pequenas.

3. Matrizes com 10% de super nós. Os super nós são aqueles que todas suas demandas de

entrada e saída são super demandas. Isto é, todas as demandas de entrada ou de saída são

demandas grandes. Neste caso, no máximo 10% de seus nós serão super nós.

4. Matrizes com 20% de super nós. Neste tipo de matriz no máximo 20% de seus nós

serão super nós.

5. Matrizes uniformes. Neste tipo de matriz todas as demandas serão grandes.

Estes valores foram escolhidos para veriﬁcarmos a inﬂuência da quantidade de demandas

grandes de uma matriz de tráfego no resultado, assim como, a inﬂuência da distribuição destas

demandas no resultado da otimização. Criamos matrizes com 30% de super demandas e 10%

de super nós por que estes tipos de matrizes possuem aproximadamente a mesma quantidade

de demandas grandes. A diferença entre estes dois tipos de matrizes é a distribuição destas

demandas.

Nas matrizes com 40% de super demandas aproximadamente a metade das demandas com

valores acima de zero são grandes. Nas matrizes com 20% de super nós, pouco mais da metade

das demandas acima de zero são grandes.

Para cada tipo de matriz criamos cinco matrizes principais. Entre essas matrizes principais

para cada tipo criamos outras 4 matrizes interpolando-as. Os valores das demandas das matrizes

interpoladas são o resultado de uma interpolação linear entre as demandas de duas matrizes

principais adjacentes.

Seja P1 a primeira matriz principal de um tipo e λ (s,d)

a demanda de tráfego do nó s

para o nó d na matriz P1. Seja P2 a segunda matriz principal do mesmo tipo e λ (s,d)

demanda de tráfego do nó s para o nó d na matriz P2. Seja I1-1-2 a primeira das quatro matrizes

interpoladas entre P1 e P2 e λ (s,d)

I1.1.2

a demanda de tráfego do nó s para o nó d na matriz

I1-1-2. O valor de λ (s,d)

I1.1.2

será:

λ (s,d)

I1.1.2

= λ (s,d)

+ [λ (s,d)

− λ (s,d)

]/5

4.1 Introdução 37

Seja λ (s, d)

I1.n.2

a demanda de tráfego do nó s para o nó d na n-ésima matriz interpolada

entre P1 e P2 para 0 < n ≤ 4 ∀n ∈ N, o valor de λ (s,d)

I1.n.2

será:

λ (s,d)

I1.n.2

= λ (s,d)

+ [λ (s,d)

− λ (s,d)

]/5∗ n

Desta forma criamos 21 matrizes de cada tipo, variando suas demandas gradativamente.

Cada matriz representa as demandas de tráfego da rede de um instante t

até um instante t

Estes instantes não estão vinculados a nenhuma unidade de tempo, pois dependem da capaci-

dade que a rede tem para se reconﬁgurar.

No conjunto de matrizes geradas, cada demanda da rede pode ter um comportamento pare-

cido com o apresentando na ﬁgura a seguir.

Figura 4.2: Uma demanda λ (s,d) hipotética do instante t

ao instante t

Para os experimentos apresentados nesta seção utilizamos o modelo MILP apresentado em

[10]. Este modelo possui uma restrição de grau lógico que é dada como argumento de entrada

no arquivo de dados. O grau lógico é a quantidade máxima de caminhos ópticos unidirecionais

que cada nó da rede pode originar ou receber.

Todos os algoritmos utilizados neste trabalho foram implementados em linguagem C. Tanto

o modelo MILP quanto as matrizes de tráfego são dados como parâmetro de entrada dos algo-

ritmos e são escritas em um arquivo de texto em linguagem Mathprog. O Anexo A apresenta

o modelo MILP utilizado para calcular a topologia virtual e o congestionamento em linguagem

MathProg.

Para redes de 6 nós os algoritmos utilizam funções do GLPK para encontrar a solução

exata, ou seja, uma topologia virtual ótima. Para redes de 14 nós os algoritmos utilizam um

algoritmo genético para encontrar uma boa topologia virtual. O algoritmo genético utilizado

neste trabalho também usa funções do GLPK para avaliar os seus indivíduos.

4.2 Soluções Ótimas 38

O funcionamento destes algoritmos é apresentado nas seções seguintes.

4.2 Soluções Ótimas

As soluções ótimas são as melhores soluções possíveis para o roteamento de tráfego na

rede em cada instante em que o tráfego foi medido. Para cada tipo de matriz com cada grau

lógico testado existem 21 matrizes representando as demandas de tráfego do instante t

até o

instante t

. Para cada instante, utilizamos a sua respectiva matriz de tráfego no modelo MILP e

encontramos o congestionamento ótimo resultante do roteamento de tráfego em uma topologia

virtual ótima. A solução ótima foi encontrada para todos os tipos de matrizes do grau lógico 1

até o grau lógico 5.

A Figura 4.3 apresenta um gráﬁco do tempo versus congestionamento das soluções ótimas

para matrizes com 30% de super demandas, calculadas com as restrições de Grau Lógico 1, 2,

3, 4 e 5, representados na legenda pelas siglas GL 1, GL 2, GL 3, GL 4 e GL 5, respectivamente.

A legenda também possui um valor nomeado de Área Hmax, que é o valor da área abaixo

da linha que representa o congestionamento em cada instante t para cada grau lógico. Podemos

chamar essa área de congestionamento acumulado. Observando o gráﬁco e o congestionamento

acumulado de cada grau lógico, podemos notar que, quanto maior o grau lógico, menor o con-

gestionamento em cada instante e, conseqüentemente, menor o congestionamento acumulado.

Figura 4.3: Gráﬁco do tempo versus congestionamento das soluções ótimas para matrizes com

30% de super demandas, calculadas com as restrições de Grau Lógico 1, 2, 3, 4 e 5.

4.3 Comparação com a Conﬁguração Estática 39

Na Tabela 4.1 temos a proporção do congestionamento acumulado para cada grau lógico

em relação ao grau lógico 1. Podemos notar que existe uma forte inﬂuência do grau lógico no

congestionamento ótimo.

GL 1 GL 2 GL 3 GL 4 GL 5

100% 36% 24% 18% 14%

Tabela 4.1: Proporção do congestionamento em relação ao grau lógico 1 das matrizes utilizadas

para gerar o gráﬁco da Figura 4.3.

Este experimento mostra a melhor conﬁguração possível para uma rede óptica em cada

instante que o tráfego é medido. Sabemos que nenhuma solução será melhor do que esta.

Nosso objetivo é encontrar um método viável que se aproxime desta solução.

Podemos avaliar qualquer método de conﬁguração, estático ou dinâmico, comparando-o às

soluções ótimas.

4.3 Comparação com a Conﬁguração Estática

Os estudos tradicionais na pesquisa em redes ópticas [10, 8] utilizam uma matriz com a

média do tráfego de cada demanda de uma rede durante determinado período para calcular a

topologia ótima. Esta topologia é utilizada pela rede durante todo seu funcionamento indepen-

dente das mudanças de tráfego.

Figura 4.4: Método Estático.

A Figura 4.4 mostra que a topologia virtual encontrada com a matriz que contém as médias

das demandas de todas as 21 matrizes é utilizada para calcular o congestionamento em cada

instante.

4.3 Comparação com a Conﬁguração Estática 40

Para avaliar o desempenho da conﬁguração estática, criamos uma matriz com a média das

demandas das matrizes utilizadas para cada experimento, de acordo com seu tipo. Ou seja,

foi gerada uma matriz com a média das demandas de todas as matrizes com 30% de super

demandas, outra matriz com a média das demandas de todas as matrizes com 40% de super

demandas, e assim, sucessivamente, para as matrizes com 10% e 20% de super nós e matrizes

uniformes.

Encontramos a topologia virtual ótima para as matrizes de média das demandas e utilizamos

esta topologia para calcular o congestionamento em cada instante, com a matriz que representa

o tráfego naquele instante.

Na Figura 4.5 podemos comparar o método estático, representado pela legenda "solucoes-

MatEstatica", com as soluções ótimas, representada pela legenda "solucoesOtimas", para ma-

trizes com 30% de super demandas com grau lógico 1.

A conﬁguração estática (solucoesMatEstatica) encontrou um congestionamento maior para

todas as matrizes utilizadas para gerar o gráﬁco da Figura 4.5 com grau lógico 1.

Figura 4.5: Comparação entre soluções ótimas e a solução estática para matrizes com 30% de

super demandas com restrição de grau lógico igual a 1.

Baseando-se na notação apresentada em [10], representaremos o congestionamento de um

instante n por λ max

. Para representar o congestionamento encontrado por um determinado

método de reconﬁguração em um instante n utilizaremos λ max

(metodo). Nenhum método

de reconﬁguração da topologia virtual pode encontrar um λ max

menor que o λ max

(otimo).

4.4 Método das Matrizes Principais 41

Podemos assim, determinar o custo ∆λ max

(metodo) por:

∆λ max

(metodo) =

λ max

(metodo) − λ max

(otimo)

λ max

(otimo)

× 100

A Tabela 4.2 mostra o custo ∆λ max

(estatico) obtido com as matrizes utilizadas para gerar

do gráﬁco da Figura 4.5 para os cinco graus lógicos testados.

MatEstatica GL1 GL2 GL3 GL4 GL5

N6SD30 Média 12.13% 6.45% 3.84% 1.68% 0.00%

DesvPad 8.58% 9.72% 6.60% 3.63% 0.00%

Máximo 36.99% 33.89% 16.68% 13.35% 0.00%

Mínimo 1.54% 0.00% 0.00% 0.00% 0.00%

Tabela 4.2: ∆λ

max

(MatEstatica) das matrizes utilizadas para gerar o gráﬁco da Figura 4.5.

Esta tabela mostra que o custo obtido pelo método estático para estas matrizes foi em média

12.13%. A tabela conﬁrma que, para este experimento, com grau lógico 1, em nenhum instante

o método estático atingiu o ótimo obtendo custo de 0%, pois o menor custo foi de 1.54%. Para

os outros graus lógicos, em algum momento o método estático atingiu o ótimo, pois o custo

mínimo foi de 0%. Outro fato interessante a ser observado é que, para este experimento, com

matrizes com 30% de super demandas e grau lógico 5, todas as matrizes atingiram o ótimo.

Esta tabela mostra que o custo obtido pelo método estático para estas matrizes foi em média

12.13%. A tabela conﬁrma que, para este experimento, com grau lógico 1, em nenhum instante

o método estático atingiu o ótimo obtendo custo de 0%, pois o menor custo foi de 1.54%. Para

os outros graus lógicos, em algum momento o método estático atingiu o ótimo, pois o custo

mínimo foi de 0%. Outro fato interessante a ser observado é que, para este experimento, com

matrizes com 30% de super demandas e grau lógico 5, todas as matrizes atingiram o ótimo.

4.4 Método das Matrizes Principais

Para este experimento encontramos a solução ótima para as matrizes principais, aquelas ge-

radas aleatoriamente, e usamos a topologia virtual encontrada para calcular o congestionamento

das matrizes interpoladas subseqüentes.

A Figura 4.6 mostra que a topologia virtual encontrada para uma determinada matriz prin-

cipal é utilizada para calcular o congestionamento das matrizes interpoladas sub-seqüentes.

Considerando que calculamos o congestionamento das matrizes interpoladas usando a to-

pologia virtual encontrada para matriz principal anterior, bem como, sendo linear a interpolação

4.4 Método das Matrizes Principais 42

Figura 4.6: Método das Matrizes Principais.

das demandas, as duas primeiras matrizes interpoladas em cada intervalo possuem demandas

mais próximas da matriz principal anterior, enquanto as duas últimas possuem demandas mais

próximas da matriz principal posterior. Assim, é esperado que o congestionamento das últimas

matrizes interpoladas de cada intervalo piore. Isso, é mostrado na Figura 4.7, que possui um

gráﬁco comparando as Soluções Ótimas, o Método Estático e o Método das Matrizes Principais

representandos pelas legendas “solucoesOtimas”, “solucoesMatEstatica” e “solucoesMatPrin-

cipal”, respectivamente. Também podemos observar nesta ﬁgura que a mudança de topologia

durante o funcionamento da rede pode melhorar seu desempenho em relação a conﬁguração

estática.

Figura 4.7: Comparação entre soluções ótimas, método estático e método das matrizes princi-

pais para matrizes com 30% de super demandas e grau lógico 1.

Na Tabela 4.3 podemos comparar o desempenho da conﬁguração estática com o método

das matrizes principais, para matrizes utilizadas na geração do gráﬁco da Figura 4.7.

4.5 Método das Matrizes Anteriores 43

MatPrincipal GL1 GL2 GL3 GL4 GL5

N6SD30 Média 1.97% 7.78% 10.62% 14.60% 18.65%

DesvPad 3.32% 13.15% 18.83% 28.54% 41.61%

Máximo 10.28% 51.79% 51.90% 102.54% 150.00%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

MatEstatica GL1 GL2 GL3 GL4 GL5

N6SD30 Média 12.13% 6.45% 3.84% 1.68% 0.00%

DesvPad 8.58% 9.72% 6.60% 3.63% 0.00%

Máximo 36.99% 33.89% 16.68% 13.35% 0.00%

Mínimo 1.54% 0.00% 0.00% 0.00% 0.00%

Tabela 4.3: ∆λ

max

(MatPrincipal) das matrizes utilizadas na geração do gráﬁco da Figura 4.7.

Para estas matrizes, a média do ∆λ max para o método das matrizes principais ﬁcou bem

abaixo da média para a conﬁguração estática com o grau lógico 1. Entretanto, o método das

matrizes principais piora com o aumento do grau lógico. Com grau lógico 2, o método das ma-

trizes principais já encontra um custo médio maior do que o método estático, além de encontrar

um ponto máximo maior.

O alto valor do desvio padrão mostra a instabilidade do método, que chegou a encontrar um

valor máximo de 150.00% para o grau lógico 5.

4.5 Método das Matrizes Anteriores

Os experimentos das Subseções 4.2, 4.3 e 4.4 são uma fonte de informação importante,

principalmente para comparação entre os métodos estudados. Ressalta-se, no entanto, que os

métodos utilizados nesses experimentos diﬁcilmente poderiam se utilizados em uma rede real.

O método utilizado na Subseção 4.2 necessita que a topologia virtual seja calculada e tro-

cada instantaneamente, o que diﬁcilmente seria possível. O método da Subseção 4.3 utiliza uma

matriz tráfego com a média de demandas futuras para calcular a topologia virtual. O método da

Subseção 4.4 necessita que a topologia virtual das matrizes principais seja calculada e trocada

instantaneamente.

O método apresentado nesta subseção não espera que a topologia virtual seja calculada e

trocada instantaneamente.

Suponhamos que certa rede óptica demore um instante de tempo para fazer a leitura do trá-

fego, calcular a nova topologia virtual e trocar a topologia virtual. Em um instante t

esta rede

estará usando a topologia virtual encontrada em t

n−1

. Neste experimento calculamos o con-

gestionamento da matriz de tráfego de um instante t

com a topologia virtual ótima encontrada

4.5 Método das Matrizes Anteriores 44

para a matriz de tráfego do instante t

n−k

, para k = 3, k = 2 e k = 1. O valor de k é o número de

unidades de tempo que determina o intervalo que a rede precisa para se reconﬁgurar.

Sabemos que quanto menor o tempo gasto para a rede se reconﬁgurar menor poderá ser o

custo do método. Queremos saber, no entanto, qual é o valor máximo de k para que este método

possa ter um custo menor do que o do método estático.

Se tivermos uma heurística que melhore a qualidade da solução de acordo com o tempo

gasto para encontrá-la, poderemos encontrar um bom compromisso entre qualidade da solução

e tempo gasto para encontrá-la.

4.5.1 Método da Matriz t − 3

Suponhamos que certa rede necessite de 3 unidades de tempo para medir o tráfego instan-

tâneo, calcular a nova topologia virtual e trocar a topologia atual pela nova. Em outras palavras,

a topologia virtual utilizada para calcular o congestionamento no instante t

é uma topologia

virtual ótima encontrada para a matriz de tráfego do instante t

n−3

. As exceções são as matrizes

, t

e t

que, por motivos de implementação, utilizam a topologia virtual ótima da matriz t

Figura 4.8: Método da Matriz t-3.

A Figura 4.8 mostra que a topologia virtual encontrada para a matriz de um instante t é

utilizada para calcular o congestionamento da matriz do instante t + 3.

O gráﬁco da Figura 4.9 mostra uma comparação entre o valor congestionamento encontrado

com as soluções ótimas, a conﬁguração estática e o Método da Matriz t − 3, representados na

legenda por “solucoesOtimas”, “solucoesMatEstatica” e “solucoesMatAnterior3”, respectiva-

mente. O experimento utilizado para gerar este gráﬁco foi feito com uma rede de 6 nós com

uma matriz de tráfego com 30% de super demandas e grau lógico 1.

4.5 Método das Matrizes Anteriores 45

Figura 4.9: Comparação entre soluções ótimas, método estático e método da matriz t − 3 para

matrizes com 30% de super demandas e grau lógico 1.

O congestionamento acumulado apresentado na legenda do gráﬁco por Área Hmax mostra

que para esta seqüência de matrizes com grau lógico 1 o Método da Matriz t − 3 teve melhor

desempenho.

MatAnterior3 GL1 GL2 GL3 GL4 GL5

N6SD30 Média 6.10% 12.18% 10.42% 11.14% 17.09%

DesvPad 6.16% 22.30% 18.66% 20.56% 32.63%

Máximo 21.67% 100.00% 51.91% 81.03% 122.32%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

MatEstatica GL1 GL2 GL3 GL4 GL5

N6SD30 Média 12.13% 6.45% 3.84% 1.68% 0.00%

DesvPad 8.58% 9.72% 6.60% 3.63% 0.00%

Máximo 36.99% 33.89% 16.68% 13.35% 0.00%

Mínimo 1.54% 0.00% 0.00% 0.00% 0.00%

Tabela 4.4: ∆λ

max

(MatAnterior3) das matrizes utilizadas na Figura 4.9.

Na Tabela 4.4 podemos comparar o custo do método da matriz t − 3 com o do método

estático para as matrizes utilizadas no gráﬁco da Figura 4.9 separados por grau lógico. Podemos

ver que o custo do método da matriz t − 3 só foi menor do que o do método estático para o grau

lógico 1. Todos os outros graus lógicos testados o método da matriz t −3 obteve um custo maior

do que o método estático, com um máximo igual a 122.32% para grau lógico 5.

4.5 Método das Matrizes Anteriores 46

4.5.2 Método da Matriz t − 2

O Método da Matriz t − 2 supõe que o tempo gasto para medir o tráfego, calcular a topo-

logia virtual e trocá-la seja de 2 unidades de tempo. Assim, a topologia virtual utilizada para

calcular o congestionamento no instante t

é uma topologia virtual ótima encontrada para a ma-

triz de tráfego do instante t

n−2

. As duas exceções são as matrizes t

e t

que, por motivos de

implementação, utilizam a topologia virtual ótima da matriz t

Figura 4.10: Método da Matriz t-2.

A Figura 4.10 mostra que a topologia virtual encontrada para a matriz de um instante t é

utilizada para calcular o congestionamento da matriz do instante t + 2.

A Figura 4.11 mostra uma comparação entre o valor congestionamento encontrado com as

soluções ótimas, a conﬁguração estática e o Método da Matriz t − 2, representados na legenda

por “solucoesOtimas”, “solucoesMatEstatica” e “solucoesMatAnterior2”, respectivamente. A

ﬁgura apresenta o congestionamento em uma rede de 6 nós com uma matriz de tráfego com

30% de super demandas e grau lógico 1.

MatAnterior2 GL1 GL2 GL3 GL4 GL5

N6SD30 Média 4.96% 7.75% 6.45% 5.13% 11.73%

DesvPad 4.14% 16.92% 13.49% 9.99% 21.59%

Máximo 13.02% 77.86% 52.32% 33.33% 66.67%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

MatEstatica GL1 GL2 GL3 GL4 GL5

N6SD30 Média 12.13% 6.45% 3.84% 1.68% 0.00%

DesvPad 8.58% 9.72% 6.60% 3.63% 0.00%

Máximo 36.99% 33.89% 16.68% 13.35% 0.00%

Mínimo 1.54% 0.00% 0.00% 0.00% 0.00%

Tabela 4.5: ∆λ

max

(MatAnterior2) das matrizes utilizadas na Figura 4.11.

4.5 Método das Matrizes Anteriores 47

Figura 4.11: Comparação entre soluções ótimas, método estático e método da matriz t − 2 para

matrizes com 30% de super demandas e grau lógico 1.

A Tabela 4.5 mostra que nas matrizes utilizadas para gerar o gráﬁco da Figura 4.11, o custo

do método da matriz t − 2 só foi menor do que o método estático para grau lógico 1.

4.5.3 Método da Matriz t − 1

O Método da Matriz t − 1 é o método que utiliza uma topologia virtual ótima da matriz de

tráfego de um instante t

n−1

para calcular o congestionamento da matriz de tráfego do instante

. Isto signiﬁca que a rede precisa de uma unidade de tempo para medir o tráfego, calcular e

mudar a topologia virtual.

A Figura 4.12 mostra que a topologia virtual encontrada para a matriz de um instante t é

utilizada para calcular o congestionamento da matriz do instante t + 1.

A Figura 4.13 apresenta o gráﬁco de um dos experimentos feitos para matrizes com 30%

de super demandas e comparando os resultados obtidos com as soluções ótimas, a conﬁguração

estática e o Método da Matriz t − 1, representados na legenda por “solucoesOtimas”, “soluco-

esMatEstatica” e “solucoesMatAnterior1”, respectivamente.

Nesta ﬁgura podemos notar que para este experimento com estas matrizes o método da

matriz t − 1 foi melhor em quase todos os pontos. A exceção, neste caso, foi a matriz do

instante t

, que utilizou uma topologia virtual ótima encontrada para matriz t

e obteve um

congestionamento mais alto que o encontrado utilizando a topologia virtual estática.

4.5 Método das Matrizes Anteriores 48

Figura 4.12: Método da Matriz t-1.

Figura 4.13: Comparação entre soluções ótimas, método estático e método da matriz t − 1 para

matrizes com 30% de super demandas e grau lógico 1.

Na Tabela 4.6 podemos comparar o custo do método estático com o método da matriz t − 1

com matrizes utilizadas na Figura 4.13.

Este método aplicado às matrizes utilizadas na Figura 4.13 com grau lógico 1 obteve uma

média quase seis vezes menor do que o método estático. Para grau lógico 2 e 3 o custo médio

deste método ainda foi menor que o estático, assim como o desvio padrão e o valor máximo,

exceto o valor máximo do grau lógico 3. No entanto, com grau lógico 4 e 5, o custo do método

estático foi menor.

O valor mínimo deste método sempre será de 0.00%, por que, devido a questões de imple-

4.6 Método da Média Anterior 49

MatAnterior1 GL1 GL2 GL3 GL4 GL5

N6SD30 Média 2.28% 3.02% 2.21% 1.86% 2.71%

DesvPad 3.03% 6.42% 4.84% 4.53% 6.84%

Máximo 9.09% 25.34% 19.09% 18.57% 29.75%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

MatEstatica GL1 GL2 GL3 GL4 GL5

N6SD30 Média 12.13% 6.45% 3.84% 1.68% 0.00%

DesvPad 8.58% 9.72% 6.60% 3.63% 0.00%

Máximo 36.99% 33.89% 16.68% 13.35% 0.00%

Mínimo 1.54% 0.00% 0.00% 0.00% 0.00%

Tabela 4.6: ∆λ

max

(MatAnterior1) das matrizes utilizadas no gráﬁco da Figura 4.13.

mentação, a matriz do instante t

utiliza sua topologia virtual ótima.

4.6 Método da Média Anterior

Este experimento utiliza a média das matrizes anteriores para calcular a topologia virtual.

Para encontrar a topologia virtual de uma matriz no instante t

calculamos uma matriz

com a média das demandas das matrizes entre o instante t

n−k

e t

n−1

. Chamaremos esta matriz

média de ∆λ (s,d)

n..k

. Utilizamos a topologia virtual ótima da matriz ∆λ (s, d)

n..k

para calcular

o congestionamento da matriz de tráfego do instante t

4.6.1 Método da Média das Duas Matrizes Anteriores

Neste experimento calculamos o congestionamento para a matriz de tráfego do instante t

utilizando a topologia virtual ótima encontrada para a matriz ∆λ (s,d)

n..2

, que é calculada da

seguinte forma:

∆λ (s,d)

n..2

λ (s,d)

n−1

+ λ (s,d)

n−2

As exceções são as matrizes t

, que não possui nenhuma anterior e usa sua própria topologia

virtual ótima, e a matriz t

, que possui apenas a matriz t

como anterior e por isso utiliza a

topologia virtual ótima encontrada para a matriz t

O gráﬁco da Figura 4.14 mostra uma comparação entre o congestionamento encontrado

com as soluções ótimas, o Método Estático, o Método da Média das Duas Matrizes Anteriores

e o Método da Matriz t − 1, representados na legenda por “solucoesOtimas”, “solucoesMa-

tEstatica”, “solucoesMedia2” e “solucoesMatAnterior1”, respectivamente. O gráﬁco mostra

experimentos feitos com matrizes de tráfego de ordem 6 com 30% de super demandas e grau

4.6 Método da Média Anterior 50

lógico 1. Utilizamos o método da matriz t − 1 como comparação, porque este foi o melhor

método heurístico até o momento.

Figura 4.14: Comparação entre soluções ótimas, método estático, método da média das duas

matrizes anteriores e método da matriz t − 1 para matrizes com 30% de super demandas e grau

lógico 1.

Nesta ﬁgura podemos observar que, neste caso, o método da média das duas matrizes ante-

riores teve melhores resultados do que o método estático. Entretanto, o desempenho do método

da média das duas matrizes anteriores foi inferior ao desempenho do método da matriz t − 1.

Considere λ (s, d)

a demanda com origem no nó s e destino ao nó d no instante t

. Con-

sidere ∆λ (s, d)

n..2

a média entre as demandas λ (s,d)

n−1

e λ (s, d)

n−2

. Se a demanda λ (s,d)

estiver aumentando linearmente em função de n, então λ (s,d)

> λ (s,d)

n−1

> ∆λ (s,d)

n..2

isto é, a diferença entre ∆λ (s,d)

n..2

e λ (s, d)

é maior do que a diferença entre λ (s,d)

n−1

e λ (s,d)

. Por outro lado, se λ (s,d) estiver diminuindo linearmente em função de t, então

λ (s,d)

< λ (s,d)

n−1

< ∆λ (s,d)

n..2

. De qualquer forma, a média terá uma diferença da matriz

do instante t

maior do que a matriz do instante t

n−1

. Isto explica a causa do desempenho deste

método ser inferior ao método da matriz t − 1.

Na Tabela 4.7 podemos comparar o desempenho deste método com o método estático, para

matrizes utilizadas no gráﬁco da Figura 4.14.

Podemos ver que neste caso o custo deste método foi menor do que o método estático tanto

para o grau lógico 1, quanto para o grau lógico 2. O método da matriz t − 2 obteve um custo

mais alto do que o método estático com o grau lógico 2.

4.6 Método da Média Anterior 51

Media2 GL1 GL2 GL3 GL4 GL5

N6SD30 Média 4.38% 3.76% 6.05% 3.12% 7.86%

DesvPad 4.39% 4.67% 9.28% 7.01% 14.58%

Máximo 14.45% 13.04% 30.12% 25.34% 56.68%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

MatEstatica GL1 GL2 GL3 GL4 GL5

N6SD30 Média 12.13% 6.45% 3.84% 1.68% 0.00%

DesvPad 8.58% 9.72% 6.60% 3.63% 0.00%

Máximo 36.99% 33.89% 16.68% 13.35% 0.00%

Mínimo 1.54% 0.00% 0.00% 0.00% 0.00%

Tabela 4.7: ∆λ

max

(Media2) das matrizes utilizadas no gráﬁco da Figura 4.14.

4.6.2 Método da Média das Três Matrizes Anteriores

Neste método utilizamos a topologia virtual ótima da matriz ∆λ (s, d)

n..3

para calcular o

congestionamento da matriz do instante t

. Podemos encontrar ∆λ (s,d)

n..3

da seguinte forma:

∆λ (s,d)

n..3

λ (s,d)

n−1

+ λ (s,d)

n−2

+ λ (s,d)

n−3

As exceções são as matrizes dos instantes t

, t

e t

. A matriz do instante t

utiliza sua

própria topologia virtual ótima por não ter nenhuma anterior. A matriz do instante t

utiliza a

topologia virtual ótima da matriz do instante t

por ser esta última sua única anterior. A matriz

do instante t

utiliza a topologia virtual ótima da matriz com a média das demandas das matrizes

dos instantes t

e t

por só possuir estas duas matrizes como suas anteriores.

A Figura 4.15 mostra uma comparação entre o congestionamento encontrado com as solu-

ções ótimas, o Método Estático, o Método da Média das Três Matrizes Anteriores e o Método

da Matriz t − 2, representados na legenda por “solucoesOtimas”, “solucoesMatEstatica”, “so-

lucoesMedia3” e “solucoesMatAnterior2”, respectivamente, para matrizes de tráfego com 30%

de super demandas e grau lógico 1.

Utilizamos o método da matriz t − 2 para veriﬁcar se o seu comportamento é parecido com

o do método da média das três anteriores.

Para esta seqüência de matrizes o método da média das três matrizes anteriores obteve o

mesmo resultado que o método da matriz t − 2 para o grau lógico 1. Entretanto, a Tabela 4.8

mostra que para os demais graus lógicos o resultado não foi o mesmo, obtendo piores resultados

do que o método da matriz t − 2, conseqüentemente, pior também do que o método da matriz

t − 1.

4.7 Método Preditivo 52

Figura 4.15: Comparação entre soluções ótimas, método estático, método da média das três

matrizes anteriores e método da matriz t − 2 para matrizes com 30% de super demandas e grau

lógico 1.

Media3 GL1 GL2 GL3 GL4 GL5

N6SD30 Média 4.95% 9.62% 6.92% 7.47% 13.19%

DesvPad 4.14% 19.30% 16.26% 18.49% 25.10%

Máximo 13.02% 77.86% 53.32% 77.86% 100.33%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

MatAnterior2 GL1 GL2 GL3 GL4 GL5

N6SD30 Média 4.96% 7.75% 6.45% 5.13% 11.73%

DesvPad 4.14% 16.92% 13.49% 9.99% 21.59%

Máximo 13.02% 77.86% 52.32% 33.33% 66.67%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Tabela 4.8: ∆λ

max

(Media3) das matrizes utilizadas no gráﬁco da Figura 4.15.

4.7 Método Preditivo

Suponhamos que exista um algoritmo que consiga estimar no instante t

as demandas de

tráfego no instante t

n+1

com baixa taxa de erro. Se conseguíssemos calcular e trocar a topologia

virtual em uma unidade de tempo teríamos um congestionamento bem próximo do ótimo.

A Figura 4.16 mostra que a topologia virtual encontrada para a matriz estimada de um

instante t é utilizada para calcular o congestionamento da matriz real do instante t. Para se

estimar o valor das demandas de uma matriz em um instante t utilizamos as demandas das

matrizes nos instantes t − 1 e t − 2.

4.7 Método Preditivo 53

Figura 4.16: Método Preditivo.

Como já conhecemos a função que rege nossas matrizes, que é uma função linear, podemos

construir um método para simular este algoritmo. Basta somarmos as demandas da matriz do

instante t

com a diferença entre suas demandas e as demandas da matriz do instante t

n−1

λ (s,d)

n+1

= λ (s,d)

+ [λ (s,d)

− λ (s,d)

n−1

] (4.1)

λ (s,d)

n+1

= 2 ∗ λ (s,d)

− λ (s,d)

n−1

(4.2)

Este método utiliza a topologia virtual encontrada para a suposta matriz do instante t

n+1

para calcular o congestionamento da matriz de tráfego real do instante t

n+1

A Figura 4.17 apresenta o gráﬁco de um dos experimentos feitos para matrizes com 30% de

super demandas e comparando os resultados obtidos com as soluções ótimas, Método Estático

e Método Preditivo, representados pelas legendas “solucoesOtimas”, “solucoesMatEstatica” e

“solucoesPreditivas”, respectivamente.

Podemos notar que neste caso este método teve apenas um erro.

A Tabela 4.9 mostra a média e o desvio padrão do custo para os métodos estático e preditivo,

para as matrizes utilizadas no gráﬁco da Figura 4.17.

Os valores da média e do desvio padrão nos mostram que este método possui um custo

muito baixo.

4.8 Experimentos com Algoritmo Genético 54

Figura 4.17: Congestionamento das soluções ótimas, método estático e método preditivo para

matrizes com 30% de super demandas e grau lógico 1.

Preditivas GL1 GL2 GL3 GL4 GL5

N6SD30 Média 0.37% 0.63% 0.11% 0.00% 0.00%

DesvPad 1.68% 2.10% 0.49% 0.01% 0.00%

Máximo 7.69% 8.70% 2.23% 0.04% 0.00%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

MatEstatica GL1 GL2 GL3 GL4 GL5

N6SD30 Média 12.13% 6.45% 3.84% 1.68% 0.00%

DesvPad 8.58% 9.72% 6.60% 3.63% 0.00%

Máximo 36.99% 33.89% 16.68% 13.35% 0.00%

Mínimo 1.54% 0.00% 0.00% 0.00% 0.00%

Tabela 4.9: ∆λ

max

(Preditivo) das matrizes utilizadas no gráﬁco da Figura 4.17.

4.8 Experimentos com Algoritmo Genético

Encontrar uma solução MILP pode ser muito custoso e demorado. O GLPK não consegue

resolver o problema apresentado em [10] para uma rede de 14 nós. Por estes motivos nos vol-

tamos a buscar novas maneiras de encontrar boas soluções mesmo que estas não sejam ótimas.

A única diferença entre este método e o Método das Soluções Ótimas e que este utiliza o

AG ao invéz do algoritmo exato.

A Meta-Heurística evolutiva Algoritmo Genético mostrou-se uma boa alternativa para o

resolvedor de MILP utilizado aqui.

Notamos que, para graus lógicos baixos, o Algoritmo Genético avalia o ﬁtness mais rapi-

4.8 Experimentos com Algoritmo Genético 55

damente do que para graus lógicos altos. No entanto, para graus lógicos baixos a convergência

para uma boa solução era mais lenta do que para graus lógicos altos. Isto signiﬁca que para

graus lógicos baixos o Algoritmo Genético precisa de mais gerações para encontrar uma boa

solução. Por isso, ﬁzemos uma pequena alteração no Algoritmo Genético. Utilizamos uma

quantidade de gerações base (xG). Esta quantidade de gerações base é utilizada pelo Algoritmo

Genético para determinar a quantidade (qG) de gerações utilizadas em cada grau lógico (GL).

Desta forma, a quantidade de gerações utilizadas em cada matriz foi qG = xG/GL.

5 Análise dos Resultados

Neste capítulo apresentamos os resultados obtidos nos experimentos com redes de 6 e 14

nós.

Nas redes com 6 nós utilizamos o GLPK para encontrar a solução exata. Nos experimentos

com redes 14 nós utilizamos o Algoritmo Genético para encontrar soluções sub-ótimas.

5.1 Experimentos com redes de 6 nós

Com redes de 6 nós, cada experimento foi feito desde o grau lógico 1, que forma um anel

unidirecional, até o grau lógico 5 que, para uma rede de 6 nós, signiﬁca gerar uma topologia

transparente. Lembramos que para este modelo de otimização, o grau lógico dado como argu-

mento é o grau lógico máximo, podendo assim, existir uma solução ótima que não necessita

utilizar todos caminhos ópticos permitidos. Por exemplo, nos experimentos aqui apresentados

várias soluções para grau lógico 5 não são transparentes, assim como alguns dos experimentos

para grau lógico 4 possuem soluções em que alguns nós utilizam apenas 3 caminhos ópticos.

5.1.1 Soluções Ótimas

Nós utilizamos as soluções ótimas para comparar todos os métodos apresentados neste

trabalho. Todos os resultados apresentam um custo relativo às soluções ótimas.

5.1.2 Comparação com a Conﬁguração Estática

Alguns dos fatos observados na Tabela 4.2 não se repetiram em outros experimentos, con-

forme vemos na Tabela 5.1.

Esta tabela apresenta a média, desvio padrão, máximo e mínimo do custo do método es-

tático em 16 experimentos. Os valores são apresentados separados por grau lógico e tipo de

5.1 Experimentos com redes de 6 nós 57

MatEstatica GL1 GL2 GL3 GL4 GL5

N6SD30 Média 13.50% 7.97% 3.44% 3.89% 1.81%

DesvPad 12.90% 10.54% 5.66% 7.56% 5.29%

Máximo 58.89% 46.95% 32.89% 33.33% 25.00%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SD40 Média 11.07% 8.63% 5.66% 3.37% 1.12%

DesvPad 11.26% 8.49% 8.38% 5.79% 3.91%

Máximo 61.58% 46.96% 48.85% 33.33% 25.92%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SN10 Média 3.24% 0.71% 1.12% 1.17% 1.83%

DesvPad 4.51% 2.92% 4.26% 5.01% 8.11%

Máximo 29.17% 24.80% 30.93% 33.33% 66.67%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SN20 Média 6.02% 6.41% 2.57% 2.32% 0.42%

DesvPad 5.22% 6.43% 4.73% 5.11% 2.93%

Máximo 26.80% 27.35% 26.78% 33.33% 25.00%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6UNI Média 6.83% 6.37% 7.94% 3.67% 0.28%

DesvPad 5.09% 4.68% 5.09% 3.55% 2.00%

Máximo 32.60% 22.79% 27.36% 18.19% 19.48%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Todos Média 8.13% 6.02% 4.15% 2.88% 1.09%

DesvPad 9.31% 7.66% 6.28% 5.64% 4.97%

Máximo 61.58% 46.96% 48.85% 33.33% 66.67%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Tabela 5.1: ∆λ

max

(MatEstatica) em 16 experimentos.

matrizes, onde "N6" representa a ordem da matriz, "SD" representa super demandas, "SN" re-

presenta super nós, "UNI" representa uniformes. O número que segue "SD" ou "SN" representa

a porcentagem de super demandas ou super nós, de acordo com o tipo da matriz. Por último, o

grupo "Todos", apresenta os valores encontrados ignorando a separação de tipos.

Nesta tabela podemos observar que, para todos os tipos de matrizes, com todos os graus

lógicos estudados, o método estático atingiu o ótimo pelo menos uma vez, pois todos os cam-

pos Mínimo apresentam o valor de 0%. O método estático com grau lógico 5 não atingiu o

ótimo com todas as matrizes em todos os experimentos, nem para as matrizes com 30% de

super demandas, que apresentaram um máximo de 0% na Tabela 4.2. Isto acontece porque o

modelo utilizado nesses experimentos restringe o grau lógico máximo, não exigindo assim que

as topologias virtuais com grau lógico 5 sejam transparentes para redes de 6 nós.

As matrizes com 10% de super nós obtiveram um custo muito menor do que as demais

para os graus lógicos 1, 2 e 3. Isto sugere que o método estático funciona melhor quando há

demandas grandes concentradas em um pequeno número de nós.

5.1 Experimentos com redes de 6 nós 58

Comparando os valores das matrizes com 30% de super demandas da Tabela 5.1, que con-

tém a análise estatística de 16 experimentos, e os valores apresentados na Tabela 4.2, que mostra

os resultados considerando apenas as matrizes utilizadas para gerar o gráﬁco da Figura 4.5, ve-

mos que o comportamento das matrizes com 30% de super demandas com o grau lógico 1

apresentadas do gráﬁco da Figura 4.5, se repete em outros experimentos, já que tanto a média

quanto o desvio padrão nas duas tabelas possuem valores próximos. Isto também acontece para

os graus lógicos 2 e 3, mas não acontece para os graus lógicos 4 e 5, onde vemos que o baixo

custo do método apresentado na Tabela 4.2 não se repetiu para os outros experimentos.

As matrizes geradas para estes experimentos representam o tráfego de uma rede do instante

até um instante t

. A matriz utilizada para calcular a topologia virtual é uma matriz com

a média das demandas do instante t

até o instante t

. A topologia virtual encontrada a partir

dessa matriz com a média das demandas é utilizada para calcular o congestionamento desde o

instante t

até o instante t

. Numa situação real, no instante t

não saberíamos o tráfego de

nenhuma matriz de um instante t

,∀n > 0. Portanto, este método não pode ser aplicado em uma

rede real. Nosso objetivo neste método é encontrar uma boa topologia virtual e utilizá-la em

cada instante t

. Desta forma, teremos um bom método estático e teremos que encontrar méto-

dos dinâmicos que obtenham um ∆λ max médio menor do que o obtido pelo método estático.

5.1.3 Método das Matrizes Principais

Na Tabela 5.2 podemos comparar o custo entre o método das matrizes principais e o método

estático em todas as matrizes em 16 experimentos.

Podemos observar que no geral, este método teve um desempenho pior que a conﬁguração

estática, tendo custo menor apenas com grau lógico 1.

Como já foi dito anteriormente, nesses experimentos, considerando t

e t

matrizes prin-

cipais, as matrizes dos instantes t

e t

possuem demandas mais próximas de t

do que de t

enquanto as matrizes dos instantes t

e t

possuem demandas mais próximas de t

do que de t

Entretanto, as matrizes em t

e t

utilizam a topologia virtual encontrada para t

, encontrando

assim um congestionamento alto.

Para o grau lógico 1, o método das matrizes principais mostrou um bom desempenho,

apresentando valores menores que o método estático na média de todas as matrizes. No entanto,

para as matrizes com 10% de super nós, onde o método estático obteve o melhor desempenho,

o método das matrizes principais ﬁcou muito acima. Para este mesmo tipo de matriz e grau

lógico 5, o método das matrizes principais obteve em média 20.12% de custo.

5.1 Experimentos com redes de 6 nós 59

MatPrincipal GL1 GL2 GL3 GL4 GL5

N6SD30 Média 7.39% 13.10% 8.73% 6.12% 12.62%

DesvPad 10.61% 24.65% 16.90% 14.99% 42.41%

Máximo 53.81% 204.63% 113.76% 102.54% 400.00%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SD40 Média 6.85% 12.56% 9.17% 4.49% 5.19%

DesvPad 9.68% 17.74% 21.21% 10.50% 22.12%

Máximo 42.42% 121.65% 202.89% 95.26% 275.40%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SN10 Média 5.96% 8.67% 6.00% 8.96% 18.94%

DesvPad 7.08% 20.18% 14.82% 21.14% 36.70%

Máximo 38.78% 126.81% 78.24% 100.00% 150.00%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SN20 Média 3.95% 8.68% 7.49% 4.92% 7.15%

DesvPad 5.14% 9.87% 12.89% 13.64% 15.27%

Máximo 25.20% 66.35% 95.37% 121.29% 112.26%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6UNI Média 3.91% 5.54% 5.02% 4.52% 1.64%

DesvPad 5.14% 6.74% 6.15% 9.18% 6.01%

Máximo 28.30% 39.58% 47.46% 100.00% 56.15%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Todos Média 5.61% 9.71% 7.28% 5.80% 9.11%

DesvPad 7.99% 17.37% 15.29% 14.59% 28.56%

Máximo 53.81% 204.63% 202.89% 121.29% 400.00%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

MatEstatica GL1 GL2 GL3 GL4 GL5

Todos Média 8.13% 6.02% 4.15% 2.88% 1.09%

DesvPad 9.31% 7.66% 6.28% 5.64% 4.97%

Máximo 61.58% 46.96% 48.85% 33.33% 66.67%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Tabela 5.2: ∆λ

max

(MatPrincipal) em 16 experimentos.

Para graus lógicos maiores que 1, o método das matrizes principais sempre foi pior do que

o método estático. Para as matrizes com 30% de super demandas e grau lógico 5, o método das

matrizes principais encontrou um custo máximo de 400.00%, além de uma média de 15.25%,

que pode ser considerada alta, já que das 21 matrizes de cada tipo em cada experimento, 5 são

matrizes principais e utilizam uma topologia virtual ótima para encontrar o congestionamento.

Podemos ver que, enquanto o método estático melhora seu desempenho com o aumento

do grau lógico, o método das matrizes principais não mantém uma regularidade. Este método

demonstrou-se instável e apresentou resultados ruins ao ser comparado com o método estático.

Esta constatação nos leva a acreditar que uma mudança de topologia em um intervalo de

tempo mal deﬁnido pode prejudicar o desempenho da rede.

5.1 Experimentos com redes de 6 nós 60

5.1.4 Método das Matrizes Anteriores

Subdividimos nesta subseção os resultados obtidos com os métodos que utilizam as matri-

zes anteriores.

5.1.4.1 Método da Matriz t − 3

A Tabela 5.3 mostra o custo obtido em 16 experimentos, separados por grau lógico e tipos

de matrizes.

MatAnterior3 GL1 GL2 GL3 GL4 GL5

N6SD30 Média 10.30% 12.69% 8.62% 6.09% 10.16%

DesvPad 11.28% 20.07% 14.14% 14.50% 31.50%

Máximo 66.82% 181.13% 62.87% 173.19% 392.24%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SD40 Média 9.73% 12.08% 8.88% 5.98% 4.48%

DesvPad 9.42% 13.99% 16.39% 14.68% 15.44%

Máximo 40.00% 81.86% 202.89% 201.88% 211.64%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SN10 Média 5.23% 6.38% 5.39% 7.34% 14.87%

DesvPad 6.26% 16.75% 14.05% 19.14% 29.73%

Máximo 38.78% 126.81% 78.24% 121.48% 150.00%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SN20 Média 5.07% 8.47% 7.95% 4.97% 5.54%

DesvPad 4.78% 8.44% 12.29% 10.95% 12.09%

Máximo 22.85% 55.11% 79.38% 100.89% 66.67%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6UNI Média 5.68% 6.21% 6.32% 5.17% 1.24%

DesvPad 5.22% 5.04% 5.11% 7.34% 4.85%

Máximo 27.29% 28.95% 32.10% 88.48% 39.91%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Todos Média 7.20% 9.17% 7.43% 5.91% 7.26%

DesvPad 8.14% 14.22% 13.04% 13.91% 21.87%

Máximo 66.82% 181.13% 202.89% 201.88% 392.24%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

MatEstatica GL1 GL2 GL3 GL4 GL5

Todos Média 8.13% 6.02% 4.15% 2.88% 1.09%

DesvPad 9.31% 7.66% 6.28% 5.64% 4.97%

Máximo 61.58% 46.96% 48.85% 33.33% 66.67%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Tabela 5.3: ∆λ

max

(MatAnterior3) em 16 experimentos.

Para grau lógico 1 todos os tipos de matrizes tiveram custo menor neste método do que

no método estático. Mas, para todos os outros graus lógicos testados este método obteve custo

maior. O máximo foi de 392.24% para as matrizes com 30% super demandas e grau lógico 5.

5.1 Experimentos com redes de 6 nós 61

Em geral, o custo médio deste método foi maior do que o método estático.

5.1.4.2 Método da Matriz t − 2

A Tabela 5.4 mostra os custos do método da matriz t − 2 separados por tipo de matriz e grau

lógico.

MatAnterior2 GL1 GL2 GL3 GL4 GL5

N6SD30 Média 6.23% 8.20% 5.32% 3.29% 4.91%

DesvPad 8.47% 13.85% 9.66% 10.56% 15.76%

Máximo 56.28% 94.01% 52.32% 160.78% 161.27%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SD40 Média 5.92% 7.66% 5.68% 3.66% 1.94%

DesvPad 6.43% 9.28% 11.75% 10.39% 7.20%

Máximo 27.09% 48.53% 167.76% 149.31% 90.64%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SN10 Média 3.71% 5.13% 3.22% 3.43% 8.45%

DesvPad 4.79% 12.89% 9.57% 11.51% 19.58%

Máximo 27.84% 100.00% 57.46% 100.00% 134.43%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SN20 Média 2.93% 5.69% 5.39% 3.20% 2.75%

DesvPad 3.41% 6.43% 9.56% 7.93% 7.52%

Máximo 17.55% 44.63% 69.87% 73.48% 59.90%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6UNI Média 3.31% 3.90% 3.88% 3.11% 0.62%

DesvPad 3.48% 3.52% 3.46% 4.42% 2.97%

Máximo 18.72% 19.30% 20.39% 46.88% 25.00%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Todos Média 4.42% 6.12% 4.70% 3.34% 3.73%

DesvPad 5.81% 10.10% 9.28% 9.31% 12.53%

Máximo 56.28% 100.00% 167.76% 160.78% 161.27%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

MatEstatica GL1 GL2 GL3 GL4 GL5

Todos Média 8.13% 6.02% 4.15% 2.88% 1.09%

DesvPad 9.31% 7.66% 6.28% 5.64% 4.97%

Máximo 61.58% 46.96% 48.85% 33.33% 66.67%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Tabela 5.4: ∆λ

max

(MatAnterior2) em 16 experimentos.

Podemos conﬁrmar nesta tabela o fato observado na Tabela 4.5. Avaliando todas as matri-

zes, independentemente do seu tipo, este método só foi melhor do que o método estático para

o grau lógico 1, obtendo médias de custo maiores para todos os outros graus lógicos estudados

nestes experimentos. Da mesma forma, o valor máximo só foi menor para o grau lógico 1.

5.1 Experimentos com redes de 6 nós 62

Observamos também que o custo deste método foi menor do que o custo apresentado pelo

método da matriz t − 3. Este é um fato animador pois nos mostra que quanto mais rápido

pudermos mudar a topologia, menor será o congestionamento encontrado em cada instante.

5.1.4.3 Método da Matriz t − 1

A Tabela 5.5 apresenta o custo deste método em 16 experimentos. Nesta tabela podemos

ver que o custo médio de todas as matrizes sempre foi menor do que o método estático em todos

os graus lógicos. O mesmo acontece com o desvio padrão, exceto para o valor máximo que foi

maior para os graus lógicos 3, 4 e 5.

MatAnterior1 GL1 GL2 GL3 GL4 GL5

N6SD30 Média 2.21% 3.10% 2.10% 1.39% 1.11%

DesvPad 3.98% 5.95% 4.30% 6.36% 4.33%

Máximo 27.14% 41.68% 25.12% 105.97% 30.38%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SD40 Média 2.01% 3.04% 2.24% 1.58% 0.37%

DesvPad 3.34% 4.46% 4.86% 4.74% 1.92%

Máximo 18.94% 25.17% 64.89% 52.51% 17.03%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SN10 Média 1.64% 2.03% 1.45% 1.10% 1.72%

DesvPad 2.62% 5.58% 5.42% 5.70% 5.64%

Máximo 14.71% 39.02% 50.00% 65.14% 42.98%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SN20 Média 1.02% 2.58% 2.39% 1.30% 0.49%

DesvPad 1.59% 3.52% 4.52% 3.30% 2.40%

Máximo 8.92% 19.13% 26.48% 27.63% 20.67%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6UNI Média 1.11% 1.53% 1.52% 1.28% 0.13%

DesvPad 1.54% 1.81% 1.78% 1.94% 1.25%

Máximo 8.46% 9.36% 9.05% 14.65% 20.37%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Todos Média 1.60% 2.46% 1.94% 1.33% 0.76%

DesvPad 2.82% 4.56% 4.37% 4.69% 3.55%

Máximo 27.14% 41.68% 64.89% 105.97% 42.98%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

MatEstatica GL1 GL2 GL3 GL4 GL5

Todos Média 8.13% 6.02% 4.15% 2.88% 1.09%

DesvPad 9.31% 7.66% 6.28% 5.64% 4.97%

Máximo 61.58% 46.96% 48.85% 33.33% 66.67%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Tabela 5.5: ∆λ

max

(MatAnterior1) em 16 experimentos

Um fato curioso é que o maior valor médio do custo foi para o grau lógico 2 para quase

5.1 Experimentos com redes de 6 nós 63

todos os tipos de matrizes. Normalmente, este método teve um bom desempenho para o grau

lógico 1, piorou seu desempenho para o grau lógico 2 e voltou a melhorar progressivamente até

o grau lógico 5. Isto acontece porque o grau lógico 1 não possui a proporcionalidade que os

demais graus lógicos possuem entre si. O grau lógico 1 consegue um valor ótimo mais do que

duas vezes maior que o grau lógico 2 e mais do que três vezes maior que o grau lógico 3. Por

isso, o grau lógico 1 é um caso especial.

Para entendermos melhor este fato devemos lembrar que o grau lógico 1 sempre gera um

anel unidirecional. Suponhamos que a conﬁguração deste anel seja uma seqüência de enlaces

do nó 1 para o nó 2, do nó 2 para o nó 3, até o nó n − 1 para o nó n e do nó n para o nó 1.

Se todas as demandas maiores que zero fossem nesta mesma seqüência a proporcionalidade

do congestionamento se aproximaria da proporcionalidade que existe entre os graus lógicos

maiores que 1. Mas este é um caso muito especial e com uma possibilidade inﬁnitamente

pequena de ocorrer em uma rede real.

Normalmente, um nó 2 possui demanda maior que zero para o nó 5, por exemplo. Então, os

enlaces que ligam 2 e 3, 3 e 4, 4 e 5, precisam transportar sua própria demanda mais a demanda

de 2 para 5. Como estas demandas que não pertencem a seqüência do anel unidirecional não

possuem caminhos alternativos, elas sobrecarregam o anel gerando um congestionamento alto,

mesmo para uma conﬁguração ótima.

Apesar de geralmente diminuir o custo médio com o aumento do grau lógico, o custo má-

ximo, na maioria das vezes, aumenta, diminuindo apenas para o grau lógico 5. Isto signiﬁca

que, uma maior quantidade de valores se aproxima do ótimo quando o grau lógico é maior.

O maior custo médio encontrado foi de 3.10% para matrizes de super demandas e grau

lógico 2, que pode ser considerado um valor aceitável. O maior dos valores máximo é de

105.97% para matrizes de super demandas e grau lógico 4, que aparenta ser um valor isolado,

já que para este tipo de matriz com este grau lógico a média foi de 1.39% com um desvio padrão

de 6.36%.

5.1.5 Método da Média Anterior

Aqui dividimos os resultados que utilizaram a média das demandas das matrizes anteriores.

5.1.5.1 Método da Média das Duas Matrizes Anteriores

Vejamos na Tabela 5.6 os resultados obtidos em 16 experimentos.

5.1 Experimentos com redes de 6 nós 64

Media2 GL1 GL2 GL3 GL4 GL5

N6SD30 Média 3.76% 5.14% 3.98% 2.74% 3.02%

DesvPad 5.50% 8.84% 7.27% 7.45% 9.23%

Máximo 27.09% 69.38% 50.00% 69.38% 81.57%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SD40 Média 3.86% 5.11% 3.18% 1.70% 1.24%

DesvPad 5.09% 6.88% 5.43% 3.56% 4.75%

Máximo 25.40% 48.52% 31.79% 26.30% 55.82%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SN10 Média 2.27% 3.32% 2.24% 2.79% 4.42%

DesvPad 3.25% 9.33% 6.57% 12.14% 11.80%

Máximo 16.27% 100.00% 50.00% 178.05% 66.67%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SN20 Média 1.82% 4.06% 3.76% 2.24% 1.13%

DesvPad 2.47% 5.13% 6.72% 5.85% 3.98%

Máximo 15.26% 27.26% 44.77% 55.85% 28.08%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6UNI Média 2.00% 2.44% 2.65% 2.06% 0.26%

DesvPad 2.58% 2.52% 2.41% 3.29% 1.43%

Máximo 18.72% 13.92% 16.21% 36.91% 12.19%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Todos Média 2.74% 4.01% 3.16% 2.31% 2.02%

DesvPad 4.08% 7.07% 5.97% 7.22% 7.42%

Máximo 27.09% 100.00% 50.00% 178.05% 81.57%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

MatEstatica GL1 GL2 GL3 GL4 GL5

Todos Média 8.13% 6.02% 4.15% 2.88% 1.09%

DesvPad 9.31% 7.66% 6.28% 5.64% 4.97%

Máximo 61.58% 46.96% 48.85% 33.33% 66.67%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Tabela 5.6: ∆λ

max

(Media2) em 16 experimentos.

Na média de todas das matrizes, independente do tipo, este método só obteve custo maior

para o grau lógico 5. Lembramos que com grau lógico 5 pode encontrar uma topologia total-

mente conexa.

Os resultados apresentados nesta tabela, apesar de serem piores do que os resultados do

método da matriz t − 1, são melhores do que os resultados do método da matriz t − 2. Como

já foi mostrado anteriormente, a matriz utilizada para calcular a topologia virtual neste método

possui demandas com valores iguais a

λ (s,d)

n−1

+λ (s,d)

n−2

5.1.5.2 Método da Média das Três Matrizes Anteriores

A Tabela 5.7 mostra o custo deste método em 16 experimentos.

5.1 Experimentos com redes de 6 nós 65

A média do custo em todos os 16 experimentos foi menor do que a média apresentada na

Tabela 4.8 para todos os graus lógicos, exceto grau lógico 1.

Media3 GL1 GL2 GL3 GL4 GL5

N6SD30 Média 5.77% 6.98% 5.70% 4.22% 4.29%

DesvPad 8.33% 12.70% 10.06% 11.64% 11.72%

Máximo 56.28% 78.65% 53.32% 113.16% 100.33%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SD40 Média 5.59% 6.53% 4.85% 2.89% 1.51%

DesvPad 6.29% 7.53% 7.80% 5.78% 4.78%

Máximo 27.09% 39.92% 41.76% 38.25% 31.74%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SN10 Média 2.80% 3.99% 3.18% 4.03% 7.60%

DesvPad 3.68% 9.78% 11.02% 14.71% 17.52%

Máximo 16.27% 63.02% 131.48% 178.05% 121.01%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SN20 Média 2.66% 5.19% 4.25% 2.61% 1.73%

DesvPad 3.29% 6.05% 8.17% 5.87% 6.03%

Máximo 17.55% 27.56% 69.87% 55.33% 66.67%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6UNI Média 3.22% 3.54% 3.64% 2.82% 0.60%

DesvPad 3.48% 3.31% 3.31% 3.90% 3.32%

Máximo 18.72% 18.30% 20.39% 36.91% 42.50%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Todos Média 4.01% 5.25% 4.32% 3.31% 3.14%

DesvPad 5.56% 8.60% 8.54% 9.34% 10.45%

Máximo 56.28% 78.65% 131.48% 178.05% 121.01%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

MatEstatica GL1 GL2 GL3 GL4 GL5

Todos Média 8.13% 6.02% 4.15% 2.88% 1.09%

DesvPad 9.31% 7.66% 6.28% 5.64% 4.97%

Máximo 61.58% 46.96% 48.85% 33.33% 66.67%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Tabela 5.7: ∆λ

max

(Media3) em 16 experimentos.

Esta tabela também mostra que para todos os experimentos e para todos os tipos de matri-

zes, sem distinção, este método obteve melhores resultados do que o método da matriz t − 2.

Podemos ver que este método apresentou melhores resultados do que o método estático para o

grau lógico 2, enquanto que, para o mesmo grau lógico, o método da matriz t − 2 teve custo

maior.

Comparando a média dos 16 experimentos, o método da matriz t −2 não obteve custo menor

em nenhum tipo de matriz em nenhum grau lógico. Ou seja, comparando o método da média

das três matrizes anteriores com o método da matriz t − 2 para todos os tipos de matrizes, todos

os graus lógicos em todos os experimentos vemos que o método da média das três matrizes

5.1 Experimentos com redes de 6 nós 66

anteriores teve custo menor.

Apesar do método da média das três matrizes anteriores ser melhor do que o método da

matriz t −2 ele não seria adequado em nenhum caso. Esse método requer que os procedimentos

de medir o tráfego, calcular a topologia virtual e trocar a topologia atual pela calculada, sejam

feitos em no máximo uma unidade de tempo, porque ele utiliza a matriz do instante t

n−1

para

encontrar a matriz média. Com este atraso é mais viável utilizar o método a matriz t − 1.

Com isso podemos concluir que utilizar a média de valores históricos recentes não contribui

para a melhoria do desempenho de um método de re-otimização dinâmico, já que a utilização

do valor mais recente para calcular a topologia virtual é, em média, mais vantajosa. Tanto o

método da matriz t − 1 quanto o método da média das duas matrizes anteriores obtiveram custo

médio menor do que o método da média das três matrizes anteriores.

5.1.6 Método Preditivo

A Tabela 5.8 mostra o custo deste método em 16 experimentos.

Para todos os tipos de matrizes este método apresentou um custo médio muito baixo. Mas,

para matrizes com 30% de super demandas e grau lógico 5, este método teve um valor máximo

de 58.59%, que pode ser considerado alto já que o valor máximo encontrado no método estático

com grau lógico 5 foi de 25.92%.

Mesmo assim, sabemos que se existir um algoritmo que consiga prever o tráfego em um

instante t

n+1

, este será o melhor dentre os métodos vistos aqui.

5.1.7 Experimentos com AG

A Tabela 5.9 mostra o custo de se usar o Algoritmo Genético com xG igual a 200 gerações

em relação a solução ótima.

Considerando que o tempo gasto para encontrar uma solução ótima utilizando o GLPK em

um determinado computador, com um processador AMD Turion de 1.3 Ghz e 1 GB de memória

principal, pode ultrapassar 30 minutos para apenas uma matriz de ordem 6 com grau lógico 3,

e o tempo gasto para encontrar uma boa solução com o Algoritmo Genético com xG = 200 no

mesmo computador para a mesma matriz é de no máximo 4 segundos, a opção do AG mesmo

com xG = 200, se mostrou uma boa alternativa para substituir o algoritmo exato em situações

em que este último é inviável.

5.1 Experimentos com redes de 6 nós 67

Preditivas GL1 GL2 GL3 GL4 GL5

N6SD30 Média 0.50% 0.81% 0.49% 0.29% 0.72%

DesvPad 2.11% 3.28% 2.71% 2.12% 4.87%

Máximo 16.72% 31.98% 35.46% 31.15% 58.59%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SD40 Média 0.40% 0.98% 0.49% 0.24% 0.16%

DesvPad 1.85% 3.48% 2.21% 1.28% 1.24%

Máximo 18.94% 35.03% 25.36% 11.68% 14.74%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SN10 Média 0.69% 0.38% 0.13% 0.33% 0.39%

DesvPad 2.13% 2.33% 0.95% 2.83% 2.38%

Máximo 14.73% 28.77% 9.71% 39.00% 23.18%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SN20 Média 0.24% 1.12% 0.60% 0.27% 0.29%

DesvPad 0.91% 3.31% 2.31% 1.99% 2.50%

Máximo 8.92% 21.75% 19.57% 27.63% 37.52%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6UNI Média 0.18% 0.43% 0.68% 0.83% 0.18%

DesvPad 0.69% 1.39% 2.29% 3.01% 1.19%

Máximo 5.13% 9.37% 23.11% 30.20% 13.42%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Todos Média 0.40% 0.74% 0.48% 0.39% 0.35%

DesvPad 1.66% 2.88% 2.18% 2.34% 2.78%

Máximo 18.94% 35.03% 35.46% 39.00% 58.59%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

MatEstatica GL1 GL2 GL3 GL4 GL5

Todos Média 8.13% 6.02% 4.15% 2.88% 1.09%

DesvPad 9.31% 7.66% 6.28% 5.64% 4.97%

Máximo 61.58% 46.96% 48.85% 33.33% 66.67%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Tabela 5.8: ∆λ

max

(Preditivo) em 16 experimentos.

Entretanto, notamos na Tabela 5.9, que o custo para grau lógico 2 foi maior do que para os

demais graus lógicos de forma relevante. Isto poderia ser uma característica do Algoritmo Ge-

nético ou o resultado de uma quantidade pequena de gerações. Para sanar esta dúvida, repetimos

os experimentos com as soluções genéticas com xG = 300.

Podemos ver na Tabela 5.10 que o aumento de 50% em xG não apresentou melhora signi-

ﬁcativa. Da mesma forma, o tempo gasto para encontrar estas soluções foi aproximadamente

50% maior.

A partir destes experimentos decidimos utilizar o Algoritmo Genético para repetir parte dos

experimentos apresentados nesta seção para rede com 14 nós.

Os resultados obtidos para redes de 14 nós são apresentados na seção seguinte.

5.2 Experimentos com redes de 14 nós 68

Geneticas GL1 GL2 GL3 GL4 GL5

N6SD30 Média 0.00% 1.01% 0.09% 0.06% 0.00%

DesvPad 0.00% 2.58% 0.71% 0.42% 0.00%

Máximo 0.00% 22.01% 9.81% 4.58% 0.00%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SD40 Média 0.00% 2.07% 0.19% 0.09% 0.00%

DesvPad 0.00% 3.25% 0.80% 0.50% 0.00%

Máximo 0.00% 17.33% 8.27% 5.26% 0.00%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SN10 Média 0.00% 0.01% 0.00% 0.00% 0.00%

DesvPad 0.00% 0.12% 0.00% 0.00% 0.00%

Máximo 0.00% 2.21% 0.00% 0.00% 0.00%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6SN20 Média 0.00% 1.36% 0.09% 0.00% 0.00%

DesvPad 0.00% 2.33% 0.54% 0.03% 0.00%

Máximo 0.00% 14.47% 5.89% 0.53% 0.00%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

N6UNI Média 0.00% 2.75% 0.96% 0.21% 0.00%

DesvPad 0.00% 2.14% 1.10% 0.58% 0.00%

Máximo 0.00% 10.66% 5.31% 3.75% 0.00%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Todos Média 0.00% 1.44% 0.26% 0.07% 0.00%

DesvPad 0.00% 2.51% 0.81% 0.40% 0.00%

Máximo 0.00% 22.01% 9.81% 5.26% 0.00%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

MatEstatica GL1 GL2 GL3 GL4 GL5

Todos Média 8.13% 6.02% 4.15% 2.88% 1.09%

DesvPad 9.31% 7.66% 6.28% 5.64% 4.97%

Máximo 61.58% 46.96% 48.85% 33.33% 66.67%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Tabela 5.9: ∆λ

max

(Genetico200G) em 16 experimentos.

Geneticas GL1 GL2 GL3 GL4 GL5

Todos Média 0.00% 1.44% 0.26% 0.07% 0.00%

DesvPad 0.00% 2.51% 0.81% 0.40% 0.00%

Máximo 0.00% 22.01% 9.81% 5.26% 0.00%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Geneticas300G GL1 GL2 GL3 GL4 GL5

Todos Média 0.00% 1.42% 0.26% 0.07% 0.00%

DesvPad 0.00% 2.50% 0.81% 0.41% 0.00%

Máximo 0.00% 22.01% 9.81% 8.33% 0.00%

Mínimo 0.00% 0.00% 0.00% 0.00% 0.00%

Tabela 5.10: ∆λ

max

(Genetico200G) e ∆λ

max

(Genetico300G) em 16 experimentos.

5.2 Experimentos com redes de 14 nós

Utilizamos redes de 6 nós na seção anterior para testar os métodos de re-otimização. Esta

seção mostra o comportamento de alguns métodos em redes com 14 nós.

5.2 Experimentos com redes de 14 nós 69

A conﬁguração do gerador de matrizes é a mesma utilizada para criar as matrizes de 6 nós,

exceto a ordem das matrizes.

Como o GLPK não consegue resolver o problema apresentado em [10] não podemos utilizar

um algoritmo exato para encontrar o valor ótimo. Para termos uma idéia de quão boa é a solução

encontrada utilizamos limites inferiores (Lower Bounds).

5.2.1 Soluções com Lower Bound Determinístico

O limite inferior escolhido como base de comparação nos experimentos de 14 nós foi o

Lower Bound Determinístico (LBD).

O LBD é encontrado dividindo maior demanda de saída ou de entrada entre os nós da

rede pelo grau lógico. O LBD produz limites inferiores iguais aos do método iterativo de

limites inferiores apresentado em [10]. O LBD produz bons limites inferiores com um custo

computacional muito baixo.

Para calcular o LBD, somamos todas as demandas das linhas e das colunas das matrizes de

tráfego. O valor do LBD será o maior valor encontrado divido pelo grau lógico.

Na Tabela 5.11 temos uma comparação entre as Soluções Ótimas e o LBD para redes de 6

nós.

Nesta tabela podemos notar que o LBD ﬁcou em média muito abaixo do valor ótimo para o

grau lógico 1. Isto acontece porque o grau lógico 1 não encontra um valor ótimo proporcional

ao demais graus lógicos. O método utilizado para encontrar limites inferiores apresentado em

[10] não consegue encontrar um limite inferior para o grau lógico 1.

Outra observação a ser feita nesta tabela é que o LBD obteve os piores resultados para ma-

trizes uniformes e o melhores resultados para as matrizes com 10% de super nós. Isto signiﬁca

que o tipo de matriz inﬂuencia na qualidade do limite inferior.

Conhecendo estas características do LBD podemos esperar que os piores resuldados dos

algoritmos serão encontrados para as matrizes uniformes.

A Figura 5.1 mostra o gráﬁco do tempo versus congestionamento para os graus lógicos 2,

4, 6 e 8, representados pela legenda GL2, GL4, GL6 e GL8, respectivamente.

O valor encontrado pelo LBD em cada matriz será usado para calcular o custo de cada

método já que, como já foi dito, não conseguiríamos encontrar a solução ótima para matrizes

de 14 nós utilizando o modelo apresentado em [10] com o GLPK.

5.2 Experimentos com redes de 14 nós 70

Otimas GL1 GL2 GL3 GL4 GL5

N6SD30 Média 39.54% 0.22% 0.03% 0.14% 1.63%

DesvPad 18.87% 1.23% 0.40% 0.86% 3.76%

Máximo 100.23% 14.38% 6.76% 9.02% 22.81%

Mínimo 1.90% 0.00% 0.00% 0.00% 0.00%

N6SD40 Média 57.60% 1.60% 0.12% 0.22% 1.61%

DesvPad 18.71% 3.07% 0.71% 1.01% 3.54%

Máximo 107.18% 15.98% 7.32% 9.73% 20.02%

Mínimo 5.48% 0.00% 0.00% 0.00% 0.00%

N6SN10 Média 14.83% 0.00% 0.00% 0.00% 0.08%

DesvPad 15.71% 0.00% 0.00% 0.00% 0.66%

Máximo 64.11% 5.00% 5.00% 5.00% 7.47%

Mínimo 0.68% 0.00% 0.00% 0.00% 0.00%

N6SN20 Média 63.40% 2.23% 0.05% 0.00% 0.84%

DesvPad 19.05% 4.86% 0.37% 0.04% 2.30%

Máximo 124.23% 25.04% 3.80% 0.77% 15.09%

Mínimo 11.44% 0.00% 0.00% 0.00% 0.00%

N6UNI Média 123.79% 28.48% 8.62% 1.75% 1.87%

DesvPad 16.36% 8.42% 5.54% 2.43% 2.82%

Máximo 159.64% 46.63% 23.01% 10.95% 10.83%

Mínimo 67.83% 0.00% 0.00% 0.00% 0.00%

Todos Média 59.83% 6.51% 1.77% 0.42% 1.21%

DesvPad 40.32% 11.94% 4.25% 1.41% 2.91%

Máximo 159.64% 46.63% 23.01% 10.95% 22.81%

Mínimo 0.68% 0.00% 0.00% 0.00% 0.00%

Tabela 5.11: Comparação entre o LBD e as Soluções Ótimas para redes de 6 nós.

Figura 5.1: Gráﬁco do tempo versus congestionamento do Lower Bound Determinístico para

matrizes com 30% de super demandas, calculadas com as restrições de Grau Lógico 2, 4, 6 e 8.

5.2 Experimentos com redes de 14 nós 71

5.2.2 Soluções Genéticas

Este método utiliza o GA (Genetic Algoritm - Algoritmo Genético) para encontrar uma

topologia virtual para as matrizes de tráfego em cada instante. Depois, o congestionamento é

calculado utilizando esta topologia virtual. A topologia virtual encontrada em cada instante não

é garantidamente a ótima, dado que o GA é uma heurística.

Se o congestionamento encontrado para uma matriz de tráfego com determinada topologia

virtual é igual ao limite inferior desta matriz de tráfego, então, esta topologia virtual é uma

topologia virtual ótima, pois ela chegou a uma solução igual ao mínimo teórico, que é o limite

inferior. Entretanto, o fato de não encontrar o valor de congestionamento igual ao limite inferior

não signiﬁca que esta topologia virtual é ou não uma solução ótima. Isso porque, o limite

inferior pode ser menor do que o valor ótimo.

A Figura 5.2 mostra a comparação entre LBD e as soluções genéticas representadas pelas

legendas “solucoesLBD” e “solucoesGeneticas”, respectivamente.

Figura 5.2: Comparação entre LBD e soluções genéticas para matrizes com 30% de super

demandas com restrição de grau lógico igual a 2.

Vemos nesta ﬁgura que as soluções genéticas normalmente ﬁcaram muito acima do LBD

na maioria das matrizes neste caso.

O custo das soluções genéticas para a seqüência de matrizes utilizada para gerar o gráﬁco

da Figura 5.2 é apresenta na Tabela 5.12.

Podemos ver na Tabela 5.12 que o GA atingiu o mesmo valor do limite inferior pelo menos

5.2 Experimentos com redes de 14 nós 72

Geneticas GL2 GL4 GL6 GL8

N14SD30 Média 25.16% 1.42% 0.00% 0.10%

DesvPad 13.91% 2.73% 0.00% 0.45%

Máximo 52.13% 9.50% 0.00% 2.07%

Mínimo 0.00% 0.00% 0.00% 0.00%

Tabela 5.12: ∆λ

max

(Genetico) das matrizes utilizadas para gerar o gráﬁco da Figura 5.2.

uma vez, já que o valor mínimo é zero. Este valor foi encontrado para a matriz do instante t

como podemos ver no gráﬁco da Figura 5.2.

O custo das soluções genéticas separado por tipo de matriz e grau lógico é apresentado na

Tabela 5.13.

Geneticas GL2 GL4 GL6 GL8

N14SD30 Média 28.22% 1.35% 0.15% 0.10%

DesvPad 13.86% 2.87% 0.70% 0.48%

Máximo 64.99% 17.38% 6.96% 4.95%

Mínimo 0.00% 0.00% 0.00% 0.00%

N14SD40 Média 39.61% 3.84% 0.39% 0.22%

DesvPad 14.20% 4.91% 1.35% 0.86%

Máximo 77.93% 23.63% 9.23% 6.48%

Mínimo 0.00% 0.00% 0.00% 0.00%

N14SN10 Média 0.62% 0.03% 0.00% 0.00%

DesvPad 2.44% 0.43% 0.00% 0.00%

Máximo 24.78% 8.38% 0.00% 0.00%

Mínimo 0.00% 0.00% 0.00% 0.00%

N14SN20 Média 5.61% 0.13% 0.03% 0.01%

DesvPad 9.55% 0.88% 0.32% 0.12%

Máximo 47.80% 8.78% 4.70% 2.38%

Mínimo 0.00% 0.00% 0.00% 0.00%

N14UNI Média 98.34% 37.74% 18.75% 8.35%

DesvPad 10.61% 7.24% 6.14% 5.03%

Máximo 125.07% 53.76% 33.57% 22.43%

Mínimo 60.14% 9.93% 0.00% 0.00%

Todos Média 34.48% 8.62% 3.86% 1.73%

DesvPad 36.68% 15.20% 7.97% 4.02%

Máximo 125.07% 53.76% 33.57% 22.43%

Mínimo 0.00% 0.00% 0.00% 0.00%

Tabela 5.13: ∆λ

max

(Genetico) em 20 experimentos.

Notamos nesta tabela que o custo foi maior para graus lógicos baixos e para matrizes uni-

formes. O fato de encontrar valores muito acima do limite inferior pode ter duas causas. Uma

destas causas pode ser que o limite inferior possui baixa qualidade e seus valores estão muito

abaixo do ótimo. Outra, que a heurística utilizada para encontrar as soluções não é uma boa

heurística.

5.2 Experimentos com redes de 14 nós 73

Com matrizes de ordem 6 o GA obteve o pior resultado para grau lógico 2. Fato que se

repetiu para as matrizes de 14 nós. Isto signiﬁca que o GA não funciona bem para o grau lógico

2. Podemos ver que o custo das soluções genéticas é baixo para os outros graus lógicos, exceto

para as matrizes uniformes.

Vemos na Tabela 5.13 que o GA encontrou o congestionamento ótimo para todas as matrizes

com 10% de super nós com os graus lógicos 6 e 8, porque o custo máximo encontrado nestes

dois casos é de 0,00%.

O GA encontrou excelentes resultados para os graus lógicos 4, 6 e 8 com matrizes de ordem

14 com super nós.

A distribuição dos valores mostrados na Tabela 5.13 pode ser vista na Figura 5.3 através de

gráﬁcos-caixa (boxplot’s).

Os gráﬁcos-caixa apresentados na ﬁgura possuem, normalmente, dois retângulos para cada

grau lógico. Estes retângulos representam 50% dos valores centrais da distribuição. A base do

retângulo mais baixo representa o primeiro quartil da distribuição. Seu topo também é base para

o retângulo mais alto e representa o segundo quartil. O topo do retângulo mais alto representa

o terceiro quartil.

Acima do retângulo superior existe uma linha que termina com um ×. Este × marca o

maior entre os valores que não ultrapassam o valor do terceiro quartil mais uma vez e meia do

intervalo interquartílico. Considerando Q3 o valor do terceiro quartil e Q1 o valor do primeiro

quartil, o intervalo interquartílico IQ é dado por IQ = Q3−Q1. Portanto o × superior é marcado

no maior valor que não ultrapassa Q3+ 1,5 × IQ.

Analogamente, existe uma linha abaixo do retângulo inferior que termina com um ×. Este

× marca o menor valor não inferior a Q1− 1,5 × IQ na distribuição.

Os valores acima de Q3 + 1, 5 × IQ e abaixo de Q1 − 1,5 × IQ são pontos exteriores e são

representados por círculos. Um círculo vazio representa apenas um valor naquele ponto. Um

círculo preenchido representa vários valores naquele ponto.

Na Figura 5.3, o gráﬁco que apresenta a distribuição do custo encontrado para as matrizes

com 40% de super demandas, mostra para o grau lógico 2 uma típica apresentação de valores

por gráﬁco-caixa. Já a distribuição apresentada para os graus lógicos 6 e 8 possuem apenas os

pontos exteriores superiores. Isto acontece por que todos os valores abaixo de Q3 + 1,5IQ são

zero.

O gráﬁco que apresenta a distribuição do custo encontrado para as matrizes com 10% de

5.2 Experimentos com redes de 14 nós 74

Figura 5.3: Distribuição do custo encontrado com o Método Genético.

super nós, não mostra nada para os graus lógicos 6 e 8. Isto acontece por que todos os valores

desta distribuição são zero.

5.2.3 Método Estático

A conﬁguração estática foi feita de forma similar àquela com matrizes de ordem 6. A

topologia virtual da matriz com a média das demandas de cada tipo foi usada para calcular o

5.2 Experimentos com redes de 14 nós 75

congestionamento das matrizes de tráfego em cada instante, de acordo com seu respectivo tipo.

O GA foi usado para encontrar a topologia virtual.

O gráﬁco da Figura 5.4 mostra a comparação entre o LBD, soluções genéticas e soluções

estáticas, representados respectivamente pelas legendas “solucoesLBD”, “solucoesGeneticas”

e “solucoesMatEstatica”.

Figura 5.4: Comparação entre LBD, soluções genéticas e soluções estáticas para matrizes com

30% de super demandas com restrição de grau lógico igual a 2.

Notamos nesta ﬁgura que o custo das soluções estáticas foi maior do que das soluções

genéticas.

Na Tabela 5.14 vemos que os valores da média, máximo e mínimo encontrados para solu-

ções estática também foram maiores do que os encontrados para solução genética.

Geneticas GL2 GL4 GL6 GL8

N14SD30 Média 25.16% 1.42% 0.00% 0.10%

DesvPad 13.91% 2.73% 0.00% 0.45%

Máximo 52.13% 9.50% 0.00% 2.07%

Mínimo 0.00% 0.00% 0.00% 0.00%

MatEstatica GL2 GL4 GL6 GL8

N14SD30 Média 43.39% 5.42% 2.72% 1.78%

DesvPad 12.61% 5.62% 4.13% 2.74%

Máximo 65.25% 15.80% 12.68% 9.35%

Mínimo 18.29% 0.00% 0.00% 0.00%

Tabela 5.14: ∆λ

max

(Genetico) e ∆λ

max

(MatEstatica) das matrizes utilizadas para gerar o grá-

ﬁco da Figura 5.4.

5.2 Experimentos com redes de 14 nós 76

A Tabela 5.15 mostra o custo da solução estática em 20 experimentos.

MatEstatica GL2 GL4 GL6 GL8

N14SD30 Média 46.24% 9.24% 3.00% 2.19%

DesvPad 13.56% 7.56% 4.12% 3.52%

Máximo 82.97% 33.97% 19.90% 17.11%

Mínimo 6.09% 0.00% 0.00% 0.00%

N14SD40 Média 55.53% 13.44% 3.75% 2.47%

DesvPad 15.49% 8.53% 4.28% 3.86%

Máximo 95.67% 35.87% 19.40% 23.73%

Mínimo 0.00% 0.00% 0.00% 0.00%

N14SN10 Média 3.72% 1.87% 1.27% 0.86%

DesvPad 6.22% 4.65% 2.86% 2.28%

Máximo 27.46% 33.33% 20.00% 14.29%

Mínimo 0.00% 0.00% 0.00% 0.00%

N14SN20 Média 14.39% 3.49% 2.04% 1.61%

DesvPad 11.83% 5.83% 3.69% 3.34%

Máximo 56.07% 33.33% 19.75% 16.72%

Mínimo 0.00% 0.00% 0.00% 0.00%

N14UNI Média 105.29% 43.41% 23.56% 12.10%

DesvPad 9.90% 7.02% 6.15% 5.29%

Máximo 128.54% 59.99% 35.68% 24.28%

Mínimo 68.00% 18.89% 3.09% 0.00%

Todos Média 45.03% 14.29% 6.72% 3.85%

DesvPad 37.66% 16.61% 9.51% 5.62%

Máximo 128.54% 59.99% 35.68% 24.28%

Mínimo 0.00% 0.00% 0.00% 0.00%

Geneticas GL2 GL4 GL6 GL8

Todos Média 34.48% 8.62% 3.86% 1.73%

DesvPad 36.68% 15.20% 7.97% 4.02%

Máximo 125.07% 53.76% 33.57% 22.43%

Mínimo 0.00% 0.00% 0.00% 0.00%

Tabela 5.15: ∆λ

max

(MatEstatica) em 20 experimentos.

Podemos ver que em todas as situações a solução genética obteve custos menores do que a

solução estática.

O GA mostrou-se um algoritmo relativamente rápido em relação a solução exata, além

desta última ser inviável para redes de 14 nós. Mesmo assim, não seria possível medir o tráfego

da rede, calcular uma nova topologia virtual e substituir a topologia virtual antiga pela nova

instantaneamente. Por isso, as próximas seções apresentarão experimentos que assumem um

atraso na troca de topologia virtual.

A distribuição dos valores mostrados na Tabela 5.15 pode ser vista na Figura 5.5.

Observamos neste gráﬁco que todas as distribuições possuem valores mais altos do que as

5.2 Experimentos com redes de 14 nós 77

Figura 5.5: Distribuição do custo encontrado com o Método Estático.

dos gráﬁcos que representam as distribuições encontradas pelo Método Genético.

5.2.4 Método das Matrizes Anteriores

Esta sub-seção mostra os resultados obtidos com o método das matrizes anteriores. O

método apresentado aqui seria igual ao utilizado nos experimentos com matrizes de ordem

6 se não fosse pelo fato dos experimentos com matrizes de ordem 14 utilizarem o GA em

5.2 Experimentos com redes de 14 nós 78

substituição à solução ótima.

5.2.4.1 Método da Matriz t − 3

Este método supõe que a rede precise de três unidades de tempo para se reconﬁgurar. Isto é,

a topologia virtual utilizada para calcular o congestionamento no instante t

é aquela encontrada

para a matriz de tráfego do instante t

n−3

, exceto as matrizes dos instantes t

, t

e t

que utilizam

a topologia virtual encontrada para a matriz do instante t

A Figura 5.6 apresenta uma comparação entre o LBD, as soluções genéticas, o método

estático e o método da matriz t − 3, referenciados na legenda do gráﬁco por “solucoesLBD”,

“solucoesGeneticas”, “solucoesMatEstatica” e “solucoesMatAnterior3”, respectivamente.

Figura 5.6: Comparação entre LBD, soluções genéticas, método estático e Método da Matriz

t − 3 para matrizes com 30% de super demandas com restrição de grau lógico 2.

Podemos ver que o Método da Matriz t − 3 neste caso teve custo menor do que o Método

Estático, pois o congestionamento acumulado foi menor. Isto é conﬁrmado pela Tabela 5.16.

Esta tabela também nos mostra que este método só foi melhor do que o Método Estático

para o grau lógico 2. Os demais graus lógicos obtiveram custos maiores do que o Método

Estático.

A Tabela 5.17 mostra o custo obtido por este método em 20 experimentos, separados por

tipo de matriz e grau lógico.

5.2 Experimentos com redes de 14 nós 79

MatAnterior3 GL2 GL4 GL6 GL8

N14SD30 Média 39.56% 10.50% 3.28% 2.02%

DesvPad 16.31% 9.44% 4.35% 3.24%

Máximo 75.18% 30.85% 14.02% 10.91%

Mínimo 6.89% 0.00% 0.00% 0.00%

MatEstatica GL2 GL4 GL6 GL8

N14SD30 Média 43.39% 5.42% 2.72% 1.78%

DesvPad 12.61% 5.62% 4.13% 2.74%

Máximo 65.25% 15.80% 12.68% 9.35%

Mínimo 18.29% 0.00% 0.00% 0.00%

Tabela 5.16: ∆λ

max

(MatAnterior3) e ∆λ

max

(MatEstatica) das matrizes utilizadas para gerar o

gráﬁco da Figura 5.6.

MatAnterior3 GL2 GL4 GL6 GL8

N14SD30 Média 45.01% 11.31% 5.05% 2.87%

DesvPad 18.18% 9.95% 6.16% 4.28%

Máximo 105.20% 50.44% 41.24% 20.44%

Mínimo 0.00% 0.00% 0.00% 0.00%

N14SD40 Média 53.59% 12.98% 5.55% 3.22%

DesvPad 16.93% 8.95% 6.03% 4.63%

Máximo 99.60% 39.57% 29.92% 33.33%

Mínimo 1.49% 0.00% 0.00% 0.00%

N14SN10 Média 10.11% 1.80% 1.01% 0.73%

DesvPad 14.25% 3.93% 2.73% 2.36%

Máximo 100.58% 33.33% 20.00% 14.29%

Mínimo 0.00% 0.00% 0.00% 0.00%

N14SN20 Média 15.82% 3.90% 1.73% 1.51%

DesvPad 16.43% 6.12% 4.20% 3.83%

Máximo 78.39% 34.96% 50.00% 33.33%

Mínimo 0.00% 0.00% 0.00% 0.00%

N14UNI Média 103.90% 42.07% 22.47% 11.38%

DesvPad 11.15% 7.67% 6.50% 5.52%

Máximo 133.30% 62.04% 39.32% 28.35%

Mínimo 66.40% 17.18% 1.03% 0.00%

Todos Média 45.69% 14.41% 7.16% 3.94%

DesvPad 36.94% 16.35% 9.49% 5.72%

Máximo 133.30% 62.04% 50.00% 33.33%

Mínimo 0.00% 0.00% 0.00% 0.00%

MatEstatica GL2 GL4 GL6 GL8

Todos Média 45.03% 14.29% 6.72% 3.85%

DesvPad 37.66% 16.61% 9.51% 5.62%

Máximo 128.54% 59.99% 35.68% 24.28%

Mínimo 0.00% 0.00% 0.00% 0.00%

Tabela 5.17: ∆λ

max

(MatAnterior3) em 20 experimentos.

5.2 Experimentos com redes de 14 nós 80

Nesta tabela podemos ver que na média geral, independente de tipo de matriz, o método da

matriz t − 3 obteve custo maior do que o método estático. Este resultado reforça aquele obtido

com matrizes de ordem 6, em que este método se mostrou inadequado para substituir o método

estático. Vale lembrar que o método estático apresentado neste trabalho não é um método que

possa ser aplicado em uma rede real.

A distribuição dos valores mostrados na Tabela 5.17 pode ser vista na Figura 5.7.

Figura 5.7: Distribuição do custo encontrado com o Método da Matriz t-3.

Os gráﬁcos desta ﬁgura mostram distribuições maiores do que as encontradas pelo Método

5.2 Experimentos com redes de 14 nós 81

Genético e menores do que as encontradas pelo Método Estático.

5.2.4.2 Método da Matriz t − 2

Este método supõe que a rede precise de duas unidades de tempo para se reconﬁgurar.

Isto é, a topologia virtual utilizada para calcular o congestionamento no instante t

é aquela

encontrada para a matriz de tráfego do instante t

n−2

, exceto as matrizes dos instantes t

e t

que

utilizam a topologia virtual encontrada para a matriz do instante t

A Figura 5.8 mostra uma comparação entre o LBD, as soluções genéticas, o método es-

tático e o método da matriz t − 2, referenciados na legenda do gráﬁco por “solucoesLBD”,

“solucoesGeneticas”, “solucoesMatEstatica” e “solucoesMatAnterior2”, respectivamente.

Figura 5.8: Comparação entre LBD, soluções genéticas, soluções estáticas e soluções da Matriz

t − 2 para matrizes com 30% de super demandas com restrição de grau lógico igual a 2.

Neste caso o Método da Matriz t − 2 teve custo menor do que o Método Estático.

A Tabela 5.18 o custo deste método com as matrizes utilizadas para gerar o gráﬁco da ﬁgura

5.8 para os graus lógicos 2, 4, 6 e 8.

Podemos ver que o custo deste método, neste caso, só foi maior do que o método estático

para o grau lógico 4.

A Tabela 5.19 mostra os custos deste método separados por grau lógico, tipo de matriz,

além de mostrar o custo médio sem separação por tipo de matriz.

5.2 Experimentos com redes de 14 nós 82

MatAnterior2 GL2 GL4 GL6 GL8

N14SD30 Média 33.74% 7.26% 2.45% 1.12%

DesvPad 15.61% 8.01% 4.54% 2.44%

Máximo 61.81% 24.21% 18.11% 10.09%

Mínimo 1.17% 0.00% 0.00% 0.00%

MatEstatica GL2 GL4 GL6 GL8

N14SD30 Média 43.39% 5.42% 2.72% 1.78%

DesvPad 12.61% 5.62% 4.13% 2.74%

Máximo 65.25% 15.80% 12.68% 9.35%

Mínimo 18.29% 0.00% 0.00% 0.00%

Tabela 5.18: ∆λ

max

(MatAnterior2) e ∆λ

max

(MatEstatica) das matrizes utilizadas para gerar o

gráﬁco da Figura 5.8.

MatAnterior2 GL2 GL4 GL6 GL8

N14SD30 Média 38.37% 7.99% 3.85% 2.22%

DesvPad 16.46% 8.19% 5.31% 3.74%

Máximo 84.51% 40.90% 30.38% 18.09%

Mínimo 0.00% 0.00% 0.00% 0.00%

N14SD40 Média 47.94% 9.67% 4.07% 2.38%

DesvPad 15.68% 7.62% 4.97% 3.85%

Máximo 93.04% 34.31% 27.17% 33.33%

Mínimo 0.00% 0.00% 0.00% 0.00%

N14SN10 Média 7.66% 1.16% 0.72% 0.62%

DesvPad 11.75% 3.22% 2.23% 2.09%

Máximo 75.85% 26.44% 20.00% 14.29%

Mínimo 0.00% 0.00% 0.00% 0.00%

N14SN20 Média 12.71% 3.05% 1.29% 1.11%

DesvPad 14.40% 5.50% 3.18% 3.09%

Máximo 72.31% 33.33% 20.00% 27.34%

Mínimo 0.00% 0.00% 0.00% 0.00%

N14UNI Média 101.54% 40.24% 20.82% 10.11%

DesvPad 10.98% 7.55% 6.41% 5.31%

Máximo 128.42% 59.13% 36.58% 23.59%

Mínimo 61.57% 14.33% 0.00% 0.00%

Todos Média 41.64% 12.42% 6.15% 3.29%

DesvPad 36.37% 15.74% 8.80% 5.12%

Máximo 128.42% 59.13% 36.58% 33.33%

Mínimo 0.00% 0.00% 0.00% 0.00%

MatEstatica GL2 GL4 GL6 GL8

Todos Média 45.03% 14.29% 6.72% 3.85%

DesvPad 37.66% 16.61% 9.51% 5.62%

Máximo 128.54% 59.99% 35.68% 24.28%

Mínimo 0.00% 0.00% 0.00% 0.00%

Tabela 5.19: ∆λ

max

(MatAnterior2) em 20 experimentos.

5.2 Experimentos com redes de 14 nós 83

Apesar dos custos no método da matriz t −2 serem menores do que no método estático para

todos os graus lógicos, a diferença entre os dois métodos é muito pequena.

A distribuição dos valores mostrados na Tabela 5.19 pode ser vista na Figura 5.9.

Figura 5.9: Distribuição do custo encontrado com o Método da Matriz t-2.

Os gráﬁcos desta ﬁgura mostram distribuições maiores do que as encontradas pelo Método

Genético e menores do que as encontradas pelo Método da Matriz t − 3.

5.2 Experimentos com redes de 14 nós 84

5.2.4.3 Método da Matriz t − 1

Este método supõe que a rede precise de uma unidade de tempo para se reconﬁgurar. Isto é,

a topologia virtual utilizada para calcular o congestionamento no instante t

é aquela encontrada

para a matriz de tráfego do instante t

n−1

, exceto a matriz do instante t

que utiliza sua própria

topologia virtual já que não possui nenhuma anterior.

A Figura 5.10 apresenta uma comparação entre o LBD, as soluções genéticas, o método

estático e o método da matriz t − 1, referenciados na legenda do gráﬁco por “solucoesLBD”,

“solucoesGeneticas”, “solucoesMatEstatica” e “solucoesMatAnterior1”, respectivamente.

Figura 5.10: Comparação entre LBD, soluções genéticas, soluções estáticas e soluções da Ma-

triz t − 1 para matrizes com 30% de super demandas com restrição de grau lógico igual a 2.

MatAnterior1 GL2 GL4 GL6 GL8

N14SD30 Média 28.38% 4.32% 1.67% 0.99%

DesvPad 15.29% 5.03% 2.97% 2.39%

Máximo 55.75% 14.51% 9.53% 8.28%

Mínimo 0.00% 0.00% 0.00% 0.00%

MatEstatica GL2 GL4 GL6 GL8

N14SD30 Média 43.39% 5.42% 2.72% 1.78%

DesvPad 12.61% 5.62% 4.13% 2.74%

Máximo 65.25% 15.80% 12.68% 9.35%

Mínimo 18.29% 0.00% 0.00% 0.00%

Tabela 5.20: ∆λ

max

(MatAnterior1) e ∆λ

max

(MatEstatica) das matrizes utilizadas para gerar o

gráﬁco da Figura 5.10.

5.2 Experimentos com redes de 14 nós 85

MatAnterior1 GL2 GL4 GL6 GL8

N14SD30 Média 32.12% 4.48% 2.08% 1.23%

DesvPad 14.70% 5.02% 3.21% 2.43%

Máximo 70.33% 23.93% 16.52% 14.64%

Mínimo 0.00% 0.00% 0.00% 0.00%

N14SD40 Média 42.58% 6.33% 2.16% 1.38%

DesvPad 14.68% 5.75% 3.12% 2.34%

Máximo 81.32% 27.39% 23.29% 14.77%

Mínimo 0.00% 0.00% 0.00% 0.00%

N14SN10 Média 4.11% 0.60% 0.38% 0.31%

DesvPad 7.11% 1.99% 1.58% 1.39%

Máximo 29.55% 15.55% 12.51% 14.29%

Mínimo 0.00% 0.00% 0.00% 0.00%

N14SN20 Média 8.92% 1.53% 0.76% 0.54%

DesvPad 10.77% 3.84% 2.15% 1.83%

Máximo 47.60% 28.38% 18.99% 14.29%

Mínimo 0.00% 0.00% 0.00% 0.00%

N14UNI Média 99.45% 38.58% 19.42% 9.00%

DesvPad 10.77% 7.38% 6.25% 5.07%

Máximo 126.04% 55.05% 34.24% 23.92%

Mínimo 57.35% 11.08% 0.00% 0.00%

Todos Média 37.44% 10.30% 4.96% 2.49%

DesvPad 36.16% 15.18% 8.12% 4.38%

Máximo 126.04% 55.05% 34.24% 23.92%

Mínimo 0.00% 0.00% 0.00% 0.00%

MatEstatica GL2 GL4 GL6 GL8

Todos Média 45.03% 14.29% 6.72% 3.85%

DesvPad 37.66% 16.61% 9.51% 5.62%

Máximo 128.54% 59.99% 35.68% 24.28%

Mínimo 0.00% 0.00% 0.00% 0.00%

Tabela 5.21: ∆λ

max

(MatAnterior1) em 20 experimentos.

Podemos ver que o Método da Matriz t − 1, neste caso, teve custo menor do que o Método

Estático.

A Tabela 5.20 mostra os custos médios encontrados com as matrizes utilizadas para gerar o

gráﬁco da Figura 5.10 separados por grau lógico.

Esta tabela mostra um ganho signiﬁcativo deste método em relação ao método estático.

A Tabela 5.21 mostra o custo médio obtido em 20 experimentos separados por tipo de

matriz de grau lógico.

Apesar de aparentar pouco ganho na Tabela 5.21 temos que levar em conta que estas solu-

ções não estão sendo comparadas ao congestionamento ótimo, e sim, a um limite inferior.

5.2 Experimentos com redes de 14 nós 86

Na Tabela 5.22 podemos ver que os custos do Método da Matriz t − 1 estão muito mais

próximos dos custos do Método Genético, que é a melhor solução possível usando GA, do que

dos custos do Método Estático. Isto mostra que este ganho aparentemente pequeno, na verdade,

apresenta uma melhoria signiﬁcativa.

Geneticas GL2 GL4 GL6 GL8

Todos Média 34.48% 8.62% 3.86% 1.73%

DesvPad 36.68% 15.20% 7.97% 4.02%

Máximo 125.07% 53.76% 33.57% 22.43%

Mínimo 0.00% 0.00% 0.00% 0.00%

MatAnterior1 GL2 GL4 GL6 GL8

Todos Média 37.44% 10.30% 4.96% 2.49%

DesvPad 36.16% 15.18% 8.12% 4.38%

Máximo 126.04% 55.05% 34.24% 23.92%

Mínimo 0.00% 0.00% 0.00% 0.00%

MatEstatica GL2 GL4 GL6 GL8

Todos Média 45.03% 14.29% 6.72% 3.85%

DesvPad 37.66% 16.61% 9.51% 5.62%

Máximo 128.54% 59.99% 35.68% 24.28%

Mínimo 0.00% 0.00% 0.00% 0.00%

Tabela 5.22: ∆λ

max

(MatAnterior1), ∆λ

max

(MatAnterior1) e ∆λ

max

(MatEstatica) em 20 expe-

rimentos.

A distribuição dos valores mostrados na Tabela 5.21 pode ser vista na Figura 5.11.

Os gráﬁcos desta ﬁgura mostram distribuições maiores do que as encontradas pelo Método

Genético e menores do que as encontradas pelo Método da Matriz t − 2.

Se o custo do Algoritmo Genético para grau lógico 2 é de 34,48% e o custo do Método

Estático para o mesmo grau lógico é de 45,03%, o custo do Método Estático é 30,60% maior do

que o custo do Algoritmo Genético. Por outro lado, o custo do Método da Matriz t − 1 é 8,58%

maior do que o custo do Método Genético.

Na Tabela 5.23 podemos ver esta comparação para os graus lógicos 2, 4, 6 e 8.

Custo Médio GL 2 GL 4 GL 6 GL 8

Método Estático 30.60% 65.78% 74.09% 122.54%

Método da Matriz t − 1 8.58% 19.49% 28.50% 43.93%

Tabela 5.23: Proporção do custo médio do Método Estático e Método da Matriz t −1 em relação

ao custo do Método Genético.

A proporção do custo médio deste dois métodos aumenta com o grau lógico, mas a propor-

ção do Método da Matriz t − 1 é sempre menor do que a do Método Estático. A diminuição do

custo foi em média 65%.

5.2 Experimentos com redes de 14 nós 87

Figura 5.11: Distribuição do custo encontrado com o Método da Matriz t-1.

Podemos concluir, portanto, que se for possível medir o tráfego da rede, calcular a nova

topologia virtual e trocar a topologia virtual antiga pela nova em uma unidade de tempo, o

Método da Matriz t − 1 é um método vantajoso em relação ao Método Estático.

6 Conclusões e trabalhos futuros

6.1 Conclusões

Com base nos resultados dos experimentos apresentados nesta dissertação, podemos con-

cluir que a re-optimização da topologia virtual de uma rede óptica pode melhorar o desempenho

da rede, assim como, permitir a utilização de seus recursos de forma mais eﬁciente.

A utilização de heurísticas e meta-heurísticas é inevitável quando se trata de problemas

complexos como o VTD. Mesmo para redes pequenas, como as redes de 6 nós, meta-heurísticas,

como o Algoritmo Genético utilizado para gerar os resultados aqui apresentados, podem encon-

trar soluções de boa qualidade com um custo computacional aceitável.

Os algoritmos utilizados para gerar os experimentos desta dissertação são ferramentas ca-

pazes de contribuir para o estudo empírico em redes ópticas. Com eles é possível avaliar novos

modelos de otimização, testar a robustez de uma nova heurística ou uma nova implementação de

uma meta-heurística conhecida, assim como, veriﬁcar a sensibilidade de modelos e heurísticas

em relação à variação de tráfego.

A biblioteca EGPTEL, que contém tais algoritmos, foi implementada de forma paramétrica,

isto é, experimentos apresentados aqui, como os métodos da matriz t −k e média das k matrizes

anteriores, podem ser refeitos com qualquer valor de k ∀ k ≥ 0.

Vale lembrar que a literatura não apresenta trabalhos que utilizaram uma quantidade tão

grande de matrizes para gerar resultados como os mostrados neste trabalho. Normalmente os

trabalho publicados nesta linha de pesquisa apresentam resultados obtidos por uma ou duas

matrizes de tráfego.

Devido a enorme quantidade de matrizes de tráfego que utilizamos neste trabalho, foi pos-

sível veriﬁcar a inﬂuência da distribuição das demandas na otimização da rede e na qualidade

dos limites inferiores obtidos para cada tipo de rede. O método utilizado para encontrar limites

inferiores neste trabalho obtêm excelentes valores para matrizes com super nós. Os piores resul-

6.2 Trabalhos Futuros 89

tados são obtidos para as matrizes uniformes, onde os limites inferiores são muito mais baixos

do que o valor ótimo. Não existia até a conclusão deste trabalho, um estudo que relacionasse a

distribuição das demandas de uma rede óptica com a qualidade de sua otimização.

Além disso, descobrimos que a distribuição das demandas inﬂuencia também na qualidade

da otimização dinâmica em relação a conﬁguração estática de uma rede óptica.

A utilização do AG mostrou-se promissora. Além obter resultados de excelente qualidade,

seu custo computacional foi muito menor do que o algoritmo exato. Um exemplo disso é que

utilizando um computador com um processador de 1,8 GHz e 1 GB de memória principal, os

experimentos com redes de 6 nós demoravam até mais de 30 minutos, enquanto com o AG e

resultado era obtido, em média, em 5 segundos.

6.2 Trabalhos Futuros

Para dar continuidade a este estudo pretendemos fazer novos experimentos com diferentes

variações de tráfego, mais tipos de matrizes, matrizes maiores, maior quantidade de matrizes por

experimento, maior quantidade de matrizes interpoladas entre as matrizes principais, e também,

outros modelos de optimização.

Após a análise dos resultados obtidos pelo algoritmo Genético, acreditamos que trabalhos

que utilizem meta-heurísticas são promissores. Por isso, nos próximos estudos, procuraremos

aﬁnar ainda mais o GA utilizado neste trabalho, assim como, utilizar outras meta-heurísticas.

Outro estudo importante que será feito é a utilização de matrizes de tráfego com dados

retirados de redes reais e com intervalo de tempo deﬁnido. Desta forma, teremos resultados

que nos permitirão avaliar a qualidade dos estudos feitos com simulação em relação aos estudos

feitos utilizando dados reais.

Referências Bibliográﬁcas

[1] LABOURDETTE, J.-F. et al. Path Routing in Mesh Optical Networks. [S.l.]: John Wiley &

Sons, 2006. ISBN 0470032987.

[2] GUIZANI, M.; BATTOU, A. Optical Switching/Networking and Computing for Multimedia

Systems. [S.l.]: CRC Press, 2002.

[3] MUKHERJEE, B. Optical communication networks. [S.l.]: McGraw-Hill New York, 1997.

[4] COCHRANE, P. Optical Network Technology. [S.l.]: Chapman & Hall, 1995.

[5] SIVALINGAM, K.; SUBRAMANIAM, S. Optical WDM Networks: Principles and Prac-

tice. [S.l.]: Kluwer Academic Publishers, 2000.

[6] RAMASWAMI, R.; SIVARAJAN, K. Optical Networks: A Practical Perspective. [S.l.]:

Morgan Kaufmann, 2002.

[7] WALI, Z.; ELSAYED, K.; HASSAN, A. Static RWA in All-Optical Network under Multi-

ﬁber, Multiple Requests Assumption. Computer Engineering and Systems, The 2006 Inter-

national Conference on, p. 172–177, 2006.

[8] ALMEIDA, R. T. R. Projeto de Topologias Virtuais para Redes Ópticas Multiserviço. Tese

(Doutorado) — UFES, 2005.

[9] ASSIS, K.; WALDMAN, H.; CALMON, L. de C. Virtual topology design for a hypothetical

optical network. v. 4289, p. 65–73, 2001.

[10] RAMASWAMI, R. et al. Design of logical topologies for wavelength-routed optical

networks. Selected Areas in Communications, IEEE Journal on, v. 14, n. 5, p. 840–851,

1996.

[11] DUTTA, R.; ROUSKAS, G. A survey of virtual topology design algorithms for wave-

length routed optical networks. Optical Networks Magazine, v. 1, n. 1, p. 73–89, 2000.

[12] YANG, X.; RAMAMURTHY, B. Dynamic routing in translucent WDM optical networks:

the intradomain case. Lightwave Technology, Journal of, v. 23, n. 3, p. 955–971, 2005.

[13] HUIBAN, G.; MATEUS, G. A MILP model for the reconﬁguration problem in multi-ﬁber

WDM networks. SBRC Simpósio Brasileiro de Redes de Computadores, May, 2005.

[14] HE, L.; MORT, N. Hybrid Genetic Algorithms for Telecommunications Network Back-Up

Routeing. BT Technology Journal, Springer, v. 18, n. 4, p. 42–50, 2000.

[15] BIENSTOCK, D.; GÜNLÜK, O. Computational experience with a difﬁcult mixed integer

multicommodity ﬂow problem. Mathematical Programming, Springer, v. 68, n. 1, p. 213–

237, 1995.

Referências Bibliográﬁcas 91

[16] YENER, B.; BOULT, T. A study of upper and lower bounds for minimum congestion

routing inlightwave networks. INFOCOM’94. Networking for Global Communications. 13th

Proceedings IEEE, p. 138–147, 1994.

[17] ALMEIDA, R. et al. Design of virtual topologies for large optical networks through an

efﬁcient MILP formulation. Optical Switching and Networking, Elsevier, v. 3, n. 1, p. 2–10,

2006.

[18] SKORIN-KAPOV, N. A new objective criterion and rounding techniques for determining

virtual topologies in optical networks. IEEE communications letters, Institute of Electrical

and Electronics Engineers, v. 11, n. 6, p. 540–542, 2007.

[19] ZHANG, Q. et al. Evolutionary Algorithms Reﬁning a Heuristic: A Hybrid Method for

Shared-Path Protections in WDM Networks Under SRLG Constraints. IEEE TRANSACTI-

ONS ON SYSTEMS, MAN, AND CYBERNETICS - PART B: CYBERNETICS, v. 37, n. 1, p. 1,

2007.

[20] GOLDBERG, D.; HOLLAND, J. Genetic Algorithms and Machine Learning. Machine

Learning, Springer, v. 3, n. 2, p. 95–99, 1988.

[21] KIRKPATRICK, S.; JR, C. G.; VECCHI, M. Optimization by Simulated Annealing. Bio-

logy and Computation: A Physicist’s Choice, World Scientiﬁc Pub Co Inc, 1994.

[22] GLOVER, F.; LAGUNA, M. Tabu Search. [S.l.]: Springer, 1997.

[23] WEISS, G. Aspects and applications of the random walk. [S.l.]: North-Holland New York,

1994.

[24] MAKHORIN, A. GLPK. GNU Linear Programming Kit. Free Software Foundation, Ja-

nuary, 2004.

[25] GENÇATA, A.; MUKHERJEE, B. Virtual-topology adaptation for WDM mesh networks

under dynamic trafﬁc. IEEE/ACM Transactions on Networking (TON), IEEE Press Pisca-

taway, NJ, USA, v. 11, n. 2, p. 236–247, 2003.

[26] GOLAB, W.; BOUTABA, R. Policy-driven automated reconﬁguration for performance

management in WDM optical networks. Communications Magazine, IEEE, v. 42, n. 1, p.

44–51, 2004.

[27] BOUILLET, E. et al. Lightpath re-optimization in mesh optical networks. IEEE/ACM

Transactions on Networking (TON), IEEE Press Piscataway, NJ, USA, v. 13, n. 2, p. 437–

447, 2005.

[28] HUIBAN, G.; DATTA, P. Virtual Topology Reconﬁguration Issues in Evolution of WDM

Optical Networks. Research report, v. 5711, 2005.

[29] LEE, H.; CHOI, H.; SUBRAMANIAM, S. Preserving survivability during logical topo-

logy reconﬁguration in WDM ring networks. Parallel Processing Workshops, 2002. Procee-

dings. International Conference on, p. 224–230, 2002.

[30] BUENO, L. et al. Áneis Lógicos Disjuntos para Projeto de Topologias Virtuais de Redes

Ópticas Tolerantes a Falhas. 2004.

Referências Bibliográﬁcas 92

[31] MAIOLI, C. et al. The design of hierarchical self-healing rings networks. ConfTele, 2005.

[32] ALMEIDA, R. T. R. et al. Changing paradigms on virtual topology and trafﬁc routing

optimization. ConfTele, 2005.

[33] OLIVEIRA, E. et al. Estratégias com algoritmos híbridos para projeto de redes ópticas. In:

Anais do SOBRAPO 2004: XXXVI Simpósio Brasileiro de Pesquisa Operacional. São João

Del Rei: [s.n.], 2004.

[34] LIMA, F. de O. et al. Reformulando o problema de projeto de anéis em redes ópticas.

I2TS, 2005.

[35] BUENO, L. et al. Anéis lógicos disjuntos para projeto de topologias virtuais de redes

ópticas tolerantes a falhas. MOMAG, 2004.

[36] OLIVEIRA, E. et al. A combined approach for designing topology and ﬂow congestion

minimization of optical networks. SBrT, 2005.

[37] SEGATTO, M. E. V. et al. Anéis lógicos disjuntos para projeto de topologias virtuais de

redes ópticas tolerantes a falhas. In: MOMAG04: XI Simpósio Brasileiro de Microondas e

Optoeletrônica e VI Congresso Brasileiro de Eletromagnetismo. [S.l.: s.n.], 2004. p. 22–27.

[38] SEGATTO, M. E. V. et al. Uma heurística para o projeto de topologias virtuais de redes

ópticas tolerantes a falhas. In: XII Simpósio Brasileiro de Telecomunicações. [S.l.: s.n.],

2004. p. 7–12.

[39] SEGATTO, M. et al. Hybrid approaches for the design of mesh and hierarchical ring opti-

cal networks. Proceedings of SPIE, SPIE, v. 6193, p. 61931A, 2006.

[40] SILVA, M. M. O. et al. Análise de redes ópticas em anéis hierárquicos. In: Simpósio

Brasileiro de Telecomunicações. [S.l.: s.n.], 2007.

[41] LIMA, F. O. et al. Estudo Empírico da Eﬁciência de Heurísticas na Otimização do Con-

gestionamento em Redes Ópticas. SBPO, 2007.

[42] ALMEIDA, R. T. R.; CALMON, L. C. Projeto de topologia virtual de redes ópticas com

restrições diferenciadas por classe de serviço. In: X Simpósio Brasileiro de Microondas e

Optoeletrônica (SBMO). [S.l.: s.n.], 2002. p. 620–623.

[43] ALMEIDA, R. T. R. et al. Addressing the electronic bottleneck to virtual topology de-

sign of optical networks. In: International Microwave and Optoelectronics Conference. [S.l.:

s.n.], 2003. p. 10–16.

[44] ALMEIDA, R. T. R. et al. Design of virtual topologies for large optical networks through

an efﬁcient MILP formulation. Submetido a Computer Networks/Elsevier, 2004.

[45] VOJTECH, J. et al. Dark Fibre Lighting Technologies. SEEFIRE - South-East Europe

Fibre Infrastructure for Research and Education, 2005.

[46] HART, G.; MANSOURATI, Z. The Dynamic Network: Managing Bandwidth and Con-

tent on Demand at the Optical Level. SCTE Conference on Emerging Technologies, 2004.

[47] PRATT, B. Strategies for Metro/Regional Optical Networks. CEF Conference, Prague,

2005.

Referências Bibliográﬁcas 93

[48] HOMA, J.; BALA, K. ROADM Architectures and Their Enabling WSS Technology. Com-

munications Magazine, IEEE, v. 46, n. 7, p. 150–154, 2008.

[49] ELDADA, L. ROADM architectures and technologies for agile optical networks. Proc.

SPIE, v. 6476, 2007.

[50] WOLFF, R. et al. Performance Optimization of Dynamic All-Optical Networks. Proc. of

OFC and NFOEC, 2006.

[51] RAMAMURTHY, B.; RAMAKRISHNAN, A. Virtual topology reconﬁguration of

wavelength-routed optical WDM networks. Global Telecommunications Conference, 2000.

GLOBECOM’00. IEEE, v. 2, 2000.

[52] BALDINE, I.; ROUSKAS, G. Trafﬁc adaptive WDM networks: a study of reconﬁguration

issues. Lightwave Technology, Journal of, v. 19, n. 4, p. 433–455, 2001.

[53] BANERJEE, D.; MUKHERJEE, B. Wavelength-routed optical networks: linear formula-

tion, resource budgeting tradeoffs, and a reconﬁguration study. IEEE/ACM Transactions on

Networking (TON), ACM Press New York, NY, USA, v. 8, n. 5, p. 598–607, 2000.

[54] YANG, X.; RAMAMURTHY, B. Dynamic routing in translucent WDM optical networks.

Communications, 2002. ICC 2002. IEEE International Conference on, v. 5, 2002.

[55] BASCH, E. et al. Architectural tradeoffs for reconﬁgurable dense wavelength division

multiplexing systems. IEEE J. Sel. Top. Quantum Electron, v. 12, p. 615–626, 2006.

[56] CHARALAMBOUS, P. et al. A national mesh network using optical cross-connect swit-

ches. Optical Fiber Communications Conference, 2003. OFC 2003, p. 789–790, 2003.

[57] NGO, H.; PAN, D.; YANG, Y. Optical switching networks with minimum number of

limited range wavelength converters. INFOCOM 2005. 24th Annual Joint Conference of the

IEEE Computer and Communications Societies. Proceedings IEEE, v. 2, 2005.

[58] CORMEN, T. et al. Algoritmos: Teoria e Prática. Editora Campus, 2002.

[59] BAZARAA, M.; JARVIS, J.; SHERALI, H. Linear programming and network ﬂows.

[S.l.]: John Wiley & Sons, Inc. New York, NY, USA, 1990.

[60] GOLDBARG, M.; LUNA, H. Otimização Combinatória e Programação Linear. Editora

CAMPUS, 2000.

[61] SIERKSMA, G. Linear and Integer Programming: Theory and Practice. [S.l.]: CRC

Press, 2002.

[62] AHUJA, R.; MAGNANTI, T.; ORLIN, J. Network ﬂows: theory, algorithms, and appli-

cations. [S.l.]: Prentice Hall, 1993.

[63] MIYAO, Y.; SAITO, H. Optimal design and evaluation of survivable WDM transport

networks. Selected Areas in Communications, IEEE Journal on, v. 16, n. 7, p. 1190–1198,

1998.

[64] GROSSO, A. et al. Logical topologies design over WDM wavelength routed networksro-

bust to trafﬁc uncertainties. Communications Letters, IEEE, v. 5, n. 4, p. 172–174, 2001.

Referências Bibliográﬁcas 94

[65] SABELLA, R. et al. A multilayer solution for path provisioning in new-generation opti-

cal/MPLS networks. Lightwave Technology, Journal of, v. 21, n. 5, p. 1141–1155, 2003.

[66] HUANG, H.; COPELAND, J. Optical networks with hybrid routing. Selected Areas in

Communications, IEEE Journal on, v. 21, n. 7, p. 1063–1070, 2003.

[67] GINSBERG, M. Essentials of artiﬁcial intelligence. [S.l.]: Morgan Kaufmann Publishers

Inc. San Francisco, CA, USA, 1994.

[68] REZENDE, S. et al. Sistemas Inteligentes: Fundamentos e Aplicações. Publicado pela

Editora Manole LTDA, São Paulo, Brasil, 2002.

[69] DARWIN, C.; DARWIN, C. The Origin of Species by Means of Natural Selection. [S.l.]:

Adamant Media Corporation, 2001.

[70] HOLLAND, J. Adaptation in natural and artiﬁcial systems. [S.l.]: University of Michigan

Press Ann Arbor, 1975.

[71] GEN, M.; CHENG, R. Genetic Algorithms and Engineering Optimization. [S.l.]: Wiley-

Interscience, 1999.

[72] FERNANDES, G. C. Algoritmos Genéticos aplicados ao Projeto de Redes de Transporte

de Dados com Roteamento de Tráfego Orientado a Circuitos Lógicos. [S.l.], 2008.

[73] JONG, K. D. Adaptive System Design: A Genetic Approach. IEEE Transactions on Sys-

tems, Man, and Cybernetics, v. 10, n. 9, p. 566–574, 1980.

ANEXO A -- Modelo MILP em Linguagem

MathProg

/* Formulação do Modelo Aggregate MILP [Ramaswami, 96]

Descrição do modelo em MathProg por Fábio Lima ([email protected]). */

#############################################################

######################### PARÂMETROS ######################

#############################################################

# 1 - Numero de nós da rede

param N, integer, > 0;

# 2 - Conjunto de indices

set I := 1..N;

# 3 - Grau lógico de saida e entrada dos nós

param graulog ’Grau logico’ , integer, > 0;

# 4 - Matriz de Trafego

param mattraf{s in I, d in I};

# 5 - Somas do tráfego partindo de cada nó

param hs{s in I} := sum{d in I: d!=s} mattraf[s,d];

#############################################################

########################### VARIÁVEIS #######################

#############################################################

# 1 - Matriz da topologia virtual

var B ’topologia’ {i in I, j in I}, binary >=0 <=1;

# 2 - Parcela de tráfego vindo de "s" passando pelo enlace (i,j)

var h{ i in I, j in I, s in I: i!=j and j!=s} >= 0;

# 3 - trafego transportado atraves do caminho optico que interliga os nós (i,j)

var H{i in I, j in I } >= 0;

# 4 - Congestionamento Máximo

var Hmax >=0;

Anexo A -- Modelo MILP em Linguagem MathProg 96

#############################################################

########################## RESTRIÇÕES ######################

#############################################################

# 1 - Restriçao de limitaçao de ﬂuxo com plano de corte

s.t. limit{i in I, j in I}: Hmax >= H[i,j];

# 2 - Restriçao de limitaçao de ﬂuxo tipo 2

s.t. limit2{i in I, j in I, s in I: i!=j and j!=s}: h[i,j,s] <= (B[i,j] * hs[s]);

# 3 - Restriçao de conservaçao de trafego tipo 1

s.t. conserv1{i in I, j in I: i!=j}: H[i,j] = sum{s in I: j!=s} h[i,j,s];

# 4 - Restriçao de conservaçao de trafego tipo 2

s.t. conserv2{i in I, s in I}: sum{j in I: i!=j and j!=s} h[i,j,s] - sum{j in I: i!=j and i!=s} h[j,i,s]

= if (s!=i) then -mattraf[s,i] else hs[s];

# 5 - Restriçao de grau logico de entrada

s.t. grau_in ’grau logico de entrada’ {j in I}: sum{i in I: i!=j} B[i,j] <= graulog;

# 6 - Restriçao de grau logico de saida

s.t. grau_out ’grau logico de saida’ {i in I}: sum{j in I: i!=j} B[i,j] <= graulog;

#############################################################

###################### FUNÇÃO OBJETIVO ####################

#############################################################

minimize congestionamento: Hmax;

solve;

end;

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 