Download PDF
ads:
LEANDRO COLOMBI RESENDO
CONTRIBUIC¸
˜
OES PARA O PROJETO DE
GROOMING DE TR
´
AFEGO SOBRE REDES
´
OPTICAS WDM
Tese apresentada ao Programa de os-Gradua¸ao
em Engenharia El´etrica do Centro Tecnol´ogico da
Universidade Federal do Esp´ırito Santo, como re-
quisito parcial para obten¸ao do Grau de Doutor
em Engenharia El´etrica, na ´area de concentra¸ao em
Automa¸ao.
Orientador: Prof. Dr. Mois´es Renato Nunes Ribeiro
Co-orientador: Prof. Dr. Jo˜ao Jos´e de Oliveira Pires
Vit´oria
Outubro 2008
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
Dados Internacionais de Catalogação-na-publicação (CIP)
(Biblioteca Central da Universidade Federal do Espírito Santo, ES, Brasil)
Resendo, Leandro Colombi, 1980-
R433c Contribuições para o projeto de grooming de tráfego sobre
redes ópticas WDM / Leandro Colombi Resendo. – 2008.
145 f. : il.
Orientador: Moisés Renato Nunes Ribeiro.
Co-Orientador: João José de Oliveira Pires.
Tese (doutorado) – Universidade Federal do Espírito Santo,
Centro Tecnológico.
1. Grooming de tráfego. 2. WDM (Telecomunicação). 3.
Programação linear. 4. Programação inteira. 5. Programação
heurística. I. Ribeiro, Moisés Renato Nunes. II. Pires, João José de
Oliveira. III. Universidade Federal do Espírito Santo. Centro
Tecnológico. IV. Título.
CDU: 621.3
ads:
LEANDRO COLOMBI RESENDO
CONTRIBUIC¸
˜
OES PARA O PROJETO DE GROOMING DE
TR
´
AFEGO SOBRE REDES
´
OPTICAS WDM
Tese submetida ao Programa de os-Gradua¸ao em Engenharia El´etrica da Univer-
sidade Federal do Esp´ırito Santo como requisito parcial para a obten¸ao do grau de
Doutor em Engenharia El´etrica, na ´area de concentra¸ao Automa¸ao.
Aprovada em 10 de outubro de 2008
COMISS
˜
AO EXAMINADORA
Prof. Dr. Mois´es Renato Nunes Ribeiro
Universidade Federal do Esp´ırito Santo
Orientador
Prof. Dr. Jo˜ao Jos´e de Oliveira Pires
Instituto Superior T´ecnico de Lisboa
Co-orientador
Prof. Dr. Geraldo Robson Mateus
Universidade Federal de Minas Gerais
Prof. Dr. Renato Tannure Rotta de Almeida
Centro Federal de Educa¸ao Tecnol´ogica do Esp´ırito Santo
Prof. Dr. Anilton Salles Garcia
Universidade Federal do Esp´ırito Santo
Prof. Dr. Elias Silva de Oliveira
Universidade Federal do Esp´ırito Santo
iv
Aos meus pais Cassemiro e Ana
v
Agradecimentos
Gostaria de agradecer a todos que, direta ou indiretamente, contribu´ıram para
que este trabalho se realizasse. Em especial, agrade¸co:
Em mem´oria do Prof. Luiz de Calazans Calmon, que me concedeu a oportu-
nidade de iniciar este trabalho.
Ao Prof. Mois´es Renato Nunes Ribeiro, e orientador, pela amizade e dedica¸ao
ao fundamentais para a evolu¸ao e conclus˜ao dessa tese.
Ao Prof. Jo˜ao Jos´e de Oliveira Pires, e co-orientador, pelas sugest˜oes que vieram
enriquecer este trabalho.
Ao CNPq pelo apoio financeiro atraes da bolsa de doutorado, indispens´avel `a
realiza¸ao deste projeto.
`
A minha esposa Rosi, pela inacredit´avel paciˆencia contribuindo para me passar
tranq¨uilidade nos momentos de maior dificuldade.
Aos amigos do Labtel, com quem compartilhei de tantas horas de trabalho.
A todos os demais amigos e parentes que muito contribu´ıram com momentos de
alegria.
vi
Resumo
O Problema de Grooming de Tafego (Traffic Grooming Problem - TGP) trata
da combina¸ao eficiente de demandas de baixa velocidade em canais de alta veloci-
dade. Com o objetivo de melhorar a utiliza¸ao da capacidade da rede, o TGP ´e
frequentemente estudado com m´etodos de otimiza¸ao usando como fun¸ao objetivo
a minimiza¸ao do n´umero de transceptores eletro-´opticos. Por´em, como o TGP per-
tence `a classe de problemas NP-Completo, solu¸oes ´otimas com um pequeno tempo
computacional ao poss´ıveis apenas para redes pequenas (por exemplo, 6 os). Neste
trabalho s˜ao propostos novos modelos de Programa¸ao Linear Inteira (Integer Lin-
ear Programming - ILP), uma heur´ıstica e uma solu¸ao h´ıbrida para o TGP em redes
transl´ucidas de edio porte (aproximadamente 12 os). Inicialmente, ao propos-
tos dois modelos ILP para o TGP, um baseado em formula¸ao n´o-enlace e outro em
enlace-caminho, de forma que seus resultados foram comparados e usados como base
para modelos mais complexos. No m´etodo h´ıbrido ´e usada uma heur´ıstica para se-
lecionar os caminhos ´opticos (i.e., a topologia virtual) e um modelo ILP para rotear
de maneira eficiente as demandas de tr´afego sobre as topologias f´ısica e virtual.
A aplica¸ao desse etodo permitiu, primeiramente, a quantifica¸ao dos benef´ıcios
dos caminhos ´opticos transparentes, em termos da redu¸ao do n´umero de transcep-
tores. Al´em disso, a diminui¸ao do processamento eletrˆonico do tr´afego de trˆansito
tamb´em foi analisada. Para redes maiores, a fase ILP no etodo h´ıbrido ainda con-
tinua sendo um gargalo para as solu¸oes ´otimas, sendo assim necess´arias solu¸oes
totalmente heur´ısticas. Este trabalho mostra que solu¸oes eficientes podem ser en-
contradas usando etodos heur´ısticos simples e apidos, onde ao foi necess´ario o
aumento do custo computacional para o ajuste de parˆametros complexos relaciona-
dos `a heur´ıstica. Finalmente ´e proposta uma integra¸ao do TGP com sobrevivˆencia.
Neste trabalho ao propostos modelos ILP para formula¸ao de um etodo itera-
tivo capaz de oferecer uma prote¸ao incremental em uma rede em malha com a
minimiza¸ao do n´umero de transceptores. Al´em disso, s˜ao estudados dois m´etodos
para a prote¸ao da interconex˜ao de redes multi-anel com dois n´os de interconex˜ao,
Anel Virtual e Drop&Continue. Para essa investiga¸ao os resultados num´ericos in-
cluem o grooming de tr´afego para diferentes cen´arios como, configura¸oes opaca vs.
transl´ucida e crescimentos de tr´afego inter-anel vs. intra-anel.
vii
Abstract
The Traffic Grooming Problem (TGP) consists in how to arrange low-bandwidth
connection requests into high-capacity lightpaths efficiently. TGP solution aims
at improving network capacity utilization. The minimal number optoelectronic
transceivers that enable accommodating traffic demands is often used as the objec-
tive function for solving TGP. However, TGP belongs to a class of NP-hard problems
and optimal solutions are only possible to be found within feasible processing time
for small networks (e.g., 6 nodes). This work proposes novel Integer Linear Pro-
gramming (ILP) models, heuristic and a hybrid solution to TGP for medium-sized
(i.e., around 12 nodes) translucent networks. Initially, ILP models using node-link
and link-path paradigms are proposed and their solutions are compared. These
models lay the foundations for more complex models addressing issues on network
design. A hybrid method is then proposed. It makes use of a heuristic for selecting
lightpaths (i.e., the virtual topology) and an ILP model to route the traffic demands
over both physical and virtual topologies efficiently. The practical implications of
such approach is that it allows, for the first time, the quantification of benefits of
transparent lightpaths in terms of transceiver count reduction. Moreover, the miti-
gation of transit traffic processing in the electronic layer is also analyzed. For large
networks the ILP phase in the hybrid approach again becomes the bottleneck for
optimal network design and a fully heuristic solution is necessary. This work shows
that efficient solutions can be found through a simple and fast tool for network design
without the need of complex parameter tuning, as comparisons with results obtained
from solving the hybrid model. Finally, the integration of TGP with survivability
is proposed. This work puts forward ILP models for an iterative method using
two ILP models to design networks with incremental protection with minimal num-
ber of transceivers in mesh networks. Dual Node Interconnected (DNI) multi-ring
topologies are studied under inter-ring traffic protection using Virtual Ring (VR)
and Drop and Continue (D&C) strategies. Results compare optimal solutions that
take into account traffic grooming for different network scenarios including opaque
vs. translucent configurations and inter vs. intra traffic growth.
Sum´ario
1 Introdu¸ao 1
1.1 Motivao e Justificativa . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Objetivos Gerais . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Objetivos Espec´ıficos . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Contribui¸oes e Organiza¸ao do Texto . . . . . . . . . . . . . . . . . 6
1.4 Trabalhos Publicados . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Revis˜ao da Literatura 10
2.1 Redes
´
Opticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.1 Principais Camadas Clientes das Redes
´
Opticas . . . . . . . . 13
2.1.2 Prote¸ao e Restaura¸ao . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Projeto de Topologia Virtual . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Roteamento e Aloca¸ao de Comprimento de Onda . . . . . . . . . . . 18
2.4 Problema de Grooming de Tafego . . . . . . . . . . . . . . . . . . . . 19
2.4.1 Arquiteturas de n´os usadas nas redes ´opticas . . . . . . . . . . 20
2.5 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.5.1 Formula¸oes Existentes para o TGP . . . . . . . . . . . . . . . 25
3 Modelos ILP para o Problema de Grooming de Tafego 36
3.1 Introdu¸ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.1.1 Trabalhos Relacionados e Contribui¸oes . . . . . . . . . . . . . 37
3.2 Modelos ILP para o Problema de Grooming de Tafego . . . . . . . . 38
3.2.1 Formula¸ao N´o-Arco (NA) . . . . . . . . . . . . . . . . . . . . 38
3.2.2 Formula¸ao Arco-Caminhos (AC) . . . . . . . . . . . . . . . . 42
3.3 Estudo de Casos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3.1 Modelos sem a Atribuao dos Comprimentos de Onda . . . . 45
3.3.2 Roteamento para Topologia Multi-Anel . . . . . . . . . . . . . 47
viii
ix
3.4 Resultados Num´ericos Comparativos . . . . . . . . . . . . . . . . . . 48
3.5 Sum´ario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4 Solu¸ao H´ıbrida para Redes Transl´ucidas 56
4.1 Introdu¸ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.1.1 Trabalhos Relacionados e Contribui¸oes . . . . . . . . . . . . . 58
4.2 Formula¸ao para o RWA (RWA-OF) . . . . . . . . . . . . . . . . . . 59
4.3 Modelo H´ıbrido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.3.1 Escolha e Roteamento de um Caminho
´
Optico . . . . . . . . . 63
4.3.2 Modelo ILP para o TGP com Caminhos
´
Opticos
Transparentes . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.4 Quantifica¸ao do Ganho dos Caminhos
´
Opticos Transparentes . . . . 68
4.4.1 Contagem de Transceptores . . . . . . . . . . . . . . . . . . . 69
4.4.2 Processamento . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.5 Sum´ario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5 Uma Heur´ıstica para o TGP 75
5.1 Introdu¸ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.1.1 Trabalhos Relacionados e Contribui¸oes . . . . . . . . . . . . . 76
5.2 Heur´ıstica para o TGP em Redes Transcl´ucidas . . . . . . . . . . . . 78
5.3 Avalia¸ao da Heur´ıstica . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.3.1 Avalia¸ao dos Parˆametros . . . . . . . . . . . . . . . . . . . . 83
5.4 Sum´ario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6 TGP com Prote¸ao e Restaura¸ao 91
6.1 Introdu¸ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.2 Sobrevivˆencia de Redes em Malha . . . . . . . . . . . . . . . . . . . . 92
6.2.1 Trabalhos Relacionados e Contribui¸oes . . . . . . . . . . . . . 93
6.2.2 Modelos ILP . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.2.3 Estudo de Casos . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.3 Interconex˜ao em Redes Transl´ucidas para Multi-an´eis com DNI . . . 105
6.3.1 Trabalhos Relacionados e Contribui¸oes . . . . . . . . . . . . . 106
6.3.2 Estrat´egias de Prote¸ao DNI . . . . . . . . . . . . . . . . . . . 107
6.3.3 Formula¸oes ILP . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.3.4 Estudo de Casos . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.4 Sum´ario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
x
7 Conclus˜oes e Trabalhos Futuros 118
A Matrizes de Tafego 121
Lista de Figuras
1.1 Representa¸ao das demandas 1-4 e 8-4 em uma rede opaca e sem
agrupamento de tr´afego . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Representa¸ao das demandas 1-4 e 8-4 em uma rede opaca e com
agrupamento de tr´afego . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Representa¸ao das demandas 1-4 e 8-4 em uma rede transl´ucida e
com agrupamento de tr´afego . . . . . . . . . . . . . . . . . . . . . . 4
2.1 Pilha de protocolo para as diferentes arquiteturas aplicadas nas redes
´opticas, adaptada de [LEE 04] . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Prote¸ao por caminho, enlace e sub-caminho, adaptado de [LEE 04] . 17
2.3 Arquitetura de os com e sem O-ADM para uma rede em anel SONET/SDH
+ WDM, adaptada de [ZHU 03] . . . . . . . . . . . . . . . . . . . . . 20
2.4 Ilustra¸ao de uma rede SONET/SDH com an´eis ADM interconecta-
dos por um DXC, adaptada de [SCH 01] . . . . . . . . . . . . . . . . 21
2.5 Diferentes arquiteturas para os os de interconex˜ao dos an´eis, adap-
tada de [WAN 02]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.6 o com capacidade de grooming, adaptada de [WAN 02] e [SOL 07] . 23
2.7 o h´ıbrido com capacidade de grooming, adaptada de [SOL 07] . . . . 24
2.8 Ilustra¸ao de uma conex˜ao . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1 Ilustra¸ao para o grooming de tr´afego no n´o i . . . . . . . . . . . . . . 39
3.2 (a) topologia de rede com 13 os; (b) grafo auxiliar representando a
interconex˜ao entre os an´eis. . . . . . . . . . . . . . . . . . . . . . . . 49
3.3 Topologias das redes de 6 n´os (a) e NSF-Net (b), adaptadas de
[ZHU 02] e [YE 03], respectivamente. . . . . . . . . . . . . . . . . . . 49
3.4 Resultados obtidos para a rede com 6 os usando como m´etricas, (a)
a soma total e (b) o min-max do n´umero de OEOs. . . . . . . . . . . 50
3.5 Resultados obtidos para a rede NSF-Net usando como etricas, (a)
a soma total e (b) o min-max do n´umero de OEOs. . . . . . . . . . . 51
xi
xii
3.6 Resultados para rede com 13 n´os com roteamento em malha, usando
como m´etricas (a) a soma total e (b) o min-max do umero de con-
vers˜oes
´
Optico-Eletrˆonico-
´
Optico . . . . . . . . . . . . . . . . . . . . 53
3.7 Resultados para rede com 13 os com roteamento para multi-anel,
usando como m´etricas (a) a soma total e (b) o min-max do umero
de convers˜oes
´
Optico-Eletrˆonico-
´
Optico . . . . . . . . . . . . . . . . . 53
4.1 (a) sem grooming de tr´afego e sem caminho ´optico, (b) com grooming
de tr´afego e sem caminho ´optico e (b) com grooming de tr´afego com
caminho ´optico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.2 Ilustra¸ao do processamento do tr´afego e de um canal transparente
em um n´o com capacidade de grooming, adaptado de [YE 03]. . . . . 58
4.3 Topologias de rede com 6 n´os (a), 8 n´os (b) e 14 n´os - NSFNet (c). . 68
4.4 N´umero de transceptores (normalizados) vs n´umero de caminhos ´opticos
permitidos, para as redes de 6 n´os (a), 8 n´os (b) e NSF-Net (c). . . . 70
4.5 Ilustra¸ao de uma solu¸ao encontrada pela heur´ıstica para a rede de
6 n´os com 2 comprimentos de onda . . . . . . . . . . . . . . . . . . . 71
4.6 Processamento (normalizado) vs N´umero de caminhos ´opticos para a
redes de 6 n´os (a), 8 n´os (b) e NSF-Net (c). . . . . . . . . . . . . . . 72
5.1 Ilustra¸ao de uma parte da vizinhan¸ca de uma solu¸ao S relacionada
aos n´os de origem-destino (2,5) . . . . . . . . . . . . . . . . . . . . . 82
5.2 Topologias das redes de 6 os (a) e 14 os (b), a apresentadas no
Cap´ıtulo 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.3 An´alise de desempenho do procedimento que gera a Solu¸ao Inicial . 84
5.4 An´alise de desempenho do procedimento de Squeeze . . . . . . . . . . 85
5.5 An´alise de desempenho do procedimento de Perturba¸ao Aleat´oria,
com o Crit´erio de Parada 2 . . . . . . . . . . . . . . . . . . . . . . . 86
5.6 An´alise de desempenho do procedimento de Perturba¸ao Aleat´oria,
com o Crit´erio de Parada 1 . . . . . . . . . . . . . . . . . . . . . . . . 86
5.7 Compara¸ao dos resultados obtidos pela Heur´ıstica proposta e pelo
m´etodo h´ıbrido para a rede de 6 n´os . . . . . . . . . . . . . . . . . . 87
5.8 Compara¸ao dos resultados obtidos pela Heur´ıstica proposta e pelo
m´etodo h´ıbrido para a rede de 14 n´os, considerando as fun¸oes obje-
tivo de min-max e de minimiza¸ao global . . . . . . . . . . . . . . . . 88
xiii
6.1 Topologia de rede, matriz de tr´afego e carga dos enlaces . . . . . . . . 101
6.2 Reconfigura¸ao Global e Local vs. Falha de enlaces . . . . . . . . . . 101
6.3 Restaura¸ao do tr´afego em uma rede sem prote¸ao e com prote¸ao
para a Falha F1 vs. Falha de enlaces . . . . . . . . . . . . . . . . . . 102
6.4 Restaura¸ao do tr´afego em uma rede sem prote¸ao e com prote¸ao
para as Falha F1 e F4 vs. Falha de enlaces . . . . . . . . . . . . . . . 103
6.5 Restaura¸ao do tr´afego em uma rede sem prote¸ao e com prote¸ao
progressiva vs. Falha de enlaces . . . . . . . . . . . . . . . . . . . . . 105
6.6 Estrat´egias de Prote¸ao para DNI . . . . . . . . . . . . . . . . . . . . 107
6.7 (a) min-max{ADM
i
} and (b)
ADM
i
vs. 10 diferentes cargas de
tr´afego inter-anel, para os modelos DNI-DC, DNI-VR e DNI-SP em
cen´arios de rede opaco e transl´ucido . . . . . . . . . . . . . . . . . . . 112
6.8 (a) min-max{ADM
i
} and (b)
ADM
i
vs. 10 diferentes cargas de
tr´afego intra-anel, para os modelos DNI-DC e DNI-VR em cen´arios
de rede opaco e transl´ucido . . . . . . . . . . . . . . . . . . . . . . . . 114
6.9 N´umero de comprimento de ondas vs. 10 cargas de tr´afego crescentes,
inter-anel(a) intra-anel(b), sobre os resultados de DNI-DC e DNI-VR,
para as redes transl´ucidas . . . . . . . . . . . . . . . . . . . . . . . . 115
Lista de Tabelas
2.1 Taxas de transmiss˜ao para redes SONET/SDH . . . . . . . . . . . . . 12
3.1 Resultados comparativos para a rede de 6 n´os . . . . . . . . . . . . . 51
4.1 N´umero aximo caminhos ´opticos limitando os comprimentos de
onda em cada enlace. . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
A.1 Matriz de tr´afego usada na rede de 6 n´os . . . . . . . . . . . . . . . . 121
A.2 Matriz de tr´afego usada na rede de 8 n´os . . . . . . . . . . . . . . . . 121
A.3 Matriz de tr´afego usada na rede de 8 n´os usada no Cap´ıtulo 7 . . . . 122
A.4 Matriz de tr´afego usada na rede de 13 n´os . . . . . . . . . . . . . . . 122
A.5 Matriz de tr´afego usada na rede NSF-NET (14 n´os) . . . . . . . . . . 123
xiv
xv
Lista de Siglas
ADM Add&Drop Multiplexer
ATM Asynchronous Transfer Mode
DXC Digital Crossconnect
DNI Dual Node Interconnection
DEMUX Demultiplex
FBG Fiber Brag Gratings
FDM Frequency Division Multiplexing
GMPLS Generalized Multiprotocol Label Switching
GFP Generic Frame Procedure
HDLC High-Level Data Link Control
ILP Integer Linear Programming
IETF Internet Enginnering Task Force
IP Internet Protocol
LSR Label-Switched Router
LCAS Link Capacity Adjustment Scheme
LAN Local Area Networks
MAN Metropolitan Area Network
MILP Mixed Integer Linear Programming
MPLS Multiprotocol Label Switching
MUX Multiplexer
OBS Optical Burst Switching
OC-N Optical Carrier-N
OCS Optical Circuit Switching
OPS Optical Packet Switching
PDH Plesiochronous Digital Hierarchy
PPP Point-to-Point Protocol
QoS Quality of Service
RWA Routing and Wavelength Assignment
SNI Single Node Interconnection
SDH Synchronous Digital Hierarchy
SONET Synchronous Optical Networking
STM-N Synchronous Transfer Mode-N
STS-N Synchronous Transport Signal-N
TDM Time Division Multiplexing
TGP Traffic Grooming Problem
VCAT Virtual Concatenation
VR Virtual Ring
VTD Virtual Topology Design
VTs Vitual Tributaries
WDM Wavelength Division Multiplexing
OADM Optical Add-Drop Multiplexers
Cap´ıtulo 1
Introdu¸ao
No in´ıcio da d´ecada de 80, o uso das redes ´opticas introduziu um novo paradigma
em telecomunica¸oes. Tais redes ao providas de uma enorme largura de banda,
podendo oferecer uma nova gama de servi¸cos, como v´ıdeo, voz e dados interativos,
ainda suportando a atual e crescente populariza¸ao da Internet e da World Wide
Web. Esse aumento de banda em cada nova gama de servi¸cos fornecidos, aliado `a
integra¸ao dos mesmos em uma ´unica rede de transporte, tem impulsionado cada vez
mais investimentos e pesquisas, inclusive em novas linhas de investiga¸oes, tentando
prever novas necessidades e tecnologias, o que possibilita uma melhor utiliza¸ao dos
recursos das redes ´opticas.
Entre os diversos benef´ıcios das redes ´opticas pode-se destacar, talvez como um
dos mais importantes, a capacidade de suportar arios canais de transmiss˜ao em uma
´unica fibra atrav´es da multiplexa¸ao por divis˜ao de comprimento de onda (Wave-
length Division Multiplexing - WDM). Um dispositivo WDM divide o espectro ´optico
de transmiss˜ao em arias faixas de frequˆencias (comprimentos de onda). Sistemas
WDM com at´e uma centena de canais a est˜ao dispon´ıveis comercialmente [MEY 08].
Para o aproveitamento dessa quantidade de largura de banda, tem-se observado um
empenho em pesquisas para desenvolver t´ecnicas eficientes com o intuito de aco-
modar as demandas de tr´afego sobre esses canais. Relacionados ao problema da
acomoda¸ao das demandas em uma rede usando sistemas WDM, pode-se citar os
seguintes sub-problemas: Projeto da Topologia Virtual (Virtual Topology Design -
VTD), Roteamento e atribui¸ao dos Comprimentos de Onda (Routing and Wave-
length Assignment - RWA) e o Problema de Grooming de Tafego (Traffic Grooming
Problem - TGP). Cada subproblema citado possui um grande n´umero de pesquisas
relacionadas, podendo ainda considerar, para cada um deles, um extenso conjunto
1
2
de casos. A seguir ´e apresentada uma breve descri¸ao de cada um desses.
Um dos principais recursos das redes ´opticas ´e a possibilidade de se estabelecer
caminhos ´opticos. Esses caminhos ao definidos como conex˜oes ponto-a-ponto
que ao transparentes aos n´os intermedi´arios, isto ´e, para essas conex˜oes ao
´e realizado processamento eletrˆonico para fins de roteamento em tais os. O
VTD consiste basicamente em uma escolha dos caminhos ´opticos da rede.
Uma vez escolhidos os os de origem e destino dos caminhos ´opticos, ´e necess´ario
acomoa-los sobre a rede f´ısica, isto ´e, escolher a rota e o comprimento de onda
usado por cada conex˜ao. A essa tarefa d´a-se o nome de RWA.
O TGP ´e definido como o problema de combinar demandas de baixa veloci-
dade em canais de transmiss˜ao de alta capacidade. Em geral, considera-se
uma configura¸ao de caminhos ´opticos pr´e-estabelecidos e o TGP consiste em
combinar o tr´afego dentro desses caminhos ´opticos.
Para cada um dos problemas, ´e poss´ıvel encontrar na literatura uma grande
quantidade de etodos para a solu¸ao, que se dividem basicamente em etodos
heur´ısticos e exatos. Os etodos heur´ısticos em geral fornecem solu¸oes sub-´otimas
para problemas com alta complexidade computacional, pois ao bem mais apidos
do que etodos usados para encontrar a solu¸ao ´otima de um problema. Os etodos
exatos mais usados para os problemas relacionados ao projeto das redes ´opticas s˜ao
os de Programa¸ao Linear Inteira (ILP - Integer Linear Programming) e de Pro-
grama¸ao Linear Inteira Mista (MILP - Mixed Integer Linear Programming). Tais
m´etodos apesar de encontrarem a solu¸ao ´otima para o problema, ao extremamente
custosos computacionalmente. No Cap´ıtulo 2, ser˜ao apresentados de forma mais de-
talhada, os aspectos estruturais e as principais propostas de algoritmos heur´ısticos
e exatos encontrados na literatura.
1.1 Motivao e Justificativa
As Figuras 1.1, 1.2 e 1.3 ilustram os problemas de VTD, RWA e TGP no contexto
das redes ´opticas. Em cada Figura ´e representado uma rede ´optica com alguns os
de n´ucleo (2, 3, 5, 6 e 7) e os de borda (1, 4 e 8), onde cada o de borda possui
3
usu´arios e servi¸cos. Na Figura 1.1 ´e representado duas demandas, com origem nos
os 1 e 8 e ambas destinadas ao o 4, em um cen´ario de rede onde as demandas
sofrem processamento eletrˆonico em todos os n´os (conhecido com rede opaca) e sem
agrupamento de tr´afego. Nesse cen´ario nota-se o uso de dois comprimentos de onda
nos enlaces 2-3 e 3-4 e um processamento eletrˆonico nos os 2, 3, 5 e 7, sendo que os
os 2 e 3 precisam processar as duas demandas. Al´em desses recursos, contabiliza-se
tamb´em 16 convers˜oes ´optica-eletrˆonica-´optica que ao realizadas por dispositivos
chamados de transceptores, que tamem representam custo `a rede.
Nó de
Borda
Nó de
Borda
Nó de
Borda
Rede óptica
Nó de núcleo
Recurso
Computacinal
Usuários
da rede
Usuários
da rede
Usuários
da rede
Recurso
Computacinal
Servidor
De dados
1
2
3
4
7
6
5
8
Figura 1.1: Representa¸ao das demandas 1-4 e 8-4 em uma rede opaca e sem
agrupamento de tr´afego
Na Figura 1.2 ao representadas as mesmas demandas, 1-4 e 8-4, por´em ad-
mitindo a possibilidade de agrupamento de tr´afego no o 2. Assim, com uma solu¸ao
para o TGP e o RWA obtˆem-se a economia de 1 comprimento de onda nos enlaces
2-3 e 3-4 com uma redu¸ao de 4 transceptores. Contudo, os os 2 e 3 continuam
com a mesma quantidade de processamento eletrˆonico.
Usando 1 caminho ´optico, entre os n´os 2 e 4, a Figura 1.3 representa uma rede
transl´ucida. Com uma solu¸ao para o VTD, RWA e o TGP combinados, essa figura
apresenta um configura¸ao onde, al´em da redu¸ao do n´umero de comprimentos de
onda e extin¸ao do processamento eletrˆonico no o 3, obteve-se a acomoda¸ao do
tr´afego com apenas 10 transceptores.
4
Nó de
Borda
Nó de
Borda
Nó de
Borda
Rede óptica
Nó de núcleo
Recurso
Computacinal
Usuários
da rede
Usuários
da rede
Usuários
da rede
Recurso
Computacinal
Servidor
De dados
1
2
3
4
7
6
5
8
Figura 1.2: Representa¸ao das demandas 1-4 e 8-4 em uma rede opaca e com
agrupamento de tr´afego
Nó de
Borda
Nó de
Borda
Nó de
Borda
Rede óptica
Nó de núcleo
Recurso
Computacinal
Usuários
da rede
Usuários
da rede
Usuários
da rede
Recurso
Computacinal
Servidor
De dados
1
2
3
4
7
6
5
8
Figura 1.3: Representa¸ao das demandas 1-4 e 8-4 em uma rede transl´ucida e com
agrupamento de tr´afego
Comparando as Figuras 1.1, 1.2 e 1.3 fica claro que um dos principais objetivos
dos problemas de VTD, RWA e TGP ´e encontrar uma configura¸ao da rede, de forma
5
a acomodar o tr´afego minimizando os custos em instala¸ao. Mais especificamente,
como ser´a mostrada, essa ´e a principal fun¸ao objetivo para o TGP, que ´e o foco
deste trabalho. Assim, o desenvolvimento desse trabalho ´e justificado pelo aspecto
pr´atico, pela relevˆancia das redes ´opticas e pela complexidade da configura¸ao dessas
redes.
1.2 Objetivo
Como j´a exposto, o escopo deste trabalho ´e a configura¸ao das redes ´opticas tendo
em vista as particulariza¸oes e recursos existentes nessas redes.
1.2.1 Objetivos Gerais
Dentro do contexto das redes ´opticas esse trabalho prop˜oe investigar o TGP, an-
teriormente exposto, juntamente com os problemas de VTD e RWA, tamb´em rela-
cionados `a configura¸ao das redes ´opticas. O desenvolvimento do trabalho se d´a,
basicamente, atrav´es da elabora¸ao de etodos para encontrar solu¸oes de boa qua-
lidade, seguindo abordagens exata e heur´ıstica.
1.2.2 Objetivos Espec´ıficos
Na literatura relacionada ao projeto de redes ´opticas, ainda existe um vasto campo a
ser explorado. Dentre os temas ainda em discuss˜ao, neste trabalho ao investigadas
e respondidas as seguintes perguntas, que nortearam o desenvolvimento do mesmo:
Existem basicamente dois paradigmas de formula¸ao para modelos ILP, for-
mula¸ao o-arco e formula¸ao arco-caminho. Por´em, qual tipo de modela-
mento ´e mais indicado para cada problema encontrado dentro do contexto das
redes ´opticas?
Qual a rela¸ao entre o n´umero de caminhos ´opticos transparentes na rede e
a redu¸ao do n´umero de transceptores que eles proporcionam? Existe algum
limite dos benef´ıcios, em redu¸ao de n´umero de transceptores e processamento
eletrˆonico, oferecidos pela utiliza¸ao dos caminhos ´opticos?
6
Buscando solu¸oes de boa qualidade para redes maiores, encontram-se na lite-
ratura in´umeras heur´ısticas. Contudo, tais m´etodos frequentemente requerem
um complexo ajuste de parˆametros ou ao extremamente simples, gerando
solu¸oes de baixa qualidade. Assim, como construir uma heur´ıstica que seja
eficiente e n˜ao haja um ajuste complexo de parˆametros?
Em uma rede de comunica¸ao ´e relativamente comum a prote¸ao parcial da
rede, pois nem todos os recursos ou demandas necessitam de prote¸ao. Nesses
casos, supondo uma prote¸ao para um elemento espec´ıfico da rede (o ou
enlace), como utilizar esse recurso extra para beneficiar as demais demandas
no caso de falha em outro ponto da rede?
Tratando de redes com topologias multi-anel com dois os de interconex˜ao,
existem basicamente duas estrat´egias de prote¸ao da interconex˜ao, Anel Vir-
tual e Drop&Continue. Qual dessas estrat´egias ´e mais interessante de ser
usada para determinado cen´ario de demandas?
´
E poss´ıvel aproximar os resul-
tados obtidos pelos dois etodos de modo que o projetista da rede tenha mais
flexibilidade para a escolha dos procedimentos de prote¸ao?
1.3 Contribui¸oes e Organiza¸c˜ao do Texto
Definidos os objetivos a serem alcan¸cados, cabe destacar as principais contribui¸oes
apresentadas nesse trabalho:
Proposi¸ao e an´alise de dois modelos matem´aticos para encontrar solu¸oes para
os problemas de grooming de tr´afego, roteamento e aloca¸ao de comprimento
de onda, um para cada tipo de formula¸ao. Com a investiga¸ao dos modelos
em diferentes cen´arios de redes ´opticas, foi poss´ıvel identificar qual formula¸ao
´e mais adequada para cada cen´ario de rede.
Proposi¸ao de um m´etodo para a solu¸ao do VTD, TGP e RWA, atraes de um
m´etodo que combina um algoritmo heur´ıstico com uma formula¸ao ILP. Adi-
cionalmente, atrav´es deste etodo ´e, pela primeira vez na literatura (dentro
do nosso conhecimento), realizada uma an´alise dos reais benef´ıcios (em termos
da redu¸ao do n´umero de transceptores e do processamento eletrˆonico) do em-
prego dos caminhos ´opticos transparentes em redes transl´ucidas. Al´em disso,
7
tal an´alise identificou a rela¸ao entre o n´umero de caminhos ´opticos, redu¸ao
do n´umero de transceptores e processamento eletrˆonico nos os intermedi´arios.
Desenvolvimento de uma heur´ıstica, livre da configura¸ao de complexos parˆa-
metros de ajuste, capaz de obter bons resultados quando comparada com as
solu¸oes exatas e com um tempo computacional aceit´avel.
Usando como base os modelos propostos ´e realizada a proposi¸ao de um
m´etodo iterativo de prote¸ao e reconfigura¸ao de redes arbitr´arias. Esse m´etodo
in´edito ´e composto por dois modelos ILP que permitem, a cada itera¸ao, en-
contrar e proteger pontos vulner´aveis na rede.
Proposi¸ao de modelos ILP espec´ıficos para a prote¸ao de interconex˜ao das
redes multi-anel, com as estrat´egias Anel Virtual e Drop&Continue. Nesse
estudo, os modelos ao investigados em diversos cen´arios de rede, comparando
redes opacas versus transl´ucidas com crescimento de tr´afego inter-anel e intra-
anel. Assim, com esse detalhamento de cen´arios, foi poss´ıvel identificar em
que situa¸ao deve ser usada cada prote¸ao de interconex˜ao.
Assim, o restante deste documento est´a dividido de forma a apresentar tais con-
tribui¸oes. O pr´oximo cap´ıtulo apresenta os aspectos estruturais e uma breve revis˜ao
da literatura relacionada ao problema do projeto de uma rede ´optica. O Cap´ıtulo 3
apresenta a proposi¸ao de dois modelos ILP, concebidos usando os dois paradigmas
de modelamentos das redes (relacionando os n´os aos enlaces e os enlaces aos cami-
nhos). Ainda neste cap´ıtulo, tamb´em ´e apresentado um conjunto de restri¸oes para
adaptar os modelos propostos `a diferentes estudos de casos em uma rede ´optica.
Um algoritmo h´ıbrido e a an´alise do benef´ıcio dos caminhos ´opticos ao propostos
no Cap´ıtulo 4. No Cap´ıtulo 5, ´e apresentada uma heur´ıstica para os problemas de
VTD, TGP e RWA. Alguns aspectos de prote¸ao e reconfigura¸ao para redes com
topologia em malha e multi-anel ao estudados no Cap´ıtulo 6. Finalmente, algumas
conclus˜oes gerais e a proposi¸ao de trabalhos futuros s˜ao mostrados no Cap´ıtulo 7.
8
1.4 Trabalhos Publicados
Peri´odicos
L. C.Resendo, M. R. N. Ribeiro, e J. Pires,Optimal Multilayer Grooming-
Oriented Design for Inter-Ring Traffic Protection in DNI Multi-Ring WDM
Networks, OSA-JON, Optical Society of America - Journal of Optical Net-
working, v.7, p.533-549, 2008.
L. C.Resendo, M. R. N. Ribeiro, e L. C.Calmon, Efficient Grooming-Oriented
Heuristical Solutions for Multi-Layer Mesh Networks, Journal of Microwaves
and Optoelectronics, pp. 263-267, 2007.
Congressos
L. C. Resendo, M. R. N. Ribeiro e J. J. O. Pires,Optimal Design for Pro-
tected Connection-oriented Ethernet over DNI Multi-ring WDM Networks, In:
Simp´osio Brasileiro de Microondas e Optoeletrˆonica & Congresso Brasileiro de
Eletromagnetismo, MOMAG2008, Florian´opolis, p. 249-253, 2008.
L. C. Resendo, M. R. N. Ribeiro, J. Pedro, e J. J. O. Pires,ILP Approaches
to study interconnection strategies for multi-Ring Networks in the Presence of
Traffic Grooming, DRCN2007, 2007, La Rochelle. 6th International Workshop
on Design and Reliable Communication Networks, 2007.
L. C. Resendo e M. R. N. Ribeiro,Complementary Optical Approaches for
Survivable WDM Mesh Network Design: Transceivers Deployment and Traf-
fic Engineering, PS2006, International Conference on Photonics in Switching,
Heraklion, p.1-3, 2006.
L. C. Resendo e M. R. N. Ribeiro,Optimal Design of Protection and Traffic
Enginnering in Survivable WDM Network, In: Workshop FAPESP TIDIA,
2006, S˜ao Paulo. Proceedings of III Workshop TIDIA, 2006. v. 1. p. 72-74.
L. C. Resendo e M. R. N. Ribeiro,Efficient Grooming-Oriented Heuristical So-
lutions for Multi-Layer Mesh Networks, In: Simp´osio Brasileiro de Microon-
das e Optoeletrˆonica & Congresso Brasileiro de Eletromagnetismo, 2006, Belo
Horizonte, MOMAG2006.
9
L. C. Resendo, L. C. Calmon e M. R. N. Ribeiro,Transparent Lightpaths Im-
proving Optimal Traffic Grooming in WDM Mesh Networks, In: ICT006, Fun-
chal, 13th International Conference on Telecommunications, p.1-4, 2006.
L. C. Resendo, L. C. Calmon e M. R. N. Ribeiro,Orthogonal Metrics for GRWA
Optical Networking, SBrT2005, Simp´osio Brasileiro de Telecomunica¸oes 2005,
Campinas, p.1-5.
L. C. Resendo, L. C. Calmon e M. R. N. Ribeiro,Simple ILP Approaches to
Grooming, Routing, and Wavelength Assignment in WDM Mesh Networks,
SBMO/IEEE MTT-S, International Conference of Microwave and Optoelec-
tronics, Brasilia, p.616-619, 2005.
Cap´ıtulo 2
Revis˜ao da Literatura
Este cap´ıtulo apresenta alguns dos principais aspectos estruturais associados ao
problema do projeto de uma rede ´optica, bem como as principais propostas en-
contradas na literatura. Esses aspectos englobam considera¸oes que incluem basi-
camente os problemas de escolha e roteamento dos caminhos ´opticos provindos da
topologia virtual, agrupamento de tr´afego, acomoda¸ao do mesmo sobre a topologia
virtual, roteamento e atribui¸ao dos comprimentos de onda. Para isto, foram ex-
planadas as principais arquiteturas de n´os para redes ´opticas em anel e malha, com
os algoritmos exatos e heur´ısticos que se destacam na literatura.
2.1 Redes
´
Opticas
Nesta sess˜ao, ´e apresentada uma breve s´ıntese sobre alguns aspectos estruturais en-
volvidos no escopo deste trabalho. A Figura 2.1 oferece uma vis˜ao geral sobre as
fases da evolu¸ao das gera¸oes de arquiteturas empregadas nas redes ´opticas. Como
mostrado na figura, at´e recentemente, os roteadores IP (Internet Protocol) eram
interconectados por circuitos virtuais provindos da tecnologia ATM (Asynchronous
Transfer Mode), que por sua vez eram conectados por enlaces SONET/SDH (SONET
- Synchronous Optical Networking/ SDH - Synchronous Digital Hierarchy) usando
circuitos TDM (Time Division Multiplexing). Com o objetivo de eliminar camadas
intermedi´arias, que geram um overhead indesejado, os roteadores IP se tornaram
capazes de interfacear diretamente com os equipamentos SONET/SDH. Assim, os
equipamentos da camada ATM come¸caram a ser gradualmente substitu´ıdos por tais
roteadores e pelos dispositivos SONET/SDH. Mais adiante, o protocolo MPLS (Mul-
10
11
tiprotocol Label Switching) conseguiu melhorar as funcionalidades do IP, atraes da
inser¸ao de otulos nos pacotes IP nos roteadores de borda, o que simplificou o rotea-
mento IP dentro dos backbones. Com o aumento da taxa de transmiss˜ao (promovido
pelo MPLS) das portas dos roteadores IP, j´a ´e poss´ıvel ter roteadores IP de alto de-
sempenho interconectados diretamente por um comprimento de onda [LIU 02]. Mais
recentemente, e ainda em desenvolvimento, outras ecnicas para comutar demandas
de sub-comprimentos de onda tˆem sido amplamente investigadas, com o objetivo
de aproveitar a vasta largura de banda oferecida pelo sistema WDM. Entre elas,
encontram-se o OCS (Optical Circuit Switching), OBS (Optical Burst Switching) e
o OPS (Optical Packet Switching)[XUE 05].
Figura 2.1: Pilha de protocolo para as diferentes arquiteturas aplicadas nas redes
´opticas, adaptada de [LEE 04]
Fibra ´optica
O meio de transmiss˜ao usado em comunica¸ao ´optica, a fibra ´optica, possui carac-
ter´ısticas importantes que devem ser consideradas em um projeto de redes ´opticas.
Uma fibra ´optica possui uma capacidade de largura de banda para transmiss˜ao com
alguns Terabits por segundo (Tbps), sendo poss´ıvel dividir essa capacidade em um
sistema WDM, onde os equipamentos produzidos atualmente podem operar a 40 Gi-
gabits por segundo (Gbps) em cada canal. Al´em da banda, as fibras ´opticas possuem
o atrativo de ter uma baixa atenua¸ao, o que para redes de longa distˆancia pode sig-
nificar uma economia consider´avel no n´umero de repetidores/regeneradores. Outra
caracter´ıstica interessante ´e o fato das fibras serem imunes a interferˆencias eletro-
12
magn´eticas[GIO 91]. Al´em disso, por serem finas e leves, com o investimento de
instala¸ao ´e comum que se passe arios pares de fibra, tendo assim muitas das fibras
instaladas ainda “apagadas”(que n˜ao est˜ao em uso). Isso possibilita um crescimento
apido de capacidade para atender um poss´ıvel crescimento de demanda. Por´em, ´e
importante mencionar algumas das dificuldades de instala¸ao de uma fibra, tais como
emendas e dobras, sendo esta ´ultima um fator que dificulta e encarece a instala¸ao
de fibra em determinados trechos, por exemplo em LANs (Local Area Networks).
Multiplexa¸ao
A multiplexa¸ao dos canais de comunica¸ao na fibra ´optica, realizada em sistemas
TDM, muito se assemelha ao sistema FDM (Frequency Division Multiplexing). Con-
tudo, a diferen¸ca b´asica entre os dois reside no fato de o WDM poder ser realizado
de forma passiva atrav´es da FBG (Fiber Bragg Gratings), que ´e uma pequena se¸ao
de fibra ´optica que age como um espelho seletivo, refletindo de volta apenas com-
primentos de onda espec´ıficos.
Com rela¸ao `a taxa de transmiss˜ao, na multiplexa¸ao WDM, nas redes SONET ´e
adotada uma taxa b´asica de sinal de 51,84 MB/s (chamada de STS-1, Synchronous
Transport Signal), e 155,52 MB/s para rede SDH (chamado de STM-1, Synchronous
Transfer Mode), de forma que os sinais de mais alta velocidade ao m´ultiplos dessas
taxas b´asicas. As interfaces ´opticas relacionadas a uma taxa de transmiss˜ao STS-N
(ou STM-N) recebem o nome de OC-N (Optical Carrier-N). A Tabela 2.1 mostra as
taxas de transmiss˜ao dos sinais nos padr˜oes SONET e SDH [RAM 02].
Tabela 2.1: Taxas de transmiss˜ao para redes SONET/SDH
SONET SDH Mb/s
STS-1 51,84
STS-3 STM-1 155,52
STS-12 STM-4 622,08
STS-24 1244,16
STS-48 STM-16 2488,32
STS-192 STM-64 9953,28
STS-768 STM-256 39814,32
No padr˜ao SONET, as taxas abaixo de STS-1 ao mapeadas em virtual tributaries
(VTs). ao definidos quatro tamanhos para as VTs: VT1.5, VT2, VT3 e VT6, para
13
sinais ass´ıncronos com taxas de 1.5, 2, 3 e 6 Mb/s, respectivamente. Esses VTs
ao multiplexados em grupos e inseridos nos sinais de alta velocidade, STS-N. Esta
tarefa de agrupamento de tr´afego ´e realizada atrav´es de processamento eletrˆonico por
equipamentos como ADM (Add&Drop Multiplexer) ou DXC(Digital Crossconnect).
2.1.1 Principais Camadas Clientes das Redes
´
Opticas
Todas as camadas clientes das redes ´opticas ao capazes de realizar o processamento
dos dados no dom´ınio eletrˆonico. Com isso, estas camadas clientes podem processar
o tr´afego em taxas inferiores `as do comprimento de onda, podendo agregar o tr´afego
e oferecer simultaneamente uma variedade de servi¸cos de baixa velocidade, como,
voz, dados e linhas para redes privadas. A seguir ao descritas algumas das principais
camadas clientes das redes ´opticas.
SONET/SDH
SDH e SONET ao padr˜oes de transmiss˜ao e multiplexa¸ao para sinais de alta ve-
locidade utilizados na Europa e EUA, respectivamente. Esses padr˜oes foram criados
para atender a novas demandas de servi¸cos, como a Internet. Alguns benef´ıcios do
padr˜ao SONET/SDH foram enumerados abaixo [KAR 99].
1. Nos sistemas SONET/SDH toda a rede ´e sincronizada em um ´unico rel´ogio
mestre, sendo mais acil e “barato”retirar e inserir, (de)multiplexar, sinais de
baixa velocidade em canais de alta velocidade. O mesmo ao acontece para
PDH, onde, por ser ass´ıncrono, um sinal de alta velocidade ´e todo demulti-
plexado para retirar e inserir parte do tr´afego.
2. O gerenciamento de redes SONET/SDH inclui um monitoramento de desem-
penho, que facilita na identifica¸ao e recupera¸ao de falhas. Ainda inclui iden-
tifica¸ao da conectividade e tipo do tr´afego, podendo influenciar as decis˜oes do
operador da rede, tendo em vista o QoS (Quality of Service) de determinadas
aplica¸oes.
3. Os padr˜oes SONET/SDH j´a prevˆeem uma interoperabilidade entre diferentes
fabricantes. O mesmo n˜ao acontece para o PDH.
14
4. A padroniza¸ao SONET/SDH pode aproveitar caracter´ısticas espec´ıficas da
topologia da rede e aplicar t´ecnicas de prote¸ao e reconfigura¸ao mais efi-
cientes. Isto significa uma reconfigura¸ao mais apida, fundamental para au-
mentar a disponibilidade dos servi¸cos da rede.
Atualmente em-se as redes SDH nova gera¸ao, que tiram proveito da simpli-
cidade e eficiˆencia da tecnologia Ethernet e da capacidade e qualidade de servi¸co
da tecnologia SDH. Tal tecnologia de rede consiste basicamente na introdu¸ao dos
seguintes recursos: VCAT (Virtual Concatenation), LCAS (Link Capacity Adjust-
ment Scheme) e GFP (Generic Frame Procedure). Esses novos recursos permitem
encaminhar o tr´afego por arios caminhos, o que torna o processo de roteamento
mais flex´ıvel [CAR 07].
IP
O IP tradicionalmente opera sobre a camada de enlace em redes locais, tais como
Ethernet e token ring. Por´em, pode trabalhar sobre canais de alta velocidade tendo
como meio f´ısico a fibra ´optica, usando para isso protocolos da camada de en-
lace como HDLC (High-Level Data Link Control) ou PPP(Point-to-Point Protocol).
Al´em da alta interoperabilidade entre diferentes tecnologias de rede, uma rede IP,
em geral, ao precisa de um sistema de gerenciamento centralizado. Os roteadores
IP podem ser auto-configur´aveis, aprendendo o roteamento na rede com informa¸oes
cedidas pelos vizinhos, atrav´es de protocolos de roteamento, como o OSPF (Open
Shortest Path First Protocol).
Atualmente, tem-se uma nova tecnologia do mundo IP com uma variedade de
aplica¸oes, o MPLS (MultiprotocolLabel Switching) [DAV 00, BLA 01]. O principal
objetivo do MPLS ´e facilitar a comuta¸ao dos pacotes dentro de uma malha de
comuta¸ao. Como exemplo de equipamento em tal malha de comuta¸ao, tem-se os
comutadores ATM em uma rede de transporte SDH e gigarouters IP em uma rede
de transporte ´optica (IP/SDH ou IP/WDM).
O MPLS atribui a cada pacote um identificador (r´otulo) que descreve o caminho
entre dois os. Os roteadores capazes de suportar essa tecnologia ao chamados de
Label-Switched Router (LSR). Assim, cada LSR manem uma tabela ou realiza uma
opera¸ao com o identificador de caminho, que indicar´a a porta de sa´ıda do LSR. Al´em
15
de acelerar o processo da comuta¸ao do pacote, o MPLS consegue prover alguma
garantia de qualidade de servi¸co `a rede IP. Tamem desenvolvido pelo IETF (Inter-
net Enginnering Task Force) [BAN 01] o GMPLS (Generalized MultiprotocolLabel
Switching) ´e uma vers˜ao estendida do MPLS. Enquanto o MPLS foi originalmente
desenvolvido para o controle da rede baseada em pacotes, o GMPLS pode controlar
arias camadas, como pacotes IP, canais de TDM e WDM, e a escolha de uma fibra,
no caso de uma rede multi-fibra.
OCS e OBS
Para as arquiteturas empregando IP-sobre-WDM, arias ecnicas de comuta¸ao
´optica tˆem sido investigadas. Entre tais t´ecnicas pode-se destacar o OCS, onde
uma conex˜ao ponto-a-ponto ´e estabelecida por um tempo relativamente longo; e o
OBS, que tenta mudar a complexidade da computa¸ao e do controle proveniente do
dom´ınio ´optico para o dom´ınio eletrˆonico [XUE 05].
2.1.2 Prote¸ao e Restaura¸ao
Em uma rede ´optica WDM a falha de um elemento de rede pode causar a perda de
uma grande quantidade de tr´afego. Assim, estudos examinando diferentes t´ecnicas
de prote¸ao em redes WDM s˜ao facilmente encontrados na literatura. Inicialmente
os estudos relacionados `a prote¸ao de redes WDM consideravam apenas a topologia
em anel, por´em, recentemente, devido ao crescimento das redes, as topologias em
malha e multi-anel tˆem sido o principal foco de alguns trabalhos [VAS 04, SOM 05].
Existem basicamente dois mecanismos para se tratar falhas em redes, por prote¸ao
ou restaura¸ao. Se os recursos para a sobrevivˆencia ao pr´e-computados e reserva-
dos enquanto a conex˜ao estiver ativa, esse mecanismo ´e chamando de prote¸ao. Por
outro lado, se a estrat´egia for calcular a rota para sobrevivˆencia apenas ap´os a falha,
´e chamado de restaura¸ao [LEE 04]. Como a restaura¸ao ´e um m´etodo reativo ini-
cializado ap´os a falha do enlace, esse ao pode garantir a sobrevivˆencia do tr´afego e
´e mais demorado para recuperar o tr´afego. Por outro lado, por ser um etodo proa-
tivo, a prote¸ao, al´em de ser mais apida, pode garantir a total sobrevivˆencia das
demandas em caso de falha. Adicionalmente, sabe-se que esquemas de restaura¸ao
possuem uma melhor taxa de utiliza¸ao da rede [VAS 04]. Como a restaura¸ao ´e
16
um esquema tipicamente dinˆamico, esse mecanismo de sobrevivˆencia est´a fora do
escopo deste trabalho.
Os esquemas de prote¸ao podem ser classificados pelo tipo de estrat´egia de rotea-
mento, como prote¸ao do caminho, enlace ou sub-caminho, e pela forma como ao
usados os recursos, a saber, dedicados ou compartilhados, [RAM 99b, RAM 03,
GER 00]. Na prote¸ao por caminho, quando ocorre uma falha no caminho de tra-
balho, o tr´afego ´e re-roteado atrav´es de um caminho de prote¸ao que deve ser dis-
junto, por o, ao caminho de trabalho. Na prote¸ao do enlace, em caso de falha,
a demanda ´e re-roteada do n´o imediatamente anterior `a falha para o n´o seguinte `a
falha [LEE 04]. Com uma solu¸ao intermedi´aria `as duas anteriores, a prote¸ao por
sub-caminho divide o caminho de trabalho em setores, provendo um caminho de
prote¸ao de cada setor. Outro aspecto que deve ser considerado por um esquema de
sobrevivˆencia ´e se os recursos destinados `a prote¸ao das demandas ao dedicados ou
compartilhados. Em um esquema de prote¸ao dedicada, o comprimento de onda usa-
do para a prote¸ao deve ser dedicado apenas a uma ´unica conex˜ao. Enquanto que,
em um esquema de prote¸ao compartilhada, o comprimento de onda usado para
prote¸ao pode ser usado por outras conex˜oes [MAI 02]. Cada combina¸ao dessas
estrat´egias possui diferentes n´ıveis de aproveitamento de recursos.
A Figura 2.2 ilustra os aspectos de roteamento para os mecanismos de prote¸ao.
Considere uma demanda com origem no o 2 e destino no o 20, roteada pelo ca-
minho 2-6-8-11-15-20. Para a prote¸ao de enlace, como anteriormente mencionado,
cada enlace possui seu pr´oprio caminho de prote¸ao. Na Figura 2.2 o enlace 2-6
possui o caminho de prote¸ao 2-3-6, o enlace 6-8 possui o caminho 6-5-8, assim su-
cessivamente, formando o caminho de prote¸ao 2-3-6-5-8-10-11-12-16-15-21-20. Note
que, al´em de demandar uma maior quantidade de recursos, n˜ao ao todas as topolo-
gias que suportam essa estrat´egia de prote¸ao. O mecanismo de sub-caminho, nesse
exemplo, dividiu a rede em duas partes: de 2 a 8 e de 8 a 20. A primeira parte
possui o caminho de prote¸ao 2-1-5-8 e segunda parte ´e protegida usando a rota
8-10-14-19-20. Apesar de o ´ultimo apresentar uma redu¸ao do custo, no geral, o
m´etodo mais econˆomico ´e a prote¸ao do caminho, que no exemplo foi roteada por
2-1-5-10-18-19-20.
Considerado os elementos a serem protegidos na rede ´optica, tˆem-se basicamente
trˆes tipos: os, enlaces (fibras) e comprimentos de onda (transmissores ou recep-
tores). Na Figura 2.2, nota-se claramente que a prote¸ao de enlaces, apesar de ser a
17
mais custosa, ainda ´e a que oferece o menor n´ıvel de prote¸ao, ao sendo capaz de
recuperar a falha de nenhum o ao longo do caminho. Por outro lado, a prote¸ao
de caminho, a estrat´egia com o menor custo na Figura 2.2, pode recuperar qualquer
tipo de falha ao longo do caminho de trabalho. Intermedi´ario a esses, a prote¸ao por
sub-caminho possui apenas alguns ponto de vulnerabilidade, que s˜ao justamente os
os de interse¸ao de dois sub-caminhos.
1
0
2
3
4
7
6
5
10
8 11 15 20
14
19
18
21
16
12
9
13 17
22
23
Caminho de trabalho
Caminho de recuparação para proteção do enlace
Caminho de recuparação para proteção do sub-caminho
Caminho de recuparação para proteção do caminho
Figura 2.2: Prote¸ao por caminho, enlace e sub-caminho, adaptado de [LEE 04]
Al´em dos mecanismos anteriormente citados, o projetista da rede ainda deve
optar entre os esquemas de recupera¸ao usando 1+1 ou 1:1. Para um esquema 1+1,
o tr´afego de prote¸ao ´e transmitido simultaneamente ao tr´afego de trabalho. Assim,
quando o n´o de destino detecta uma falha no caminho de trabalho, basta comutar
para o caminho de prote¸ao. Esse esquema ´e o que possui a recupera¸ao mais apida,
por´em, por duplicar todas as demandas por caminhos disjuntos aos de trabalho,
tamb´em ´e o que exige maior quantidade de recursos adicionais. No esquema 1:1
o tr´afego de prote¸ao ´e enviado apenas quando for detectada uma falha. Como
a rede ao precisa suportar a duplica¸ao simultˆanea de todas da demandas, esse
esquema possui um menor uso de recursos adicionais quando comparado ao 1+1,
como mostrado na Se¸ao 6.2.
Adicionalmente, a prote¸ao de uma rede pode ser feita tanto na camada ´optica
quanto na camada eletrˆonica. Por´em, como o objetivo deste trabalho ´e a investiga¸ao
do TGP, que depende do processamento eletrˆonico nos os, os esquemas de prote¸ao
propostos no Cap´ıtulo 6 consideram a prote¸ao realizada pela camada eletrˆonica.
18
2.2 Projeto de Topologia Virtual
Como mencionado, o VTD ´e definido como o conjunto de todos os caminhos ´opticos
que ao configurados entre os os. Caso exista um caminho ´optico transparente
para cada demanda de tr´afego de rede, esta ´e chamada de topologia transparente.
Tais topologias podem se tornar invi´aveis, pois uma rede relativamente grande onde
existe demanda entre todos os os se tornaria extremamente cara. Para exempli-
ficar, uma rede transparente de 15 os com demandas entre todos os pares de os
exige 15 × (15 1) = 210 caminhos ´opticos. Por outro lado, pode-se considerar
uma rede onde os caminhos ´opticos coincidam com os enlaces f´ısicos, de forma que
uma demanda de tr´afego necessite passar por arios caminhos ´opticos at´e atingir
o destino. Essa rede, conhecida como rede opaca, exige que as demandas sofram
convers˜ao ´optico-eletrˆonica, processamento eletrˆonico e convers˜ao eletrˆonico-´optica
nos os intermedi´arios. Nesse cen´ario ´e exigida uma grande quantidade de pro-
cessamento eletrˆonico em todos os os da rede, que por sua vez ´e traduzido em
equipamentos.
Em uma solu¸ao de compromisso entre os dois extremos, redes transparentes e
redes opacas, os caminhos s˜ao acomodados sobre a topologia f´ısica percorrendo um
ou mais enlaces. Por´em, quando conveniente, ´e permitido o processamento eletrˆonico
nos os intermedi´arios. Os trabalhos, encontrados na literatura, tratando desses
cen´arios de redes em como fun¸ao objetivo a minimiza¸ao do congestionamento
[RAM 96, RAM 02, BAN 90], que consiste na carga alocada em um caminho ´optico,
ou o processamento eletrˆonico nos n´os [ALM 06].
2.3 Roteamento e Aloca¸ao de Comprimento de
Onda
O problema de RWA talvez seja um dos problemas relacionados ao projeto de redes
WDM que tenha recebido maior aten¸ao por parte dos pesquisadores desta ´area
[ZAN 00], dado que toda rede usando tecnologia WDM deve dispor de um processo
de RWA para estabelecer uma conex˜ao. Esse problema possui basicamente dois
objetivos: i) acomodar os caminhos ´opticos, provenientes do projeto da topologia
19
virtual sobre a topologia f´ısica; e ii) atribuir os comprimentos de onda a cada enlace,
de forma que um comprimento de onda n˜ao seja atribu´ıdo a dois caminhos ´opticos
em um mesmo enlace.
Os etodos adotados para roteamento basicamente podem usar: um roteamento
pr´e-fixado, com mais de uma rota alternativa pr´e-computada ou rotas adaptativas
[ZAN 00]. Para um esquema de rotas alternativas pr´e-fixadas, m´ultiplas rotas devem
ser consideradas. Nesse esquema, cada o da rede precisa manter uma tabela de
roteamento seguindo uma ordem, por exemplo, primeiro, segundo, at´e o Kesimo
menor caminho. Esse esquema ´e largamente utilizado para aprovisionamento de
conex˜oes dinˆamicas, pela facilidade de controle das rotas e recursos que est˜ao em uso.
No caso do roteamento adaptativo, a rota ´e escolhida dinamicamente dependendo
do estado atual da rede. Apesar de ser o m´etodo mais flex´ıvel, apresenta a grande
desvantagem de ser necess´ario calcular o roteamento a cada requisi¸ao, exigindo uma
grande quantidade de processamento.
Um aspecto importante para o roteamento dos caminhos ´opticos em uma rede
WDM ´e a escolha do comprimento de onda que ser´a usado. Esta escolha possui
a restri¸ao cl´assica da continuidade do comprimento de onda. Caso seja imposta
tal restri¸ao, o caminho ´optico usado para atender a requisi¸ao deve ter o mesmo
comprimento de onda em todos os enlaces f´ısicos ao longo do caminho. Tal restri¸ao
dificulta consideravelmente a disponibilidade de comprimentos de onda para atender
as demandas, o que normalmente aumenta a probabilidade de bloqueio. Por outro
lado, para aumentar a flexibilidade da rede, ´e necess´aria a aquisi¸ao de equipamentos
conversores de comprimento de onda, que ainda ao relativamente caros, ou de
processamento eletrˆonico, que tamb´em n˜ao ´e desej´avel.
2.4 Problema de Grooming de Tafego
Como mencionado em 2.1.1, um sistema SONET/SDH permite que canais WDM
ainda possam multiplexar arios canais de baixas taxas de transmiss˜ao (sub-compri-
mentos de onda). Por´em, essa multiplexa¸ao implica na retirada e inser¸ao de tr´afego
em determinados n´os da rede [ZHU 05], onde ser´a necess´ario introduzir equipamen-
tos do tipo Add-Drop Multiplexer (ADM). Assim, arias requisi¸oes de tr´afego podem
ser agrupadas em um mesmo comprimento de onda. Grooming de tr´afego est´a di-
20
retamente relacionado a um rico conjunto de problemas, incluindo planejamento da
rede, projeto da topologia e aprovisionamento de conex˜oes [ZHU 05]. O TGP pode
ser visto sob duas perspectivas: i) na primeira, tratada na maior parte desse tra-
balho, ´e dada uma matriz de tr´afego e a topologia da rede, o etodo de otimiza¸ao
deve atender todas as demandas minimizando o custo total da rede. ii) e a segunda,
dado um conjunto de recursos e demandas, deve-se maximizar a quantidade total
de demandas atendidas, o throughput da rede. No Cap´ıtulo 7 ´e proposto um modelo
ILP que trata o TGP sob esse ponto de vista.
2.4.1 Arquiteturas de n´os usadas nas redes ´opticas
Para a formaliza¸ao do problema de estudo ´e necess´ario tomar conhecimento dos as-
pectos estruturais que envolvem o mesmo, incluindo as limita¸oes e “facilidades”tecno-
ogicas que nortear˜ao os modelos de otimiza¸ao.
Grooming de tr´afego para Redes em Anel
Em uma rede SONET/SDH tradicional ao usados multiplexadores de inser¸ao e
retirada eletrˆonicos (ADMs), para que os elementos da rede possam inserir e retirar
tr´afego nos canais de alta velocidade. At´e pouco tempo, nas redes SONET/SDH
era necess´ario um ADM para cada comprimento de onda em todos os os da rede.
Contudo, uma fibra ´optica a suporta mais de uma centena de comprimentos de onda,
o que torna extremamente dispendiosa a instala¸ao dessas redes. Atualmente a ´e
poss´ıvel a inser¸ao e retirada de apenas um comprimento de onda espec´ıfico, feito de
forma “passiva”, isto ´e, sem o uso de processamento eletrˆonico. Tais equipamentos
ao chamados de multiplexadores ´opticos de inser¸ao e retirada (OADMs - Optical
Add-Drop Multiplexers). A arquitetura do n´o em um anel SONET/SDH, junto com
a representa¸ao dos ADMs e OADMs, s˜ao apresentados na Figura 2.3.
ADM
ADM
ADM
(b) Com O-ADM
ADM
(a) Sem O-ADM
Figura 2.3: Arquitetura de os com e sem O-ADM para uma rede em anel
SONET/SDH + WDM, adaptada de [ZHU 03]
21
Visto que grande parte do tr´afego em um o ´e de trˆansito (est´a apenas sendo
roteado por este o), e analisados os custos de instala¸ao e manuten¸ao de uma
rede ´optica WDM, fica claro que os componentes de interface eletro-´optico possuem
uma parcela dominante no custo total. Portanto, uma sele¸ao adequada dos locais
de instala¸ao dos ADMs, bem como um arranjo cuidadoso de quais comprimentos
de onda ao inseridos e retirados em cada n´o da rede, e o agrupamento do tr´afego
de maneira conveniente podem diminuir drasticamente os custos de uma rede. A
Figura 2.4 ilustra os elementos de uma rede SONET/SDH com dois an´eis ADM
interconectados por um DXC (Digital Cross-Connect) e TMs (Terminal Multiplexer)
com uma topologia em linha.
Figura 2.4: Ilustra¸ao de uma rede SONET/SDH com an´eis ADM interconectados
por um DXC, adaptada de [SCH 01]
Grooming de Tafego em An´eis Interconectados
Na primeira gera¸ao de redes ´opticas, a topologia predominante foi para redes em
anel SONET + WDM, assumindo a rede como um ´unico anel. Por´em o padr˜ao para
an´eis SDH imp˜oem um limite aximo de 16 os para cada anel [G.7 96]. Assim,
com o crescimento das redes ´opticas, a topologia das redes vem convergindo para
an´eis interconectados em malha. As conex˜oes dos an´eis podem ser feitas atraes da
interse¸ao de um ou dois n´os, Single Node Interconnection (SNI) e Dual Node Inter-
connection (DNI). Em [WAN 02] os autores apresentam quatro arquiteturas de n´os
de interconex˜ao, mostradas na Figura 2.5. Nesse mesmo trabalho foi proposto um
modelo ILP e uma heur´ıstica como etodo de solu¸oes para as arquiteturas apresen-
tadas. Atrav´es desses algoritmos foram comparadas as estrat´egias de interconex˜ao
atrav´es das diferentes restri¸oes impostas por cada uma delas.
Na Figura 2.5 (a) a interconex˜ao dos an´eis ´e feita atrav´es de um DXC, que
22
add/drop local
Anel
A
Anel
B
Anel
B
Anel
A
add/drop local
Anel
B
Anel
A
add/drop local
add/drop local
O-ADM
Switch
eletrônico
MUX/DEMUX
óptico
MUX/DEMUX
SONET
(a)
(b)
(d) (c)
Switch óptico
Figura 2.5: Diferentes arquiteturas para os n´os de interconex˜ao dos an´eis, adaptada
de [WAN 02].
processa o tr´afego para portas locais ou para um SONET MUX/DEMUX, enviando
novamente `a rede atraes de um OADM. Em (b) e (c) ao apresentadas duas arquite-
turas de OXCs, onde (b) ´e totalmente transparente e em (c) ´e feito de forma opaca.
Usando dois OXCs e um DXC, a arquitetura ilustrada em (d) ´e a que promove maior
flexibilidade na interconex˜ao de an´eis.
Grooming de Tafego para Redes em Malha
At´e poucos anos atr´as, a grande maioria dos trabalhos relacionados ao TGP en-
contrados na literatura eram baseados em redes com topologia em anel. Contudo,
recentemente, observa-se uma tendˆencia para o estudo do problema utilizando redes
com topologia em malha. Este fenˆomeno ´e justificado pela implementa¸ao de novos
dispositivos e arquiteturas para os n´os da rede. Mesmo para an´eis interconectados,
tamb´em usando infra-estrutura da primeira gera¸ao de redes ´opticas, ao encon-
23
tradas limita¸oes que dificultam sua escalabilidade. Por exemplo, prejudicando a
acomoda¸ao do tr´afego crescente nessas redes, oferecendo poucas possibilidades de
reroteamento para a prote¸ao e aplica¸oes do tipo multicast (quando a demanda
possui uma origem e mais de um destino).
Em [ZHU 02] o grooming de tr´afego ´e realizado pelo elemento de rede chamado de
G-Fabric que ´e um dispositivo de comuta¸ao eletrˆonica, como os DXCs. Na Figura
2.6 ´e ilustrado como esse recurso ´e interligado a um OXC atrav´es de um conjunto de
transceptores, respons´aveis pela convers˜ao ´optica-eletrˆonica-´optica. Assim, os tran-
sceptores representam tamb´em o n´umero de portas do OXC, que est´a diretamente
relacionado ao custo do equipamento.
Anel B
Anel A
add/drop local
DXC
Figura 2.6: o com capacidade de grooming, adaptada de [WAN 02] e [SOL 07]
Recentemente, novas arquiteturas foram propostas, como na Figura 2.7 apresen-
tada em [SOL 07], que apresenta uma arquitetura de um o h´ıbrido que re´une as
facilidades de um o grooming “cl´assico”e um n´o de anel com um comprimento de
onda destinado a cada n´o. Um monitor de comprimento de onda ´e usado para reti-
rar uma amostra do sinal e encontrar time slots livres dentro de cada canal. Ent˜ao,
posteriormente, as demandas saindo do DXC para a rede ao multiplexadas e o sinal
´e inserido novamente na rede. Uma desvantagem dessa arquitetura ´e a inser¸ao de
atraso do sinal para a sincroniza¸ao do DXC.
Em [COX 01] o problema do projeto da topologia f´ısica e virtual numa rede em
malha WDM ´e descrito de forma a descobrir como conectar os elementos de rede
(OADMs, DXCs ou OXCs) e rotear o tr´afego, para satisfazer todas as demandas e
minimizar o custo total da rede. O custo da rede foi ponderado segundo os custos
da fibra, do sistema WDM utilizado e dos dispositivos. Como m´etodos de solu¸ao,
24
Anel B
Anel A
add/drop local
DXC
Monitor de
comprimento de onda
OXC
Figura 2.7: o h´ıbrido com capacidade de grooming, adaptada de [SOL 07]
ao propostos um modelo ILP e duas meta-heur´ısticas. Como resultado, o trabalho
apresenta uma compara¸ao entre redes em anel e em malha, onde foi mostrado
que as redes em malha possuem uma melhor rela¸ao custo/benef´ıcio para ´areas
razoavelmente grandes, enquanto os an´eis s˜ao mais atrativos para interconex˜oes de
MANs.
2.5 Trabalhos Relacionados
A topologia f´ısica da rede WDM ´e representada por um multigrafo, G = (N, E, W ),
valorado e ao direcionado, onde N ´e o conjunto dos os, E ´e o conjunto dos enlaces
f´ısicos, tal que e E pode suportar um conjunto W de canais ao sobrepostos
(comprimentos de onda). O valor de um enlace pode corresponder `a distˆancia geo-
gr´afica entre os dois n´os ligados por ele. Neste estudo ´e considerado que o valor do
enlace ser´a sempre igual a 1, assim, a distˆancia corresponder´a ao n´umero de saltos.
O n´umero de comprimentos de onda em cada fibra e a capacidade suportada por
cada um deles ´e dada por |W | e C, respectivamente. As requisi¸oes de tr´afego ao
comumente apresentadas em matrizes, podendo ser uma ´unica matriz contendo a
demanda est´atica m´edia entre cada par de os ou uma matriz para cada tipo de
demanda(STM-1, STM-3, STM-12, etc).
Existem na literatura dois etodos asicos para encontrar solu¸oes para o TGP,
25
modelos exatos e heur´ısticos. Por´em, em [CHI 00] e [WAN 00] ´e mostrado que o TGP
pertence `a classe de problemas NP-Completo. Assim, por possuir uma complexidade
exponencial, etodos para encontrar solu¸oes ´otimas ao extremamente restritos ao
tamanho da rede investigada, n˜ao sendo capazes de solucionar redes como mais de
14 os [ALM 06, BAN 01]. Para resolver este problema em redes maiores, arias
heur´ısticas ao facilmente encontradas na literatura, [CHI 00, WAN 00, MUK 01,
ZHA 00, SIM 99]. Como avalia¸ao dos resultados heur´ısticos, podemos citar an´alises
de limite inferior para diferentes crit´erios de tr´afego e modelos de redes [WAN 00,
MUK 01, SIM 99].
2.5.1 Formula¸oes Existentes para o TGP
A implementa¸ao de modelos ILP seguem dois paradigmas de formula¸ao, arco-
caminho ou n´o-arco [PIO 04]: i) no primeiro caso as rotas devem ser previamente
conhecidas e indexadas. Como neste tipo de formula¸ao as vari´aveis tˆem um controle
da rota como um todo, ao a necessidade de uma restri¸ao de continuidade de fluxo,
simplificando computacionalmente o modelo. Por´em, para redes de grande porte
e com um alto grau de liberdade de roteamento, a quantidade de rotas poss´ıveis
ser´a um complicador na implementa¸ao do modelo. ii) para o segundo caso, as
vari´aveis de fluxos de um o conhecem apenas os os adjacentes a ele. Isto implica na
necessidade de uma restri¸ao de continuidade de fluxo, aumentando a complexidade
computacional do modelo. Por outro lado, ao existe o esfor¸co para pr´e-computar
as rotas, e a quantidade de vari´aveis de fluxo ´e igual ao n´umero de enlaces.
No Cap´ıtulo 3 ao propostos dois modelos ILP, usando os dois paradigmas de
formula¸ao. Tais modelos s˜ao usados como base para o restante dos estudos desen-
volvidos neste trabalho. Para futuras compara¸oes, a seguir ao apresentados alguns
dos principais modelos encontrados na literatura.
Em [ZHU 02], os autores prop˜oem um modelo para o TGP com uma formula¸ao
o-arco. Como ´e mostrado mais adiante, o trabalho considera um conjunto de
matrizes de requisi¸oes, uma para cada granularidade de tr´afego. Sobre uma rede
irregular e fixando o n´umero de transceptores em cada n´o, o objetivo dos modelos ´e
maximizar o n´umero de conex˜oes realizadas com sucesso (throughput da rede). Antes
de mostrar as express˜oes do modelo, ´e apresentada a nota¸ao usada no trabalho:
26
m e n os conectados por um enlace f´ısico.
i e j os de origem e termina¸ao, respectivamente, de um caminho ´optico. Aqui
um caminho ´optico pode percorrer um ou m´ultiplos enlaces f´ısicos.
s e d os de fonte e destino de uma requisi¸ao. Uma requisi¸ao de tr´afego pode
atravessar um ou arios caminhos ´opticos. A Figura 2.8 esclarece como uma
requisi¸ao pode ser atendida.
y A granularidade das requisi¸oes de tr´afego, y 1, 3, 12, 48.
t Indica quantas requisi¸oes do tipo OC-y ´e requerida entre o par (s, d).
Figura 2.8: Ilustra¸ao de uma conex˜ao
Dados do problema:
N N´umero de n´os da rede
W N´umero de comprimentos de onda por fibra. Foi assumido que todas as fibras
possuem o mesmo n´umero de comprimentos de onda.
P
mn
Matriz de adjacˆencias da topologia f´ısica.
P
w
mn
Indica a existˆencia do comprimento de onda w na fibra P
mn
.
T R
i
N´umero de transmissores no n´o i.
RR
i
N´umero de receptores no o i. Nesse trabalho foi considerado que os transceivers
ao todos ajust´aveis para qualquer comprimento de onda em W .
C Capacidade de um comprimento de onda.
Λ O conjunto das matrizes de tr´afego, Λ = {Λ
y
}.
Vari´aveis:
27
V
ij
N´umero de caminhos ´opticos entre os n´os i e j.
V
w
ij
N´umero de caminhos ´opticos entre os os i e j no comprimento de onda w.
Note que, se V
w
ij
> 1 indica que os caminhos ´opticos entre i e j sobre o
comprimento de onda w pode ter diferentes caminhos.
P
ij,w
mn
N´umero de caminhos ´opticos entre os os i e j roteado pelo enlace f´ısico (m, n)
sobre o comprimento de onda w.
λ
sd,t
ij,y
´
E o t-´esimo OC-y do n´o s para d passando pelo caminho ´optico (i, j).
S
y,t
sd
´
E um bin´ario, igual a 1 se o tesimo OC-y do o s para d foi roteado com
sucesso, e zero caso contr´ario.
As vari´aveis podem ser divididas em grupos da seguinte forma: V
ij
e V
w
ij
como
vari´aveis de topologia virtual, P
ij,w
mn
como vari´avel de roteamento na topologia f´ısica,
e λ
sd,t
ij,y
e S
y,t
sd
como vari´aveis de roteamento de tr´afego.
O objetivo adotado nesse trabalho foi maximizar o n´umero total de requisi¸oes
de baixa velocidade roteadas com sucesso.
Maximize:
y,s,d,t
y × S
y,t
sd
(2.1)
A seguir s˜ao apresentados os grupos de restri¸oes da formula¸ao.
Restri¸oes de topologia virtual:
j
V
ij
T R
i
i (2.2)
i
V
ij
RR
j
j (2.3)
w
V
w
ij
= V
ij
i, j (2.4)
V
w
ij
, V
ij
Z. (2.5)
28
Restri¸oes de roteamento da topologia f´ısica:
m
P
ij,w
mk
=
n
P
ij,w
kn
ifk = i, j i, j, w, k (2.6)
m
P
ij,w
mi
= 0 i, j, w (2.7)
n
P
ij,w
jn
= 0 i, j, w (2.8)
n
P
ij,w
in
= V
w
ij
i, j, w (2.9)
m
P
ij,w
mj
= V
w
ij
i, j, w (2.10)
i,j
P
ij,w
mn
P
w
mn
m, n, w (2.11)
P
ij,w
mn
{0, 1}. (2.12)
Restri¸oes de tr´afego na topologia virtual:
i
λ
sd,t
id,y
= S
y,t
sd
s, d y {1, 3, 12, 48} t [1, Λ
y,sd
] (2.13)
j
λ
sd,t
sj,y
= S
y,t
sd
s, d, t y {1, 3, 12, 48} t [1, Λ
y,sd
] (2.14)
i
λ
sd,t
ik,y
=
j
λ
sd,t
kj,n
ifk = s, d s, d, k, t (2.15)
i
λ
sd,t
is,y
= 0 s, d y {1, 3, 12, 48} t [1, Λ
y,sd
] (2.16)
j
λ
sd,t
dj,y
= 0 s, d y {1, 3, 12, 48} t [1, Λ
y,sd
] (2.17)
y,t
s,d
y × λ
sd,t
ij,y
V
ij
× C i, j (2.18)
S
y,t
sd
{0, 1}. (2.19)
As equa¸oes anteriores ao baseadas no princ´ıpio da conservao de fluxo e re-
cursos. A seguir ´e apresentada uma breve explica¸ao para cada restri¸ao.
29
As express˜oes 2.2 e 2.3 asseguram que o n´umero de caminhos ´opticos entre os
os (i, j) seja menor ou igual ao n´umero de transmissores e receptores dos os
i e j, respectivamente.
A express˜ao 2.4 mostra que os caminhos ´opticos entre (i, j) podem usar dife-
rentes comprimentos de onda entre (i, j).
A restri¸ao de conservao de fluxo est´a expressa em 2.6-2.10, sendo que a
express˜ao 2.6 assegura que o tr´afego que entra ´e igual ao que sai, em um
o intermedi´ario k do caminho ´optico (i, j) no comprimento de onda w. A
express˜ao 2.7 garante que em um o de origem i do caminho ´optico (i, j) no
comprimento de onda w ao a entrada de tr´afego; analogamente, 2.8 garante
que um o de ermino ao possui escoamento de tr´afego. A express˜ao 2.9
assegura que no o de origem i do caminho ´optico (i, j) para um comprimento
de onda w a quantidade de caminhos ´opticos saindo ´e igual a soma de todos os
caminhos ´opticos (i, j) sobre o comprimento de onda w; analogamente, temos
para entrada de tr´afego nos n´os de t´ermino, 2.10.
Para assegurar que ser´a usado apenas um comprimento de onda w no enlace
f´ısico (m, n) foram usadas as express˜oes 2.11 e 2.12
As express˜oes 2.13-2.19 ao respons´aveis pelo roteamento e agrega¸ao do tr´afego
de baixa velocidade sobre a topologia virtual, sem exceder a capacidade do
comprimento de onda.
O modelo apresentado em [ZHU 02] est´a entre os modelos mais completos encon-
trados na literatura. Por´em, devido `a complexidade dos modelos, ele ´e extremamente
restrito ao tamanho da rede. Os autores apresentam solu¸oes ´otimas apenas para
redes de 6 os e sugerem uma heur´ıstica para redes maiores. Assim, a exemplo desse
modelo e de outros que s˜ao apresentados a seguir, conclui-se que para a formula¸ao
de um modelo ILP para o TGP, ao necess´arios alguns cuidados para que tal modelo
possa resolver problemas em redes com mais de 10 os [HU 04]. Dentre as oes
mais simples a serem tomadas para aumentar a escalabilidade dos modelos pode-se
citar: o particionamento do problema, a relaxa¸ao de algumas vari´aveis e imposi¸ao
de restri¸oes para a redu¸ao do espa¸co de busca das vari´aveis. Os modelos propostos
neste trabalho utilizam algumas dessas estrat´egias. Por exemplo, ao ines de inserir
novas vari´aveis para o roteamento dos caminhos ´opticos, a exemplo do que foi feito
em [ZHU 02], isso pode ser realizado por um m´etodo externo ao modelo.
30
Outro trabalho semelhante foi apresentado em [DUT 02a]. Por´em, essa for-
mula¸ao foi usada apenas como recurso para ilustra¸ao do problema, e nenhum
exemplo foi resolvido usando a formula¸ao. A seguir ao apresentadas a nota¸ao,
express˜oes e descri¸oes.
Dados do problema:
p
lm
Indica se o enlace (l, m) existe ou n˜ao na topologia f´ısica.
C
´
E definido como a capacidade do comprimento de onda.
t
(sd)
´
E a demanda de tr´afego entre os os (s, d) (assim, a matriz de tr´afego ´e
representada por T = [t
(sd)
]).
W
´
E o n´umero m´aximo de comprimentos de onda suportado por um enlace.
onde i, j, s, d, l, m {0, . . . , N 1} e w {0, . . . , W 1}.
Vari´aveis:
b
ij
N´umero de caminhos ´opticos do n´o i para o n´o j.
b
ij
(l, m) N´umero de caminhos ´opticos que passam no enlace f´ısico (l, m).
c
(w)
ij
(l, m)
´
E um bin´ario igual a 1, se o caminho ´optico ij usa o comprimento de onda
(w) no enlace f´ısico (l, m), e zero caso contr´ario.
t
ij
representa a quantidade de tr´afego agregado no caminho ´optico de i para j.
t
(sd)
ij
Corresponde a parcela da demanda de sd (t
(sd)
) em t
ij
.
Diferentemente do modelo anterior, nesse foram sugeridas trˆes fun¸oes objetivos.
A minimiza¸ao do n´umero de caminhos ´opticos:
min :
ij
b
ij
(2.20)
A minimiza¸ao da quantidade de comutadores eletrˆonicos:
min :
s,d,i,j
t
(sd)
ij
s,d
t
(sd)
(2.21)
31
A maximiza¸ao do n´umero de caminhos ´opticos em um n´o:
max
i
(max(
j
b
ji
,
j
b
ij
)) (2.22)
Restri¸oes de topologia f´ısica:
b
ij
(l, m) b
ij
p
lm
, i, j, l, m (2.23)
c
(w)
ij
(l, m) p
lm
, i, j, k, l, m (2.24)
Restri¸oes de roteamento dos caminhos ´opticos:
N1
l=0
b
ij
(m, l)
N1
l=0
b
ij
(l, m) =
b
ij
se m = i
b
ij
se m = j
zero caso contr´ario
m, i, j (2.25)
ij
b
ij
(l, m) w l, m (2.26)
Restri¸oes de atribui¸ao do comprimento de onda no caminho ´optico:
W 1
k=0
c
(w)
ij
(l, m) = b
ij
(l, m) i, j, l, m (2.27)
i,j
c
(w)
ij
(l, m) 1 k, l, m (2.28)
N1
l=0
c
(w)
ij
(m, l) =
N1
l=0
c
(k)
ij
(l, m)
b
ij
se m = i
b
ij
se m = j
zero caso contr´ario
i, j, k, m (2.29)
Restri¸oes do roteamento de tr´afego:
t
ij
=
s,d
t
(sd)
ij
i, j (2.30)
t
ij
= b
ij
C i, j (2.31)
N1
j=0
t
(sd)
ij
N1
j=0
t
(sd)
ji
=
t
(sd)
se i = s
t
(sd)
se i = d
zero caso contr´ario
i, j (2.32)
32
A express˜ao 2.23 garante que um caminho ´optico ser´a roteado apenas por
enlaces f´ısicos existentes.
A express˜ao 2.24 assegura que, se existe um comprimento de onda k sendo
usado no enlace (l, m) pelo caminho ´optico (i, j), ent˜ao a existˆencia do enlace
(l, m) deve ser garantida .
As express˜oes 2.25, 2.29 e 2.32 correspondem `a conservao dos caminhos
´opticos e do fluxo. Em 2.25 ´e garantido que nenhum caminho ´optico ser´a
criado ou perdido durante o caminho de i para j. Para a continuidade do
comprimento de onda ao longo do caminho de i para j foi usada a express˜ao
2.29. E 2.32 ´e a cl´assica restri¸ao de conservao de fluxo.
Em 2.26 ´e garantido que a somat´oria dos caminhos ´opticos no enlace (l, m)
ao deve exceder o n´umero m´aximo de comprimentos de onda de um enlace.
Em 2.27 ´e garantido que o n´umero de caminhos ´opticos de i para j no enlace
(l, m) ´e igual a quantidade de comprimentos de onda no enlace (l, m) referentes
ao caminho ´optico de i para j.
2.28 garante que para um dado comprimento de onda em um enlace (l, m)
deve existir no m´aximo um caminho ´optico passando por esse canal.
A restri¸ao de agrega¸ao de tr´afego 2.30 mostra que a quantidade de tr´afego
do caminho ´optico ij ´e a soma das demanda sd roteadas por ij (T
(sd)
ij
).
Garantindo o limite da capacidade do comprimento de onda temos a restri¸ao
2.31.
Mais recentemente, foram propostos em [HU 04] dois modelos para o grooming de
tr´afego, onde foi considerado um roteamento com e sem atribui¸ao de comprimentos
de onda. Ainda ´e proposta uma heur´ıstica para a atribui¸ao de comprimento de
onda para o caso do roteamento sem essa atribui¸ao. A rede nesse trabalho, ´e
representada por dois grafos, G
f
= (V
f
, E) e G
o
= (V
o
, L), onde V
f
´e o conjunto de
os adjacentes da camada f´ısica interconectados por um elemento de E (conjunto de
enlaces f´ısicos), e V
o
o conjunto de os adjacentes da camada ´optica interconectados
por um caminho ´optico do conjunto L. A seguir ao apresentadas a nota¸ao da
formula¸ao, as express˜oes do modelo e descri¸ao de cada restri¸ao. Estrat´egia similar
a essa foi usada no Cap´ıtulo 4 e Se¸ao 6.3, onde se trata de redes transl´ucidas. Por´em,
33
para aumentar a escalabilidade do etodo, no Cap´ıtulo 4 os caminhos ´opticos ao
pr´e-roteados por uma heur´ıstica e o modelo ILP trata cada caminho ´optico como
uma conex˜ao transparente fim-a-fim. Na Se¸ao 6.3 ao usados dois modelos ILP,
um para rotear o tr´afego sobre os caminhos ´opticos e outro para rotear os caminhos
´opticos sobra a topologia f´ısica e atribuir-lhes comprimentos de onda.
W
´
E o n´umero m´aximo de comprimentos de onda suportado por um enlace.
D Conjunto de demandas.
s
d
Tamanho da demanda d D.
C Capacidade do comprimento de onda.
A = [a
v,l
]
|V
o
|×|L|
, onde a
v,l
= 1 se o caminho ´optico l se origina no o v, -1 se l
termina no n´o v e 0 caso contr´ario.
B = [b
e,l
]
|E|×|L|
, onde b
e,l
= 1 se caminho ´optico l passa pelo enlace f´ısico e e 0
caso contr´ario.
u
d
= [u
v,d
]
vV
o
, onde u
v,d
= 1 se o v ´e o n´o de origem da demanda d, -1 se ´e o n´o
de destino e 0 caso contr´ario.
x
d
= [x
l,d
]
lL
, onde x
l,d
= 1 se a demanda d passa pelo caminho ´optico l e 0 caso
contr´ario.
y
w
= [y
l,w
]
lL
, onde y
l,w
= 1 se o comprimento de onda w ´e atribu´ıdo ao caminho
´optico l e 0 caso contr´ario.
1 ´e o vetor unit´ario, [1, 1, ..., 1].
A fun¸ao objetivo adotada ´e a de minimiza¸ao do umero de comprimentos de
onda, sendo considerado como equivalente `a minimiza¸ao do n´umero de transcep-
tores. O modelo a seguir fornece uma solu¸ao para o TGP e RWA.
Minimize:
wW,lL
y
l,w
(2.33)
Restri¸oes:
Ax
d
= u
d
d D (2.34)
34
By
w
1 w W (2.35)
dD
s
d
x
l,d
C
wW
y
l,w
l L (2.36)
Descri¸ao das restri¸oes:
A equa¸ao 2.34 garante que um caminho ´optico selecionado para atender uma
demanda d, constitui um caminho que inicia no o origem de d e termina no
o de destino de d.
A express˜ao 2.35 implica que cada caminho ´optico ter´a um ´unico comprimento
de onda.
A express˜ao 2.36 restringe a capacidade do caminho ´optico l.
Para o mesmo problema, por´em sem a atribui¸ao dos comprimento de onda,
´e ainda definido o vetor t = [t
l
]
lL
, onde t
l
´e a quantidade de comprimento de
onda necess´arios no caminho ´optico l L. As express˜oes desta formula¸ao ao
apresentadas como:
Minimize:
lL
t
l
(2.37)
Restri¸oes:
Ax
d
= u
d
d D (2.38)
Bt |W |1 (2.39)
dD
s
d
x
l,d
Ct
l
l L (2.40)
Note que segundo as defini¸oes feitas no trabalho, cada caminho ´optico l foi
tratado como uma conex˜ao, sendo que a escolha e o roteamento destes caminhos
foram assumidos como previamente resolvidos. Para apresentar resultado para redes
de grande porte (redes com mais de 40 os) foi usado um n´umero reduzido de
demandas (uma matriz de tr´afego esparsa).
Por fim, os modelos aqui apresentados permitem uma maior compreens˜ao do
TGP e servem como compara¸ao com os modelos propostos no pr´oximo cap´ıtulo.
35
Vale lembrar que a proposi¸ao dos novos modelos ´e motivada pela dificuldade de
se adaptar um dos modelos existentes na literatura aos estudos desenvolvidos no
restante do trabalho. Essas dificuldades podem ser enumeradas basicamente pela
grande complexidade dos modelos, que impossibilitam a investiga¸ao de redes maiores
e tamb´em pela dificuldade de reprodu¸ao de resultados.
Cap´ıtulo 3
Modelos ILP para o Problema de
Grooming de Tafego
Neste cap´ıtulo ao propostos dois modelos ILP para o problema de grooming de
tr´afego juntamente com a atribui¸ao dos comprimentos de onda. Adicionalmente,
ao apresentados alguns estudos de casos relacionados a esse problema, por exemplo,
restri¸oes espec´ıficas para o roteamento de uma rede multi-anel. Como resultados
num´ericos s˜ao apresentadas compara¸oes entre os modelos propostos.
3.1 Introdu¸c˜ao
O TGP, como a mencionado, ´e definido na literatura como o problema de combinar
demandas de tr´afego de baixa velocidade em canais de alta capacidade [HU 04].
Para isso, ao utilizadas as t´ecnicas de multiplexa¸ao existentes nas redes ´opticas.
As propostas para encontrar solu¸oes para o TGP ao divididas basicamente em dois
m´etodos: pela solu¸ao de modelos matem´aticos (usando formula¸oes ILP - integer
linear programming e MILP - mixed integer linear programming) e heur´ısticas. Neste
cap´ıtulo ao propostos dois modelos ILP com o intuito de encontrar solu¸oes para
tal problema, incluindo alguns estudos de casos. A proposi¸ao de novos modelos,
que ao usados como base para os estudos realizados no restante do trabalho, ´e mo-
tivada pelos seguintes fatos: alguns dos trabalhos encontrados na literatura apresen-
tam resultados num´ericos dos modelos imposs´ıveis de serem reproduzidos, por n˜ao
apresentarem a topologia investigada ou a matriz de demandas, [JAE 07, HU 04];
a trabalhos onde os modelos propostos s˜ao usados apenas como uma formaliza¸ao
36
37
ilustrativa do problema investigado [COX 01, DUT 02a]; e encontram-se ainda for-
mula¸oes, que apesar de serem relativamente completas, ao incapazes de resolver,
em tempo vi´avel, redes com mais de 8 n´os [ZHU 02].
3.1.1 Trabalhos Relacionados e Contribui¸oes
A primeira formaliza¸ao para o TGP usando modelos matem´aticos, segundo seus au-
tores, foi proposto em [MUK 01]. Nesse trabalho ao apresentados dois modelos ILPs
para redes em anel usando tecnologia SONET/SDH, onde ambos os modelos em
como fun¸oes objetivo a minimiza¸ao do umero de ADMs. Tamb´em minimizando
os custos de instala¸ao de uma rede em anel, por´em de forma indireta, os modelos
propostos em [DUT 01, DUT 02b] buscam minimizar o n´umero de caminhos ´opticos
instalados. Como mencionado, devido ao crescimento das redes ´opticas, os traba-
lhos mais atuais consideram redes com topologias em malha e/ou em multi-anel.
Como exemplo de modelos tratando do TGP para redes em malhas pode-se citar
os modelos em [ZHU 02, DUT 02a, HU 04], apresentados e discutidos no cap´ıtulo
anterior. Dentre os trabalhos tratando de topologia multi-anel, pode-se destacar
[WAN 02, FAR 02], que discutem diferentes arquiteturas de n´os para interconex˜ao
de an´eis. Comparando as topologias em malha e multi-anel tem-se [BOW 05] e
[BIN 00], onde o primeiro apresenta um estudo anal´ıtico dos custos dessas duas
topologias e o segundo prop˜oe modelos ILPs para a sobrevivˆencia em redes ´opticas
totalmente transparentes.
Segundo [DUT 02a], o problema de encaminhamento do tr´afego nas redes ´opticas,
na sua forma completa, ´e a solu¸ao em conjunto dos seguintes sub-problemas: o
VTD, para a escolha dos caminhos ´opticos entre os os; o RWA, para o rotea-
mento e atribui¸ao dos comprimentos de onda aos caminhos ´opticos sobre os enlaces
f´ısicos; e o TGP para o roteamento das demandas de tr´afego sobre os caminhos
´opticos. Contudo, como visto em [ZHU 02], um modelo exato contemplando todas
as restri¸oes para este problema ´e invi´avel para redes reais. Assim, ao longo deste
trabalho os problemas de TGP, RWA e VTD ao investigados, ora independentes
ora juntos. Por exemplo, neste cap´ıtulo ao propostos modelos considerando o prob-
lema de TGP com e sem a aloca¸ao dos comprimentos de onda, a no Cap´ıtulo 4
´e proposta uma solu¸ao h´ıbrida para a configura¸ao de uma rede ´optica, dentro do
escopo do VTD, RWA e TGP.
38
Este cap´ıtulo se prop˜oe as estudar a t´ecnicas de modelamento para o problema do
projeto das redes ´opticas, em especial o TGP. Para isso s˜ao propostos dois modelos
ILP para o TGP com atribui¸ao de comprimentos de onda: usando os paradigmas de
formula¸ao de redes o-arco(NA) e arco-caminho (AC). Junto dos modelos tamb´em
ao apresentadas adapta¸oes para alguns estudos de caso. Por exemplo, modelos
contemplando apenas o TGP (sem atribui¸ao de comprimento de onda), que podem
ser usado para redes maiores, e restri¸oes de roteamento, usadas para comparar
redes com topologia em malha e multi-anel. Nos resultados num´ericos, al´em da
an´alise dos arios cen´arios de rede, ´e mostrado o tipo de modelo que melhor se
adapta para cada um desses cen´arios. Adicionalmente, tais observoes a indicam
qual formula¸ao ´e usada em cada estudo (cap´ıtulo) no restante deste trabalho.
3.2 Modelos ILP para o Problema de Grooming de
Tafego
Nesta se¸ao ao apresentados os dois modelos de programa¸ao linear inteira, com
as formula¸oes o-arco e arco-caminho. Ambos considerando as mesmas restri¸oes,
por´em, com as devidas altera¸oes nas vari´aveis para assimilar as diferentes for-
mula¸oes do problema.
3.2.1 Formula¸ao N´o-Arco (NA)
A Figura 3.1 ilustra algumas possibilidades do grooming de tr´afego em um o. Nessa
figura ao representados: o tr´afego destinado ao o i, o tr´afego gerado por ele, e
o tr´afego processado no o. A fibra de entrada e sa´ıda possui trˆes comprimentos
de onda, que por sua vez podem suportar arias demandas de baixa velocidade.
Note que o o i retira da rede todo o tr´afego destinado a ele (representado por
d = i) e adiciona o tr´afego gerado por ele (representado por s = i). A agrega¸ao de
tr´afego, que caracteriza o problema de grooming de tr´afego, pode ser observada nos
comprimentos de onda 1 e 2, de entrada e sa´ıda do o, e ´e explicitado pelas vari´aveis
C
sd
ij,1
e X
ij,1
, descritas posteriormente.
Nota¸ao matem´atica utilizada no modelo:
39
s = i d = i
id
ij
C
1,
1,ij
X
i
DXC
w = 1
w = 2
w = 3
w = 1
w = 2
w = 3
Figura 3.1: Ilustra¸ao para o grooming de tr´afego no n´o i
i e j ao os adjacentes da rede, ligados por uma conex˜ao bidirecional representada
por ij e ji. Para o caso das redes opacas, tratado neste cap´ıtulo, ij e ji
representam um par de fibras entre os n´os i e j. Contudo, o modelo pode ser
facilmente estendido para redes com m´ultiplos pares de fibras, bastando para
isso a inser¸ao de um novo ´ındice para a diferencia¸ao dos pares de fibras.
s e d ao, respectivamente, os n´os de origem e destino de uma demanda.
w ´e um comprimento de onda pertencente ao conjunto W .
Dados do problema:
E[i][j]: representa a matriz de adjacˆencias, descrevendo as liga¸oes de uma topologia
f´ısica.
|N| n´umero de n´os da rede, ou seja, a quantidade de elementos de conjunto N.
|W | n´umero m´aximo de comprimentos de onda suportado por um enlace.
traf[s][d]: representa a matriz de tr´afego, onde o elemento da linha s e coluna d representa
a demanda de tr´afego com origem em s e destino em d.
C quantidade m´axima de tr´afego transportado por um comprimento de onda.
Vari´aveis:
X
ij,w
´e a quantidade de tr´afego no enlace ij sobre o comprimento de onda w (re-
presentado na Figura 3.1).
40
XB
ij,w
´e uma vari´avel bin´aria igual a 1, se o comprimento de onda w ´e usado no enlace
ij, e zero caso contr´ario. Esta vari´avel ´e usada para contabilizar a existˆencia
do comprimento de onda no enlace ij.
C
sd
ij,w
´e a quantidade de tr´afego no comprimento de onda w do enlace ij, o qual tem
como origem e destino o par sd (representado na Figura 3.1).
D
sd,w
´e a fra¸ao da demanda de tr´afego (traf[s][d]) sobre o comprimento de onda w.
OEO
i
vari´avel com o umero de convers˜oes ´optico-eletrˆonico-´optico (transceptores)
em cada n´o i.
Tendo a definidas as vari´aveis C
sd
ij,w
e X
ij,w
, pode-se voltar a Figura 3.1 para a
visualiza¸ao da utiliza¸ao dessas vari´aveis. Note que X
ij,1
(a quantidade de tr´afego
no enlace ij sobre o comprimento de onda 1) recebe tr´afego de duas origens, uma
demanda proveniente do comprimento de onda 1 e que ´e processada eletronicamente
para ser agregada a outra proveniente do o i. Como aqui i = s, esta demanda ´e
apresentada por C
id
ij,1
.
Fun¸oes objetivo: Dentro do contexto de minimiza¸ao de custos existem arias
abordagens, como, por exemplo, a minimiza¸ao de caminhos ´opticos em uma topolo-
gia virtual ou a minimiza¸ao de comprimentos de onda em uma rede opaca. Neste
trabalho ao consideradas as seguintes fun¸oes objetivo: i) minimizar o n´umero total
de transceptores (3.1); ii) e minimizar a quantidade de transceptores no pior caso,
i.e., o n´o com o maior n´umero de transceptores (3.2).
min :
i
OEO
i
(3.1)
min : max{OEO
i
} (3.2)
Restri¸oes:
C × XB
ij,w
X
ij,w
, i, j, w; E[i][j]=1 e w W (3.3)
sd
C
sd
ij,w
= X
ij,w
, i, j, w; E[i][j]=1 e w W (3.4)
41
w
D
sd,w
= traf[s][d], s, d; s = d (3.5)
j
C
sd
ij,w
j
C
sd
ji,w
=
D
sd,w
se i = s
D
sd,w
se i = d
zero se i = s e i = d
s, d, i, w; s = d e w W (3.6)
j
w
XB
ij,w
= OEO
i
, i (3.7)
X
ij,w
Z
+
, : i, j, w; E[i][j]=1 e w W (3.8)
C
sd
ij,w
Z
+
, s, d, i, j, w; s = d, E[i][j]=1 e w W (3.9)
D
sd,w
Z
+
, s, d, w; s = d e w W (3.10)
OEO
i
Z
+
, i (3.11)
XB
ij,w
{0, 1}, i, j, w; E[i][j]=1 e w W (3.12)
Descri¸ao do modelo matem´atico:
Esse modelo tem como fun¸ao objetivo a minimiza¸ao do n´umero de transcep-
tores e assim, pela restri¸ao (3.7), reduzindo tamb´em o n´umero de comprimentos
de onda usados nos enlaces, representado pela vari´avel XB
ij,w
. A express˜ao (3.3)
indica que caso exista algum tr´afego sendo roteado pelo comprimento de onda w no
enlace ij, representado por X
ij,w
, obrigatoriamente a vari´avel XB
ij,w
deve assumir
o valor 1. Assim, tal express˜ao ´e usada para estabelecer a rela¸ao entre as vari´aveis
X
ij,w
e XB
ij.w
. Al´em disso, como C ´e o parˆametro indicando a capacidade do com-
primento de onda, a restri¸ao (3.3) tamb´em assegura que a quantidade de tr´afego
em um comprimento de onda n˜ao exceder´a a capacidade do mesmo.
A express˜ao (3.4) pode ser chamada de restri¸ao de grooming de tr´afego. A
somat´oria de C
sd
ij,w
sobre sd indica que todas as demandas que tiverem alguma fra¸ao
de tr´afego sendo roteado pelo comprimento de onda w e enlace ij ao agregadas e
atribu´ıdas `a vari´avel X
ij,w
. Assim, essa restri¸ao permite o agrupamento de tr´afego,
que ´e um dos principais objetivos do grooming de tr´afego.
A restri¸ao (3.5) permite que uma demanda de tr´afego seja fracionada e roteada
42
usando mais de um comprimento de onda. Adicionalmente, tal restri¸ao assegura
que a demanda de tr´afego sd sobre todos os comprimentos de onda ser´a igual a
demanda da tr´afego (traf[s][d]), garantindo que todo tr´afego ´e atendido.
Nas equa¸oes (3.6) tem-se a cl´assica restri¸ao de conservao de fluxo. A diferen¸ca
entre as somat´oria, do lado esquerdo da igualdade, indica a quantidade de tr´afego
de todas as demandas sd, que est´a entrando ou saindo de um determinado o i.
Caso i seja igual a s, a somat´oria de todo tr´afego entrando ou saindo de s deve ser
igual `a fra¸ao dessa demanda distribu´ıda em cada comprimento de onda. Caso o n´o
ao seja nem origem e nem destino da demanda, enao a somat´oria das parcelas de
tr´afego deve ser igual a zero, pois o tr´afego ´e apenas de passagem nesse o. Para
o caso de i ser igual `a d, ent˜ao a explica¸ao ´e an´aloga ao caso de i = s, por´em, a
demanda aqui recebe o sinal negativo, que a um sentido ao fluxo do tr´afego. Assim,
assegura-se que toda demanda ´e inserida na rede apenas no o de origem e retirado
apenas no n´o de destino.
Na restri¸ao (3.7), as somat´orias de XB
ij,w
em j e w indicam a quantidade de
canais usados para interligar o o i `a todos os outros os fisicamente adjacentes.
Assim essa restri¸ao ´e usada para contabilizar o n´umero de transceptores existentes
no n´o i.
As express˜oes (3.8), (3.9), (3.10) e (3.11) representam as restri¸oes de ao-
negatividade e integralidade das vari´aveis X
ij,w
, C
sd
ij,w
, D
sd,w
e OEO
i
, respectiva-
mente. A restri¸ao (3.12) garante que a vari´avel XB
ij,w
´e bin´aria.
3.2.2 Formula¸ao Arco-Caminhos (AC)
Outra forma de representar o mesmo problema relaciona um caminho entre um
par de os fonte e destino aos enlaces usados por esse caminho, formula¸ao AC.
Como esta representa¸ao admite o conjunto de caminhos poss´ıveis como um dado
de entrada, ´e necess´ario um esfor¸co adicional de implementa¸ao para calcular tais
caminhos e relacion´a-los aos enlaces usados. Sendo assim, al´em dos dados de entrada
a definidos, aqui s˜ao necess´arios os seguintes elementos:
Dados do Problema:
R
sd
conjunto com as rotas entre um par sd. Neste trabalho, as palavras “rota”e
43
“caminho”s˜ao tratados como sinˆonimos.
r ´ındice que identifica uma rota (r R
sd
).
δ
sd
ij,r
parˆametro que relaciona os enlaces aos candidatos a caminho para cada de-
manda. Assume 1 se o enlace ij ´e usado pela rota r para transmitir a demanda
de tr´afego sd, e 0 caso contr´ario. Esse parˆametro ´e obtido atrav´es de um al-
goritmo que calcula e indexa as k rotas com o menor umero de saltos entre
todos os pares de os. Existem na literatura arios algoritmos capazes de cal-
cular esse conjunto de rotas. Neste trabalho, foi utilizado o Algoritmo de Yen
[YEN 71].
Al´em dos parˆametros a mencionados, no pr´oximo modelo deve ser retirada a
vari´avel D
sd,w
e inserida uma nova vari´avel de configura¸ao da rede, definida a
seguir:
Vari´aveis
C
sd
r
´e a quantidade de tr´afego que tem como origem e destino o par de n´os sd e ´e
transmitida atrav´es da rota r.
Observe que C
sd
r
substitui a vari´avel de fluxo C
sd
ij,w
. Al´em disso, como a vari´avel
D
sd,w
est´a diretamente relacionada `a conservao do fluxo na restri¸ao 3.6, que n˜ao
´e usada no pr´oximo modelo.
Ser˜ao usadas como fun¸oes objetivo as express˜oes (3.1) e (3.2), respectivamente,
assim como no modelo anterior.
min :
i
OEO
i
min : max{OEO
i
}
Restri¸oes: Note que as duas primeiras restri¸oes j´a foram definidas no modelo
NA, em 3.3 e 3.7, respectivamente.
C × XB
ij,w
X
ij,w
, : i, j, w; E[i][j]=1 e w W (3.13)
44
j
w
XB
ij,w
= OEO
i
, i (3.14)
r
C
sd
r
= traf[s][d], s, d; s = d (3.15)
sd
r
δ
sd
ij,r
× C
sd
r
=
w
X
ij,w
, i, j; E[i][j]=1 (3.16)
X
ij,w
Z
+
, i, j, w; E[i][j]=1 e w W (3.17)
C
sd
r,w
Z
+
, s, d, r, w; s = d, r R
sd
e w W (3.18)
OEO
i
Z
+
, i (3.19)
XB
ij,w
{0, 1}, i, j, w; E[i][j]=1 e w W (3.20)
Descri¸ao do modelo matem´atico:
Note que as duas primeiras restri¸oes, (3.13) e (3.14), ao equivalente `as restri¸oes
(3.3) e (3.7), respectivamente. Ainda comparando com o modelo NA, tem-se que as
restri¸oes (3.4) e (3.5) ao substitu´ıdas respectivamente por (3.16) e (3.15). Como
o tipo de formula¸ao AC possui as poss´ıveis rotas pr´e-computadas, ao existe a
necessidade do uso de restri¸oes para assegurar a continuidade de fluxo.
A equa¸ao (3.15) mostra que a somat´oria das partes de uma demanda sd para
todas as rotas, deve ser igual `a demanda de tr´afego sd. Isto assegura que todo o
tr´afego ´e atendido. Por´em, diferente do que foi feito no modelo NA, no modelo
AC a divis˜ao da demanda ´e feita primeiramente nas diferentes rotas, pela restri¸ao
(3.15), e em seguida nos comprimentos de onda, com a restri¸ao (3.16).
A equa¸ao (3.16) ´e an´aloga `a restri¸ao (3.4), que possibilita o agrupamento de
tr´afego nos comprimentos de onda. Na restri¸ao (3.16), para cada enlace ij, o
parˆametro de entrada δ
sd
ij,r
seleciona as rotas das demandas que agregam tr´afego no
enlace ij, distribuindo, assim, essas demandas nos comprimentos de onda.
O conjunto de restri¸oes (3.17), (3.18) e (3.19) asseguram a ao negatividade e
integralidade das vari´aveis C
sd
r,w
, X
ij,w
e OEO
i
, respectivamente, e a restri¸ao (3.20)
garante que XB
ij,w
´e uma vari´avel bin´aria.
45
3.3 Estudo de Casos
Nesta se¸ao ´e apresentado um conjunto de vari´aveis e restri¸oes que podem ser
adicionadas aos modelos, adaptando-os ao estudo de diferentes casos. Tais restri¸oes
incluem condi¸oes espec´ıficas de roteamento e atribui¸ao de comprimentos de onda,
como mostrado a seguir.
3.3.1 Modelos sem a Atribui¸ao dos Comprimentos de Onda
A atribui¸ao dos comprimentos de onda ´e uma das partes fundamentais para um
projeto de redes ´opticas com tecnologia WDM. Tal restri¸ao aumenta consideravel-
mente a complexidade dos modelos limitando a escalabilidade dos mesmos. Por´em,
assumindo que todos os os da rede s˜ao dotados de equipamentos para o processa-
mento eletrˆonico do tr´afego, constituindo uma rede opaca, o problema da atribui¸ao
de comprimentos de onda fica restrita a cada enlace individualmente. Essa carac-
ter´ıstica permite uma simplifica¸ao do modelo, tal que a atribui¸ao dos comprimen-
tos de onda possa ser realizada por um algoritmo externo ao modelo. A seguir ´e
apresentada uma implementa¸ao dos modelos em uma forma simplificada, com a
relaxa¸ao da atribui¸ao dos comprimentos de onda, onde as vers˜oes simplificadas
dos modelo NA e AC, s˜ao chamadas rNA e rAC, respectivamente.
Vari´aveis:
X
ij
´e a quantidade de tr´afego no enlace ij.
C
sd
ij
´e a quantidade de tr´afego do enlace ij que tem como origem o o s e destino
o n´o d.
Fun¸ao Objetivo: Os modelos rNA e rAC, assim como as formula¸oes NA
e AC, tamb´em tratam do projeto de redes ´opticas. Portanto, a minimiza¸ao do
n´umero de transceptores continua a ser o objetivo, sendo este representado pelas
express˜oes (3.1) e (3.2), apresentadas a seguir.
min :
i
OEO
i
46
min : max{OEO
i
}
Restri¸oes: Para o modelo rNA.
sd
C
sd
ij
= X
ij
, i, j; E[i][j]=1 (3.21)
j
C
sd
ij
j
C
sd
ji
=
traf[s][d] para i = s
- traf[s][d] para i = d
zero se i = s e i = d
s, d, i; s = d (3.22)
OEO
i
j
X
ij
C
, i (3.23)
X
ij
, OEO
i
Z
+
, i, j; E[i][j]=1 (3.24)
C
sd
ij
Z
+
, s, d; s = d (3.25)
Descri¸ao do modelo matem´atico:
As express˜oes (3.21) e (3.22) ao an´alogas `as restri¸oes (3.4) (de agrega¸ao de
tr´afego) e (3.6) (de conservao de fluxo), respectivamente. Por´em, como nesse
modelo ao a atribui¸ao de comprimento de onda, as restri¸oes (3.21) e (3.22)
dispensam o ´ındice w de identifica¸ao de comprimento de onda. Adicionalmente,
na restri¸ao (3.22) tamb´em ao aparece a divis˜ao do tr´afego nos comprimentos de
onda, realizado no modelo NA pela vari´aveis D
sd,w
.
Nesse modelo ao existe um vari´avel espec´ıfica para a contagem do umero
de transceptores por o, como ocorre no modelo NA. Assim, a inequa¸ao (3.23)
estima o n´umero de transceptores necess´arios em um n´o, dividindo a quantidade de
tr´afego passando do no i para todos os os fisicamente adjacentes pela capacidade
do comprimento de onda, C.
As restri¸oes (3.24) e (3.25) expressam as condi¸oes de ao-negatividade e inte-
gralidade das vari´aveis do modelo.
47
Da mesma forma, segue a implementa¸ao simplificada do modelo rAC. Todas as
vari´aveis usadas nesse modelo a foram anteriormente definidas e as restri¸oes 3.26
e 3.27 s˜ao equivalentes `as restri¸oes 3.15 e 3.23, respectivamente. A ´unica restri¸ao
inserida nesse modelo ´e a (3.28), que ´e an´aloga `a (3.16), por´em, sem atribui¸ao de
comprimentos de onda aos enlaces.
r
C
sd
r
= traf[s][d], s, d; s = d (3.26)
OEO
i
j
X
ij
C
, i (3.27)
sd
r
δ
sd
ij,r
× C
sd
r
= X
ij
, i, j E[i][j]=1 (3.28)
Considerando um cen´ario de rede opaca, a atribui¸ao do comprimento de onda
ao influencia nos resultados de um modelo ´otimo que minimiza o n´umero de trans-
ceptores, como ´e mostrado nos resultados. Por´em, para completar o projeto da
rede, ´e necess´ario atribuir os comprimentos de onda `as vari´aveis de roteamento das
conex˜oes, C
sd
ij
e C
sd
r
, nos modelos rNA e rAC, respectivamente. Assim para etapa
de atribui¸ao dos comprimentos de onda `as rotas, tem-se na literatura uma grande
quantidade de publica¸oes apresentando algoritmos de RWA [PIO 04].
3.3.2 Roteamento para Topologia Multi-Anel
Controlando o roteamento, pode-se selecionar rotas espec´ıficas para uma determi-
nada demanda sd, atendendo a restri¸oes de qualidade de servi¸co ou de gerencia-
mento da rede. Um caso cl´assico de gerenciamento de redes ´e o das redes com
topologia multi-anel, que diferem das redes em malha apenas pelo roteamento. En-
quanto uma rede em malha tem total liberdade para rotear uma demanda usando
qualquer enlace dispon´ıvel, nas redes multi-anel as demandas ao divididas entre
intra-anel, quando a fonte e destino de uma demanda pertencem ao mesmo anel,
e inter-anel, quando a fonte e destino est˜ao em an´eis diferentes, obedecendo `as
seguintes restri¸oes de roteamento: i) o caminho usado por uma demanda intra-
anel ao deve deixar o anel que cont´em os os fonte e destino; ii) uma demanda
inter-anel deve ser roteada de forma a passar pelo menor umero de an´eis poss´ıvel
[C.R 08]. Assim, limitando as possibilidades de rotas para cada demanda, nota-se
48
que tais restri¸oes de caminho podem facilitar o gerenciamento da rede e reduzir o
consumo de recursos. A Figura 3.2 ilustra uma rede multi-anel onde (a) representa
a conex˜ao entre os n´os e (b) a interconex˜ao dos an´eis. Vale ainda mencionar que a
estrutura de interconex˜ao dos an´eis para este exemplo ´e feita por dois os, conhe-
cida com dual node interconnection (DNI) [VAS 04]. Contudo, esta caracter´ıstica e
sua importˆancia ao devidamente discutidas no Cap´ıtulo 6, referente a aspectos de
prote¸ao e restaura¸ao das redes ´opticas.
Para um estudo das redes multi-anel, basta inserir algumas restri¸oes `as vari´aveis
de roteamento de cada modelo, C
sd
ij,w
para NA e C
sd
r
para AC. Como no modelo
AC cada rota r ´e pr´e-computada, para preencher os valores dos dados de entrada
δ
sd
ij,r
basta incluir as restri¸oes descritas anteriormente na fun¸ao que relaciona as
rotas aos enlaces. Isto ´e, se o caminho n˜ao pertence ao conjunto das rotas poss´ıveis
da topologia multi-anel para um par fonte e destino, deve-se atribuir 0 `a δ
sd
ij,r
para
todo ij. Por outro lado, para o modelo NA quando um determinado enlace ij ao
pertence ao conjunto de enlaces dispon´ıveis para uma demanda sd, devido `a uma
restri¸ao imposta pela topologia multi-anel, deve-se assumir C
sd
ij,w
= 0 para todo w.
Desta forma, os modelos s˜ao facilmente adapt´aveis ao estudo das redes multi-anel.
3.4 Resultados Num´ericos Comparativos
Nesta se¸ao, s˜ao apresentados resultados num´ericos para os modelos at´e agora pro-
postos, usando para isso trˆes topologias diferentes, com 6, 13 e 14 os, represen-
tadas respectivamente pelas Figuras 3.3 (a), 3.2 (a) e 3.3 (b). O software usado
para solucionar os modelos matem´aticos de programa¸ao linear inteira foi o CPLEX
9.0 [cpl ], computando cada exemplo em um computador Duo Core 1,62Ghz com
2GB RAM. Como o problema tratado por esse estudo ´e NP-Completo, foi arbitrado
um limite de tempo de 24 horas de processamento. Note que os modelos usando
a estrat´egia que indexa os enlaces aos caminhos exigem um pr´e-processamento das
rotas, por´em, o tempo desse pr´e-processamento ´e insignificante e ao influencia os
resultados obtidos. Foram interrompidos todos os exemplos em que o processo de
otimiza¸ao excedeu este tempo de processamento, apresentando o resultado junto
com o gap indicado pelo software. O gap dado pelo software ´e definido como (supe-
rior - inferior)/inferior, tal que superior e inferior ao os limites da solu¸ao primal
49
e dual, respectivamente [RAA 07].
Em todas as simula¸oes apresentadas, ´e assumido que cada comprimento de
onda ´e capaz de transportar 64 unidades de tr´afego com uma granularidade de uma
unidade de tr´afego. As Tabelas A.1, A.4 e A.5, no Anexo, apresentam as matrizes
de tr´afego que devem ser atendidas sobre as redes de 6, 13 e 14 os. Essa matriz foi
gerada por um algoritmo que atribui demandas de 16, 32, 48 e 64 unidades de tr´afego
com respectivamente 45%, 30%, 20% e 5% de probabilidade, tendo tais demandas
e probabilidades sido escolhidas arbitrariamente. Esse algoritmo tamb´em foi usado
para gerar as matrizes de tr´afego para as outras topologias estudadas.
Figura 3.2: (a) topologia de rede com 13 os; (b) grafo auxiliar representando a
interconex˜ao entre os an´eis.
3
1
0
4
2
5
(a)
CA
1
WA
CA
2
TX
CO
UT
NE
IL
PA
GA
MD
NJ
NY
MI
(b)
Figura 3.3: Topologias das redes de 6 os (a) e NSF-Net (b), adaptadas de [ZHU 02]
e [YE 03], respectivamente.
As Figuras 3.4, 3.5, 3.6 e 3.7 apresentam os resultados obtidos pelos modelos NA
e AC e suas relaxa¸oes, com as fun¸oes objetivo (3.1) e (3.2) representadas pelos
´ındices 1 e 2, respectivamente. Para cada instˆancia (modelo e fun¸oes objetivo)
os resultados apresentam como etricas o n´umero total de transceptores (OEOs)
necess´arios `a rede em (a) e o n´umero de transceptores no o mais carregado em
(b), para cada modelo e fun¸ao objetivo. Assim, note que o eixo das ordenadas
das Figuras 3.4-3.7 (a) coincide com a fun¸ao objetivo que minimiza o n´umero total
50
de transceptores, instˆancia NA
1
, AC
1
, rNA
1
e eAC
1
. Por´em, para compara¸ao,
nessas figuras tamb´em ao apresentados o total de transceptores da rede obtidos
pelos modelos que minimizando o min-max. Analogamente, tem-se que a instˆancia
de minimiza¸ao do pior caso, com ´ındice 2, tem a fun¸ao objetivo coincidindo com
o eixo das ordenadas nas Figuras 3.4-3.7 (b).
0
5
10
15
20
25
30
ΟΕΟ
i
Modelos NA
AC
1
NA
1
rNA
1
rAC
1
rNA
2
rAC
2
AC
2
NA
2
0
5
10
15
20
25
30
Modelos AC
1
min:
ΟΕΟ
i
2
min:max
{
ΟΕΟ
i
}
(a) (b)
0
2
4
6
8
Min:Max
{ΟΕΟ
i
}
AC
1
NA
1
rNA
1
rAC
1
rNA
2
rAC
2
AC
2
NA
2
0
2
4
6
8
Figura 3.4: Resultados obtidos para a rede com 6 n´os usando como m´etricas, (a) a
soma total e (b) o min-max do n´umero de OEOs.
Um resultado esperado, que pode ser constatado na Figura 3.4 (a), ´e o fato de os
modelos com a fun¸ao objetivo (3.1) (NA
1
, AC
1
, rNA
1
e rAC
1
) encontrarem um
n´umero total de OEOs menor que os obtidos pelas fun¸oes objetivo (3.2) (NA
2
, AC
2
,
rNA
2
e rAC
2
). Por outro lado, quando analisado como m´etrica o valor do min-max
encontrado por cada instˆancia, tem-se que a fun¸ao objetivo (3.2) obt´em valores
inferiores aos da fun¸ao (3.1). Esses resultados mostram que, para um cen´ario de
redes ´opticas, um m´etodo de otimiza¸ao usando como fun¸ao objetivo a redu¸ao
global de custos, produz configura¸oes onde o tr´afego est´a mal distribuido na rede,
ou seja, uma rede desbalanceada. Por outro lado, o m´etodo de otimiza¸ao usando
o min-max gera um cen´ario de rede mais balanceada, por´em, como esse m´etodo se
preocupa apenas com o pior caso e n˜ao com o global, ele produz uma configura¸ao
com um n´umero maior de transceptores. Comparando a Figura 3.4 (a) e (b), nota-se
que houve ainda um caso onde o modelo NA
1
, que utiliza a fun¸ao objetivo (3.1),
encontrou o mesmo valor do min-max que as instˆancias otimizadas para a fun¸ao
objetivo (3.2). Essa exce¸ao ´e devido ao reduzido tamanho da rede estudada, pois
nas instˆancias maiores ao foram encontrados casos como este, ao contr´ario, essa
diferen¸ca tornou-se mais n´ıtida.
Como ilustra¸ao das possibilidades de roteamento nas estrat´egias de formula¸ao,
51
ao apresentados na Tabela 3.1 os resultados das rotas da demanda 1-4 obtidos
por NA
2
e AC
1
, para a topologia apresentada na Figura 3.3 (a). Como a foi
mencionado, ambos os modelos possuem a capacidade de particionar o tr´afego no
o de origem. No exemplo de N A
2
, as parti¸oes usaram comprimentos de onda
diferentes, onde a conex˜ao seguindo pela rota 1-3-4 usou o comprimento de onda 1
e a conex˜ao passando por 1-0-3-4 usou o comprimento de onda 2. O modelo AC
1
,
por sua vez, roteou essa demanda pelos caminhos 1-2-4 e 1-3-4, ambos usando o
comprimento de onda 1, como mostra o exemplo da Tabela 3.1.
Tabela 3.1: Resultados comparativos para a rede de 6 n´os
modelos demanda caminho quantidade de tr´afego comprimentos de onda
utilizados
N A
2
1-4 (1,3),(3,4) 16 1
(1,0),(0,3),(3,4) 16 2
AC
1
1-4 (1,2),(2,4) 16 1
(1,3),(3,4) 16 1
0
20
40
60
80
100
120
140
160
180
200
220
240
260
OEO
i
Modelos NA
AC
1
NA
1
rNA
1
rAC
1
rNA
2
rAC
2
AC
2
NA
2
0
20
40
60
80
100
120
140
160
180
200
220
240
260
1
min:
ΟΕΟ
i
2
min:max
{
ΟΕΟ
i
}
1,69%
1,10%
1,38%
2,58%
Modelos AC
0
2
4
6
8
10
12
14
16
18
20
22
24
Min:Max{OEO
i
}
AC
1
NA
1
rNA
1
rAC
1
rNA
2
rAC
2
AC
2
NA
2
0
2
4
6
8
10
12
14
16
18
20
22
24
5,56%
(a) (b)
Figura 3.5: Resultados obtidos para a rede NSF-Net usando como etricas, (a) a
soma total e (b) o min-max do n´umero de OEOs.
A Figura 3.5 apresenta resultados para a rede NSF-Net. Como primeira ob-
servao, nota-se que os modelos que usam a express˜ao (3.1) n˜ao atingiram o valor
´otimo ap´os 24 horas de processamento. Assim, conclui-se que modelos usando tal
fun¸ao objetivo ao computacionalmente mais custosos, em rela¸ao ao n´umero total
de transceptores, do que os modelos usando a express˜ao (3.2). Adicionalmente,
os modelos usando a estrat´egia de formula¸ao que relaciona os os aos enlaces
52
(NA) tamem tem uma complexidade computacional maior do que as formula¸oes
(AC), como ´e observado comparando o gap dos modelos NA
2
e AC
2
na Figura 3.5
(b). Outro ind´ıcio dessa diferen¸ca no custo computacional dos dois m´etodos de for-
mula¸ao pode ser observado comparando NA
1
e AC
1
na Figura 3.5 (a), onde tem-se
que NA
1
encontrou 184 convers˜oes ´optico-eletrˆonico-´optico, enquanto AC
1
encon-
trou 183. Por´em, o primeiro, ap´os 24 horas de processamento, foi interrompido com
um gap de 2,58% e o segundo com 1,69%. O gap apresentado por NA
2
na Figura
3.5 (b) tamb´em justifica o fato de NA
2
encontrar o valor do min-max maior do que
AC
2
na Figura 3.5 (b). O problema do desbalanceamento das redes otimizadas com
a fun¸ao objetivo 3.1 acentua-se na rede NSF-Net, em compara¸ao com a rede de 6
os, pois os modelos usando a express˜ao (3.1) como fun¸ao objetivo encontraram,
no pior caso, 23 OEOs e uma quantidade total de aproximadamente 180 OEOs. En-
quanto os modelos usando o min-max como fun¸ao objetivo encontraram, no pior
caso, 17 OEOs e aproximadamente 240 OEOs no total. Comparando os modelos
NA e AC com suas relaxa¸oes, tem-se como diferen¸ca apenas a atribui¸ao dos com-
primentos de onda. Assim, como essa atribui¸ao ao influencia na minimiza¸ao do
n´umero de OEOs, no cen´ario de rede adotado, o resultado ´otimo das relaxa¸oes s˜ao
os mesmos encontrados pelos modelos originais (NA e AC). Por´em, por ter um
menor n´umero de vari´aveis as relaxa¸oes possuem um custo computacional menor,
como ´e observado no gap dos modelos NA
1
, AC
1
, rNA
1
e rAC
1
na Figura 3.5 (a).
Cabe destacar que o uso do gap como parˆametro para comparar o custo computa-
cional, o ´e alido para compara¸ao entre modelos usando a mesma fun¸ao objetivo.
Como por exemplo, o fato dos gaps de NE
2
e NE
1
serem 5,56% e 2,58%, respecti-
vamente, ao significa que NE
2
possui uma complexidade computacional maior que
NE
1
.
As Figuras 3.6 e 3.7 mostram os resultados obtidos para a rede de 13 os con-
siderando o roteamento em malha e multi-anel, respectivamente. A an´alise com-
parativa entre redes em malha e multi-anel tem atra´ıdo recentes trabalhos na ´area
de projeto de redes ´opticas [BOW 05], pois o crescimento das redes em anel levou
`a interconex˜ao destas topologias. Assim, faz-se necess´ario discutir qual ´e a melhor
pol´ıtica para tratar o tr´afego roteado por essas redes.
Os comenarios feitos anteriormente, analisando o custo computacional das fun-
¸oes objetivo (3.1) e (3.2), e comparando as formula¸oes NA e AC, continuam
alidos para a redes de 13 n´os considerada, tanto em malha quanto em multi-anel.
53
0
20
40
60
80
100
120
140
160
180
200
220
OEO
i
Modelos NA
AC
1
NA
1
rNA
1
rAC
1
rNA
2
rAC
2
AC
2
NA
2
0
20
40
60
80
100
120
140
160
180
200
220
1
min:
ΟΕΟ
i
2
min:max{
ΟΕΟ
i
}
1,36%
1,52%
2,44%
2,41%
Modelos AC
(a) (b)
0
20
6,67%
Min:Max{OEO
i
}
AC
1
NA
1
rNA
1
rAC
1
rNA
2
rEA
2
AC
2
NA
2
0
2
4
6
8
10
12
14
16
18
20
Figura 3.6: Resultados para rede com 13 os com roteamento em malha, usando
como m´etricas (a) a soma total e (b) o min-max do n´umero de convers˜oes
´
Optico-
Eletrˆonico-
´
Optico
0
20
40
60
80
100
120
140
160
180
200
220
ΟΕΟ
i
Modelos NA
AC
1
NA
1
rNA
1
rAC
1
rNA
2
rAC
2
AC
2
NA
2
0
20
40
60
80
100
120
140
160
180
200
220
1
min:
ΟΕΟ
i
2
min:max
{
ΟΕΟ
i
}
2,45%
1,05%
1,28%
3,44%
Modelos AC
0
2
4
6
8
10
12
14
16
18
20
Min:Max{OEO
i
}
AC
1
NA
1
rNA
1
rAC
1
rNA
2
rAC
2
AC
2
NA
2
6,67%
6,67%
0
2
4
6
8
10
12
14
16
18
20
(a) (b)
Figura 3.7: Resultados para rede com 13 os com roteamento para multi-anel, u-
sando como m´etricas (a) a soma total e (b) o min-max do n´umero de convers˜oes
´
Optico-Eletrˆonico-
´
Optico
Por´em, comparando as estrat´egias de roteamento destacam-se algumas diferen¸cas.
Verifica-se que uma otimiza¸ao global dos custos aplicados a uma rede multi-anel
leva a uma configura¸ao de rede ligeiramente desbalanceada, quando comparado
com um roteamento em malha, pois no roteamento multi-anel, na Figura 3.7 (b),
todas as formula¸oes usando a fun¸ao objetivo (3.1) encontraram 17 OEOs no pior
caso, enquanto as mesmas formula¸oes encontraram 16 OEOs para a rede em malha.
Contudo, usando a express˜ao (3.2) como fun¸ao objetivo encontrou-se 14 OEOs no
min-max, para rNA
2
e rCA
2
como roteamento multi-anel e malha e AC
2
para malha
e 15 para NA
2
e AC
2
em multi-anel e NA
2
em malha. Os casos onde se encontrou 15
54
OEOs, se devem ao fato de o processamento ter sido interrompido, como mostrado
atrav´es do gap nas Figuras 3.6 (b) e 3.7 (b). Assim, para o projeto de redes ´opticas,
al´em dos custos de instala¸ao da rede, devem ser considerados aspectos operacionais
como o balanceamento da rede. Esta ´ultima m´etrica mencionada indica a diferen¸ca
entre os enlaces de maior e menor uso, e est´a relacionado ao congestionamento
[RAM 96], que minimiza o enlace com o maior uso. Com rela¸ao ao n´umero total de
OEOs, ´e relativamente dif´ıcil tirar conclus˜oes definitivas devido ao gap apresentado
em todos os casos. Contudo, aparentemente, o n´umero de OEOs encontrado pelos
modelos NA
1
e AC
1
ser´a o mesmo para redes com topologia em malha e multi-anel.
3.5 Sum´ario
Neste cap´ıtulo ao propostos dois m´etodos asicos para formula¸oes de programa¸ao
linear inteira envolvendo problemas de redes ´opticas, al´em de um conjunto de estudo
de casos tratando das caracter´ısticas dessas redes, como, por exemplo, roteamento
do tr´afego. A an´alise num´erica dos resultados conta com trˆes topologias de redes,
com 6, 13 e 14 os, sendo que a rede de 13 os foi analisada com roteamento em
malha e multi-anel. Como o problema tratado nesse trabalho pertence `a classe
de problemas NP-Completo, nessa an´alise foi estipulado o limite de processamento
de 24 horas. Caso o modelo ao encontre o valor ´otimo dentro desse per´ıodo, o
processo ´e interrompido, exibindo o resultado encontrado e o gap. Nos resultados
num´ericos foi analisada a diferen¸ca de complexidade computacional entre o uso das
fun¸oes objetivo de minimiza¸ao global e min-max. Os resultados ainda mostram
que modelos com uma minimiza¸ao global dos custos frequentemente produzem
cen´arios de rede desbalanceados, enquanto que minimiza¸oes por min-max, apesar
de produzirem configura¸oes bem balanceadas, apresentam um grande umero de
transceptores quando comparados com uma minimiza¸ao global. Assim, deve-se
buscar solu¸oes de compromisso em uma rede balanceada e com o custo global
reduzido [FAR 00].
Como ´ultimo resultado, foi comparado o roteamento em malha e multi-anel em
uma mesma rede de 13 os. Constatou-se que na rede multi-anel a otimiza¸ao global,
apesar de encontrar a mesma quantidade total de OEOs, produz uma configura¸ao
mais desbalanceada que as redes em malha. Ao passo que, usando min-max as duas
55
estrat´egias de roteamento ao similares. Assim, em termos de custo de instala¸ao,
tem-se que as redes ao similares. Embora intuitivamente, espera-se que as redes
multi-anel tenham uma complexidade operacional menor, devido `a setoriza¸ao em
sub-redes. Contudo, ainda se faz necess´aria uma investiga¸ao para comparar o custo
operacional dessas redes de forma mais detalhada. Assim, sendo poss´ıvel ponderar
entre o custo total de instala¸ao, o balanceamento da rede e os custos operacionais,
para a escolha de uma pol´ıtica de roteamento.
Al´em desses resultados, ao longo dos cap´ıtulos existentes neste trabalho, cada
novo modelo proposto utilizar´a uma das duas formas de modelamento, associando
os os aos enlaces ou os enlaces aos caminhos, exemplificados por NA e AC, respec-
tivamente. A escolha da formula¸ao usada depende das caracter´ısticas do problema
em estudo, como, por exemplo: os modelos propostos no Cap´ıtulo 4 ao formulados
associando os os aos enlaces, pois o objetivo dos modelos ´e rotear o tr´afego sobre um
conjunto de caminhos ´opticos, tendo o maior grau de liberdade poss´ıvel; enquanto
que nos modelos propostos para a prote¸ao da interconex˜ao de anel, apresentados no
Cap´ıtulo 6, utilizam formula¸oes que associam os enlaces aos caminhos, pois com a
predefini¸ao dos caminhos ´e poss´ıvel controlar as rotas e reduzir consideravelmente
o n´umero de vari´aveis do modelo.
Cap´ıtulo 4
Solu¸c˜ao H´ıbrida para Redes
Transl´ucidas
No Cap´ıtulo 3, os modelos NA e AC foram propostos para os problemas de TGP
e RWA, onde o tr´afego foi acomodado sobre uma rede opaca (ou uma topologia
virtual). Neste cap´ıtulo ao propostos dois modelos, sendo um composto por duas
formula¸oes ILP e o outro contando com uma solu¸ao h´ıbrida, que ser´a chamado de
modelo h´ıbrido por contar com uma heur´ıstica e uma formula¸ao ILP. Ambos para a
solu¸ao de redes considerando as restri¸oes do VTD, TGP e RWA. Adicionalmente,
usando o modelo h´ıbrido, os resultados num´ericos apresentam uma investiga¸ao
quantificando a redu¸ao do n´umero de transceptores e do processamento eletrˆonico,
com a inser¸ao de caminhos ´opticos em uma rede ´optica transl´ucida.
4.1 Introdu¸c˜ao
Com o objetivo de diferenciar o caminho ´optico do enlace f´ısico, este ´e aqui definido
como uma conex˜ao transparente com dois ou mais enlaces f´ısicos. Esse caminho
´optico, que por um lado possibilita uma economia do n´umero de transceptores ao
longo de uma conex˜ao, tamb´em exige a instala¸ao de um par transmissor/receptor
e a ocupa¸ao de um comprimento de onda ao longo do caminho, que representa um
custo adicional e um complicador para os modelos de otimiza¸ao. Para uma rede com
demandas de tr´afego entre todos os n´os, uma conex˜ao direta entre cada par de n´os
pode gerar uma configura¸ao demasiadamente custosa e subutilizada. Assim, uma
rede transl´ucida oferece uma rela¸ao de compromisso entre uma rede opaca e uma
56
57
rede totalmente transparente, em um esquema de roteamento multicamada (´optica
e eletrˆonica). A Figura 4.1 mostra uma ilustra¸ao com os benef´ıcios do agrupamento
de tr´afego e caminhos ´opticos transparentes. Nessa figura ao representadas duas
demandas de tr´afego, uma de 6 para 3 e outra de 6 para 2. Considerando o trans-
ceptor como um par transmissor/receptor, note que na Figura 4.1 (a) os os 6 e 1
necessitam ambos de dois transceptores. Assim, para o tr´afego ser acomodado sem
a estrat´egia de agrupamento de tr´afego e os benef´ıcios dos caminhos ´opticos, ao
necess´arios 7 transceptores e 2 comprimentos de onda, como mostrado na Figura
4.1(a). Quando usado o agrupamento de tr´afego (Figura 4.1(b)), ´e poss´ıvel reduzir
os recursos para 4 transceptores e 1 comprimento de onda. Por´em, em um cen´ario
usando ambos, agrupamento de tr´afego e caminhos ´opticos, ainda ´e economizado
um transceptor, como apresentado na Figura 4.1(c). Essa ilustra¸ao deixa clara a
relevˆancia do estudo da otimiza¸ao nas redes ´opticas transl´ucidas.
1 2 3
456
traf[6][2]
traf[6][2]
traf[6][3] traf[6][3]
traf[6][3]
1 2 3
456
traf[6][3]+
traf[6][2]
traf[6][3]
traf[6][3]+
traf[6][2]
(a)
1 2 3
456
traf[6][3]+
traf[6][2]
traf[6][3]
(b)
(c)
Figura 4.1: (a) sem grooming de tr´afego e sem caminho ´optico, (b) com grooming
de tr´afego e sem caminho ´optico e (b) com grooming de tr´afego com caminho ´optico
A Figura 4.2 ilustra a arquitetura de um n´o da rede considerado nesse cap´ıtulo.
Nesse o est´a representada a inser¸ao, retirada, processamento eletrˆonico do tr´afego
e um caminho ´optico. O processamento eletrˆonico do o na figura ´e representado
pela presen¸ca de um DXC, onde ao processadas as demandas de entrada, sa´ıda e
as demandas dos comprimentos de onda w = 1 e w = 2. Al´em disso, atrav´es das
funcionalidades do cross-connect ´optico (OXC), no comprimento de onda w = 3 ´e
representada a passagem de um caminho ´optico transparente, ou seja, sem o uso de
transceptores e sem acrescentar tr´afego ao DXC.
58
DXC
Switch Óptico
i
C
id
ij
X
ij
d=i
s=i
w=1
w=2
w=3
Tx
Rx
D
E
M
U
X
D
E
M
U
X
M
U
X
M
U
X
Figura 4.2: Ilustra¸ao do processamento do tr´afego e de um canal transparente em
um n´o com capacidade de grooming, adaptado de [YE 03].
4.1.1 Trabalhos Relacionados e Contribui¸oes
Na literatura alguns trabalhos a descrevem as caracter´ısticas das redes transl´uci-
das e dos caminhos ´opticos desde a d´ecada de 90, [RAM 99a][SHE 07]. Devido `a
quantidade de restri¸oes, algoritmos exatos usados para encontrar o conjunto ´otimo
de caminhos ´opticos e o TGP de forma unificada, ao restritos quanto ao tamanho da
rede. Por exemplo, [ZHU 02] e [HUI 02] prop˜oem modelos ILP para resolver redes
de 6 os e heur´ısticas para redes maiores. Para aumentar a capacidade dos modelos
ILPs, em [KAR 04], ´e proposta a subdivis˜ao da rede em v´arias sub-redes, de forma
que os caminhos ´opticos fiquem restritos a uma sub-rede. Essa estrat´egia reduz a
complexidade do modelo, por´em limita as possibilidades de conex˜oes transparentes.
Assim, os resultados dependem da rela¸ao de compromisso entre a complexidade
do modelo e a flexibilidade dos caminhos ´opticos, isto ´e, o tamanho de cada sub-
rede. Adicionalmente, nos modelos apresentados no trabalho ao reservados recursos
da rede para a prote¸ao e recupera¸ao. Em [JAE 07] ´e proposto um modelo ILP
capaz de resolver em tempo aceit´avel rede de at´e 30 os, mas sem considerar o
59
problema de roteamento e aloca¸ao de comprimentos de onda. Contudo, os trabalhos
encontrados na literatura, que citam os benef´ıcios do uso de caminhos ´opticos em
redes transl´ucidas, ao apresentam uma quantifica¸ao exata da economia efetiva dos
caminhos ´opticos.
Assim, a investiga¸ao realizada neste cap´ıtulo se prop˜oe a quantificar a redu¸ao
do n´umero de transceptores e do processamento eletrˆonico nos os, obtidas com a
inser¸ao de caminhos ´opticos na rede. Para isso ao propostos neste cap´ıtulo dois
m´etodos para solu¸ao do problema de redes transl´ucidas. O primeiro m´etodo con-
siste em dividir o problema em dois modelos ILP: i) primeiro, atrav´es da matriz de
adjacˆencias ao disponibilizados os caminhos ´opticos na rede. Assim, com o modelo
rNA, s˜ao escolhidos os caminhos ´opticos e realizado o roteamento do tr´afego sobre
a camada ´optica, de modo a minimizar o n´umero de transceptores; ii) em outro
modelo apresentado a seguir, cada caminho ´optico ´e acomodado sobre a camada
f´ısica. Para a redu¸ao dos tempos computacionais das estrat´egias que usam uni-
camente modelos ILP, o segundo m´etodo trata-se de um algoritmo h´ıbrido. Nesse
m´etodo uma heur´ıstica seleciona os poss´ıveis caminhos ´opticos e suas rotas sobre
a camada f´ısica, em seguida um modelo ILP escolhe quais destes caminhos ´opticos
devem ser efetivamente usados e acomoda o tr´afego sobre a camada ´optica. Assim,
foi poss´ıvel controlar os caminhos ´opticos permitidos aos modelos ILP em um tempo
computacional vi´avel.
4.2 Formula¸c˜ao para o RWA (RWA-OF)
Primeiramente, com o modelo rNA ao selecionados os caminhos ´opticos usados
na rede. Assim, desconsiderando a distˆancia dos caminhos ´opticos, do ponto de
vista de uma conex˜ao, um caminho ´optico ´e similar a um enlace f´ısico, pois para a
camada eletrˆonica, ambos representam uma conex˜ao ponto a ponto. Baseado nisso,
formulou-se um m´etodo de solu¸ao para a aloca¸ao dos caminhos ´opticos em uma
rede transl´ucida.
Considere a seguinte nota¸ao para diferenciar os caminhos ´opticos dos enlaces
f´ısicos:
g e h ao n´os da rede fisicamente adjacentes, conectados pelo par de fibras gh e hg.
60
l e m ao os de origem e destino de um caminho ´optico bidirecional, notado por lm
e ml.
i e j representam dois os adjacentes em uma conex˜ao transparente, seja esta um
enlace f´ısico (gh) ou um caminho ´optico transparente (lm).
w representa um elemento pertencente ao conjunto dos comprimentos de onda,
w W .
Como dados do problema, tˆem-se os seguintes elementos:
Ef[g][h] representa a matriz de adjacˆencias dos enlaces f´ısicos, isto ´e, Ef[g][h] = 1 se
existe um par de fibras conectando os n´os g e h, e zero, caso contr´ario.
Ec[l][m] representa a matriz de adjacˆencias dos caminhos ´opticos, ou seja, Ec[l][m] =
1, se h´a permiss˜ao para instalar um caminho ´optico entre o par de os lm, e
zero, caso contr´ario. Note que, pela defini¸ao desta matriz, ´e poss´ıvel permi-
tir apenas alguns caminhos ´opticos, ou simplesmente “disponibilizar”todas as
possibilidades de caminhos ´opticos e deixar que o modelo selecione o conjunto
´otimo. Na descri¸ao do modelo h´ıbrido proposto, ´e apresentado um algoritmo
para a pr´e-sele¸ao dos caminhos ´opticos
E[i][j] representa a matriz de adjacˆencias das conex˜oes transparentes, E[i][j] = Ef[i][j]
+ Ec[i][j]. Note que, pela defini¸ao de caminho ´optico dada neste cap´ıtulo
tem-se que Ef[i][j] + Ec[i][j] 1; i, j.
T
ij
Nos modelos NA e AC, a vari´avel XB
ij,w
identifica se existe uma conex˜ao
entre os os i e j usando o comprimento de onda w. Assim, define-se o dado
de entrada T
ij
como a quantidade de conex˜oes partindo do n´o i destinado ao
o j, isto ´e T
ij
=
w
XB
ij,w
. Note ainda que, de posse das matrizes Ef e Ec,
pode-se dividir T
ij
em T
gh
e T
lm
. Sendo T
gh
o n´umero de canais destinados a
conectar os fisicamente adjacentes, e T
lm
o n´umero de caminhos ´opticos entre
os n´os l e m.
Para o projeto da topologia virtual, dentre a restri¸oes mais comuns, existe a
limita¸ao de distˆancia que um sinal percorrer´a transparentemente e o n´umero de
saltos dado pelo caminho ´optico [FIL 03]. Contudo, neste trabalho, tais aspectos
ao foram levados em conta, pois o objetivo n˜ao ´e apenas atribuir o caminho ´optico
61
em uma boa configura¸ao para a rede, e sim mensurar a economia de recursos
promovida pelos caminhos ´opticos.
Assim, na primeira fase, ´e usada apenas a matriz E e um dos modelos sem
aloca¸ao de comprimentos de onda (rNA ou rAC) para gerar os resultados para
as vari´aveis C
sd
ij
. De posse de C
sd
ij
e das matrizes Ef e Ec, tem-se o conjunto ´otimo
de caminhos ´opticos e o roteamento do tr´afego sobre a camada ´optica. Resta enao
atribuir os comprimentos de onda e acomodar os caminhos ´opticos sobre a camada
f´ısica. Portanto, faz-se necess´ario a proposi¸ao de um novo modelo considerando
a restri¸ao do n´umero aximo de comprimentos de onda por enlace f´ısico sem
repeti¸ao de atribui¸ao (unicidade). A seguir ´e apresentado o conjunto das vari´aveis
usadas nesse modelo.
XB
gh,w
: ´e uma vari´avel bin´aria igual a 1, se o comprimento de onda w ´e usado no
enlace f´ısico gh, e zero no caso contr´ario.
W B
lm
w
: ´e uma vari´avel bin´aria igual a 1, se o comprimento de onda w ´e usado pelo
caminho ´optico lm, e zero no caso contr´ario.
W B
lm
gh,w
: ´e uma vari´avel bin´aria igual a 1, se o comprimento de onda w do enlace
gh ´e usado para rotear o caminho ´optico lm, e zero no caso contr´ario.
W
gh
: ´e definido como a quantidade de comprimentos de onda no enlace f´ısico gh.
Fun¸ao objetivo: Como est´a sendo tratada da aloca¸ao de comprimentos
de onda, a fun¸ao objetivo minimiza a quantidade necess´aria no enlace mais car-
regado. A seguir s˜ao apresentadas as express˜oes usadas para representar o modelo
de atribui¸ao de comprimentos de onda.
Min : Max{W
gh
} g, h (4.1)
Restri¸oes:
w
XB
gh,w
= T
gh
, g, h; Ef[g][h]=1 (4.2)
w
W B
lm
w
= T
lm
, l, m; Ec[l][m]=1 (4.3)
62
w
XB
gh,w
+
lm
w
W B
lm
gh,w
= W
gh
, g, h; Ef[g][h]=1 (4.4)
XB
gh,w
+
lm
W B
lm
gh,w
1, g, h, w; Ef[g][h]=1 e w W (4.5)
h
W B
lm
gh,w
h
W B
lm
hg,w
=
W B
lm
w
se g = s
W B
lm
w
se g = d
zero se g = s e g = d
,
l, m, g, w; Ec[l][m]=1, Ef[g][h]=1 e w W (4.6)
W
gh
Z
+
, g, h; Ef[g][h]=1 (4.7)
XB
gh,w
{0, 1}, g, h, w; Ef[g][h]=1 e w W (4.8)
W B
lm
w
{0, 1}, l, m, w; Ec[l][m]=1 e w W (4.9)
W B
lm
gh,w
{0, 1}, l, m, g, h, w; Ef[g][h]=1, Ec[l][m]=1 e w W (4.10)
Descri¸ao do modelo matem´atico:
Como a mencionado o n´umero de transceptores no o i usados para conectar
ao o j ´e dado pela quantidade de comprimentos de onda no enlace ij. Assim, na
equa¸ao (4.2) a somat´oria de XB
gh,w
em w representa o n´umero de comprimentos de
onda existentes no enlace gh. Assim, tal restri¸ao possibilita a contagem do n´umero
de transceptores no n´o g que s˜ao usados para conectar ao n´o h. An´aloga `a equa¸ao
(4.2), a restri¸ao representada pela equa¸ao (4.3) indica o umero de transceptores
usados na conex˜ao transparente entre os n´os l e m.
Na equa¸ao (4.4), a primeira somat´oria `a esquerda da igualdade indica a quan-
tidade de comprimentos de onda existentes no enlace gh que ao usados para criar
uma conex˜ao ogica em g e h. A segunda somat´oria contabiliza o umero de com-
primentos de onda em todos os caminhos ´opticos que passam pelo enlace gh. Assim,
a soma desses dois elementos resulta na quantidade total de comprimentos de onda
usados em cada enlace f´ısico.
Na express˜ao (4.5), a vari´avel W B
gh,w
indica o uso do comprimento de onda w no
enlace gh e a somat´oria apresentada nessa restri¸ao contabiliza o n´umero de cami-
nhos ´opticos passando por gh que usam o comprimento de onda w. Assim, limitando
a soma desses dois elementos ´e poss´ıvel assegurar a unicidade de cada comprimento
63
de onda w em todos os enlaces f´ısicos, ou seja, tem-se que cada comprimento de
onda ou ser´a usado para uma conex˜ao direta entre gh ou ser´a usado por apenas um
caminho ´optico.
Nas equa¸oes (4.6), note que a vari´avel W B
lm
w
´e bin´aria e indica que o com-
primento de onda w est´a sendo usado para atender o caminho ´optico lm. Assim,
como essa restri¸ao ´e an´aloga `a restri¸ao (3.6) apresentada no Cap´ıtulo 3, tem-se
que a express˜ao (4.6) representa a continuidade do comprimento de onda, usado
para atender uma caminho ´optico lm, ao longo da rede.
A restri¸ao (4.7) assegura a ao-negatividade e integralidade da vari´avel W
gh
e
as restri¸oes (4.8), (4.9) e (4.10) garantem que as demais vari´aveis sejam bin´arias.
4.3 Modelo H´ıbrido
Como mencionado, modelos ILP contendo as restri¸oes para o VTD, TGP e RWA ao
incapazes de solucionar redes com mais de 8 os. Al´em disso, como esse estudo tem
o objetivo de quantificar a redu¸ao do n´umero de transceptores e do processamento
eletrˆonico, ´e proposto nessa se¸ao um modelo h´ıbrido para o VTD, TGP e RWA,
com uma adi¸ao gradativa dos caminhos ´opticos.
O modelo h´ıbrido, ´e composto de duas etapas, sendo uma para a escolha e rotea-
mento dos caminhos ´opticos e outra para o problema do agrupamento de tr´afego.
Na primeira fase do algoritmo ´e proposta uma heur´ıstica, objetivando a redu¸ao do
custo computacional para resolver problemas com redes maiores. A solu¸ao obtida
nessa etapa ´e passada como restri¸ao para a segunda fase, onde ´e empregado um
modelo ILP para garantir a otimalidade do n´umero de transceptores.
4.3.1 Escolha e Roteamento de um Caminho
´
Optico
Tentando reduzir o n´umero de transceptores nos os intermedi´arios em uma conex˜ao,
a fun¸ao usada para escolher os caminhos ´opticos pondera entre: i) a quantidade de
tr´afego da requisi¸ao entre os os s e d; e ii) a quantidade de saltos de uma demanda
sd, considerando que esta sempre ´e roteada pelo caminho m´ınimo, isto ´e, caminho
com o menor n´umero de saltos. Por outro lado, para cada caminho ´optico, um novo
64
transceptor precisa ser instalado. Assim, espera-se que a redu¸ao do n´umero de
transceptores obtida pelo uso de novos caminhos ´opticos tenha um limite.
Na heur´ıstica proposta, os caminhos ´opticos s˜ao escolhidos segundo uma ordem
de prioridade, T L
sd
,
T L
sd
= H
sd
× (traf[s][d]+traf[d][s]), (4.11)
onde H
sd
´e o n´umero de saltos do caminho m´ınimo entre sd e traf[s][d] ´e a demanda
de tr´afego entre os n´os sd, dada pela matriz de tr´afego.
Assumindo |N| como o n´umero de n´os e |Ef| como o n´umero de enlaces f´ısicos,
define-se L como o n´umero m´aximo de caminhos ´opticos poss´ıvel:
L =
|N|(|N| 1)
2
|Ef|. (4.12)
Como
|N|(|N|−1)
2
´e o n´umero de conex˜oes bidirecionais de um grafo completo de N
os, subtraindo o n´umero de enlaces f´ısicos da rede(|Ef|), tem-se o n´umero aximo
de conex˜oes fim-a-fim que podem ser inseridas na rede. Por exemplo, assuma a
topologia f´ısica de uma rede com 8 os e 10 enlaces. Como um grafo completo
de uma rede de 8 os possui 28 arestas, subtraindo o n´umero de enlaces f´ısicos,
obtˆem-se que o umero aximo de conex˜oes transparentes de dois ou mais saltos,
ao 18 caminhos ´opticos. O pseudo-c´odigo 4.1 ilustra o procedimento que acomoda
os caminhos ´opticos na topologia f´ısica.
Na linha 4 do Algoritmo 4.1 as rotas a est˜ao previamente ordenadas com um
n´umero ao decrescente de saltos. Assim, os caminhos ´opticos ao roteados segundo
o menor caminho que tenha pelo menos um comprimento de onda dispon´ıvel. Isto
´e feito de forma que cada enlace f´ısico ainda tenha dispon´ıvel pelo menos um com-
primento de onda para a comunica¸ao entre os fisicamente adjacentes. Uma vez
escolhidos e roteados todos os caminhos ´opticos, a redu¸ao do n´umero de trans-
ceptores ´e quantificada atrav´es de uma sequˆencia em cen´arios de rede. De modo
que o primeiro cen´ario de rede tenha, al´em dos enlaces f´ısicos, um caminho ´optico
para rotear as demandas de tr´afego; o segundo, com 2 caminhos ´opticos; e subse-
quentemente, o ´ultimo cen´ario de rede possui dispon´ıvel L caminhos ´opticos, al´em
dos enlaces f´ısicos. Atraes dessa sequˆencia de cen´arios de rede, com uma quanti-
65
Algoritmo 4.1 Atribui¸ao dos Caminhos
´
Opticos
1: Entrada: Escolher n´umero de caminhos ´opticos existentes na rede.
2: Ordenar os caminhos ´opticos segundo T L
sd
.
3: for Para todos os caminhos ´opticos l. do
4: for Percorrer todas as rotas k, poss´ıveis para o caminho ´optico l. do
5: for Percorrer todos os comprimentos de ondas, w. do
6: if ´e poss´ıvel atribuir o caminho ´optico l na rota k e comprimento de onda
w. then
7: ir para a linha 3 e atribuir outro caminho ´optico.
8: end if
9: end for
10: end for
11: end for
dade progressiva de caminhos ´opticos, os resultados num´ericos mostram a rela¸ao
entre a quantidade de caminhos ´opticos dispon´ıveis, a economia de transceptores e
o processamento eletrˆonico.
4.3.2 Modelo ILP para o TGP com Caminhos
´
Opticos
Transparentes
O modelo de programa¸ao linear inteira aqui proposto ´e baseado na formula¸ao
rNA apresentado no Cap´ıtulo 3, adiciona-se aqui apenas as restri¸oes impostas
pelos caminhos ´opticos, pr´e-calculados pela parte heur´ıstica do etodo. A seguir
´e apresentado o modelo destacando-se as diferen¸cas em rela¸ao ao modelo da rede
opaca:
g e h ao os da rede fisicamente adjacentes.
l e m ao n´os de origem e destino de um caminho ´optico bidirecional.
i e j representam dois n´os adjacentes em uma conex˜ao transparente.
Dados do problema: Os elementos a foram definidos e descritos, aqui ser˜ao
apenas apresentados.
Ef[g][h] representa a matriz de adjacˆencias dos enlaces f´ısicos.
66
Ec[l][m] representa a matriz de adjacˆencias dos caminhos ´opticos.
E[i][j] representa a matriz de adjacˆencias das conex˜oes transparentes.
W max
gh
´e o n´umero de comprimentos de onda que restaram no enlace f´ısico gh ap´os o
roteamento de todos os caminhos ´opticos.
Vari´aveis (ver a representa¸ao na Figura 4.2):
OEO
i
: vari´avel com o n´umero de transceptores em cada n´o i.
X
ij
´e a quantidade de tr´afego no enlace ij.
C
sd
ij
´e a quantidade de tr´afego do enlace ij que tem como origem o o s e destino
o n´o d.
T
ij
´e o n´umero de conex˜oes em cada conex˜ao ij, que como a visto, pode ser
dividido em T
gh
e T
lm
.
Fun¸ao objetivo: Como o objetivo ´e minimizar o n´umero de transceptores
usados na rede transl´ucida, optou-se por usar como fun¸ao objetivo a minimiza¸ao
do n´umero de convers˜oes ´optico-eletrˆonico-´optico em um n´o.
min :
ij
OEO
i
(4.13)
Restri¸oes:
sd
C
sd
ij
= X
ij
, i, j; E[i][j]=1 e s = d (4.14)
j
C
sd
ij
j
C
sd
ji
=
traf[s][d] se i = s
traf[s][d] se i = d
zero se i = s e i = d
,
s, d, i; E[i][j]=1 e s = d (4.15)
T
ij
X
ij
C
, i, j; E[i][j]=1 (4.16)
OEO
i
=
j
T
ij
, i N (4.17)
67
T
gh
W max
gh
, g, h; Ef[g][h]=1 (4.18)
T
lm
= 1, l, m; Ec[l][m]=1 (4.19)
C
sd
ij
Z
+
, s, d, i, j; E[i][j]=1 e s = d (4.20)
X
ij
Z
+
, i, j; E[i][j]=1 (4.21)
T
ij
Z
+
, i, j; E[i][j]=1 (4.22)
OEO
i
Z
+
, i N (4.23)
Descri¸ao do modelo matem´atico:
As restri¸oes 4.14 e 4.15 foram definidas, como (3.21) e (3.22), e discutidas no
Cap´ıtulo 3. A express˜ao (4.16) ´e an´aloga `a restri¸ao (3.23), por´em aqui ´e contabi-
lizado o n´umero de conex˜oes entre o par de n´os ij. A express˜ao (4.17) contabiliza o
n´umero de conex˜oes deixando o o i e atribui o n´umero de transceptores necess´arios
a esse n´o.
O roteamento dos caminhos ´opticos exige a reserva de alguns recursos da rede,
tais como comprimentos de onda em cada enlace. Ap´os a atribui¸ao dos cami-
nhos ´opticos, realizada pelo Algoritmo 4.1, ´e armazenado no parˆamento W max
gh
a
quantidade de comprimentos de onda que ainda est˜ao dispon´ıveis em cada enlace.
Assim, a express˜ao (4.18) assegura que um enlace f´ısico gh ao exceder´a o n´umero
de comprimentos de onda que foram deixados dispon´ıveis.
A express˜ao 4.19 garante que cada caminho ´optico transparente ter´a apenas um
comprimento de onda dispon´ıvel, assim o modelo ILP considera um caminho ´optico
como uma conex˜ao transparente com apenas um comprimento de onda.
As restri¸oes (4.20), (4.21), (4.22) e (4.23) asseguram a n˜ao-negatividade e inte-
gralidade das vari´aveis do modelo.
Na primeira fase do modelo h´ıbrido proposto, foi assumido que os caminhos
´opticos seriam escolhidos sob a restri¸ao de continuidade de comprimento de onda.
O modelo de ILP usado para tratar a rede opaca n˜ao adota tal restri¸ao pois, nessa
fase, o tr´afego passa por processamento eletrˆonico ap´os cada salto. Portanto, tem-
se que a atribui¸ao do comprimento de onda da rede opaca pode ser feita em um
est´agio de p´os-processamento, sem perdas na qualidade das solu¸oes.
68
4.4 Quantifica¸c˜ao do Ganho dos Caminhos
´
Opticos
Transparentes
Nesta Se¸ao ´e realizado um estudo num´erico com o objetivo de quantificar a redu¸ao
do n´umero de transceptores e processamento eletrˆonico, atrav´es da inser¸ao de cami-
nhos ´opticos na rede. Para isso foi utilizado o m´etodo h´ıbrido apresentado anteri-
ormente. Para verificar os ganhos obtidos pelos caminhos ´opticos foram usadas
trˆes topologias de rede com 6 os, 8 os e 14 os - NSFNet (Figura 4.3 (a), (b)
e (c), respectivamente), e 5 matrizes de tr´afego para cada topologia. As matrizes
de tr´afego foram geradas segundo as especifica¸oes feitas no Cap´ıtulo 3, Se¸ao 3.4
e est˜ao dispon´ıveis no Apˆendice A. Todos os resultados apresentados para as redes
com 6 e 8 os possuem gap igual a zero, ou seja, ao resultados ´otimos. Por´em,
devido ao tamanho da rede NSF-Net, o processamento foi interrompido ap´os 24 ho-
ras. Ap´os essas 24 horas de processamento algumas instˆancias obtiveram o ´otimo
e outras foram interrompidas, de forma que a m´edia do gap de todas as instˆancias
para a rede NSF-Net foi de 2,67%, e nenhuma obteve gap superior a 5%.
1 2 3
4 5 6
1 2
3 4
5
7
6
8
(a) (b)
CA
1
WA
CA
2
TX
CO
UT
NE
IL
PA
GA
MD
NJ
NY
MI
(c)
Figura 4.3: Topologias de rede com 6 n´os (a), 8 n´os (b) e 14 n´os - NSFNet (c).
69
4.4.1 Contagem de Transceptores
A Figura 4.4 mostra a percentagem do n´umero de transceptores, normalizado pela
quantidade usada na rede opaca, necess´arios para acomodar as demandas de tr´afego
sobre a topologia ogica da rede. As extremidades dos segmentos verticais represen-
tam os resultados aximo e m´ınimo obtidos em uma das 5 matrizes de tr´afego, e as
marca¸oes horizontais, as m´edias. Seguindo essas defini¸oes, pode-se observar uma
redu¸ao consider´avel do n´umero de transceptores `a medida que ao permitidos mais
caminhos ´opticos. Essa caracter´ıstica ´e observada em todas as matrizes de tr´afego.
Comparando, na Figura 4.4, os gr´aficos (a), (b) e (c) nota-se que com o aumento do
n´umero de n´os da topologia estudada, maior e mais clara ´e a tendˆencia da redu¸ao
do n´umero de transceptores. Por´em, esta redu¸ao atinge um limite onde ao ´e mais
poss´ıvel diminuir o n´umero de transceptores com o acr´escimo de caminhos ´opticos.
A Figura 4.4 (a), por apresentar resultados para a rede de 6 os, tem uma
grande varia¸ao percentual do n´umero de transceptores devido `as diferen¸cas entre
as matrizes de tr´afego. Devido a pouca possibilidade de caminhos, as topologias
menores sofrem varia¸oes maiores de configura¸oes. Como exemplo num´erico, para
uma das matrizes de tr´afego acomodadas na rede de 6 os (Figura 4.3 (a)), em
um cen´ario onde a rede ´e opaca, foram encontrados 25 transceptores necess´arios
para atender a todas as demandas. Permitindo o uso de cinco caminhos ´opticos
transparentes, obteve-se uma redu¸ao de 7 transceptores para esta rede. Poem,
nenhuma melhoria foi observada ap´os este ponto. A Figura 4.4 (c), que apresenta
resultados obtidos analisando a topologia NSF-Net (Figura 4.3 (c)), mostra que
as redes maiores sofrem menos com as varia¸oes do tr´afego tornando a redu¸ao
do umero de transceptores mais claros. Os trˆes casos estudados apresentaram
patamares de redu¸ao diferentes, com aproximadamente 20%, 30% e 45% para os
casos da Figura 4.4 (a), (b) e (c), respectivamente. Todavia, por observao dos
gr´aficos tem-se que em todos os casos o limite da redu¸ao do n´umero de transceptores
foi obtido com aproximadamente 75% da quantidade de caminhos ´opticos permitidos
(L), de forma que ap´os esse patamar ao houve redu¸ao do n´umero de transceptores.
A Tabela 4.1 mostra o n´umero de caminhos ´opticos (|Ec|) alcan¸cados pela
heur´ıstica, com a limita¸ao do n´umero de comprimentos de onda (W) dispon´ıveis
nos enlaces f´ısicos, para as trˆes topologias na Figura 4.3. Estes resultados, apesar de
ao serem o foco da an´alise desta se¸ao, s˜ao importantes de serem mencionados. A
70
0 1 2 3 4 5 6 7 8
70
75
80
85
90
95
100
Número de Transceptores (%)
Caminhos Ópticos
0 2 4 6 8 10 12 14 16 18
65
70
75
80
85
90
95
100
Número de Transceptores (%)
Caminhos Ópticos
0 10 20 30 40 50 60 70
50
55
60
65
70
75
80
85
90
95
100
Número de Transceptores (%)
Caminhos Ópticos
(a)
(b)
(c)
Figura 4.4: N´umero de transceptores (normalizados) vs n´umero de caminhos ´opticos
permitidos, para as redes de 6 n´os (a), 8 n´os (b) e NSF-Net (c).
71
Tabela 4.1: N´umero aximo caminhos ´opticos limitando os comprimentos de onda
em cada enlace.
6 n´os 8 n´os NSF-Net
W |Ec| |Ec| |Ec|
2 2 2 4
3 5 6 7
4 6 12 11
5 8 15 13
6 - 18 20
7 - - 22
.
.
.
.
.
.
.
.
.
.
.
.
15 - - 70
redu¸ao do n´umero de comprimento de ondas reduz tamb´em o n´umero de vari´aveis
do modelo e, conseq¨uentemente, o tempo computacional. Como aspecto pr´atico, a
redu¸ao do n´umero de comprimentos de onda em uma fibra contribui para a redu¸ao
de interferˆencia ao-linear, por exemplo, a auto-modula¸ao de fase, a modula¸ao de
fase cruzada e a mistura de quatro ondas [AGR 01].
Como foi anteriormente citado, os caminhos ´opticos devem ser alocados na rede
de maneira que os fisicamente adjacentes continuem tendo uma conex˜ao transpa-
rente, mesmo ap´os a adi¸ao dos caminhos ´opticos. Como exemplo, assuma a topolo-
gia f´ısica da rede de 6 os apresentada na Figura 4.3 (a). Considerando que a 2
comprimentos de onda dispon´ıveis, a Figura 4.5 ilustra uma solu¸ao encontrada pela
heur´ıstica. Note que ´e preservado pelo menos um comprimento de onda dedicado
`a conex˜ao direta de os fisicamente adjacentes. Como ´e mostrado na Tabela 4.1,
5 comprimentos de onda foram suficientes para fazer com que a rede de 6 os se
tornasse totalmente conectada por liga¸oes ponto a ponto transparentes.
1 2 3
4 5 6
Figura 4.5: Ilustra¸ao de uma solu¸ao encontrada pela heur´ıstica para a rede de 6
os com 2 comprimentos de onda
72
4.4.2 Processamento
0 1 2 3 4 5 6 7 8
20
30
40
50
60
70
80
90
100
110
120
Processamento Eletrônico (%)
Caminhos Ópticos
0 2 4 6 8 10 12 14 16 18
10
20
30
40
50
60
70
80
90
100
Processamento Eletrônico (%)
Caminhos Ópticos
0 10 20 30 40 50 60 70
0
10
20
30
40
50
60
70
80
90
100
110
Processamento Eletrônico (%)
Caminhos Ópticos
(b)
(a)
(c)
Figura 4.6: Processamento (normalizado) vs N´umero de caminhos ´opticos para a
redes de 6 n´os (a), 8 n´os (b) e NSF-Net (c).
73
As Figuras 4.6 (a), (b) e (c) mostram a redu¸ao do processamento eletrˆonico
do tr´afego encontrado para as redes de 6 os, 8 os e 14 n´os, respectivamente. A
primeira observao ´e que, assim como ocorre com o n´umero de transceptores, o
percentual da redu¸ao do processamento eletrˆonico da rede tamb´em ´e crescente com
o tamanho da topologia. Essa redu¸ao atingiu patamares de aproximadamente 60%,
70% e 90% para as redes de 6 os, 8 os e NSF-Net, respectivamente. Note que,
mesmo com a possibilidade de uma rede totalmente transparente, o modelo ainda
ao alcan¸cou o processamento igual a zero. A explica¸ao para isso se deve ao fato
de que a fun¸ao objetivo minimiza apenas o n´umero de transceptores, e a redu¸ao
do processamento ´e obtida como consequˆencia da presen¸ca dos caminhos ´opticos.
Isso ainda implicou em resultados onde se atingiu mais de 100% do processamento
normalizado pela rede opaca, como ocorreu para 1 caminho ´optico na Figura 4.6 (a)
e 10 caminhos ´opticos na Figura 4.6 (c).
´
E not´orio ainda, na Figura 4.6, que para
algumas matrizes de tr´afego, podem ocorrer varia¸oes com o acr´escimo da possibili-
dade de novos caminhos ´opticos, como nas abscissas 8 e 10 da Figura 4.6 (b). Por´em,
apesar dessa varia¸ao do processamento para algumas matrizes de tr´afego, o uso dos
caminhos ´opticos alcan¸cou uma excelente redu¸ao do processamento eletrˆonico nos
os. Vale a pena destacar, como aspecto pr´atico, que como consequˆencia da redu¸ao
do processamento, obt´em-se tamb´em um aumento da confiabilidade da rede, pois
em caso de uma falha em um switch eletrˆonico, a quantidade de tr´afego perdida ser´a
menor.
4.5 Sum´ario
Foram propostos nesse cap´ıtulo dois m´etodos para resolver o problema de grooming
de tr´afego em redes transl´ucidas. O primeiro, composto por dois modelos ILPs,
ilustra o problema estudado com uma apresenta¸ao similar a outras encontradas
na literatura, por exemplo [ZHU 02]. Enquanto o segundo, composto por uma
heur´ıstica e um modelo ILP, foi usado para gerar os resultados num´ericos. Nos re-
sultados num´ericos, atraes da adi¸ao progressiva dos caminhos ´opticos foi poss´ıvel
constatar, nas Figuras 4.4 e 4.6, uma redu¸ao progressiva do n´umero de transcep-
tores e do processamento eletrˆonico. Tamb´em ´e importante destacar a convergˆencia
dos gr´aficos observados nessas figuras. Os resultados demonstram que a redu¸ao do
n´umero de transceptores e processamento eletrˆonico est´a limitada, em aproximada-
74
mente 75% do n´umero de caminhos ´opticos poss´ıveis. Na pr´atica, essa convergˆencia
significa que a instala¸ao de um n´umero de caminhos ´opticos superior a esse limi-
te, implicar´a em um poss´ıvel aumento dos custos gerenciais da rede, sem que haja
benef´ıcios. Esse resultado tamb´em pode ser aplicado para a constru¸ao de algorit-
mos heur´ısticos, pois reduz o espa¸co de busca da heur´ıstica evitando a inser¸ao de
elementos desnecess´arios.
Como o objetivo desta etapa do trabalho ´e uma quantifica¸ao dos benef´ıcios
obtidos pelos caminhos ´opticos, os aspectos de camada f´ısica para a implementa¸ao
de um caminho ´optico ao foram considerados. Por´em, em investiga¸oes futuras,
algoritmos para a escolha dos caminhos ´opticos podem considerar alguns aspectos
da camada f´ısica, como o comprimento e n´umero de saltos dos caminhos ´opticos.
Cap´ıtulo 5
Uma Heur´ıstica para o TGP
Apesar dos bons resultados obtidos pelo algoritmo h´ıbrido, proposto no Cap´ıtulo 4,
a fase onde ´e empregado o modelo ILP do algoritmo ainda limita o projeto `as redes
de edio porte, e redes com algumas dezenas de os continuam intrat´aveis para um
tempo de otimiza¸ao vi´avel. Assim, neste cap´ıtulo ´e proposta uma heur´ıstica que,
de posse dos caminhos ´opticos, usa quatro fun¸oes asicas para gerar e aprimorar
uma configura¸ao de rede: uma fun¸ao para gerar a solu¸ao inicial, uma fun¸ao de
elimina¸ao de canais subutilizados, uma busca local e uma fun¸ao para tentar evitar
m´ınimos locais. Adicionalmente, ao apresentados alguns resultados num´ericos com-
parados com resultados obtidos pelo modelo h´ıbrido proposto no cap´ıtulo anterior.
5.1 Introdu¸c˜ao
O problema do TGP minimizando o umero de transceptores em uma rede ´optica,
como a mencionado, ´e NP-Completo. Assim, com o intuito de resolver redes de
tamanhos maiores, ´e comum o particionamento de tal problema, nos quatro sub-
problemas referidos a seguir.
Determina¸ao da topologia virtual (VTD).
Roteamento dos caminhos ´opticos sobre a camada f´ısica.
Atribui¸ao dos comprimentos aos caminhos ´opticos.
Roteamento das requisi¸oes de conex˜oes de baixa velocidade sobre a topologia
virtual (TGP).
75
76
Existem trabalhos onde o TGP ´e considerado como um caso particular do VTD,
como em [ZHU 05]. Por´em, admitindo essa subdivis˜ao do problema do projeto
de redes ´opticas, podem-se identificar as seguintes propostas para cada um dos
subproblemas: no Cap´ıtulo 3, os modelos NA e AC ao propostos para encontrar
resultados ´otimos para o problema de TGP e atribui¸ao dos comprimentos de onda,
enquanto que os modelos rNA e rAC ao propostos apenas para o TGP. No Cap´ıtulo
4, ´e proposto um modelo h´ıbrido onde uma heur´ıstica pr´e-seleciona e roteia um
conjunto de caminhos ´opticos poss´ıveis. Em seguida um modelo ILP escolhe os
caminhos ´opticos que devem ser efetivamente usados e encontra uma solu¸ao para
o TGP. Seguindo a tendˆencia de tentar encontrar solu¸oes de boa qualidade em
um tempo computacional vi´avel, nesse cap´ıtulo ´e proposta uma heur´ıstica para o
problema descrito no Cap´ıtulo 4.
5.1.1 Trabalhos Relacionados e Contribui¸oes
Na literatura existem alguns algoritmos que a ao bem conhecidos para alguns desses
subproblemas. Dentre os problemas mencionados, provavelmente o mais estudado
´e o problema de roteamento e atribui¸ao dos comprimentos de onda. Para o rotea-
mento, os algoritmos encontrados na literatura podem ser divididos em trˆes etodos
asicos: rota fixa, rotas alternativas pr´e-fixadas e rotas adaptativas [ZAN 00], onde
o m´etodo de rota fixa utiliza apenas uma rota poss´ıvel para atender cada conex˜ao.
Assim, caso n˜ao haja mais recurso em algum ponto da rota a conex˜ao ´e bloqueada.
O etodo de rotas alternativas ´e similar ao anterior, por´em possui um conjunto
de poss´ıveis rotas. Para o mecanismo de rotas adaptativas o caminho ´e calculado
dinamicamente conforme o estado atual de rede. Junto com o roteamento, ´e comum
encontrar a atribui¸ao dos comprimentos de onda, formando o conhecido problema
de RWA. Em [ZAN 00] ao analisados 10 algoritmos para a atribui¸ao dos compri-
mentos de onda, sendo constatado um similar desempenho entre todos eles.
Para o TGP a existem propostas na literatura uma grande quantidade de
heur´ısticas, sendo algumas citadas a seguir. Uma das formas de se construir uma
heur´ıstica ´e atrav´es do uso de uma meta-heur´ıstica. Sendo a meta-heur´ıstica uma
representa¸ao de um algoritmo geral que pode ser aplicado em diferentes problemas
de otimiza¸ao, necessitando apenas de pequenas modifica¸oes para a adapta¸ao de
um problema espec´ıfico [BLU ]. A seguir ao citadas e comentadas algumas meta-
77
heur´ısticas aplicadas ao TGP:
GRASP: em [BRU 02] ´e apresentado um algoritmo para encontrar solu¸oes
para o VTD com a minimiza¸ao do n´umero de caminhos ´opticos, por´em o
trabalho ainda carece de uma compara¸ao com modelos exatos e a apresenta¸ao
de uma busca local sistem´atica, que os autores sugerem como trabalhos futuros;
Algoritmo Gen´etico: em [AWW 06] ´e apresentado junto com outras heur´ısticas
para a compara¸ao. Contudo, em geral, uma compara¸ao de resultados entre
heur´ısticas n˜ao ´e muito confi´avel, pois nenhuma delas assegura a otimalidade
de resultados ou um limite inferior nos resultados;
Simulated Annealing: em [DAT 03] ´e apresentado para o problema do TGP,
com prote¸ao para falha ´unica de enlace. Como o trabalho anteriormente men-
cionado, esse tamb´em apresenta a compara¸ao com outras heur´ısticas, por´em
inclui nos resultados num´ericos uma compara¸ao com modelos ILPs, admitindo
solu¸oes com 10% de gap. Adicionalmente, a proposta do trabalho se limita
ao estudo das redes opacas e, infelizmente, tamem ao oferece suporte para
a reprodu¸ao dos resultados, omitindo as matrizes de tr´afego estudadas;
Busca Tabu: aplicado ao TGP ´e detalhada em [BOU 06]. Contudo, o tra-
balho ao apresenta compara¸oes ou meios para reprodu¸ao dos resultados. O
processo usado para gerar a solu¸ao inicial para a heur´ıstica nesse trabalho
´e similar ao proposto neste Cap´ıtulo. Por´em, como nas outras heur´ıstica
citadas, nos algoritmos propostos ao existe a possibilidade da sub-divis˜ao
de uma demanda em mais de uma conex˜ao. Como a divis˜ao de demandas
´e frequentemente observada em solu¸oes para o TGP geradas por modelos
´otimos, a heur´ıstica proposta nesse cap´ıtulo tenta imitar esse fenˆomeno para
a redu¸ao do n´umero de transceptores;
encontram-se ainda outros m´etodos, como heur´ısticas baseadas na intui¸ao
do autor apresentada em [ZHU 05]. A heur´ıstica apresentada nesse trabalho
´e extremamente simples, primeiro as conex˜oes de um salto e em seguida o
restante, em ordem decrescente da quantidade de demanda. Note que tal
algoritmo apenas constr´oi uma solu¸ao, ao apresentando nenhum tipo de
busca local ou tentativa de melhoria da solu¸ao gerada.
78
A heur´ıstica proposta nesse cap´ıtulo segue a subdivis˜ao do problema de otimiza¸ao
das redes ´opticas descrita a seguir. Ap´os a pr´e-sele¸ao dos caminhos ´opticos, o
m´etodo utilizado para otimiza¸ao do TGP ´e composto basicamente de quatro fun¸oes:
a constru¸ao de uma solu¸ao inicial, um etodo para eliminar canais subutiliza-
dos, um procedimento de busca local e um procedimento para gerar perturba¸oes
aleat´orias no processo de busca local. Como na fase inicial desse trabalho foi poss´ıvel
obter bons resultados, mesmo sem o procedimento de busca local, este etodo
tamb´em ´e apresentado. Na pr´oxima se¸ao ´e apresentado um pseudo-c´odigo dando
uma vis˜ao geral da constru¸ao da heur´ıstica, bem como uma explica¸ao de cada
uma das fun¸oes que a comp˜oe. Na Se¸ao 5.3 ao apresentados alguns resultados
num´ericos para redes de 6 e 14 os, contendo ainda os resultados obtidos por um
modelo ILP para a compara¸ao. Finalmente, na ´ultima se¸ao, ao apresentadas
algumas conclus˜oes e sugeridas poss´ıveis formas de evolu¸ao desta heur´ıstica.
5.2 Heur´ıstica para o TGP em Redes Transcl´ucidas
Na fase inicial desse trabalho foi apresentado como proposta de heur´ıstica o algo-
ritmo similar ao descrito o pseudo-c´odigo do Algoritmo 5.1, diferenciado apenas pelo
procedimento de Busca Local, que ao estava contido no algoritmo inicial. Tal al-
goritmo, apesar de ser considerado extremamente simples, a obt´em resultados de
boa qualidade quando comparados com modelos exatos. Assim, o pseudo-c´odigo do
Algoritmo 5.1, representa em linhas gerais a heur´ıstica proposta. A pr´e-sele¸ao e o
roteamento do conjunto de caminhos ´opticos ´e realizada da mesma forma como foi
feito no cap´ıtulo anterior, separado do algoritmo usado para resolver o TGP. Assim,
os caminhos ´opticos s˜ao apenas novas restri¸oes para o TGP, que agora ´e resolvido
pelos procedimentos Squeeze, BL e PA do Algoritmo 5.1).
De posse dos poss´ıveis caminhos ´opticos resultantes do VTD, ´e necess´aria uma
solu¸ao inicial para dar in´ıcio aos procedimentos para as melhorias de solu¸ao, pro-
postos no Algoritmo 5.1. Vale destacar que em todos os procedimentos onde ´e
realizado algum roteamento de demanda, ´e permitida a subdivis˜ao das demandas
em canais e rotas diferentes. Mais adiante ´e exemplificado este recurso.
Para gerar o cen´ario inicial, ´e utilizado um algoritmo para encontrar as k-menores
rotas entre cada par origem e destino. Nesse trabalho ´e usado o algoritmo de Yen
79
Algoritmo 5.1 Heur´ıstica
1: Entrada: Matriz de tr´afego e a topologia da rede
2: Projeto de Topologia Virtual (Algoritmo 4.1)
3: Gerar Solu¸ao Inicial
4: Squeeze (Algoritmo 5.2)
5: for Crit´erio de parada 1 do
6: Busca Local - BL)
7: for Crit´erio de parada 2 do
8: Perturba¸ao Aleat´oria - PA(Algoritmo 5.3)
9: end for
10: end for
[YEN 71]. Durante a constru¸ao da solu¸ao inicial, o algoritmo primeiramente tenta
atribuir a rota com o menor n´umero de saltos. Para gerar solu¸oes iniciais de boa
qualidade foram analisados trˆes processos, atribuindo as demandas na ordem cres-
cente, decrescente e arbitr´aria. Adicionalmente, tem-se que as redes estudadas neste
cap´ıtulo sempre ter˜ao capacidade para acomodar as demandas de tr´afego. Apenas
por quest˜oes de implementa¸ao, os comprimentos de onda foram previamente orde-
nados como, {1, 2, ..., w}. Assim, tˆem-se os seguintes casos:
1. A demanda entre o par sd ´e menor do que a banda dispon´ıvel no “menor”canal
de uma ´unica rota, sendo as rotas ordenadas pela quantidade de umero de
saltos. Neste caso, a atribui¸ao ´e trivial e a demanda ´e imediatamente alocada.
2. A demanda entre e o par sd ´e maior do que a banda dispon´ıvel no “menor”canal
de uma ´unica rota, por´em ainda existem outros canais dispon´ıveis nessa rota.
Assim, ´e alocada a maior quantidade de demanda poss´ıvel no canal “menor”e
o restante nos canais seguintes, obedecendo a ordem pr´e-estabelecida. Note
que, nesse caso, a demanda ´e subdividida usando mais de um canal na mesma
rota.
3. A demanda entre o par sd ´e maior do que a banda dispon´ıvel no “menor”canal
de uma ´unica rota, sendo que a ao existem mais canais dispon´ıveis nesta
rota. Assim, ´e alocada a maior quantidade de demanda poss´ıvel nesta rota e
o restante da demanda ´e alocado na pr´oxima rota, seguindo os procedimentos
1 e 2 anteriores. Neste caso, a demanda tamem ´e subdividida, por´em usando
mais de uma rota.
80
Para as fun¸oes a seguir, denotar-se-´a uma configura¸ao/solu¸ao da rede por S
e o n´umero de transceptores usados nesta solu¸ao por NT (S).
Squeeze:
Essa fun¸ao tem como objetivo eliminar dispositivos subutilizados, atrav´es de um
procedimento determin´ıstico descrito no pseudoodigo do Algoritmo 5.2.
Algoritmo 5.2 Squeeze
1: Entrada: Uma configura¸ao da rede, C
sd
r,w
2: for Para cada canal w sobre uma conex˜oes ponto-a-ponto (enlace f´ısico ou cam-
inho ´optico) ij. do
3: if w ´e subutilizado then
4: Encontrar todas as demandas sd passando por este canal.
5: Re-rotear sd usando um caminho disjunto de ij, criando uma nova con-
figura¸ao C
sd
r,w
.
6: if NT (C
sd
r,w
) < NT (C
sd
r,w
) then
7: Aceitar C
sd
r,w
como a configura¸ao atual.
8: end if
9: end if
10: end for
Descri¸ao do Algoritmo 5.2:
O procedimento percorre todos os comprimentos de onda em cada conex˜ao ponto-
a-ponto (enlace f´ısico ou caminho ´optico transparente), buscando canais com um
baixo n´ıvel de utiliza¸ao. Em cada enlace, os comprimentos de onda ao numerados
aleatoriamente, de 1 at´e o n´umero aximo de canais permitidos. Por sua vez, os
enlaces ao arbitrariamente ordenados. Assim, o etodo percorre todos os enlaces e
comprimentos de onda, ordenados arbitrariamente. Quando encontrado um compri-
mento de onda w na condi¸ao de subutilizado, o algoritmo tenta re-rotear todas as
demandas sd passando por este w, de forma que cada nova rota deve ser disjunta do
enlace ij, onde foi encontrado o comprimento de onda w com baixa utiliza¸ao. Esta
tarefa tem o objetivo de eliminar um transceptor do cen´ario de rede C
sd
r,w
, que est´a
sendo subutilizado. Os caminhos alternativos ao escolhidos priorizando as rotas
com menor n´umero de saltos. Para isso ao encontrados na literatura algoritmos
para os k caminhos m´ınimos, como por exemplo o Algoritmo de Yen [YEN 71], a
mencionado. Por observao, ´e considerado um canal subutilizado aquele trans-
portando tr´afego abaixo de 25% da capacidade. Acima desse valor, observou-se
que, quando o algoritmo elimina o uso de um componente, acaba tornando subu-
81
tilizado outro ponto da rede. Resultados num´ericos comprovando estas afirma¸oes
ao apresentados mais adiante.
Perturba¸ao Aleat´oria
Esse procedimento realiza uma erie de perturba¸oes aleat´orias na solu¸ao atual,
atrav´es do re-roteamento de uma demanda sd escolhida. O objetivo aqui ´e tentar
escapar de poss´ıveis m´ınimos locais encontrados pela Busca Local. O Algoritmo 5.3
mostra o pseudo-c´odigo do procedimento. Apesar do algoritmo usar uma id´eia bem
simples, foi poss´ıvel obter bons resultados.
Algoritmo 5.3 PA
1: Escolha aleat´oria de uma demanda sd
2: Desalocar traf[s][d] do(s) caminho(s) usado(s) para atender sd
3: Escolha aleat´oria de uma novo caminho para sd
4: if NW (C
sd
r,w
) < NW (C
sd
r,w
) then
5: Aceitar C
sd
r,w
como solu¸ao da configura¸ao atual
6: end if
Descri¸ao do Algoritmo 5.3:
Em uma configura¸ao da rede C
sd
r,w
´e escolhida aleatoriamente uma demanda sd,
sendo todos os pares sd equiprov´aveis. Assim, toda a demanda de sd (traf[s][d])
´e realocada em um novo caminho diferente do anterior, gerando assim uma nova
configura¸ao da rede C
sd
r,w
. Como anteriormente, as possibilidades das novas rotas
tamb´em ao equiproaveis. Caso C
sd
r,w
tenha um menor n´umero de transceptores em
rela¸ao `a configura¸ao C
sd
r,w
, ´e considerada como cen´ario atual.
Busca Local
Primeiramente, ´e necess´ario definir a vizinhan¸ca onde ´e realizada a busca por
uma solu¸ao melhor. Assim, seja C
sd
r,w
uma configura¸ao da rede, onde tal estrutura
cont´em informa¸ao sobre o particionamento, roteamento, atribui¸ao de comprimento
de onda e carga de todas as demanda de origem-destino (sd). Como as rotas ao
indexadas em ordem crescente do n´umero de saltos, a vizinhan¸ca assumida ´e definida
como a troca de uma rota de ´ındice t por outra de ´ındice (t + 1) ou (t 1), para
todas as subdivis˜oes de cada demanda sd. Como exemplo, assuma uma configura¸ao
S onde existe uma demanda de 48 unidades de tr´afego do n´o 2 para o n´o 5, sendo
roteadas 32 unidades de tr´afego pela rota 0 e comprimento de onda 1, e 16 unidades
de tr´afego sendo roteados usando a rota 1 e comprimento de onda 0. Seguindo o
82
estilo das vari´aveis definidas no Cap´ıtulo 3, C
s,d
r,w
representa a quantidade de tr´afego
com origem no o s e destino no o d usando a rota r e comprimento de onda w. Na
Figura 5.1 ´e destacada, com uma elipse tracejada, a parte da vizinhan¸ca de S que
est´a relacionada com o par origem-destino (2,5). Note que o ´ındice do comprimento
de onda est´a com uma interroga¸ao, isso significa que o algoritmo tenta alocar a
demanda em quest˜ao em qualquer comprimento de onda daquela rota; caso ao seja
poss´ıvel, este elemento ´e exclu´ıdo da vizinhan¸ca de C
sd
r,w
. Assim, a busca local ´e
realizada em toda vizinhan¸ca, ou seja, as trocas descritas ao realizadas para todo
par sd.
C = 32
C
= 16
C
= 16
C
= 16C = 32
Figura 5.1: Ilustra¸ao de uma parte da vizinhan¸ca de uma solu¸ao S relacionada
aos n´os de origem-destino (2,5)
Durante o processo de an´alise da vizinhan¸ca, caso um novo cen´ario encontrado
possua uma configura¸ao com um n´umero menor de transceptores, este novo cen´ario
´e considerado como a solu¸ao atual. Para o caso de uma solu¸ao possuir o mesmo
n´umero de transceptores do cen´ario atual, ´e decidido aleatoriamente, com uma
probabilidade de 50%, se esse elemento da vizinhan¸ca se torna o cen´ario atual. Isso
possibilita a troca sistem´atica de configura¸ao sem que haja aumento do n´umero de
transceptores.
5.3 Avalia¸ao da Heur´ıstica
A avalia¸ao da heur´ıstica foi feita sobre duas topologias de rede, de 6 e 14 os
apresentadas no Cap´ıtulo 3. A Figura 5.2 ilustra a topologia f´ısica dessas duas redes.
As matrizes de tr´afego tamb´em s˜ao as mesmas usadas no Cap´ıtulo 3, apresentadas
no Anexo 5.2 como as matrizes A.1 e A.5, respectivamente. O desempenho da
heur´ıstica foi avaliado com um n´umero crescente de caminhos ´opticos, semelhante
ao que foi feito no cap´ıtulo anterior.
Para a compara¸ao com os resultados obtidos pela heur´ıstica proposta, tamem
83
3
1
0
4
2
5
(a)
CA
1
WA
CA
2
TX
CO
UT
NE
IL
PA
GA
MD
NJ
NY
MI
(b)
Figura 5.2: Topologias das redes de 6 os (a) e 14 os (b), a apresentadas no
Cap´ıtulo 3
ao apresentados os resultados obtidos pela heur´ıstica sem o processo de busca local
e pelo etodo h´ıbrido, proposto no cap´ıtulo anterior. Contudo, os processos de
resolu¸ao dos modelos ILPs foram limitados a aproximadamente 1 hora. Os modelos
ILPs gerados pelo m´etodo h´ıbrido foram resolvidos usando o software Cplex 9.0.
5.3.1 Avalia¸ao dos Parˆametros
Nesta se¸ao ´e analisado o desempenho de cada procedimento utilizado na heur´ıstica
e os resultados obtidos com a varia¸ao dos parˆametros existentes em cada um deles.
Solu¸ao Inicial
A Figura 5.3 apresenta os resultados num´ericos obtidos pela fun¸ao usada para gerar
a solu¸ao inicial, comparando a acomoda¸ao das demandas em ordem crescente (as
demandas de menor carga primeiro), arbitr´aria e decrescente(as demandas de maior
carga primeiro). Contr´ario ao esperado nota-se claramente que a ordena¸ao de-
crescente produz solu¸oes iniciais de baixa qualidade, o que pode comprometer o
desempenho das fun¸oes Squeeze e BL, afetando tamb´em o resultado final obtido
pela heur´ıstica. Essa caracter´ıstica se deve ao fato do algoritmo permitir o parti-
cionamento do tr´afego em rotas e canais diferentes. Adicionalmente, comparando
a ordena¸ao crescente e arbitr´aria observa-se que a primeira ´e ligeiramente melhor,
por´em, a casos onde a ordena¸ao arbitr´aria obteve resultados melhores do que a
ordena¸ao crescente. Contudo, os resultados num´ericos mostraram que a diferen¸ca
entre estas duas formas de ordena¸ao, crescente e arbitr´aria, ao ´e suficiente para
influenciar no desempenho das fun¸oes Squeeze e BL.
84
5 15 25 35 45 55 65
0
50
100
150
200
mero de caminhos ópticos
Número de transceptores
Crescente
Arbitrária
Decrescente
Figura 5.3: An´alise de desempenho do procedimento que gera a Solu¸ao Inicial
Parˆametro de Subutiliza¸ao dos Comprimentos de onda
A Figura 5.4 mostra os resultados obtidos para as configura¸oes iniciais e o pro-
cedimento Squeeze em alguns dos n´ıveis de conectividade estudados (i.e., n´umero
de caminhos ´opticos diferentes). O procedimento Squeeze ´e analisado variando o
parˆametro que define quais comprimentos de onda est˜ao sendo subutilizados. As-
sim, os resultados investigados ao: o resultado obtido pelo procedimento usado
para construir a solu¸ao inicial e o procedimento de Squeeze, considerando canais
subutilizados como 25%, 50% e 75% da sua capacidade. O procedimento que obteve
melhor desempenho considerava a extin¸ao dos canais utilizando 25% da sua capaci-
dade, exceto para 15 e 25 caminhos ´opticos, que obtiveram resultados poximos ao
de 50%. Portanto, o crit´erio para determinar a sub-utiliza¸ao de comprimentos de
onda usados na heur´ıstica foi de 25% da capacidade do canal. Adicionalmente, note
que a tentativa de deixar todos os comprimentos de onda com uma alta utiliza¸ao
pode piorar a solu¸ao inicial, que j´a ´e considerada boa. Por exemplo, para os casos
da rede com 5 e 65 caminhos ´opticos.
Crit´erios de Parada
O Algoritmo 5.1 apresenta dois loops, sendo o primeiro para repetir o processo de
busca local e, interno a esse, outro para repetir o dist´urbio aleat´orio. Por quest˜ao de
simplicidade foi adotado o n´umero de itera¸oes como crit´erio de parada em ambos
85
5 15 25 35 45 55 65
0
50
100
150
200
Número de transceptores
mero de caminhos ópticos
Solução inicial
Squeeze (25%)
Squeeze (50%)
Squeeze (75%)
Figura 5.4: An´alise de desempenho do procedimento de Squeeze
os casos. A escolha desses n´umeros de itera¸oes foi puramente emp´ırica, atraes dos
resultados ilustrados nas Figuras 5.5 e 5.6.
A Figura 5.5 representa alguns dos resultados obtidos pelo procedimento de
Perturba¸ao Aleat´oria. Para esse teste, o algoritmo PA foi aplicado sobre a solu¸ao
inicial, variando apenas o umero de itera¸oes (para 100, 1000 e 10000 itera¸oes).
Nota-se que na maioria dos casos, 100 itera¸oes ao ao suficientes para uma melhora
consider´avel, sendo que 1000 e 10000 itera¸oes obtiveram resultados bem pr´oximos.
Para os resultados com 15 e 35 caminhos ´opticos, 1000 itera¸oes alcan¸caram um
resultado ligeiramente inferior ao atingido com 10000 itera¸oes. Esse fenˆomeno se
deve `a total aleatoriedade no procedimento. A Figura 5.6 ilustra o desempenho
do procedimento de busca local em rela¸ao ao n´umero de itera¸oes. Nota-se que
10 ou 100 itera¸oes atingiram os mesmos resultados, melhorando apenas ap´os 1000
itera¸oes. Para simplificar o gr´afico ao apresentadas at´e 1000 itera¸oes, por´em
realizando mais testes, para o procedimento BL, constatou-se ao haver mais ganhos
na qualidade das solu¸oes a partir de 1000 itera¸oes. Sendo assim, para o Crit´erio
de Parada 1 considerou-se 1000 itera¸oes, enquanto que para o Crit´erio de Parada
2 considerou-se 100 itera¸oes. Cabe lembrar que o loop do procedimento PA est´a
dentro do Crit´erio de Parada 1, que j´a possui 1000 itera¸oes.
86
5 15 25 35 45 55 65
0
50
100
150
200
Número de transceptores
mero de caminhos ópticos
Solução inicial
PA (100 iterações)
PA (1000 iterações)
PA (10000 iterões)
Figura 5.5: An´alise de desempenho do procedimento de Perturba¸ao Aleat´oria, com
o Crit´erio de Parada 2
5 15 25 35 45 55 65
0
50
100
150
200
Número de transceptores
mero de caminhos ópticos
Solução inicial
BL (10 iterações)
BL (100 iterações)
BL (1000 iterações)
Figura 5.6: An´alise de desempenho do procedimento de Perturba¸ao Aleat´oria, com
o Crit´erio de Parada 1
Compara¸ao da heur´ıstica com um Modelo ILP
As Figuras 5.7 e 5.8 trazem os resultados obtidos pelas heur´ısticas propostas e pelo
modelo h´ıbrido, para as redes de 6 e 14 n´os, respectivamente. A abscissa apresenta
o n´umero de caminhos ´opticos dispon´ıveis para rede e a ordenada tr´as o n´umero
de transceptores obtidos em cada instˆancia. Adicionalmente, o umero no topo
da coluna dos resultados do m´etodo h´ıbrido mostra o gap retornado pelo Cplex
ap´os uma hora de processamento, sendo que as colunas que n˜ao apresentam tal gap
obtiveram o resultado ´otimo para a instˆancia em quest˜ao.
87
A Figura 5.7 apresenta os resultados da heur´ıstica, com e sem busca local, com-
parados com o modelo h´ıbrido usando como fun¸ao objetivo a minimiza¸ao global
do umero de transceptores, para a rede de 6 os ilustrados na Figura 5.2 (a).
Nessa compara¸ao os resultados apresentados pela heur´ıstica com busca local foram
pr´oximos do ´otimo obtidos pelo modelo h´ıbrido. Isto pode ser observado em todos os
n´ıveis de conectividade da rede, desde a rede opaca at´e a rede com a possibilidade de
uso de todos os caminhos ´opticos. Cabe destacar que a rede de seis n´os n˜ao oferece
um umero de vari´aveis suficiente para uma an´alise do tempo computacional, pois
a heur´ıstica ´e resolvida quase que instantaneamente, e o modelo ILP ao excedeu
1 minuto de processamento em nenhuma das instˆancias. Comparando os resultados
heur´ısticos nota-se que a heur´ıstica com busca local obteve melhores resultados em
quase todos os casos, exceto para 4 e 6 caminhos ´opticos, onde as duas obtiveram
os mesmos resultados.
0 1 2 3 4 5 6 7
0
5
10
15
20
25
Número de transceptores
Número de caminhos ópticos
Heurística proposta (sem Busca Local)
Heurística proposta (com Busca Local)
Modelo híbrido
Figura 5.7: Compara¸ao dos resultados obtidos pela Heur´ıstica proposta e pelo
m´etodo h´ıbrido para a rede de 6 n´os
A Figura 5.8 apresenta os resultados obtidos pela heur´ıstica proposta e pelo mod-
elo h´ıbrido (apresentado no Cap´ıtulo 4), com as fun¸oes objetivo de minimiza¸ao
global (express˜ao 3.1) e minimiza¸ao do “pior caso”(express˜ao 3.2), para a rede de
14 os. Comparando os tempos computacionais dos trˆes m´etodos tem-se que: a
formula¸ao ILP com minimiza¸ao global foi interrompida ap´os uma hora de proces-
samento, sendo apresentado o gap no topo de cada coluna, a formula¸ao otimizada
para o min-max ´e resolvida em menos de 1 minuto e a heur´ıstica obt´em o resultado
com aproximadamente 4 minutos. Como esperado, a fun¸ao objetivo (3.1) obtˆem
88
0 5 10 15 20 25 30 35 40 45 50 55 60 65 70
0
50
100
150
200
Número de transceptores
mero de caminhos ópticos
Modelo híbrido (min-max)
Heurística Proposta
Modelo híbrido (Minimização global)
33,3 %
36,1 %
25,7 %
19,3 %
9,4 %
8,7 %
5,9 %
4,5 %
9,9 %
3,7 %
3,7 %
2,7 %
1,9 %
1,8 %
1,9 %
Figura 5.8: Compara¸ao dos resultados obtidos pela Heur´ıstica proposta e pelo
m´etodo h´ıbrido para a rede de 14 os, considerando as fun¸oes objetivo de min-max
e de minimiza¸ao global
melhores resultados em rela¸ao ao n´umero total de transceptores, por´em, o modelo
com esta fun¸ao objetivo mostra claramente uma complexidade computacional mais
elevada, sendo esta complexidade crescente com o n´umero de conex˜oes da rede,
como mostrado atrav´es do gap. Observando os resultados obtidos pela fun¸ao ob-
jetivo (3.2), tal comportamento ´e explicado pelo fato da otimiza¸ao ser feita para
o pior caso. Encontrando o m´ınimo, para o pior caso o modelo pode distribuir o
tr´afego na rede de maneira mais uniforme, aumentando o n´umero total de transcep-
tores. Por´em, quando o novo caminho ´optico acrescido proporciona uma redu¸ao
no “pior caso”, o modelo passa a ter menos espa¸co para rotear o tr´afego, assim
obtendo tamb´em um n´umero baixo de transceptores. Adicionalmente, tem-se que
a formula¸ao minimizando o pior caso obteve o min-max igual 5 transceptores para
a rede opaca (zero caminho ´optico), 4 transceptores para a rede com 5 caminhos
´opticos, 3 para a rede com 10 e 15 caminhos ´opticos, 2 para a rede tendo de 20 a 40
caminhos ´opticos e 1 para a rede tendo acima de 45 caminhos ´opticos.
Comparando os resultados da Heur´ıstica com as duas formula¸oes ILP, na Figura
5.8, nota-se que a Heur´ıstica proposta obteve um resultado entre as duas for-
mula¸oes. Exceto para 45 caminhos ´opticos, onde ambas as formula¸oes ILP foram
melhores do que a Heur´ıstica. Por´em, como podem ser observadas na figura, as for-
89
mula¸oes ILP apresentam dificuldades. Como por exemplo, o fato da minimiza¸ao
global possui uma alta complexidade computacional, exigindo um tempo de proces-
samento muito grande, e os resultados obtidos pelo min-max ao altamente depen-
dentes do umero de caminhos ´opticos dispon´ıveis na rede, ao sendo conhecido a
priori o n´umero de caminhos ´opticos para o melhor desempenho do modelo. En-
quanto a heur´ıstica proposta independe desses fatores.
5.4 Sum´ario
A heur´ıstica proposta neste cap´ıtulo subdivide o problema de VTD e TGP de forma
similar `a feita no cap´ıtulo anterior, onde o algoritmo de VTD se resume em habilitar
os caminhos ´opticos e o TGP ´e respons´avel por escolher o conjunto dos caminhos
´opticos que ao efetivamente usados. A heur´ıstica proposta para o TGP, apresen-
tada neste cap´ıtulo, consiste basicamente em quatro fun¸oes: uma para gerar a
solu¸ao inicial, uma fun¸ao para tentar eliminar canais subutilizados, uma busca
local e uma fun¸ao para gerar um perturba¸ao aleat´oria no processo de busca lo-
cal, tentando “fugir”de poss´ıveis m´ınimos locais. Para avaliar a heur´ıstica, nos
resultados num´ericos, foram usadas duas redes, com 6 e 14 os. Nas primeiras
an´alises feitas para a heur´ıstica, s˜ao apresentados alguns resultados num´ericos com
o desempenho individual de cada procedimento. Al´em disso, ´e mostrado o desen-
volvimento do processo de escolha dos parˆametros envolvidos na heur´ıstica. Em
seguida, faz-se uma compara¸ao da heur´ıstica proposta com os resultados do mode-
lo h´ıbrido, para as fun¸oes objetivo de minimiza¸ao global e min-max. Para a rede
com 6 os, a heur´ıstica obteve resultados pr´oximos aos encontrados pelo modelo
ILP (para a minimiza¸ao global), encontrando o ´otimo para o caso da rede com 2
caminhos ´opticos. Para a rede com 14 os, os resultados da Heur´ıstica proposta
ao comparados um modelo ILP usando as fun¸oes objetivo de minimiza¸ao global
e min-max. Para tais resultados, a Figura 5.8 mostra que a heur´ıstica obtˆem valores
intermedi´arios aos alcan¸cados pelas duas fun¸oes objetivos, por´em, sem as diferentes
dificuldades apresentadas por cada fun¸ao objetivo do modelo. Como por exemplo,
a complexidade do modelo usando a minimiza¸ao global, em rela¸ao ao n´umero de
conex˜oes, e a varia¸ao dos resultados para as diferentes quantidades de caminhos
´opticos, com o min-max. Adicionalmente, os resultados da Figura 5.8 podem ser
utilizados para inferir o crescimento da complexidade do modelo com as fun¸oes
90
objetivos de minimiza¸ao global e min-max, em rela¸ao ao n´umero de conex˜oes de
uma topologia. Para isso basta observar o crescimento do gap ap´os uma hora de
processamento do modelo ILP, na minimiza¸ao global.
Na heur´ıstica proposta, cada fun¸ao apresentada para construir ou melhorar as
solu¸oes do algoritmo, ao gerais a um etodo heur´ıstico, isto ´e, ao facilmente
adapt´aveis `a filosofia da maioria das meta-heur´ısticas conhecidas na literatura. As-
sim, como trabalhos futuros pode-se “evoluir”a heur´ıstica, inserindo novas fun¸oes,
para o uso de outras estrat´egias, como por exemplo, m´ultiplas solu¸oes iniciais ou o
“cruzamento”de solu¸oes.
Cap´ıtulo 6
TGP com Prote¸c˜ao e Restaura¸c˜ao
Nesse cap´ıtulo ao abordados dois aspectos dos projetos da prote¸ao e restaura¸ao
em redes ´opticas com capacidade de grooming. Primeiramente, na Se¸ao 6.2, ao
propostos dois modelos ILP para prote¸ao e restaura¸ao de redes ´opticas com topolo-
gia em malha. Adicionalmente, tem-se que o uso combinado desses dois modelos
produz um etodo iterativo para uma prote¸ao progressiva da rede. Em seguida,
na Se¸ao 6.3, realizou-se um estudo comparativo entre dois m´etodos de prote¸ao
para interconex˜oes de redes com topologia em anel. Para isso foram propostos dois
modelos ILP, um para cada estrat´egia de prote¸ao.
6.1 Introdu¸c˜ao
Uma fibra ´optica pode transportar mais de uma dezena de terabits por segundo
[ZHA 04], atraes da multiplexa¸ao de canais com diferentes comprimentos de onda.
Consequentemente, uma falha nos enlaces ´opticos ou em qualquer elemento da rede
resulta em uma perda muito grande de tr´afego com grandes preju´ızos para a ope-
radora e para os clientes. Assim, a sobrevivˆencia a falhas ´e um assunto de suma
importˆancia para o projeto da rede. Estudos relacionando as taxas de falhas nos
componentes da rede (transmissor, receptor, fibra, etc) e o tempo necess´ario para
a restaura¸ao indicam que o rompimento da fibra ´e a falha mais comum e a que
necessita de maior tempo para reparo [TO 94]. Portanto, ´e nesse contexto de falha
que est´a situada a maioria dos trabalhos relacionados `a sobrevivˆencia das redes
´opticas, como por exemplo [FAN 03, RAM 99b, OU 03, YAO 05].
91
92
Tradicionalmente, as redes ´opticas foram inicialmente desenvolvidas para topolo-
gia em anel, como ocorreu nas redes SDH de primeira gera¸ao. A popularidade das
redes baseadas em anel se deve principalmente `a simplicidade do gerenciamento e `as
propriedades de sobrevivˆencia, como o fato do tempo de restaura¸ao ser inferior a
50ms [G.7 96]. Contudo, essa topologia apresenta uma baixa eficiˆencia de utiliza¸ao
de recursos e o padr˜ao para redes SDH limitam o tamanho dos an´eis em at´e 16 n´os
[G.7 96]. Com o crescimento das redes, as topologias em evolu´ıdo para redes em
malha e multi-anel, que ser˜ao os objetos de estudo nas Se¸oes 6.2 e 6.3.
Na pr´oxima se¸ao, ao apresentados alguns conceitos necess´arios para o estudo
do projeto de prote¸ao de rede. Na Se¸ao 6.2, ao propostos dois modelos de pro-
grama¸ao linear inteira para a prote¸ao e restaura¸ao da rede frente a falhas es-
pec´ıficas. O modelo proposto para o projeto de prote¸ao considera um cen´ario de
rede e uma falha, para inserir recursos adicionais de forma a assegurar a sobre-
vivˆencia da rede no caso de ocorrer a falha prevista. Adicionalmente, esse projeto
de prote¸ao pode ser realizado com uma reconfigura¸ao local ou global: na re-
configura¸ao local apenas as demandas que foram afetadas diretamente pela falha
ser˜ao realocadas, enquanto que na reconfigura¸ao global ap´os uma falha na rede
todo tr´afego deve ser realocado. Complementando o primeiro modelo, ´e proposta
tamb´em nesta se¸ao uma formula¸ao ILP que busca minimizar o tr´afego perdido
no caso de falha de algum dispositivo da rede. Como os dois modelos usam um
cen´ario inicial e uma altera¸ao neste cen´ario, estes s˜ao capazes de simular qualquer
tipo de falha ou altera¸ao na rede. Ainda tem-se que o uso combinado dos modelos
produz um m´etodo interativo de prote¸ao capaz de encontrar e suprir pontos vul-
ner´aveis na rede. Na Se¸ao 6.3 ´e proposta uma investiga¸ao tratando da prote¸ao
na interconex˜ao de an´eis, com dois os de interconex˜ao entre os an´eis, dual node
interconnection (DNI). Dentre as op¸oes de prote¸ao em DNI, as mais conhecidas e
estudadas neste cap´ıtulo ao o anel virtual, (virtual ring - VR), e Drop and Continue
(D&C) [VAS 04], que s˜ao melhor explicadas na Se¸ao 6.3.
6.2 Sobrevivˆencia de Redes em Malha
Os conceitos asicos sobre prote¸ao e restaura¸ao das redes ´opticas a foram apre-
sentados na Se¸ao 2.1.2. Assim, na pr´oxima se¸ao ao apresentados elementos que
93
est˜ao diretamente relacionados ao estudo da prote¸ao das redes em malha.
6.2.1 Trabalhos Relacionados e Contribui¸oes
Frequentemente, os trabalhos encontrados ao direcionados para a prote¸ao total da
rede, n˜ao permitindo uma prote¸ao parcial ou prote¸ao de elementos espec´ıficos da
rede. Por exemplo, [FAN 03, RAM 99b], que prop˜oem modelos ILPs para prote¸ao.
Ambos os trabalhos apresentam etodos ILPs para o problema de grooming de
tr´afego, com prote¸ao dedicada e compartilhada, para redes em malhas. Por´em,
devido `a complexidade dos modelos, os resultados num´ericos apresentados contem-
plam apenas matrizes esparsas, como ´e o caso de [FAN 03], que resolve um modelo
para uma topologia de 10 n´os com somente 18 demandas.
Recentemente alguns estudos em proposto a investiga¸ao da prote¸ao parcial da
rede, [SIV 06, FAN 05]. Esse tipo de prote¸ao ocorre quando o usu´ario admite que
apenas uma parte da demanda seja recuperada em caso de falha no caminho de tra-
balho. Em [SIV 06] ´e apresentado um etodo para a prote¸ao parcial considerando
tr´afego dinˆamico, portanto sai do escopo de estudo realizado nesse trabalho. Com
propostas de modelos ILP, o trabalho [FAN 05] apresenta duas formula¸oes: uma
para a minimiza¸ao dos custos da rede e outra para a maximiza¸ao da prote¸ao.
Assim, seguindo a id´eia de prote¸ao parcial, nesta se¸ao ao propostos dois modelos
ILPs para prote¸ao e restaura¸ao de redes em malha. Por´em, diferente dos modelos
encontrados na literatura, os modelos aqui propostos consideram o estado atual da
rede, provendo assim uma prote¸ao 1:1.
O primeiro modelo apresentado tem como proposta o projeto de prote¸ao de redes
(PPR). Nesse modelo, dada uma rede previamente configurada e uma ou mais falhas,
o objetivo ´e encontrar o n´umero m´ınimo de transceptores (e seus posicionamentos)
para recuperar 100% do tr´afego, re-roteando apenas as demandas afetadas pela
falha. Nos mesmos moldes do modelo anterior, ´e proposto tamem um projeto
para a restaura¸ao de tr´afego (PRT), onde, identificando recursos dispon´ıveis na
rede, s˜ao propostos esquemas de configura¸ao da rede para restaura¸ao do m´aximo
de tr´afego, em caso de falhas que n˜ao foram previamente previstas no projeto de
prote¸ao. Assim, o uso combinado dos dois modelos forma um etodo interativo,
promovendo uma prote¸ao parcial e progressiva da rede. Esse m´etodo ainda ´e capaz
de encontrar e proteger pontos vulner´aveis na rede.
94
6.2.2 Modelos ILP
O modelo apresentado a seguir representa a formula¸ao matem´atica para a estrat´egia
de prote¸ao anel virtual (virtual ring - VR). Esse modelo segue o etodo de for-
mula¸ao que relaciona os enlaces aos caminhos, devido `a facilidade em se controlar
as rotas a serem usadas. Esse etodo ´e exemplificado pelo modelo rAC do Cap´ıtulo
3. Assim, aqui s˜ao usados os mesmos dados de entrada: R
sd
para o conjunto de ro-
tas entre um par sd; r como ´ındice que identifica uma rota, r R
sd
; e δ
sd
ij,r
como o
parˆametro bin´ario que assume 1 se o enlace ij ´e usado pela rota r para transmitir a
demanda de tr´afego sd, e 0 caso contr´ario. ao usadas tamb´em as mesmas vari´aveis
do rAC: C
sd
r
, que ´e a quantidade de tr´afego que tem como origem e destino o par
de os sd e est´a sendo transmitida atraes da rota r, e X
ij
, que ´e a quantidade
de tr´afego no enlace ij. O modelo deve indexar os caminhos de prote¸ao e uma
vari´avel bin´aria do caminho de trabalho, que ´e usado para garantir que os caminhos
de trabalho e prote¸ao sejam disjuntos. Assim, do modelo discutido no Cap´ıtulo 3,
tem-se que adicionar as vari´aveis com as seguintes defini¸oes:
P
sd
r
representa a quantidade de tr´afego com origem em s e destino em d, usando a
rota r para um caminho de prote¸ao. Os caminhos de prote¸ao considerados
nesse trabalho devem ser disjuntos, por o, aos caminhos de trabalho de cada
demanda.
P B
sd
r
´e uma vari´avel bin´aria que indica o uso da rota r para atender a demanda de
prote¸ao sd. Ent˜ao, ela assume o valor um se a rota r ´e usada pela demanda
sd para prote¸ao, e zero caso contr´ario.
CB
sd
r
´e uma vari´avel bin´aria indicando o uso da rota r para atender a demanda de
trabalho sd.
Assim como todos os modelos tratando do projeto de rede nesse trabalho, o
modelo de redes opacas com prote¸ao 1+1 tamb´em utiliza a minimiza¸ao do n´umero
de conversores ´optico-eletrˆonico-´optico (OEO) como fun¸ao objetivo, a apresentado
pela express˜ao 3.1.
min :
i
OEO
i
95
Restri¸oes:
traf[s][d] × CB
sd
r
C
sd
r
, s, d, r; s = d e r R
sd
(6.1)
traf[s][d] × P B
sd
r
P
sd
r
, s, d, r; s = d e r R
sd
(6.2)
EOE
i
j
X
ij
C
, i (6.3)
CB
sd
r
+
r
P B
sd
r
1, s, d, r, r
; s = d; r, r
R
sd
(6.4)
sd
r
δ
sd
ij,r
×
C
sd
r
+ P
sd
r
= X
ij
, i, j; E[i][j]=1 (6.5)
r
P
sd
r
= traf[s][d], s, d; s = d (6.6)
X
ij
, XN
ij
Z
+
, i, j, k; E[i][j]=1 (6.7)
C
sd
r
, P
sd
r
Z
+
, s, d, r; s = d e r R
sd
(6.8)
OEO
i
Z
+
, i (6.9)
CB
sd
r
, P B
sd
r
{0, 1} s, d, r; s = d e r R
sd
(6.10)
Descri¸ao do modelo matem´atico:
Semelhante `a restri¸ao (3.3) que relaciona as vari´aveis X
ij,w
e XB
ij,w
, a restri¸ao
(6.1) ´e usada para estabelecer a rela¸ao entre as vari´aveis C
sd
r
e CB
sd
r
. Al´em disso,
(6.1) assegura que C
sd
r
nunca exceder´a a demanda de tr´afego sd. Analogamente
tem-se a restri¸ao (6.2) para os caminho de prote¸ao.
A restri¸ao (6.3) ´e an´aloga `a (3.23), e expressa o n´umero de transceptores
necess´arios, conforme a quantidade de tr´afego usando o enlace ij e a capacidade
de cada comprimento de onda do canal C.
As vari´aveis bin´arias CB
sd
r
e P B
sd
r
indicam uso da rota r pelo tr´afego de tra-
balho da demanda sd e o uso da rota r
pelo tr´afego de prote¸ao da demanda sd,
respectivamente. Como todas as rotas s˜ao pr´e-computadas pode-se associar a cada
rota de trabalho r R
sd
um conjunto de rotas r
R
sd
de modo que todas as rotas
r
ao disjuntas `a rota dada r. A partir desse controle das rotas a serem usadas
pelas demandas de trabalho e prote¸ao, a restri¸ao (6.4) assegura que os caminhos
96
de trabalho e prote¸ao, usados para atender uma demanda sd, devem ser disjuntos
por n´o.
A Equa¸ao (6.5) define a restri¸ao de grooming de tr´afego, essa restri¸ao ´e an´aloga
`a restri¸ao (3.16). Por´em, na restri¸ao (6.5) a soma ´e realizada sobre as demandas
de trabalho e prote¸ao que passando em um enlace ij, de forma que essa soma deve
ser igual a X
ij
.
A restri¸ao (6.6) ´e an´aloga `a (3.15), por´em para o tr´afego de prote¸ao. Assim, a
restri¸ao (6.6) garante que todo tr´afego possui uma caminho de prote¸ao.
As express˜oes (6.7), (6.8) e (6.9) representam as restri¸oes de n˜ao-negatividade
e integralidade das vari´aveis X
ij
, XN
ij
, C
sd
r
, P
sd
r
e OEO
i
, respectivamente, e a
restri¸ao (6.10) assegura que as vari´aveis CB
sd
r
e P B
sd
r
ao bin´arias.
Para ambos os modelos apresentados a seguir, ´e utilizada a mesma nota¸ao
proposta para os modelos do tipo NA, que ´e utilizada devido a sua flexibilidade e
simplicidade para trabalhar com elementos isolados na rede. Por´em, como aqui s˜ao
tratadas a prote¸ao e restaura¸ao, tˆem-se como dados de entrada uma configura¸ao
da rede e a falha a ser tratada, representadas por:
Net
sd
ij,w
: que conem todas as informa¸oes da configura¸ao de trabalho da rede, com
roteamento e comprimento de onda para cada demanda sd, que ao foram
alteradas com a falha.
F : um conjunto que conem todas as demandas que devem ser re-roteadas devido
a alguma falha (por enlace, o ou comprimento de onda). Note que com F
definido, ´e poss´ıvel tratar qualquer tipo de falha, simples ou m´ultipla.
Projeto de Prote¸ao de Redes (PPR)
O objetivo deste modelo ´e minimizar os custos de instala¸ao. Assim pode-se con-
siderar 3.1, min :
i
OEO
i
, como fun¸ao objetivo.
Para gerar a nova configura¸ao da rede, ser´a usado como base o modelo NA,
adicionando apenas as restri¸oes de configura¸ao inicial da rede, Net
sd
ij,w
.
Restri¸oes: Do modelo NA ao utilizadas as restri¸oes (3.3), (3.4), (3.6), (3.7)
e (3.5), apresentadas a seguir, completando o modelo com a restri¸ao (6.16).
97
C × XB
ij,w
X
ij,w
, i, j, w; E[i][j]=1 e w W (6.11)
sd
C
sd
ij,w
= X
ij,w
, i, j, w; E[i][j]=1 e w W (6.12)
j
C
sd
ij,w
j
C
sd
ji,w
=
D
sd,w
se i = s
D
sd,w
se i = d
zero se i = s = d
s, d, i, w; s = d e w W (6.13)
j
w
XB
ij,w
= OEO
i
, i (6.14)
w
D
sd,w
= traf[s][d], s, d; s = d (6.15)
C
sd
ij,w
= Net
sd
ij,w
; s, d / F (6.16)
X
ij,w
Z
+
, i, j, w; E[i][j]=1 e w W (6.17)
C
sd
ij,w
Z
+
, s, d, i, j, w; s = d, E[i][j]=1 e w W (6.18)
D
sd,w
Z
+
, s, d, w; s = d e w W (6.19)
OEO
i
Z
+
, i (6.20)
XB
ij,w
{0, 1}, i, j, w; E[i][j]=1 e w W (6.21)
Descri¸ao do modelo matem´atico:
As 5 primeiras restri¸oes existentes no modelo P P R ao iguais `as do modelo
NA, apresentado e discutido no Cap´ıtulo 3.
A equa¸ao (6.16) transfere para o modelo as informa¸oes da configurao de
trabalho da rede, excluindo as demandas afetadas pela falha. Esta restri¸ao ainda
assegura que, em caso de falha, uma demanda que ao foi diretamente afetada n˜ao
seja interrompida para o processo de restaura¸ao. A esse processo dar-se-´a o nome
de reconfigura¸ao local. Por outro lado, se tal restri¸ao for ignorada, de forma
que o modelo ao receba o estado atual da rede como dado, o modelo retornar´a
uma reconfigura¸ao global da rede. Esta restri¸ao tamb´em ´e considerada como
contribui¸ao nessa proposta de modelo. Como tal restri¸ao insere uma configura¸ao
98
parcial da rede, tem-se uma redu¸ao nos custos computacionais consequente da pr´e-
atribui¸ao de algumas vari´aveis no modelo. Al´em do estudo da prote¸ao, tal restri¸ao
pode ser utilizada para investiga¸ao de tr´afego incremental na rede.
As express˜oes (6.17), (6.18), (6.19) e (6.20) representam as restri¸oes de ao-
negatividade e integralidade das vari´aveis X
ij,w
, C
sd
ij,w
, D
sd,w
e OEO
i
, respectiva-
mente. A restri¸ao (6.21) assegura que a vari´avel XB
ij,w
´e bin´aria.
Projeto de Restaura¸ao de Tafego (PRT)
Como em [ZHU 02], que trata do projeto de rede e ao da prote¸ao, neste modelo
os recursos dispon´ıveis nas redes ao uma restri¸ao do problema e ao o objetivo do
processo. Assim, dentro das condi¸oes da rede e uma falha ao prevista, busca-se
a maximiza¸ao do tr´afego recuperado. Como vari´avel adicional tem-se S
sd,w
, que
´e uma vari´avel de folga, representando a fra¸ao da demanda de tr´afego (traf[s][d])
sobre o comprimento de onda w que ao foi poss´ıvel re-rotear em virtude da falha
analisada.
Fun¸ao objetivo: um projeto de restaura¸ao deve minimizar a quantidade total
de tr´afego perdido, como representado em 6.22.
min :
sd,w
S
sd,w
(6.22)
Restri¸oes: Do modelo NA ao utilizadas as restri¸oes 3.3, 3.4, 3.6 e 3.7. Ainda,
a restri¸ao 3.5 ´e substitu´ıda por 6.27 e adicionada 6.28.
C × XB
ij,w
X
ij,w
, i, j, w; E[i][j]=1 e w W (6.23)
sd
C
sd
ij,w
= X
ij,w
, i, j, w; E[i][j]=1 e w W (6.24)
j
C
sd
ij,w
j
C
sd
ji,w
=
D
sd,w
se i = s
D
sd,w
se i = d
zero se i = s = d
s, d, i, w; s = d e w W (6.25)
99
j
w
XB
ij,w
= OEO
i
, i (6.26)
w
(D
sd,w
+ S
sd,w
) = traf[s][d], s, d; s = d (6.27)
XB
ij,w
=
1 quando
s,d/R
Net
sd
ij,w
= 0
0 caso contr´ario
, i, j; E[i][j]=1 e w W (6.28)
X
ij,w
Z
+
, i, j, w; E[i][j]=1 e w W (6.29)
C
sd
ij,w
Z
+
, s, d, i, j, w; s = d, E[i][j]=1 e w W (6.30)
D
sd,w
, S
sd,w
Z
+
, s, d, w; s = d e w W (6.31)
OEO
i
Z
+
, i (6.32)
XB
ij,w
{0, 1}, i, j, w; E[i][j]=1 e w W (6.33)
Descri¸ao do modelo matem´atico:
As 4 primeiras restri¸oes existentes no modelo P P R ao iguais `as do modelo
NA, apresentado e discutido no Cap´ıtulo 3.
Na restri¸ao (6.27) a soma das fra¸oes, de uma demanda, para todos os com-
primentos de onda, seja para o tr´afego recuperado (D
sd,w
) ou perdido (S
sd,w
) deve
ser igual a demanda exigida pela matriz (traf[s][d]). Como a fun¸ao objetivo tenta
minimizar o tr´afego perdido, note que a vari´avel S
sd,w
pode atingir o valor zero e
assim recuperar todo o tr´afego, sendo distribu´ıdo pelas fra¸oes de D
sd,w
.
A somat´oria existente na restri¸ao (6.28) assume um valor maior do que 0 se
existe algum tr´afego usando o comprimento de onda w no enlace ij, fixando a exis-
tˆencia de um transceptor nesse ponto da rede. No caso contr´ario, n˜ao ´e permitido a
instala¸ao de novos equipamento na rede. Isto ´e, a express˜ao 6.28 atribui os trans-
ceptores que podem ser usados na restaura¸ao da rede. Assim, o modelo permite
apenas o uso dos transceptores (e portanto dos comprimentos de onda) dos enlaces
ij alocados a uma demanda sd que n˜ao foi afetada.
As express˜oes (6.29), (6.30), (6.31) e (6.32) representam as restri¸oes de ao-
negatividade e integralidade das vari´aveis X
ij,w
, C
sd
ij,w
, D
sd,w
, S
sd,w
e OEO
i
. A
restri¸ao (6.33) garante que a vari´avel XB
ij,w
´e bin´aria.
Os dois modelos propostos, um para localizar um umero m´ınimo de transcep-
100
tores em um projeto de prote¸ao de rede (PPR), e outro para encontrar a melhor
configura¸ao da engenharia de tr´afego (PRT), minimizando a quantidade de de-
mandas ao atendidas, ao facilmente combinados formando um m´etodo iterativo,
que ser´a detalhado mais adiante. Com essas caracter´ısticas, esse etodo ´e capaz
de destacar as deficiˆencias no projeto de prote¸ao considerando diferentes falhas, e
aprimorar a prote¸ao demandando recursos nos pontos cr´ıticos da rede.
6.2.3 Estudo de Casos
Para an´alise dos modelos ´e necess´ario um cen´ario inicial (topologia f´ısica e con-
figura¸ao de roteamendo do tr´afego) e um conjunto de falhas a serem consideradas,
onde PPR e PRT possam ser aplicados. Assim, ´e poss´ıvel encontrar a solu¸ao ´otima
para o posicionamento dos recursos de prote¸ao e o plano de restaura¸ao da rede
para a melhor utiliza¸ao dos recursos. Na Figura 6.1 ´e mostrada a topologia de 8
os e a carga dos enlaces obtidas do cen´ario inicial, gerado pelo modelo NA, que
cont´em 47 transceptores. A matriz de tr´afego considerada neste estudo est´a apre-
sentada no Apˆendice A como a Tabela A.3. Os enlaces foram representados por
F
k
, com k = {1, 2, ..., 10}, e sua carga por Y
i,j
(definido pela express˜ao 6.34) a
ordenadas de forma decrescente. Por exemplo, o enlace com a maior carga, F 1, que
possui a carga Y
3,4
= 384 unidades de tr´afego, corresponde `a liga¸ao entre os os 3 e
4. Os estudos de casos s˜ao investigados com objetivo de mostrar a flexibilidade dos
modelos. No primeiro, o custo da rede ´e analisado para o caso de falha de um ´unico
enlace, evitando uma reconfigura¸ao global da rede. Enao, a axima sobrevivˆencia
de tr´afego ´e encontrada para o projeto tratando a falha de um enlace, e, finalmente,
´e mostrado como as formula¸oes podem melhorar a configura¸ao da rede provendo
sobrevivˆencia, com o m´ınimo de recursos adicionados.
Y
ij
=
w
[X
ij,w
+ X
ji,w
], i, j; i < j (6.34)
Reconfigura¸ao Global vs. Local
A Figura 6.2 mostra o aumento do n´umero de transceptores necess´arios para prote¸ao
total do tr´afego versus as poss´ıveis falhas de enlace, considerando as estrat´egias de re-
configura¸ao local e global. Para reconfigura¸ao global, o projeto de re-roteamento
101
3
5
6
7
4
2
1
0
F
3
(
360
)
F2 (
376
)
F
1
(
384
)
F
7
(
248
)
F
9
(
224
)
F
10
(
224
)
F
4
(
312
)
F
5
(
256
)
F
8
(
248
)
F
6
(
256
)
Figura 6.1: Topologia de rede, matriz de tr´afego e carga dos enlaces
pode impor uma mudan¸ca em todas as demandas na configura¸ao da rede. En-
quanto para reconfigura¸ao local apenas trata as demandas que foram diretamente
afetadas pela falha, ao permitindo mudan¸ca nas demais demandas. Em uma rede
real, a reconfigura¸ao global ´e impratic´avel pois a re-aloca¸ao de todas as demandas
provoca uma perda enorme de tr´afego. Por´em, essa estrat´egia ´e apresentada como
um recurso de compara¸ao.
0%
5%
10%
15%
20%
25%
30%
35%
40%
45%
50%
55%
60%
65%
F10F9F8
F7F6F5
F4F3F2
Aumento do Número de Transceptores
Reconfiguração Local
F1
Reconfiguração Global
Figura 6.2: Reconfigura¸ao Global e Local vs. Falha de enlaces
Como esperado, uma reconfigura¸ao local ´e sempre mais custosa. Contudo, a
diferen¸ca dos custos de prote¸ao ao excedeu 20%, mesmo para a falha do enlace
F1 (o enlace mais carregado no cen´ario inicial). Assim, conforme o servi¸co prestado
a cada demanda, ap´os uma falha o operador pode decidir quais demandas podem
sofrer uma reconfigura¸ao, beneficiando assim servi¸cos de alta disponibilidade. Cabe
destacar que tamb´em foi calculada a prote¸ao de todos os enlaces pela estrat´egia
102
1+1. Tal prote¸ao necessitou de 168% transceptores a mais do que o cen´ario inicial.
Reconfigura¸ao do Tafego para um Melhor uso dos Recursos de Prote¸ao
A Figura 6.3 mostra a porcentagem de tr´afego recuperado pelo modelo PRT para
cada falha de enlace, considerando o cen´ario inicial (modelo NA sem prote¸ao)
e a configura¸ao obtida por PPR em um esquema de reconfigura¸ao local, para
o caso de prote¸ao da falha no enlace F1. Comparando a quantidade de tr´afego
recuperado por PRT nos dois cen´arios, fica claro como um projeto de rede com uma
configura¸ao ´otima, mas sem prote¸ao, ´e extremamente vulner´avel. Por exemplo,
na Figura 6.3 pode-se notar que, para o projeto ´otimo sem prote¸ao, o modelo PRT
conseguiu recuperar no aximo 15% do tr´afego afetado para o caso de falha no
enlace F6, sendo que as demandas utilizando os enlaces F1, F7, F8, F9 e F10 seriam
totalmente perdidas.
0%
10%
20%
30%
40%
50%
60%
70%
80%
90%
100%
Tráfego Recuperado
PPR para falha em F1
Projeto ótimo sem proteção
F2
F1
F3 F4
F5 F6
F7 F8
F9
F10
Figura 6.3: Restaura¸ao do tr´afego em uma rede sem prote¸ao e com prote¸ao para
a Falha F1 vs. Falha de enlaces
Claro que toda a rede com capacidade livre ´e capaz de recuperar parte do tr´afego
perdido por uma falha. Por´em, na Figura 6.3 ´e mostrado como o modelo PRT
pode otimizar o uso dos recursos. Assim, tem-se que uma rede com capacidade
livre (17 transceptores adicionais dado pelo modelo PPR) para re-acomoda¸ao das
384 unidades de tr´afego no caso de falha em F1, pode beneficiar outros pontos
da rede. Al´em do esperado 100% de prote¸ao do tr´afego para falha de F1, como
mostrado na Figura 6.3, as demandas atingidas por outras falhas tamb´em podem
103
ser parcialmente ou at´e totalmente recuperadas. Embora a configura¸ao da rede
obtida com a reconfigura¸ao dada por PRT possa ser completamente diferente do
esquema obtido usando PPR para falha F1, ´e claro que ambos devem ser capazes
de recuperar totalmente as 384 unidades de tr´afego para o caso de falha em F1.
Al´em disso, ´e poss´ıvel notar que as configura¸oes espec´ıficas para cada falha dada
por PRT obtˆem um uso ´otimo para os transceptores adicionais, alcan¸cando uma
prote¸ao completa para F6 (embora o projeto de PPR tenha sido para prote¸ao de
F1) e aproximadamente 95% e 85% de restaura¸ao de tr´afego para falhas em F2 ou
F5, respectivamente.
Custos da Rede para um Projeto de Prote¸ao Progressiva
Na Figura 6.3, pode-se observar que as demandas sobre os enlaces F3 e F4 ao
tiveram melhorias significativas na prote¸ao, com os recursos adicionados para pro-
teger F1, comparando com o projeto sem prote¸ao. Ent˜ao, um processo de prote¸ao
iterativo pode ser realizado, reaplicando o modelo PPR para assegurar n´ıveis de so-
brevivˆencia para a rede, como minimiza¸ao dos recursos adicionados. Por exemplo,
para o enlace menos protegido na Figura 6.3 (i.e., F4) utilizou-se o modelo PPR para
encontrar o umero m´ınimo de transceptores necess´arios para proteger este enlace,
sendo que 13 transceptores devem ser adicionados para tal tarefa. Combinando os
resultados obtidos por PPR para a prote¸ao de F1 ou F4, 31 transceptores devem ser
adicionados ao cen´ario inicial, assegurando 100% de prote¸ao do tr´afego em ambos,
no caso de falha ´unica de enlace. Calculando os benef´ıcios desses recursos adicionais,
PRT pode melhorar significativamente as taxas de restaura¸ao para outras falhas
de enlaces, como apresentados na Figura 6.4, que em princ´ıpio foi projetada apenas
para F1 ou F3. Note que, al´em da prote¸ao total de F6, que j´a tinha sido anterior-
mente obtida, as configura¸oes geradas pelo PRT foram capazes de recuperar quase
completamente as demandas interrompidas pelas falhas F5, F7 ou F10. No pior caso
de falha, aproximadamente 25% do tr´afego foi deixado sem servi¸co, para uma falha
em F3. Assim, o pr´oximo passo do processo ´e concatenar os recursos exigidos para a
prote¸ao de F3 com os recursos adicionais da prote¸ao das falhas F1 e F4, obtendo
100% de prote¸ao para essas falhas.
Seguindo com as pr´oximas itera¸oes do m´etodo proposto, a Figura 6.5 apresenta
os resultados para os casos de falha em cada enlace, adicionando sequencialmente
104
0%
10%
20%
30%
40%
50%
60%
70%
80%
90%
100%
Tráfego Recuperado
PPR para falha em F1 ou F4
Projeto ótimo sem proteção
F2
F1
F3 F4
F5 F6
F7 F8
F9
F10
Figura 6.4: Restaura¸ao do tr´afego em uma rede sem prote¸ao e com prote¸ao para
as Falha F1 e F4 vs. Falha de enlaces
os recursos destinados `a prote¸ao de F3, F9, F2 e F5, representados pela Figura
6.5 (a), (b), (c) e (d), respectivamente. Note que na Figura 6.5 (d) ainda ao foi
obtido 100% de restaura¸ao para todas as falhas. Por´em, com o acr´escimo de mais
1 transceptor, esse n´ıvel de prote¸ao ´e atingido. Nota-se tamb´em que os recursos
inseridos e os benef´ıcios extras obtidos a cada itera¸ao ao tipicamente decrescentes.
Assim, como nas primeiras itera¸oes, para a prote¸ao de F1 e F4 foram adicionados
a maior parte dos recursos extras e tamem obteve-se a maior evolu¸ao na prote¸ao.
Por´em, para atingir a prote¸ao 1:1 para todas as falhas de enlaces foram preciso 7
itera¸oes, onde 6 itera¸oes est˜ao representadas nas Figuras 6.3-6.5 e a s´etima ´e usada
para “completar”a prote¸ao de F7 (que ainda se mostra com aproximadamente 95%
de prote¸ao, na Figura 6.5 (d)). Ao final do processo, o etodo proposto encontrou
um resultado total de 92 transceptores para admitir uma prote¸ao para a falha de
qualquer enlace da rede, enquanto que, para uma prote¸ao usando a estrat´egia 1+1,
foram necess´arios 126 transceptores. Contudo, vale destacar que o m´etodo proposto
ao suporta a duplica¸ao de todo o tr´afego, como feito para a prote¸ao 1+1.
O etodo iterativo proposto obteve uma economia de 34 transceptores em rela¸ao
`a prote¸ao 1+1 (34 transceptores corresponde a 37% a mais que o m´etodo iterativo
proposto nesta se¸ao). Por´em, na pr´atica, existem demandas com exigˆencia de
QoS que n˜ao admitem o tempo de restaura¸ao necess´ario em um esquema 1:1. As-
sim, etodos h´ıbridos, combinando 1+1 e 1:1 tˆem sido propostos para minimizar as
105
0%
10%
20%
30%
40%
50%
60%
70%
80%
90%
100%
Tráfego Recuperado
PPR para falha em F1, F3 ou F4
Projeto ótimo sem proteção
F2
F1
F3 F4
F5 F6
F7 F8
F9
F10
0%
10%
20%
30%
40%
50%
60%
70%
80%
90%
100%
Tráfego Recuperado
PPR para falha em F1, F3, F4 ou F9
Projeto ótimo sem proteção
F2
F1
F3 F4
F5 F6
F7 F8
F9
F10
0%
10%
20%
30%
40%
50%
60%
70%
80%
90%
100%
Tráfego Recuperado
PPR para falha em F1, F2, F3, F4 ou F9
Projeto ótimo sem proteção
F2
F1
F3 F4
F5 F6
F7 F8
F9
F10
0%
10%
20%
30%
40%
50%
60%
70%
80%
90%
100%
Tráfego Recuperado
PPR para falha em F1, F2, F3, F4, F5, F7 ou F9
Projeto ótimo sem proteção
F2
F1
F3 F4
F5 F6
F7 F8
F9
F10
(c)
(a) (b)
(d)
Figura 6.5: Restaura¸ao do tr´afego em uma rede sem prote¸ao e com prote¸ao
progressiva vs. Falha de enlaces
desvantagens de cada esquema [SHE 05, SIV 03]. Seguindo esta tendˆencia, chamada
de Quality of Protection - QoP, ´e poss´ıvel combinar o modelo 1+1 com o m´etodo
proposto, provendo diferentes n´ıveis de sobrevivˆencia para cada demanda. Este es-
quema h´ıbrido certamente ir´a produzir um cen´ario de rede de custo intermedi´ario e
prover QoS para as demandas que realmente necessitam desse servi¸co.
6.3 Interconex˜ao em Redes Transl´ucidas para Multi-
an´eis com DNI
Na se¸ao anterior foram propostos dois algoritmos para prote¸ao e restaura¸ao com
um estudo de caso. Apesar do estudo de caso apresentado considerar apenas redes
106
em malha, os modelos podem ser adaptados em um caso de rede multi-anel, bastando
para isso seguir as indica¸oes feitas no Cap´ıtulo 3. Como a prote¸ao interna de
um anel ´e um assunto bem discutido na literatura, esta se¸ao tem como foco as
estrat´egias para a prote¸ao da interconex˜ao de an´eis.
6.3.1 Trabalhos Relacionados e Contribui¸oes
Como mencionado, s˜ao encontrados na literatura dois tipos asicos de interconex˜ao
de anel, com um ou dois os de interse¸ao, chamados de SNI e DNI, respectiva-
mente. Por´em, a estrat´egia SNI, que tem apenas um ponto de conex˜ao, deve ser
evitada sempre que for exigida uma rede com um alto n´ıvel de confiabilidade. Um
esquema de prote¸ao DNI, por ter dois pontos de conex˜ao entre os an´eis, pode ser
implementado atraes das estrat´egias 1+1, que neste contexto ao conhecidas como
anel virtual (virtual ring - VR) e drop and continue (D&C) [VAS 04]. Mais recen-
temente, o trabalho [RAI 08] prop˜oe um algoritmo heur´ıstico para o problema de
agrupamento de tr´afego em uma rede multi-anel com prote¸ao D&C. Por´em, ape-
sar de investigar o crescimento do tr´afego na rede, este trabalho mant´em sempre a
mesma propor¸ao entre as demandas intra-anel e inter-anel. Al´em disso, ao ao
apresentados modelos exatos ou limites inferiores que avaliem os resultados obtidos
pela heur´ıstica. Tamb´em duplicando o sinal como VR, por´em apenas nos os de
interconex˜ao, o D&C o utiliza para fins de redundˆancia os recursos destinados `a
interconex˜ao dos an´eis. Para an´alise destas estrat´egias, dois modelos ILPs s˜ao pro-
postos, um para cada m´etodo de prote¸ao de interconex˜ao em uma rede multi-anel
com DNI (VR e D&C). Seguindo os moldes dos modelos de projeto de redes para
o problema de grooming de tr´afego, a fun¸ao objetivo de minimiza¸ao do custo da
rede, traduzido em n´umero de converoes opto-eletrˆonico-opto, ´e tratada em uma
rede SDH pelo n´umero ADMs (add-drop multiplexers). Al´em da proposi¸ao do mo-
delo ILP para a estrat´egia D&C, esse estudo ainda tr´as como contribui¸ao a inves-
tiga¸ao da topologia multi-anel DNI para redes transl´ucidas com caminhos ´opticos
internos aos an´eis. Adicionalmente, os resultados num´ericos tamb´em apresentam o
crescimento das demandas de tr´afego inter-anel e intra-anel.
107
6.3.2 Estrat´egias de Prote¸ao DNI
A Figura 6.6 exemplifica os dois esquemas de prote¸ao considerados neste trabalho,
VR e D&C. Para simplificar a ilustra¸ao foi usada uma rede formada por dois an´eis
bidirecionais. Embora as duas demandas de um par de n´os, na pr´atica, possam ser
roteadas por diferentes caminhos, para simplificar, na Figura 6.6, ao consideradas as
duas dire¸oes usando o mesmo caminho. Considere uma demanda de conex˜ao entre
os n´os 1 e 3 atrav´es do caminho 1-2
a
-2
b
-3, sendo este o caminho de trabalho. Cabe
ainda destacar que 2
a
e 2
b
ao partes de um mesmo o. A linha tracejada representa o
fluxo de tr´afego para o caso da prote¸ao VR, enquanto a linha pontilhada representa
o fluxo de tr´afego para o caso da prote¸ao D&C. O esquema de prote¸ao de VR gera
uma c´opia do sinal na origem (n´o 1) e envia para o destino (n´o 3) usando para isso
um caminho disjunto ao caminho de trabalho, 1-6-5
a
-5
b
-4-3, formando assim, um
anel virtual. O esquema D&C tamb´em duplica o sinal, por´em apenas entre os os
de interse¸ao. O sinal entra no n´o 2a, ´e enao copiado para o o 2
b
e enviado para
outro o de interconex˜ao 5a, o qual tamem envia o sinal para 2
b
(atrav´es do o 5
b
).
Assim, o n´o 2
b
pode selecionar o melhor sinal e transmitir para o n´o 3 no anel Rb.
R
R
X
X
X
Figura 6.6: Estrat´egias de Prote¸ao para DNI
Arquitetura dos N´os da Rede Multi-anel Considerada
Em uma rede multi-anel, os os podem ser classificados em dois tipos de acordo
com suas caracter´ısticas de interconex˜ao: os internos e os de interconex˜ao.Os n´os
internos s˜ao aqueles pertencentes a um ´unico anel, enquanto os os de interconex˜ao
est˜ao situados na interse¸ao de an´eis.
Um o interno do anel ´e composto por um demultiplexador WDM (DMUX),
108
um multiplexador WDM (MUX), um comutador ´optico e alguns ADMs. A fun¸ao
deste o ´e demultiplexar o sinal WDM para extrair os comprimentos de onda que
carregam tr´afego destinado ao o, enquanto os outros passam de forma transparente
pelo o. Al´em disso, o o pode retirar um comprimento de onda para agregar tr´afego
de baixa velocidade atrav´es do processamento eletrˆonico oferecido pelos ADMs, os
quais tamb´em em a fun¸ao de adicionar e retirar tr´afego para portas locais. Na
arquitetura de um n´o de interse¸ao, os comutadores ´opticos s˜ao usados para retirar
comprimentos de onda que carregam tr´afego entre os an´eis e podem deixar passar,
transparentemente, um tr´afego interno ao anel. Os ADMs ao respons´aveis pelo
agrupamento de tr´afego dentro do anel, enquanto os comutadores eletrˆonicos (DXC)
ao usados para comutar tr´afego de baixa velocidade dentro do n´o de interconex˜ao,
ou adicionar e retirar tr´afego para portas locais.
Note que as arquiteturas escolhidas para formar os an´eis permitem a imple-
menta¸ao de uma rede transl´ucida, por´em com algumas restri¸oes. A principal
restri¸ao da rede transl´ucida ´e a limita¸ao imposta aos caminhos ´opticos, que devem
estar contidos inteiramente dentro de um ´unico anel. Para exemplificar, considere
o anel R0 na Figura 3.2 contida no Cap´ıtulo 3. Como um caminho ´optico ´e uma
conex˜ao transparente com dois ou mais saltos, os caminhos ´opticos poss´ıveis ao 0-2
e 1-3. Note que tal restri¸ao ´e totalmente condizente com o estudo de uma rede
multi-anel, pois uma das caracter´ısticas do roteamento de uma rede multi-anel ´e
que a demanda intra-anel ao deve usar recursos de outro anel. Al´em disso, tal
caracter´ıstica facilita o gerenciamento da rede e reduz a complexidade durante o
projeto.
6.3.3 Formula¸oes ILP
Os modelos aqui propostos seguem as mesmas defini¸oes apresentadas na Se¸ao 4.2,
onde a primeira fase do projeto multicamada, com a escolha dos caminhos ´opticos
e o roteamento sobre a camada ´optica, ´e realizado por um dos modelos propostos a
seguir. Portanto a matriz de adjacˆencias usada nessa se¸ao segue a mesma defini¸ao
feita na Se¸ao 4.2: ´e a soma das matrizes de adjacˆencias da topologia f´ısica e dos
poss´ıveis caminhos ´opticos, E[i][j] = Ef[i][j] + Ec[i][j]. A segunda fase, com o rotea-
mento dos caminhos ´opticos sobre a camada f´ısica e a atribui¸ao dos comprimentos
de onda, pode ser realizada pelo modelo RWA-OF, apresentado na Se¸ao 4.2. Claro
109
que para o uso de tal modelo neste estudo, deve-se considerar o roteamento multi-
anel, restringindo os enlaces f´ısicos que poder˜ao ser utilizados em cada caminho
´optico. Esse modelo, no contexto da rede multi-anel aqui estudado ´e chamado de
DNI-RWA. A seguir ao destacadas apenas as vari´aveis adicionais inseridas em cada
modelo.
Multi-Anel com DNI e Prote¸ao D&C (DNI-DC)
A principal caracter´ıstica da estrat´egia D&C ´e a duplica¸ao do sinal na interse¸ao dos
an´eis, indicando que deve haver uma duplica¸ao das vari´aveis (trabalho e prote¸ao)
nos enlaces de interconex˜ao dos an´eis, por exemplo, 2a-5a na Figura 6.6. Assim, as
vari´aveis adicionadas s˜ao:
X
k
ij
com k K = {0, 1, 2}, onde X
0
ij
representa a quantidade de tr´afego no enlace
ij interno a um anel; X
1
ij
e X
2
ij
representam a quantidade de tr´afego no enlace
ij, de trabalho e backup respectivamente, usados na interconex˜ao de an´eis.
XN
k
ij
´e a quantidade de comprimentos de onda no enlace ij para k K = {0, 1, 2}.
Fun¸ao Objetivo: Nesse estudo cada ADM representa uma convers˜ao OEO
em um contexto de redes SDH/SONET. Assuma ADM
i
com o n´umero de ADMs no
o i. Ent˜ao, representada pela express˜ao 6.35, pode-se descrever o objetivo como a
minimiza¸ao do n´umero de ADMs para o pior caso, isto ´e, para o o que necessitar
do maior n´umero. Isso ´e feito com o objetivo de reduzir os custos da rede, enquanto
mant´em a mesma com um tr´afego balanceado.
min max{ADM
i
} (6.35)
Restri¸oes: Do modelo AC ´e utilizada a restri¸ao 3.15. A restri¸ao 3.14 ser´a
substitu´ıda por 6.36 e 6.37, e 3.16 substitu´ıda por 6.38.
XN
k
ij
X
k
ij
C
, i, j, k; E[i][j] e k {1, 2, 3} (6.36)
j,k
XN
k
ij
= ADM
i
, i (6.37)
110
sd
r
δ
sd
ij,r
× C
sd
r
= X
k
ij,w
, i, j, k, r; E[i][j], k {1, 2, 3} e r R
sd
(6.38)
X
k
ij
, XN
k
ij
Z
+
, i, j, k; E[i][j]=1 e k {1, 2, 3} (6.39)
C
sd
r
Z
+
, s, d, r; s = d e r R
sd
(6.40)
ADM
i
Z
+
, i (6.41)
Descri¸ao do modelo matem´atico:
A restri¸ao (6.36), an´aloga `a restri¸ao (3.23), contabiliza a quantidade de com-
primentos de onda necess´arios em um enlace, conforme a quantidade de tr´afego nele
e a capacidade de transporte de cada comprimento de onda, sendo isso realizado
para cada tipo de enlace, ou seja, k {1, 2, 3}
A restri¸ao (6.37) contabiliza o n´umero de ADMs no o i que fazem conex˜ao
com os os adjacentes, seja esta feita por um enlace interno ao anel ou um enlace
de interconex˜ao de an´eis.
A equa¸ao (6.38) representa a restri¸ao de grooming de tr´afego, mostrando que a
soma das demandas passando pelo enlace ij deve ser igual a X
k
ij
. Note que do lado
esquerdo da igualdade ao existe o ´ındice k, enao para implementa¸ao ´e necess´ario o
cuidado de aplicar a somat´oria duas vezes sempre que o enlace ij for de interconex˜ao
de an´eis, para k = 2, 3. Isso garante a duplica¸ao do tr´afego nos os de interconex˜ao,
como exige a prote¸ao D&C.
As express˜oes (6.39), (6.41) e (6.41) representam as restri¸oes de ao-negatividade
e integralidade das vari´aveis do modelo.
Para o modelo 1+1 ser adaptado `a prote¸ao da interconex˜ao dos an´eis, basta que
as vari´aveis de prote¸ao P
sd
r
sejam consideradas apenas para as demandas inter-anel,
ou seja, o ao consideradas duas rotas para as demandas de prote¸ao, as rotas de
sentido hor´ario e anti-hor´ario. A prote¸ao da interconex˜ao de anel tratada nessa
se¸ao ´e chamada de DNI-VR.
111
6.3.4 Estudo de Casos
Para avaliar diferentes condi¸oes de tr´afego em um cen´ario com um crescimento de
demandas, utilizou-se um conjunto de matrizes de tr´afego e a topologia f´ısica da
rede apresentada na Figura 3.2. As demandas de uma matriz de tr´afego podem
ser intra-anel e inter-anel. Cada uma delas ´e obtida por sorteio de um n´umero dos
conjuntos {1, 2, ..., L
intra
}, ou {1, 2, ..., L
inter
}, para demandas intra-anel e inter-anel,
respectivamente. Com o objetivo de obter valor de demandas mais realistas, cada
elemento sorteado para a matriz de tr´afego ´e ainda multiplicado por 16, represen-
tando assim um m´ultiplo de STM-16. Nas Figuras 6.7-6.9 a abscissa ´e notada por
L
inter
/L
intra
, indicando os limites superiores (L
inter
e L
intra
) para os conjuntos. Por
exemplo, para abscissa 6/1 na Figura 6.7, cada demanda intra-anel assume o valor
fixo de 16 unidades de tr´afego, enquanto as demandas inter-anel podem assumir,
de forma aleat´oria, 16, 32, 48, 64, 80 ou 96 unidades de tr´afego, todos com igual
probabilidade de ocorrˆencia. Al´em dos m´etodos de prote¸ao, DNI-DC e DNI-VR,
´e implementado tamb´em como parˆametro de compara¸ao, um modelo exato para
o problema de grooming de tr´afego para uma rede multi-anel DNI transl´ucida sem
prote¸ao (DNI-SP). Tal modelo ´e alcan¸cado seguindo as orienta¸oes de roteamento
multi-anel do Cap´ıtulo 3 e de redes transl´ucidas do Cap´ıtulo 4. Cabe destacar que
as Figuras 6.7 e 6.8 apresentam os resultados do n´umero de ADMs obtidos pelos
modelos DNI-DC e DNI-VR, enquanto a Figura 6.9 mostra o n´umero de compri-
mentos de onda encontrados ap´os a acomoda¸ao dos caminhos ´opticos na topologia
f´ısica.
Resultados para o n´umero de ADMs sob DNI-DC e DNI-VR
A Figura 6.7 mostra como a varia¸ao de carga inter-anel influencia no n´umero de
ADMs para DNI-DC, DNI-VR e DNI-SP em cen´arios de redes opaca e transl´ucida.
Neste exemplo, as demandas intra-anel foram fixadas em 16 unidades de tr´afego,
analisando os resultados de 10 matrizes de tr´afego com demandas inter-anel cres-
centes. Enquanto a Figura 6.7(a) tem como ordenada o resultado obtido pela fun¸ao
objetivo (min-max), a Figura 6.7(b) mostra o n´umero total de ADMs encontrados,
calculando a soma de todos os ADMs em cada o i da configura¸ao obtida com a
fun¸ao objetivo 6.35.
112
2/1 4/1 6/1 8/1 10/1 12/1 14/1 16/1 18/1 20/1
0
10
20
30
40
50
60
70
DNI-DC(opaco)
DNI-VR(opaco)
DNI-SP(opaco)
L
inter
/L
intra
Min: Max {ADM
i
}
DNI-DC(translúcido)
DNI-VR(translúcido)
DNI-SP(translúcido)
(a)
(b)
2/1 4/1 6/1 8/1 10/1 12/1 14/1 16/1 18/1 20/1
0
250
500
750
1000
1250
1500
1750
DNI-DC (opaco)
DNI-VR (opaco)
DNI-SP (opaco)
L
inter
/L
intra
Σ
A
D
M
i
DNI-DC (translúcido)
DNI-VR (translúcido)
DNI-SP (translúcido)
Figura 6.7: (a) min-max{ADM
i
} and (b)
ADM
i
vs. 10 diferentes cargas de
tr´afego inter-anel, para os modelos DNI-DC, DNI-VR e DNI-SP em cen´arios de
rede opaco e transl´ucido
Como uma demanda inter-anel geralmente precisa de um n´umero maior de saltos
para alcan¸car o destino, comparado com demandas intra-anel, ´e natural que o custo
da rede cres¸ca mais rapidamente no tipo de evolu¸ao do tr´afego mostrado na Figura
6.7. O modelo DNI-DC apresentou, na Figura 6.7(a), aproximadamente o mesmo
113
valor para os modelos opaco e transl´ucido, enquanto na Figura 6.7(b) o modelo
opaco apresentou um resultado ligeiramente maior. Assim, nesse caso, como os dois
modelos apresentam o mesmo min-max o modelo transl´ucido ´e prefer´ıvel por possuir
um n´umero total de ADMs menor. Isto se deve ao fato da estrat´egia D&C duplicar
a quantidade de tr´afego na interse¸ao dos an´eis. Note que, para rede opaca, o DNI-
VR chega a requerer mais que o dobro do n´umero de ADMs que o DNI-DC alcan¸ca
no n´o mais carregado, enquanto o n´umero de ADMs na Figura 6.7 (b) mostra uma
diferen¸ca aproximadamente 50% entre os dois m´etodos.
A estrat´egia D&C tamb´em ao foi capaz de se beneficiar dos caminhos ´opticos
para esse tipo de evolu¸ao de tr´afego, ao contr´ario da protao VR, como mostrado
na Figura 6.7. Como um caminho ´optico est´a confinado aos an´eis, este ´e incapaz
de promover a redu¸ao de ADMs nos n´os de interse¸ao, onde D&C duplica o sinal.
Por´em, como foi definido, um cen´ario transl´ucido nunca ser´a mais custoso do que
um cen´ario opaco, pois os caminhos ´opticos ao interpretados pelos modelos como
uma possibilidade de redu¸ao do consumo de recursos e, na pior das hip´oteses, n˜ao
ao usados, tornando a rede opaca.
Na Figura 6.8 ´e apresentada uma an´alise da varia¸ao de carga intra-anel. Esta
Figura ´e apresentada nos mesmos moldes da 6.7. Observando os resultados obtidos
para as redes opacas, nota-se uma tendˆencia de crescimento linear no n´umero de
ADMs em ambas as Figuras (6.7 e 6.8). Por´em, destaca-se nessas redes a diferen¸ca
da taxa de crescimento que, como j´a mencionado, ´e bem maior para o crescimento
de tr´afego inter-anel. Com o recurso dos caminhos ´opticos fornecido pelo cen´ario de
rede transl´ucida, ambas as estrat´egias de prote¸ao foram beneficiadas em termos de
custo de implementa¸ao da rede. Por´em, um importante resultado foi o fato de os
custos obtidos pelo modelo DNI-VR se aproximarem dos obtidos pelo modelo DNI-
DC com a introdu¸ao dos caminhos ´opticos. Isto possibilita uma maior flexibilidade
durante a escolha do esquema de prote¸ao na fase de projeto da rede. Diferente de
uma arquitetura opaca, em que a escolha pela prote¸ao D&C ´e ´obvia, como mostram
as Figuras 6.7 e 6.8. Enquanto na Figura 6.8 DNI-DC e DNI-VR apresentaram um
custo similar para redes transl´ucidas, na Figura 6.7 h´a uma diferen¸ca consider´avel,
principalmente para L
inter
6. Nota-se tamb´em que a rede transl´ucida ode su-
portar o crescimento at´e L
intra
8, enquanto uma pequena altera¸ao em L
inter
desencadeia uma significante mudan¸ca no custo total da rede.
114
1/2 1/4 1/6 1/8 1/10 1/12 1/14 1/16 1/18 1/20
4
8
12
16
DNI-DC (opaco)
DNI-VR (opaco)
DNI-SP (opaco)
L
inter
/L
intra
Min: Max {ADM
i
}
DNI-DC (translúcido)
DNI-VR (translúcido)
DNI-SP (translúcido)
(a)
(b)
1/2 1/4 1/6 1/8 1/10 1/12 1/14 1/16 1/18 1/20
75
150
225
300
375
450
525
L
inter
/L
intra
Σ
A
D
M
i
DNI-DC (opaco)
DNI-VR (opaco)
DNI-SP (opaco)
DNI-DC (translúcido)
DNI-VR (translúcido)
DNI-SP (translúcido)
Figura 6.8: (a) min-max{ADM
i
} and (b)
ADM
i
vs. 10 diferentes cargas de
tr´afego intra-anel, para os modelos DNI-DC e DNI-VR em cen´arios de rede opaco e
transl´ucido
Resultados para DNI-RWA para o DNI-DC, DNI-VR, DNI-SP
Com a segunda parte do projeto de rede, a Figura 6.9 apresenta o min-max do
n´umero de comprimentos de onda obtido por DNI-RWA para os projetos de topolo-
115
2/1 4/1 6/1 8/1 10/1 12/1 14/1 16/1 18/1 20/1
10
20
30
40
50
60
70
80
L /L
Min:Max{ W }
(a)
(b)
1/2 1/4 1/6 1/8 1/10 1/12 1/14 1/16 1/18 1/20
4
8
12
16
20
24
Min:Max{ W }
L /L
Figura 6.9: N´umero de comprimento de ondas vs. 10 cargas de tr´afego crescentes,
inter-anel(a) intra-anel(b), sobre os resultados de DNI-DC e DNI-VR, para as redes
transl´ucidas
gia virtual encontrados por DNI-DC, DNI-VR e DNI-SP. A Figura 6.9 apresenta o
crescimento do tr´afego inter-anel (a) e intra-anel (b). Sendo que o crescimento do
tr´afego inter-anel exigiu aproximadamente o dobro de comprimentos de onda, no
116
enlace mais ocupado para o mesmo crescimento de tr´afego intra-anel. Por exem-
plo, D&C alcan¸cou 12 comprimentos de onda para L
inter
/L
intra
= 1/10 na Figura
6.9(a), enquanto para L
inter
/L
intra
= 10/1 alcan¸cou 37 comprimentos de onda na
Figura 6.9(b). Como o resultado da aloca¸ao de comprimentos de onda depende da
configura¸ao da rede, otimizada para o n´umero ADMs, podem-se observar alguns
casos onde o n´umero de comprimento de onda de uma rede sem prote¸ao foi maior
do que uma rede com prote¸ao. Por exemplo, DNI-RWA sobre DNI-SP obteve,
para L
intra
14, um n´umero maior de comprimentos de onda do que DNI-RWA
sobre DNI-DC nas redes transl´ucidas, mostrado na Figura 6.9 (b). Isso indica um
congestionamento, em algum enlace, na configura¸ao obtida pelo modelo DNI-SP.
Como aspecto pr´atico, a an´alise do n´umero de comprimentos de onda, tamb´em ´e
um importante parˆametro para a tomada de decis˜ao sobre as estrat´egias de prote¸ao
e gerenciamento que ao adotadas na rede. O n´umero de comprimentos de onda,
al´em de influenciar no dimensionamento de equipamentos como os OXCs, implicam
em aspectos de camada f´ısica, com por exemplo, na interferˆencia que os canais de
comprimentos de onda causam entre si.
6.4 Sum´ario
Nesse cap´ıtulo foram investigados dois aspectos diferentes para a prote¸ao das redes
´opticas, um para prote¸ao e restaura¸ao de redes em malha e outro para a prote¸ao
da interconex˜ao de an´eis. No primeiro estudo ao propostos dois modelos ILPs, um
para minimizar o n´umero de transceptores para o projeto de prote¸ao de elementos
espec´ıficos da rede e outro para encontrar a melhor configura¸ao que minimize a
perda de tr´afego frente a uma falha ao prevista. Assim, tem-se que o uso interativo
dos modelos culminou em um m´etodo para prote¸ao progressiva das demandas, que
pode ser classificado como 1:1. Para compara¸ao dos resultados obtidos pelo etodo
proposto ´e apresentado um modelo ILP para a estrat´egia de prote¸ao 1+1. Como
esperado, o m´etodo proposto possui um custo de implementa¸ao inferior `a prote¸ao
1+1, por´em, em caso de falha, as demandas necessitam de um tempo superior para
a restaura¸ao. Assim, uma solu¸ao que apresente uma boa rela¸ao de compromisso
entre custo e tempo de restaura¸ao sugere um modelo h´ıbrido provendo diferentes
classes de prote¸ao.
117
O segundo estudo desenvolvido nesse cap´ıtulo foi realizado sob um cen´ario de
redes WDM transl´ucidas com topologia multi-anel. Focando na prote¸ao da inter-
conex˜ao dos an´eis, admitiu-se ainda a existˆencia de caminhos ´opticos internos aos
an´eis. Para o estudo foram usadas duas estrat´egias de prote¸ao, conhecidas como
D&C e VR (1+1), sendo proposto um modelo ILP para cada uma. A an´alise rea-
lizada conta ainda com duas formas de evolu¸ao do tr´afego, inter-anel e intra-anel.
Para o crescimento de tr´afego inter-anel, a estrat´egia de prote¸ao D&C que duplica
o tr´afego na interconex˜ao dos an´eis, apresentou um custo total superior `a estrat´egia
VR, mesmo com o benef´ıcio dos caminhos ´opticos transparentes. Contudo, para uma
evolu¸ao de demandas intra-anel, um cen´ario de rede transl´ucida proporcionou uma
equipara¸ao, tanto em termos de custos totais como em caso do n´o mais carregado
(min-max). Adicionalmente, com o uso do modelo para aloca¸ao de comprimentos de
onda proposto no Cap´ıtulo 4, como esperado, constatou-se que uma rede transl´ucida
necessita de um n´umero maior de comprimentos de onda para a implementa¸ao dos
caminhos ´opticos. Assim, atrav´es desse estudo ´e poss´ıvel definir, baseando-se em
um cen´ario de rede e na expectativa de evolu¸ao do tr´afego, a estrat´egia de prote¸ao
de interconex˜ao dos an´eis. Apesar desse estudo investigar as estrat´egias de inter-
conex˜ao das redes em anel, a investiga¸ao ´e conduzida de maneira `a analisar a rede
observando cada o. Por´em, se o estudo tiver como foco somente a interconex˜ao,
a avalia¸ao da rede pode ser realizada analisando apenas a interliga¸ao dos an´eis,
somando as demandas e tratando o anel como um ´unico o, como representado no
grafo auxiliar apresentado na Figura 3.2.
Cap´ıtulo 7
Conclus˜oes e Trabalhos Futuros
Neste trabalho s˜ao abordados diversos aspectos relacionados a um projeto de redes
´opticas WDM. Nos dois cap´ıtulos iniciais deste texto ao apresentados, primeira-
mente, o contexto em que o estudo est´a situado e, em seguida, os aspectos tec-
nol´ogicos que permeiam o estudo, bem como uma breve revis˜ao bibliogr´afica asso-
ciada ao tema estudado. O Cap´ıtulo 3 apresenta dois modelos ILPs, chamados de
NA e AC, para solu¸ao do problema de grooming de tr´afego, roteamento e aloca¸ao
de comprimento de onda. O modelo NA usa uma estrat´egia que associa os os
aos enlaces e o modelo AC que associa os enlaces aos caminhos. Um conjunto de
caracter´ısticas espec´ıficas das redes ´opticas tamb´em foi apresentado na forma de
restri¸oes particulares para cada modelo. Adicionalmente, uma an´alise compara-
tiva dos modelos tamem foi apresentada, incluindo ainda uma caracteriza¸ao dos
modelos, identificando qual destes seria mais adequado a determinado problema de
redes.
No Cap´ıtulo 4 foi proposto um modelo h´ıbrido (heur´ıstica + PLI) para redes
transl´ucidas. Na primeira fase desse modelo a heur´ıstica pr´e-seleciona e roteia um
conjunto de caminhos ´opticos poss´ıveis. Em seguida, um modelo ILP ´e proposto
para selecionar os caminhos ´opticos que ao efetivamente usados e rotear as de-
mandas de tr´afego sobre os caminhos ´opticos. A partir de tal modelo ´e realizado
um estudo quantitativo mostrando os benef´ıcios dos caminhos ´opticos no custo da
rede. A an´alise da redu¸ao dos custos, em n´umero de transceptores e processamento
eletrˆonico nos os, mostrou que existe um limite para a quantidade de caminhos
´opticos instalados. Tal limite ´e dado por aproximadamente 75% do n´umero de
caminhos ´opticos necess´arios para obter uma topologia l´ogica representada por um
grafo completo. Assim, ap´os quantidade limite, cada caminho ´optico apenas repre-
118
119
senta um custo operacional extra, sem oferecer benef´ıcios para o custo do projeto da
rede. Ap´os a proposi¸ao de um modelo h´ıbrido, um algoritmo heur´ıstico ´e proposto
no Cap´ıtulo 5, para redes transl´ucidas, com o intuito de otimizar redes maiores. Na
heur´ıstica ao utilizados basicamente quatro procedimentos: a pr´e-sele¸ao dos cami-
nhos ´opticos permitidos, que ´e realizado pelo mesmo algoritmo no modelo h´ıbrido;
um procedimento para tentar eliminar comprimentos de onda subutilizados; uma
busca local; e um procedimento para gerar perturba¸oes aleat´orias, como tentativa
de escapar de poss´ıveis m´ınimos locais. No Cap´ıtulo 5 tamb´em ´e apresentada uma
an´alise de desempenho da heur´ıstica, incluindo resultados de cada procedimento,
computados independentemente, e compara¸oes com os resultados encontrados pelo
modelo ILP anteriormente proposto.
No Cap´ıtulo 6 ao apresentados alguns aspectos de prote¸ao e restaura¸ao de
redes ´opticas. Primeiramente, dois modelos ILPs complementares ao propostos
para prote¸ao e restaura¸ao de redes ´opticas. De posse destes modelos foi poss´ıvel
formular um processo iterativo para encontrar pontos cr´ıticos na rede e gerar projetos
de prote¸ao otimizada para tal ponto. Adicionalmente, os resultados obtidos por
esse m´etodo iterativo tamb´em ao comparados com os resultados de um modelo ILP
para a prote¸ao 1+1. Assim ´e mostrado que, se a rede admite um tempo maior de
prote¸ao, o modelo proposto, com uma prote¸ao iterativa, pode reduzir considera-
velmente os custos de sobrevivˆencia da rede quando comparado com a prote¸ao 1+1.
Al´em disso, tem-se que esse etodo proposto ainda possui a capacidade de prover
prote¸ao diferenciada para as demandas. Podendo atrav´es do modelo PPR prover
uma prote¸ao 1+1 e atrav´es o modelo PRT uma prote¸ao 1:1.
Outro aspecto investigado no Cap´ıtulo 6 foi a prote¸ao da interconex˜ao de an´eis
DNI. Para isso foi proposto um modelo ILP para a estrat´egia de prote¸ao drop
and continue. Tamb´em aqui os resultados foram comparados com o modelo ILP
para prote¸ao 1+1 que, no contexto de topologia multi-anel, ´e conhecido como
anel-virtual. Para este estudo foram apresentados resultados para redes opacas e
transl´ucidas, analisando o crescimento de tr´afego das demandas intra-anel e inter-
anel. Um dos resultados importantes encontrados nesse estudo foi o fato dos cami-
nhos ´opticos permitirem que as estrat´egias de prote¸ao D&C e VR obtenham resulta-
dos pr´oximos para um crescimento de tr´afego intra-anel. Tal resultado permite uma
maior flexibilidade na escolha da estrat´egia de prote¸ao das demandas inter-an´eis,
em um projeto de redes ´opticas com o cen´ario indicado.
120
Trabalhos Futuros
Para todos os cap´ıtulos onde ao propostos modelos, Cap´ıtulos 3, 4, 5 e 6, ainda
´e poss´ıvel inserir restri¸oes de forma a contemplar diversos aspectos da rede. Por-
tanto, cabe destacar as seguintes possibilidades de estudos para trabalhos futuros:
um aumento do n´umero de amostras das matrizes de tr´afego estudadas, de forma
a trazer resultados estat´ısticos, principalmente nos Cap´ıtulo 3, 4 e 5, como foi feito
com a evolu¸ao das demandas na Se¸ao 6.3. Um aprimoramento dos modelos ILPs e
heur´ısticas propostas, a fim de que sejam capazes de contemplar aspectos de camada
f´ısica [SZO 05, BOG 07]. Os efeitos de camada f´ısica podem ser divididos em dois
grupos: os com efeitos lineares, por exemplo, PMD (polarization mode dispersion),
ASE (amplified spontaneous emission), etc; e efeitos n˜ao-lineares, por exemplo, XT
(crosstalk), XPM (cross phase modulation), etc. Por´em, devido `a dificuldade de se
trabalhar com efeitos ao-lineares, ´e comum encontrar m´etodos tratando de aproxi-
ma¸oes lineares de tais fenˆomenos. Assim, em uma rede transl´ucida, pode-se inserir,
na fase de acomoda¸ao dos caminhos ´opticos, algumas das restri¸oes anteriormente
mencionadas, minimizando a penalidade inserida no caminho ´optico. Ainda dentro
do projeto de instala¸ao de uma rede ´optica pode-se considerar custos diferenciados
para cada elemento da rede, como por exemplo, o custo do transceptor ou do com-
primento de onda podem ser dependentes do n´o ou do enlace a ser alocado. Outro
aspecto interessante a ser desenvolvido nos modelos ILPs e heur´ısticas, incluindo
os modelos de prote¸ao, ´e a inser¸ao de parˆametros para descrever os custos de
opera¸ao e manuten¸ao da rede (Operational Expenditure - OPEX), pois os elemen-
tos considerados nos modelos ao usados para delinear apenas os custos de instala¸ao
da rede (Capital Expenditure - CAPEX). Relacionado aos custos OPEX e CAPEX
sugere-se ainda uma compara¸ao em redes com roteamento bifurcado ou ao, pois
os resultados dessa compara¸ao ao de grande interesse para o gerenciamento da
rede. Finalmente, exclusivamente para proposta de trabalhos futuros dos estudos
sobre prote¸ao e restaura¸ao realizados no Cap´ıtulo 6, existe a possibilidade de uma
diferencia¸ao das demandas para prover n´ıveis de prote¸ao diferentes na rede.
Apˆendice A
Matrizes de Tafego
Tabela A.1: Matriz de tr´afego usada na rede de 6 n´os
os
0 1 2 3 4 5
0 0 48 48 32 16 16
1
32 0 16 48 32 48
2
16 16 0 16 48 64
3
16 16 16 0 32 16
4
64 16 16 32 0 16
5
16 16 16 48 16 0
Tabela A.2: Matriz de tr´afego usada na rede de 8 n´os
os
0 1 2 3 4 5 6 7
0 0 16 32 32 48 32 48 64
1
32 0 16 48 32 48 64 32
2
16 48 0 32 64 48 48 16
3
32 16 48 0 32 48 48 16
4
64 32 16 32 0 64 64 48
5
48 64 48 32 16 0 48 64
6
16 48 16 48 32 64 0 32
7
32 48 32 64 32 64 64 0
121
122
Tabela A.3: Matriz de tr´afego usada na rede de 8 n´os usada no Cap´ıtulo 7
os
0 1 2 3 4 5 6 7
0 48 16 48 48 32 16 16
48
0 32 16 16 48 48 16
16
16 0 16 32 32 16 48
32
16 16 0 16 48 16 48
16
16 48 32 0 16 16 16
32
64 16 32 16 0 16 48
16
16 48 32 16 16 0 32
32
32 16 16 32 32 16 0
Tabela A.4: Matriz de tr´afego usada na rede de 13 n´os
os
1 2 3 4 5 6 7 8 9 10 11 12 13
1 0 16 16 32 16 32 16 32 16 48 16 48 16
2
16 0 64 32 32 32 16 32 48 48 32 16 16
3
16 16 0 48 16 48 32 48 64 48 32 16 32
4
32 48 48 0 32 16 32 32 16 32 16 16 16
5
32 48 16 32 0 16 16 48 32 16 48 16 16
6
16 48 16 16 16 0 16 32 64 16 32 32 16
7
16 16 32 32 32 32 0 64 16 16 16 32 32
8
16 32 16 48 16 16 64 0 32 16 16 48 32
9
16 32 16 32 64 48 32 16 0 16 16 48 32
10
48 32 32 16 48 16 48 16 32 0 16 64 64
11
32 48 32 32 16 16 16 32 48 32 0 16 48
12
16 32 48 32 64 32 16 48 16 32 16 0 16
13
32 64 16 16 16 16 16 48 16 48 32 16 0
123
Tabela A.5: Matriz de tr´afego usada na rede NSF-NET (14 n´os)
os
1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 0 48 16 48 48 32 16 16 16 16 48 32 32 48
2
48 0 32 16 16 48 48 16 16 16 32 32 16 16
3
16 16 0 16 32 32 16 48 16 48 16 32 16 32
4
32 16 16 0 16 48 16 48 16 16 48 16 32 16
5
16 16 48 32 0 16 16 16 32 48 32 32 32 48
6
32 64 16 32 16 0 16 48 32 16 32 32 16 48
7
16 16 48 32 16 16 0 32 48 48 48 48 16 16
8
32 32 16 16 32 32 16 0 48 16 32 64 16 16
9
16 48 48 32 32 48 32 16 0 32 32 32 16 32
10
16 16 16 16 32 16 64 32 16 0 32 16 32 32
11
32 16 16 48 32 32 32 32 16 16 0 32 32 32
12
16 16 64 16 32 16 16 64 32 32 16 0 32 16
13
32 16 32 16 32 16 32 16 16 16 48 48 0 64
14
48 16 32 32 32 32 32 32 32 16 16 64 16 0
Referˆencias Bibliogr´aficas
[AGR 01] AGRAWAL, G. P. Nonlinear fiber optics. Academic Press, New York, 2001.
[ALM 06] ALMEIDA, R. T. R. et al. Design of virtual topologies for large optical networks
through an efficient MILP formulation. Optical Switching and Networking,
Elsevier, [S.l.], v.3, p.2–10, 2006.
[AWW 06] AWWAD, O.; AL-FUQAHA, A. I.; GUIZANI, M. Genetic approach for traffic
grooming, routing, and wavelength assignment in WDM optical networks with sparse
grooming resources. In: ICC ’06, IEEE INTERNATIONAL CONFERENCE ON
COMMUNICATIONS, 2006. [s.n.], 2006. v.6, p.2447–2452.
[BAN 90] BANNISTER, J.; FRATTA, L.; BERLA, M. Topological design of the
wavelength-division optical network. In: IEEE INFOCOM, p.1005–1013. 1990.
[BAN 01] BANERJEE, A. et al. Generalized multiprotocol label switching: An overview of
routing and management enhancements. IEEE Communication Magazine,
[S.l.], p.144–151, 2001.
[BIN 00] BINETTI, S. et al. Mesh and multi-ring optical networks for long-haul applications.
Journal of Lightwave Technology, [S.l.], v.18, n.12, p.1677–1684, 2000.
[BLA 01] BLACK, U. MPLS and Label Switching Networks. Prentice Hall, 2001.
[BLU ] BLUM, C.; MANFRIN, M. http://www.metaheuristics.net. acesso em:
27/05/2006.
[BOG 07] BOGLIOLO, G.; CURRI, V.; MELLIA, M. Considering transmission impairments in
rwa problem: Greedy and metaheuristic solutions. In: OFC 2007, 2007. [s.n.], 2007.
[BOU 06] BOUFFARD, A.; HOULE, A.; JAUMARD, B. Grwa provisionning and segment
protection in wdm optical networks. In: CCECE ’06, CANADIAN CONFERENCE
ON ELECTRICAL AND COMPUTER ENGINEERING, 2006. [s.n.], 2006.
p.999–1002.
124
125
[BOW 05] BOWORNTUMMARAT, C. et al. Using mesh and multi-ring methods in the design
of survivable wavelength-routed all-optical networks. European Transactions on
Telecommunications, [S.l.], v.16, p.157–172, 2005.
[BRU 02] BRUNATO, M.; BATTITI, R. A multistart randomized greedy algorithm for traffic
grooming on mesh logical topologies. In: CONFERENCE ON OPTICAL
NETWORK DESIGN AND MODELLING, 2002. [s.n.], 2002. p.417–430.
[CAR 07] CARVALHO, A. R. M. Dimensionamento e an´alise de desempenho de redes
NG-SDH para suporte de tr´afego IP. Instituto Superior T´ecnico, Universidade
T´ecnica de Lisboa, 2007. Disserta¸ao de Mestrado.
[CHI 00] CHIU, A. L.; MODIANO, E. H. Traffic grooming in algorithms for reducing
electronic multiplexing costs in WDM ring networks. IEEE/OSA Journal of
Lightwave Technology, [S.l.], v.18, p.2–12, Jan, 2000.
[COX 01] COX, L. A.; JR.; SANCHEZ, J. Cost savings from optimized packing and grooming
of optical circuits: mesh versus ring comparisons. Optical Networks Magazine,
[S.l.], p.72–90, May/Jun, 2001.
[cpl ] http://www.cplex.com. acesso em: 27/05/2006.
[C.R 08] C.RESENDO, L.; RIBEIRO, M. R. N.; PIRES, J. Optimal multilayer
grooming-oriented design for inter-ring traffic protection in dni multi-ring wdm
networks. OSA-JON, Optical Society of America - Journal of Optical
Networking, [S.l.], v.7, p.533–549, 2008.
[DAT 03] DATTA, P.; SRIDHARAN, M.; SOMANI, A. K. A simulated annealing approach for
topology planning and evolution of mesh-restorable optical networks. In:
PROCEEDINGS OF IFIP WORKING CONFERENCE ON OPTICAL NETWORK
DESIGN AND MODELING, 2003. [s.n.], 2003. v.1, p.23–40.
[DAV 00] DAVIE, B.; REKHTER, Y. MPLS: Technology and Applications. Morgan
Kaufmann, 2000.
[DUT 01] DUTTA, R. Virtual Topology Design for Traffic Grooming in WDM
Networks. Graduate Faculty of North Carolina State University, 2001. Tese de
Doutorado.
[DUT 02a] DUTTA, R.; ROUSKAS, G. Traffic grooming in WDM networks: past and future.
IEEE Network, [S.l.], p.46–56, Nov/Dec, 2002.
126
[DUT 02b] DUTTA, R.; TOUSKAS, G. On optimal traffic grooming in WDM rings. IEEE
Journal on Selected Areas in Communications, [S.l.], p.110–121, Jan, 2002.
[FAN 03] FANG, J.; SOMANI, A. K. Enabling subwavelength level traffic grooming in
survivable WDM optical network design. In: GLOBECOM 2003 - IEEE GLOBAL
TELECOMMUNICATIONS CONFERENCE, 2003. [s.n.], 2003. v.22, p.2761–2766.
[FAN 05] FANG, J. et al. On partial protection in groomed optical WDM mesh networks.
Dependable Systems and Networks, 2005. DSN 2005. Proceedings.
International Conference on, [S.l.], v.28, p.228–237, 2005.
[FAR 00] FARINA, M. Cost-effective Evolutionary Strategies for Pareto Optimal
Front Approximation in Multiobjective Shape Design Optimization of
Electromagnetic Devices. UNIVERSITY OF PAVIA, 2000. Tese de Doutorado.
[FAR 02] FARAHMAND, F.; FUMAGALL, A.; TACCA, M. Near-optimal design of WDM
dual-ring with dual-crossconnect architecture. In: PROCEEDINGS- SPIE THE
INTERNATIONAL SOCIETY FOR OPTICAL ENGINEERING, 2002. [s.n.], 2002.
p.286–297.
[FIL 03] FILHO, A. L. S.; WALDMAN, H. Strategies for designing translucent wide-area
networks. Proceedings of the 2003 SBMO/IEEE MTT-S International
Microwave and Optoelectronics Conference, IMOC 2003., [S.l.], v.2,
p.931–936, 2003.
[G.7 96] G.707, I.-T. R. Network Node Interface for the Synchronous Digital
Hierarchy (SDH).
[GER 00] GERSTEL, O.; RAMASWAMI, R. Optical layer survivability: A services
perspective. IEEE Commun. Mag., [S.l.], v.38, p.104–113, 2000.
[GIO 91] GIOZZA, W. F.; CONFORTI, E.; WALDMAN, H. Fibras
´
Opticas: Tecnologia
e Projeto de Sistemas. Makron: McGrall Hill, 1991.
[HU 04] HU, J.; LEIDA, B. Traffic grooming, routing, and wavelength assignment in optical
WDM network. In: PROCEEDINGS OF THE IEEE INFOCOM 2004, 2004. [s.n.],
2004. p.495–501.
[HUI 02] HUIBAN, G.; PERENNES, S.; SYSKA, M. Traffic grooming in WDM networks
with multi-layer switches. In: ICC 2002, IEEE INTERNATIONAL CONFERENCE
ON COMMUNICATIONS, 2002. [s.n.], 2002. v.5, p.2896–2901.
127
[JAE 07] JAEKEL, A. et al. New techniques for efficient traffic grooming in WDM mesh
networks. In: PROCEEDINGS OF 16TH INTERNATIONAL CONFERENCE ON
COMPUTER COMMUNICATIONS AND NETWORKS, 2007. ICCCN 2007, 2007.
[s.n.], 2007. p.303–308.
[KAR 99] KARTALOPOULOS, S. V. Understanding SONET/SDH and ATM :
communications networks for the next millennium. New York : IEEE Press,
1999.
[KAR 04] KARASAN, E.; ARISOYLU, M. Design of translucent optical networks: Partitioning
and restoration. Photonic Network Commun., [S.l.], v.8, n.2, p.209–221, 2004.
[LEE 04] LEE, Y.; MUKHERJEE, B. Traffic engineering in next-generation optical networks.
IEEE Communications Surveys, [S.l.], v.6, n.4, p.16–32, 2004.
[LIU 02] LIU, K. H. IP over wdm. John Wiley and Sons, 2002.
[MAI 02] MAIER, G. et al. Optical network survivability: Protection techniques in the WDM
layer. Photonic Network Communications, [S.l.], v.3, p.251–269, 2002.
[MEY 08] MEYNELL, K.; ET AL. Earnest. Report on Technical Issues, [S.l.], p.1–104,
Mar, 2008.
[MUK 01] MUKHERJEE, J. W. V. R. V. W. C. B. Improved approaches for cost-effective
traffic grooming in wdm ring networks: ILP formulations and single-hop and
multihop connections. IEEE/OSA Journal of Lightwave Technology, [S.l.],
v.19, n.11, p.1645–1653, 2001.
[OU 03] OU, C. et al. Traffic grooming for survivable WDM networks - shared protection.
IEEE Jour. On Selected Areas In Communications, [S.l.], v.21, p.1367–1383,
2003.
[PIO 04] PIORO, M.; MEDHI, D. Routing, Flow, and Capacity Design in
Communication and Computer Networks. Morgan Kaufmann, 2004.
[RAA 07] RAACK, C. et al. Capacitated network design using general flow-cutset inequalities.
In: PROCEEDINGS OF THE INTERNATIONAL NETWORK OPTIMIZATION
CONFERENCE (INOC 2007), 2007. [s.n.], 2007. p.7–14.
[RAI 08] RAI, S. et al. On provisioning in dual-node interconnected SONET/SDH rings.
Selected Areas in Communications, IEEE Journal on, [S.l.], v.26, n.3,
p.36–46, April, 2008.
128
[RAM 96] RAMASWAMI, R.; SIVARAJAN, K. N. Design of logical topologies for wavelength
routed optical network. IEEE J. Sel. Areas Comun, [S.l.], v.14, p.840–851, Jun,
1996.
[RAM 99a] RAMAMURTHY, B. et al. Transparent vs. opaque vs. translucent
wavelength-routed optical networks. Optical Fiber Communication
Conference and the International Conference on Integrated Optics and
Optical Fiber Communication, OFC/IOOC ’99, [S.l.], v.1, p.59–61, 1999.
[RAM 99b] RAMAMURTHY, S.; MUKHERJEE, B. Survivable WDM mesh networks, parti
-protection. In: INFOCOM’99, 1999. [s.n.], 1999. p.744–751.
[RAM 02] RAMASWAMI, R.; SIVARAJAN, K. N. Optical Networks: A Practical
Perspective. Morgan Kaufmann, 2002.
[RAM 03] RAMAMURTHY, S.; SAHASRABUDDHE, L.; MUKHERJEE, B. Survivable WDM
mesh networks. IEEE/OSA J. Lightwave Tech., [S.l.], v.21, p.870–883, Apr,
2003.
[SCH 01] SCHMUTZER, C.; TOMSU, P. Christian Schmutzer Peter Tomsu. Next
Generation Optical Networks: The Convergence of IP Intelligence and
Optical Technologies. Prentice Hall, 2001.
[SHE 05] SHENAI, R.; SIVALINGAM, K. Hybrid survivability approaches for optical wdm
mesh networks. Journal of Lightwave Technology, [S.l.], v.23, n.10,
p.3046–3055, 2005.
[SHE 07] SHEN, G.; TUCKER, R. S. Translucent optical networks: the way forward [topics in
optical communications]. Communications Magazine, IEEE, [S.l.], v.45, n.2,
p.48–54, Feb. 2007.
[SIM 99] SIMMONS, J.; GOLDSTEIN, E.; SALEH, A. Quantifying the benefit of wavelength
add-drop in wdm rings with independent and dependent traffic. IEEE/OSA
Journal of Lightwave Technology, [S.l.], v.17, p.48–57, 1999.
[SIV 03] SIVAKUMAR, M. et al. A hybrid protection-restoration mechanism for enhancing
dual-failure restorability in optical mesh-restorable networks. In: IN OPTICAL
NETWORKING AND COMMUNICATIONS (OPTICOMM), 2003. [s.n.], 2003.
[SIV 06] SIVAKUMAR, M.; SIVALINGAM, K.; SOMANI, A. Partial protection in optical
wdm networks: Enhanced support for dynamic traffic. Broadband
Communications, Networks and Systems, 2006. BROADNETS 2006. 3rd
International Conference on, [S.l.], p.1–5, 2006.
129
[SOL 07] SOLANO, F. et al. G+: Enhanced traffic grooming in WDM mesh networks using
lighttours. IEEE Journal on Selected Areas in Communications, [S.l.], v.25,
n.5, 2007.
[SOM 05] SOMANI, A. K. Survivability and Traffic Grooming in WDM Optical
Networks. Cambridge University Press, 2005.
[SZO 05] SZODENYI, A. et al. Design of traffic grooming optical virtual private networks
obeying physical limitations. In: SECOND IFIP INTERNATIONAL
CONFERENCE ON WIRELESS AND OPTICAL COMMUNICATIONS
NETWORKS, WOCN 2005, 2005. [s.n.], 2005. p.221–225.
[TO 94] TO, M.; NEUSY, P. Unavailability analysis of long-haul networks. Selected Areas
in Communications, IEEE Journal on, [S.l.], v.12, n.1, p.100–109, Jan 1994.
[VAS 04] VASSEUR, J. P.; PICKAVET, M.; DEMEESTER, P. Network Recovery:
Protection and Restoration of Optical, SONET-SDH, IP, and MPLS.
Morgan Kaufmann, 2004.
[WAN 00] WAN, P.; CALINESCU, G.; FRIEDER, O. Grooming of arbitrary traffic in
sonet/wdm blsrs. Selected Areas in Communications, [S.l.], v.18, n.10,
p.1995–2003, Oct, 2000.
[WAN 02] WANG, J.; MUKHERJEE, B. Interconnected WDM ring networks: Strategies for
interconnection and traffic grooming. SPIE Optical Netwroks Magazine, [S.l.],
v.3, n.5, p.10–20, 2002.
[XUE 05] XUE, F. et al. Performance comparison of optical burst and circuit switched
networks. In: TECHNICAL DIGEST OF IEEE/OSA OPTICAL FIBER
COMMUNICATION CONFERENCE, 2005. [s.n.], 2005.
[YAO 05] YAO, W.; RAMAMURTHY, B. Survivable traffic grooming with path protection at
the connection level in WDM mesh networks. Journal of Lightwave
Technology, [S.l.], v.23, n.10, p.2846–2853, 2005.
[YE 03] YE, Y. et al. Algorithms for the design of WDM translucent optical networks. Opt.
Express, [S.l.], v.11, p.2917–2926, 2003.
[YEN 71] YEN, J. Y. Finding the k shortest loopless paths in a network. Management
Science, [S.l.], v.17, n.11, p.712–716, 1971.
[ZAN 00] ZANG, H.; JUE, J. P.; MUKHERJEE, B. A review of routing and wavelength
assignment approaches for wavelength-routed optical WDM networks. SPIE
Optical Networks Magazine, [S.l.], v.1, n.1, p.47–60, 2000.
130
[ZHA 00] ZHANG, X.; QIAO, C. An effective and comprehensive approach for traffic
grooming and wavelength assigment in SONET/WDM rings. IEEE/ACM Trans.
Networking, [S.l.], v.8, n.5, p.608–617, 2000.
[ZHA 04] ZHANG, J.; MUKHERJEE, B. A review of fault management in WDM mesh
networks: Basic concepts and research challenges. IEEE Network, [S.l.], p.41–48,
2004.
[ZHU 02] ZHU, K.; MUKHERJEE, B. Traffic grooming in an optical WDM mesh network.
IEEE Journal on Selected Areas in Communications, [S.l.], v.20, n.1,
p.122–133, Jan, 2002.
[ZHU 03] ZHU, K.; MUKHERJEE, B. A review of traffic grooming in WDM opticas networks:
architectures and challenges. Optical networks Magazine, [S.l.], v.4, n.2,
p.55–64, 2003.
[ZHU 05] ZHU, H.; ZHU, K.; MUKHERJEE, B. Traffic Grooming in Optical WDM
Mesh Networks. Springer Science + Business Media, 2005.
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