Embed Size (px)
Citation preview
Estratégias de Planeamento para Tráfego Estático e Dinâmico em Redes de Transporte Óticas
André Mira Pereira Fernandes
Dissertação para obtenção de Grau de Mestre em
Engenharia Eletrotécnica e de Computadores
Orientadores:
Prof. João José de Oliveira Pires
Doutor João Manuel Ferreira Pedro
Júri Presidente: Prof. José Eduardo Charters Ribeiro da Cunha Sanguino
Orientador: Prof. João José de Oliveira Pires
Vogal: Prof. Amaro Fernandes de Sousa
Outubro 2017
III
Para a minha família
IV
V
Agradecimentos Quero agradecer ao Professor João Pires pela atribuição desta dissertação, bem como pela orientação
e disponibilidade que demonstrou ao longo de todo o tempo de elaboração deste trabalho.
Quero também agradecer ao Dr. João Pedro e ao Dr. Rui Dias Morais por todo o apoio e pelas
sugestões fornecidas, também elas fundamentais para a realização desta dissertação.
Agradeço também à minha família por me ter apoiado ao longo de todo o processo, bem como aos
meus amigos por todo o companheirismo e ajuda que me prestaram.
VI
VII
Abstract Today we are witnessing an unprecedented growth in telecommunications traffic. However, this growth
becomes uncertain due to the unpredictability both from the technology and the client service
development. Therefore, these aspects lead to an urge from the operators not only to provide network
resources, which can give response to these high streams of data while maintaining the quality of
service, but also to plan the network resources carefully to reduce CAPEX (Capital Expenditure). It is
consequently essential and necessary for operators to have good planning tools. This thesis aims to
describe a planning tool which handles traffic demands from client services and attempts to plan WDM
(Wavelength Division Multipplexing) networks using OTN (Optical Transport Networks) technology for
incoming static or dynamic traffic. This tool was also extended to support three multiperiod planning
approaches. Using the planning tool, a study was conducted to analyse three routing strategies and four
lightpath selection approaches in the traffic grooming process to understand the context in which each
of them is more cost-efficient in a dynamic traffic scenery, followed by another study in which were
considered three multiperiod planning approaches for incoming static traffic. These were analysed for
three different scenarios, and the impact of the traffic prediction for each planning strategy was put to
the test.
Keywords WDM networks, OTN, Traffic grooming, Multiperiod planning
VIII
IX
Resumo Atualmente assistimos a um crescimento sem precedentes do tráfego na área das telecomunicações.
Ainda assim, este crescimento é também incerto, uma vez que o desenvolvimento de novas tecnologias
e serviços de cliente são muitas vezes imprevisíveis. Estes aspetos levaram as operadoras a terem
que disponibilizar não só os recursos necessários para atender a esses débitos elevados e manter a
qualidade de serviço, mas também a ter que planear os recursos da rede com cuidado, de forma a
reduzir o CAPEX (Capital Expenditure). Assim, é fundamental para as operadoras possuírem boas
ferramentas de planeamento. Neste trabalho foi adaptada uma ferramenta de planeamento que ao
receber como input os requisitos de tráfego cliente, tem como objetivo o planeamento de redes WDM
(Wavelength Division Multiplexing) utilizando a tecnologia OTN (Optical Transport Networks) para
cenários de tráfego estático ou dinâmico. A ferramenta foi também estendida para suportar a utilização
de três estratégias diferentes de planeamento multiperiodo. Usando a ferramenta desenvolvida, foi feito
um estudo para análise de três estratégias de encaminhamento e quatro estratégias de seleção de
lightpaths no processo de agregação do tráfego, de forma a perceber qual o contexto em que cada uma
é mais eficiente em termos de custo, num cenário de tráfego dinâmico. Neste trabalho, foi ainda
conduzido outro estudo sobre as três estratégias de planeamento multiperiodo implementadas na
ferramenta de planeamento. Estas foram analisadas com recurso a diferentes cenários de trafego onde
é testada a resiliência das diferentes estratégias a previsões de tráfego diferentes do tráfego real.
Palavras Chave Redes WDM, OTN, Agregação do tráfego, Planeamento multiperiodo
X
XI
Índice Abstract…………………………………………………………………………………………………….....…VII
Resumo…………………………………………………………………………………………..………………IX
Lista de Figuras .................................................................................................................................... XIII
Tabelas ................................................................................................................................................XVII
Lista de Abreviações ............................................................................................................................XIX
1 Introdução ........................................................................................................................................ 1
1.1 Redes de transporte – Evolução ............................................................................................. 1
1.2 Enquadramento e motivação ................................................................................................... 2
1.3 Objetivo e estrutura do trabalho .............................................................................................. 3
1.4 Contribuições ........................................................................................................................... 4
2 Considerações Gerais e Tecnologia OTN ....................................................................................... 7
2.1 Descrição de uma rede de telecomunicações ........................................................................ 7
2.2 Redes OTN .............................................................................................................................. 9
2.2.1 Modelo de camadas OTN .................................................................................................... 9
2.2.2 Domínio elétrico: estrutura das subcamadas .................................................................... 10
2.2.3 Domínio ótico: subcamadas e elementos de rede ............................................................ 12
2.2.4 Arquitetura dos elementos da rede ................................................................................... 14
2.2.5 ROADMs – Reconfigurable Add and Drop Multiplexers.................................................... 17
2.3 RWA, agregação e planeamento multiperiodo...................................................................... 18
2.3.1 Encaminhamento ............................................................................................................... 19
2.3.2 Ordenação de caminhos e atribuição de comprimentos de onda ..................................... 20
2.3.3 Agregação de tráfego ........................................................................................................ 22
2.3.4 Estratégias de planeamento multiperiodo ......................................................................... 26
3 Algoritmos para Encaminhamento e Cálculo do Número Mínimo de Regeneradores .................. 29
3.1 Algoritmos de encaminhamento ............................................................................................ 29
3.2 Cálculo do número mínimo de regenerações ....................................................................... 31
3.3 Resultados e conclusões ....................................................................................................... 35
4 Descrição do Simulador de Redes OTN ........................................................................................ 41
4.1 Modulo de geração de recursos da rede ............................................................................... 41
4.2 Modulo de geração de tráfego............................................................................................... 44
XII
4.3 Módulo de mapeamento e agregação do tráfego ................................................................. 45
4.4 Mapeamento em cenário multiperiodo .................................................................................. 48
5 Mapeamento do Tráfego Cliente – Mapeamento Direto e Agregação .......................................... 51
5.1 Mapeamento direto de ODUs ................................................................................................ 52
5.2 Agregação/Multiplexagem de ODUs ..................................................................................... 53
5.3 Estratégias para seleção de lightpaths ................................................................................. 54
5.4 Resultados – tráfego dinâmico .............................................................................................. 56
5.4.1 Impacto do critério de custo para o estabelecimento dos caminhos estáticos ................. 56
5.4.2 Impacto das diferentes estratégias de seleção de lightpaths ........................................... 60
5.5 Análise comparativa de estratégias de planeamento multiperiodo – Tráfego Estático ........ 66
6 Conclusões ..................................................................................................................................... 71
A. Topologias Físicas das Redes Analisadas ....................................................................................... 73
B. Algoritmo dos 𝑘𝑘 Caminhos Alternativos (exemplo de execução) ..................................................... 75
C. Distribuições Estatísticas na Geração de Tráfego Dinâmico ........................................................... 77
Distribuição exponencial ................................................................................................................ 77
Distribuição de pareto generalizada ............................................................................................... 77
Log-Normal ..................................................................................................................................... 78
Constante ....................................................................................................................................... 79
D. Algoritmo IGABAG (exemplo de execução) ..................................................................................... 81
Bibliografia ............................................................................................................................................. 85
XIII
Lista de Figuras Figura 1.1. Utilização Máxima dos Recursos Óticos ............................................................................... 2 Figura 2.1. Diferentes topologias físicas: (a) Malha; (b) Anel; (c) Estrela. .............................................. 7 Figura 2.2. Grelhas normalizadas pela ITU-T: (a) Grelha Fixa - espaçamento de 50GHz entre canais;
(b) Grelha Flexível - espaçamento variável entre canais. (adaptada de [7]) .......................................... 9 Figura 2.3. Adição de cabeçalhos nos domínios ótico e elétrico (extraída de [9]).................................. 9 Figura 2.4. Opções de multiplexagem nas redes OTN (extraída de [7]) .............................................. 12 Figura 2.5. Representação do Optical terminal Multiplexer .................................................................. 13 Figura 2.6. Rede Simplificada; Camadas, elementos de rede e separação entre domínios ótico e elétrico
(extraída de [9]) ..................................................................................................................................... 14 Figura 2.7. Arquitetura do nó de uma rede translucida (OTN/WDM Switch) ........................................ 15 Figura 2.8 - Arquitetura do nó de uma rede opaca ............................................................................... 16 Figura 2.9. Arquitetura do nó de uma rede transparente ...................................................................... 17 Figura 2.10. Algoritmo de agregação IGABAG (retirado de [18] ) ........................................................ 25 Figura 2.11. Abordagens de planeamento multiperiodo (retirado de [5]) ............................................. 27 Figura 3.1. Algoritmo de Dijkstra ........................................................................................................... 30 Figura 3.2. Algoritmo dos 𝑘𝑘 caminhos mais curtos (adaptado de [23]) ................................................. 31 Figura 3.3. Regeneração de sinais óticos num nó da rede (extraída de [24]) ...................................... 32 Figura 3.4. Obtenção de caminhos de menor custo para cada um dos critérios numa rede exemplo. 33 Figura 3.5. Algoritmo para o calculo do número mínimo de regeneradores necessário para cada
conjunto de caminhos entre pares de nós. ........................................................................................... 34 Figura 3.6. Número médio de saltos de cada k-caminho alternativo - Rede COST239 ....................... 35 Figura 3.7. Número médio de saltos de cada k-caminho - Rede NSFNET .......................................... 36 Figura 3.8. Número médio de saltos de cada k-caminho alternativo – Rede UBN............................... 36 Figura 3.9. Número mínimo de regeneradores para um alcance máximo do sistema de 1100 km - Rede
COST239 ............................................................................................................................................... 37 Figura 3.10. Número mínimo de regeneradores para um alcance máximo do sistema de 1500 km -
Rede COST239 ..................................................................................................................................... 38 Figura 3.11. Número mínimo de regeneradores para um alcance máximo do sistema de 3000 km - Rede
NSFNET ................................................................................................................................................ 38 Figura 3.12. Número mínimo de regeneradores para um alcance máximo do sistema de 3500 km - Rede
NSFNET ................................................................................................................................................ 38 Figura 3.13. Número mínimo de regeneradores para um alcance máximo do sistema de 3000 km -
Rede UBN.............................................................................................................................................. 39 Figura 3.14. Número mínimo de regeneradores para um alcance máximo do sistema de 3500 km - Rede
UBN ....................................................................................................................................................... 39 Figura 4.1. Tempos entre pedidos de tráfego e a sua duração. ........................................................... 42 Figura 4.2. GUI para geração de recursos da rede .............................................................................. 43
XIV
Figura 4.3. Ficheiro NetInfo_NetworkName .......................................................................................... 43 Figura 4.4. Interface que permite ao utilizador escolher entre tráfego estático e dinâmico ................. 44 Figura 4.5. Interface que permite ao utilizador escolher os parâmetros do tráfego estático ................ 44 Figura 4.6. Interface do gerador de tráfego ........................................................................................... 45 Figura 4.7. Ficheiro TrafficTrace_NetworkName.txt ............................................................................. 46 Figura 4.8. Diagrama de funcionamento do programa de mapeamento e agregação do tráfego ........ 47 Figura 4.9 - Ficheiro de tráfego estático para planeamento multiperiodo ............................................. 48 Figura 4.10 - Divisão dos ficheiros e execuções do programa de mapeamento e agregação -
Planeamento de Todos os Períodos ..................................................................................................... 48 Figura 4.11 - Divisão dos ficheiros e execuções do programa de mapeamento e agregação -
Planeamento Incremental...................................................................................................................... 49 Figura 4.12 - Divisão dos ficheiros e execuções do programa de mapeamento e agregação -
Planeamento de Fim de Vida ................................................................................................................ 49 Figura 5.1. Mapeamento do tráfego cliente: (a) Mapeamento direto; (b) Agregação do tráfego
recorrendo a multiplexagem flexível. ..................................................................................................... 51 Figura 5.2. Processo de decisão entre mapeamento direto e agregação do tráfego ........................... 52 Figura 5.3. Processo de mapeamento direto do tráfego (ritmo ODU = ritmo de linha) ....................... 52 Figura 5.4. Processo de Agregação do tráfego cliente (ritmo ODU < ritmo de linha) ........................... 54 Figura 5.5. Ilustração da utilização da estratégia 1 numa rede exemplo .............................................. 55 Figura 5.6. Ilustração da utilização da estratégia 2 numa rede exemplo .............................................. 56 Figura 5.7. Número de Interfaces de linha em função do nº de pedidos de tráfego – Rede COST239 58 Figura 5.8. Número de Interfaces de linha em função do nº de pedidos de tráfego – Rede NSFNET 58 Figura 5.9. Número de Interfaces de linha em função do nº de pedidos de tráfego – Rede UBN ....... 58 Figura 5.10. Interfaces de linha (OTU-4) utilizadas e probabilidade de bloqueio - Estratégia 1 - Rede
COST239 ............................................................................................................................................... 62 Figura 5.11. Interfaces de linha (OTU-4) utilizadas e probabilidade de bloqueio - Estratégia 2 - Rede
COST239 ............................................................................................................................................... 62 Figura 5.12. Interfaces de linha (OTU-4) utilizadas e probabilidade de bloqueio - Estratégia 3 - Rede
COST239 ............................................................................................................................................... 62 Figura 5.13. Interfaces de linha (OTU-4) utilizadas e probabilidade de bloqueio - Estratégia 4 (+3
caminhos) - Rede COST239 ................................................................................................................. 62 Figura 5.14. Número de interfaces de linha (OTU-5) utilizadas para pedidos de tráfego com débito ODU-
0 – Rede NSFNET. ................................................................................................................................ 64 Figura 5.15. Número de interfaces de linha (OTU-5) utilizadas para pedidos de tráfego com débito ODU-
3 – Rede NSFNET. ................................................................................................................................ 64 Figura 5.16. Número de interfaces de linha (OTU-5) utilizadas para pedidos de tráfego com débito ODU-
0 – Rede UBN. ...................................................................................................................................... 64 Figura 5.17. Número de interfaces de linha (OTU-5) utilizadas para pedidos de tráfego com débito ODU-
3 – Rede UBN. ...................................................................................................................................... 64 Figura 5.18 – Nº de pedidos de tráfego com débito ODU-3 bloqueados – rede NSFNET ................... 65
XV
Figura 5.19 - Nº de pedidos de pedidos de tráfego com débito ODU-3 bloqueados – rede UBN ........ 65 Figura 5.20. Número de interfaces de linha OTU-4 obtidas para cada um dos tipos de planeamento
multiperiodo – Cenário 1 ....................................................................................................................... 67 Figura 5.21. Número de interfaces de linha OTU-4 obtidas para cada um dos tipos de planeamento
multiperiodo – Cenário 2 ....................................................................................................................... 68 Figura 5.22. Aumento relativo do número de interfaces de linha OTU-4 relativamente à previsão perfeita
para cada uma das estratégias de planeamento multiperiodo ............................................................. 68 Figura 5.23. Número de interfaces de linha OTU-4 obtidas para cada um dos tipos de planeamento
multiperiodo – Cenário 3 ....................................................................................................................... 69
XVI
XVII
Tabelas Tabela 2.1 - Tramas OTU e débito disponibilizado…………………………………………………………11
Tabela 2.2 - Tramas ODU e débito disponibilizado……………………………………………………..…..11
Tabela 5.1. Número de Interfaces com e sem penalidade de transmissão por salto (impacto da
regeneração) - rede NSFNET ............................................................................................................... 59 Tabela 5.2. Número de Interfaces com e sem penalidade de transmissão por salto (impacto da
regeneração) - rede UBN ...................................................................................................................... 60
XVIII
XIX
Lista de Abreviações AP All Periods Planning
DWDM Dense Wavelength Division Multiplexing
EOL End Of Life Planning
ILP Integer Linear Programming
OCh Optical Channel
ODU Optical Data Unit
OMS Optical Multiplexing Section
OPU Optical channel Payload Unit
OTN Optical Transport Network
OTU Optical channel Transport Unit
ROADM Reconfigurable Optical Add and Drop Multiplexers
SDH Synchronous Digital Hierarchy
TDM Time Division Multiplexing
WDM Wavelength Division Multiplexing
1
1 Introdução 1.1 Redes de transporte – Evolução Inicialmente, as redes de transporte começaram a ser implementadas nas redes das operadoras para
interligar os comutadores de telefone e telégrafo. Para que pudesse existir uma cobertura regional,
nacional, e até internacional, a rede teria que estender-se ao longo de milhares de quilómetros. Nos
primeiros anos, eram usados sistemas analógicos de transmissão por meio de cobre e cabo coaxial.
Nos anos setenta já se começava a verificar uma evolução nos sistemas de tecnologia digital e a
introdução de outras tecnologias importantes como Multiplexagem por Divisão no Tempo (TDM). Estes
avanços possibilitaram que os sistemas existentes suportassem uma largura de banda
significativamente maior e sob maiores distâncias.
No entanto, o sistema analógico/digital de transmissão necessitava de uma grande quantidade de
equipamento para fins de amplificação e regeneração. Isso dava-se devido à natureza dos meios de
transmissão em cobre e em cabo coaxial, onde existem perdas significativas de sinal sob grandes
distâncias.
A invenção e aperfeiçoamento dos lasers semicondutores e das fibras óticas nos anos 80 deram origem
a uma nova era da transmissão por fibra ótica. As vantagens eram evidentes. A fibra ótica
proporcionava muito menores perdas que o cobre ou o cabo coaxial, proporcionando às operadoras
uma poupança significativa nos custos de equipamento para amplificação e regeneração, bem como
nos custos associados à manutenção da rede.
Nos anos 90, a introdução dos amplificadores óticos e dos multiplexers por divisão no comprimento de
onda veio tornar ainda mais viável a transmissão sob redes óticas, oferecendo aos operadores uma
maior eficiência de custo e potencial de capacidade disponível virtualmente ilimitada para a rede de
transporte [1].
Entre os anos 90 e meados do novo milénio, já existiam grandes esperanças e especulação em relação
a uma rede totalmente transparente. De facto, muitos previam uma rede Backbone relativamente
simples onde os sinais de cliente seriam multiplexados ao nível ótico e comutados na rede sem que
elementos da rede core tivessem que efetuar qualquer processamento elétrico destes sinais [2].
Em resposta a esta pretensão generalizada, a ITU-T Study Group 15 (SG15) desenvolveu uma série
de normas para Redes Óticas de Transporte (ou Optical Transport Networks - OTN). Estas normas
cobrem a camada física, o ritmo de sinal e a especificação do formato, bem como os requisitos de
funcionamento do equipamento em redes com multiplexagem por divisão no comprimento de onda [2].
As OTN disponibilizam invólucros digitais que são compatíveis com múltiplas tramas de dados de
diferentes serviços de cliente, aglomerando-as num ODU (Optical Data Unit) comum. Esta
2
característica permite que a rede encaminhe grandes volumes de qualquer tipo de tráfego de forma
eficiente, incluindo Ethernet e SDH [3]. Resumindo, o surgimento das OTN veio trazer um conceito
simples, porém poderoso. Como mostra a Figura 1.1, esta tecnologia permite abranger uma gama
diversa de sinais de cliente, sob uma rede ótica quase transparente, com perdas pouco significativas,
e com uma grande largura de banda disponível, graça ao aparecimento da tecnologia DWDM (Dense
Wavelength Division Multiplexing) em redes óticas.
Figura 1.1. Utilização Máxima dos Recursos Óticos
1.2 Enquadramento e motivação O aumento significativo do tráfego do tráfego nos últimos anos muito se deve à utilização crescente
serviços de telecomunicações em quase todos os seus quadrantes. Segundo [4] , alguns fatores como
o aumento dos dispositivos, o aumento do número de pessoas que utilizam os serviços, a maior
velocidade de banda larga disponibilizada aos clientes, bem como a cada vez maior predominância de
tráfego vídeo existente na internet fazem com que nas últimas décadas se possa observar uma grande
dinâmica na área das telecomunicações. Para que seja possível corresponder a esta imensa magnitude
de tráfego e manter uma boa qualidade de serviço é necessário um cuidadoso planeamento da rede.
De facto, é expectável que as redes OTN venham a exibir um comportamento dinâmico a longo prazo
devido a rápidas mudanças tanto nos requisitos de tráfego (traffic demands) como a nível da tecnologia.
Em relação aos requisitos de tráfego, os clientes requerem maiores larguras de banda e maior
acessibilidade a novos serviços de comunicação que surjam no mercado.
Todos estes fatores tornam evidente a necessidade de se implementarem ferramentas de
planeamento. Estas têm como objetivo oferecer soluções eficientes no que diz respeito à utilização dos
recursos disponíveis, face às necessidades do cliente. Além do mais, o facto de novas tecnologias
estarem constantemente a surgir no sentido de melhorar o desempenho das redes, faz com que as
ferramentas de planeamento também sejam usadas para avaliar e comparar as várias alternativas
3
antes e avançar para o seu fabrico, introdução no mercado e utilização. Assim, as ferramentas de
planeamento têm um papel importantíssimo e afetam diretamente a competitividade das operadoras.
Esta dissertação foca-se no planeamento de redes OTN. Nesse sentido a ferramenta usada recorre a
métodos heurísticos para obter soluções eficientes. Estes, ao contrário dos modelos ILP (Integer Linear
Programming) tendem a ser rápidos, escaláveis e adequados para problemas de grandes dimensões.
Contudo, a sua utilização não garante a obtenção de soluções ótimas. Os modelos ILP por sua vez
geram sempre soluções ótimas, muito embora possam trazer grandes limitações em termos de
escalabilidade, dependendo dos recursos computacionais disponíveis [5].
O pacote de software utilizado deriva de um conjunto de ferramentas inicialmente desenvolvidas em
linguagem C pelo co-orientador desta dissertação, Dr. João Pedro, e focam-se no planeamento de
tráfego dinâmico (tráfego converge para a rede sem que haja conhecimento antecipado sobre o
mesmo). Este possui um módulo inicial que gera um conjunto de pedidos de tráfego (sinais de tráfego
cliente que têm como objetivo serem encaminhados da rede) de acordo com algumas especificações,
que são por sua vez mapeados através da utilização de algoritmos heurísticos de encaminhamento e
agregação. Neste módulo, o tráfego é agregado de forma a reduzir, tanto quanto possível, o número
de interfaces de linha utilizadas e a probabilidade de bloqueio seguindo várias estratégias diferentes.
O programa, uma vez que adaptado para linguagem MatLab, terá como objetivo adicional o suporte de
planeamento de redes em cenário multiperiodo (planeamento efetuado sob vários períodos de tempo
individuais, tendo em conta diferentes objetivos).
1.3 Objetivo e estrutura do trabalho O objetivo deste trabalho consiste na implementação de um simulador de redes OTN programado na
linguagem de programação MatLab, e adaptá-lo para suportar o encaminhamento de tráfego estático
utilizando estratégias de planeamento sob múltiplos períodos de tempo (Planeamento Multiperiodo). O
pacote de software implementado é baseado num programa da autoria do Dr. João Pedro, co-orientador
nesta dissertação.
No Capítulo 2 faz-se uma descrição geral de uma rede de telecomunicações, e introduz-se o conceito
de OTN, especificando-se a tecnologia ao nível da sua arquitetura no domínio elétrico e ótico. Neste
capítulo são também feitas algumas considerações sobre o encaminhamento, atribuição de
comprimentos de onda, bem como dos estudos feitos no âmbito dos métodos de agregação do tráfego
cliente existentes na literatura. Finalmente, são descritas algumas estratégias de planeamento
multiperiodo que foram implementadas no simulador de redes OTN utilizado nesta dissertação.
No Capítulo 3 descrevem-se os algoritmos de encaminhamento que foram implementados no
simulador. Analisam-se também algumas estratégias de atribuição de custos implementadas e o seu
desempenho ao nível dos requisitos de regeneração do sinal ótico. São posteriormente apresentados
alguns resultados que visam comparar cada uma das estratégias.
4
O Capítulo 4 foca-se essencialmente na descrição da ferramenta desenvolvida em MatLab. O objetivo
é que o leitor possa ficar familiarizado com o contexto em que os resultados obtidos no cap. 5 foram
recolhidos.
No Capítulo 5 são apresentados os algoritmos de mapeamento de tráfego que foram utilizados nesta
dissertação. Apresentam-se fluxogramas e esquemas que visam esclarecer o leitor sobre a estrutura
dos algoritmos implementados, e faz-se uma descrição textual dos mesmos. A última subsecção deste
capítulo apresenta os resultados obtidos da simulação de três critérios de custo para o estabelecimento
das rotas fixas e de quatro estratégias de seleção de lightpaths no processo de agregação. É
posteriormente feita uma análise comparativa sobre o desempenho das estratégias, concluindo sobre
em que cenários cada uma delas é mais adequada. Finalmente, é feito um estudo sobre três estratégias
de planeamento multiperiodo com tráfego estático com discrepâncias impostas entre o tráfego previsto
e o tráfego real.
No Capítulo 6 são apresentadas as conclusões que se retiraram da análise dos resultados obtidos no
âmbito desta dissertação, e são feitas algumas sugestões relativamente ao trabalho futuro que poderá
vir a ser desenvolvido.
1.4 Contribuições As principais contribuições resultantes desta dissertação incidem essencialmente nos seguintes
pontos:
• Estudo dos algoritmos de encaminhamento heurísticos como é o caso dos algoritmos de
Dijkstra e dos 𝑘𝑘-caminhos mais curtos. Apresentação de abordagens a nível de atribuições de
custo de arestas da rede de forma a minimizar o número mínimo de regeneradores necessários
para cada caminho.
• Adaptação para MatLab de um programa de geração dos recursos e características da rede,
mediante as opções do utilizador. Foi criada uma GUI (Guide User Interface) que permite ao
utilizador escolher as especificações pretendidas para a rede e para o tráfego a gerar. Neste
programa o utilizador terá ao seu dispor dois ficheiros, um descrevendo as características da
rede, e outro especificando todos os pedidos de tráfego cliente gerados.
• Adaptação para MatLab de um simulador de redes OTN para mapeamento do tráfego cliente
gerado no módulo inicial. O utilizador tem a opção de escolher o tipo de encaminhamento com
diferentes critérios de custo. O utilizador também pode escolher o método de atribuição de
comprimentos de onda, bem como as estratégias envolvidas no processo de agregação do
tráfego cliente. O simulador foi expandido de forma a suportar a agregação de tráfego estático
e com três opções de planeamento multiperiodo.
5
• Estudo e avaliação dos resultados provenientes da utilização das várias estratégias
implementadas no simulador. Os resultados são analisados tendo em conta sobretudo as
interfaces de linha utilizadas e a probabilidade de bloqueio dos pedidos de tráfego.
6
7
2 Considerações Gerais e Tecnologia OTN 2.1 Descrição de uma rede de telecomunicações Uma rede de telecomunicações pode ser descrita através de um grafo 𝐴𝐴(𝑁𝑁, 𝐿𝐿), em que 𝑁𝑁 =
{𝑛𝑛1,𝑛𝑛2, … ,𝑛𝑛𝑁𝑁} representa o conjunto de vertices e 𝐿𝐿 = {𝑙𝑙1, 𝑙𝑙2, … , 𝑙𝑙𝑁𝑁} representa o conjunto de arestas.
Estas redes são utilizadas para transmitir informação a longa distância de forma confiável, ou seja, sem
perda de informação ou distorção.
As redes são distinguidas por terem diferentes topologias físicas. Uma topologia física é definida por
um conjunto de nós (onde normalmente se encontram os elementos da rede) e arestas (que interligam
fisicamente os nós, e que no caso das redes OTN consistem em fibras óticas), que caracterizam a rede.
Algumas topologias físicas comuns são a topologia em malha (mesh), anel (ring) e estrela (star), que
estão representadas, respetivamente, na Figura 2.1. No Anexo A estão representadas as topologias
físicas para três redes de teste, as quais vão ser utilizadas nos estudos no âmbito desta dissertação.
Além disso, os grafos podem ser direcionados, ou não direcionados. Um grafo direcionado é composto
por um conjunto de arestas com uma determinada orientação. Já nos grafos não direcionados,
convenciona-se que o fluxo de informação pode ser feito de modo bidirecional em todas as ligações
físicas. Na prática, em redes óticas, uma ligação física direcionada representa uma fibra ótica com uma
certa orientação, enquanto que uma ligação física não direcionada consiste em duas fibras óticas
orientadas em direções opostas (de modo bidirecional).
Uma topologia física 𝐴𝐴(𝑁𝑁, 𝐿𝐿) pode ser representada através de uma matriz 𝑁𝑁𝑁𝑁𝑁𝑁 em que 𝑁𝑁 designa o
número de nós, ou elementos da rede, os quais estão em geral localizados nos vértices. Nesta matriz,
o valor de cada entrada 𝑙𝑙𝑖𝑖𝑖𝑖 contém o valor correspondente à distância que separa o nó 𝑖𝑖 do nó 𝑗𝑗, ou à
representação das adjacências, em que o valor “1” indica que existe ligação física entre os nós 𝑖𝑖 e 𝑗𝑗 e
o valor “0” indica que essa ligação não existe.
(a) (b) (c)
Figura 2.1. Diferentes topologias físicas: (a) Malha; (b) Anel; (c) Estrela.
8
Outro conceito importante em redes de telecomunicações prende-se com o fluxo de tráfego. Neste
sentido, introduz-se o conceito de topologia lógica (ou virtual). Essencialmente, a topologia lógica
representa a forma como ocorre o fluxo de tráfego na rede. Este fluxo pode ser descrito em termos de
pedidos de tráfego, ou de ligações lógicas.
Como referido anteriormente, em termos práticos, numa representação da topologia lógica, um vértice
corresponde a um nó da rede, onde existe adição ou extração de tráfego, e uma aresta corresponde ao
fluxo de tráfego existente entre os nós limítrofes. As topologias lógicas podem também ser
representadas pelas chamadas matrizes de tráfego em que os elementos da entrada da matriz 𝑑𝑑𝑖𝑖𝑖𝑖
representam o número de unidades de tráfego cliente que fluem entre o nó de origem 𝑖𝑖 e nó de destino
𝑗𝑗.
No caso em que se conhecem, à priori, todos os pedidos de tráfego, é possível formular uma matriz
imutável ao longo do tempo. Diz-se neste caso que o tráfego é estático. Caso não se conheçam todos
os pedidos de tráfego, ou estes venham chegando progressivamente à rede, um a um, sem que haja
conhecimento antecipado sobre as suas características, diz-se que o tráfego é dinâmico, ou seja, a
matriz de pedidos de tráfego muda ao longo do tempo de forma imprevisível.
A tecnologia utilizada nesta dissertação para o transporte de tráfego é a OTN, que pressupõe a
presença de ROADMs (Reconfigurable Add and Drop Mulltiplexer) e ODU switches como elementos
de rede presentes nos nós, bem como fibras óticas sob a tecnologia DWDM nas suas ligações físicas.
A tecnologia DWDM distingue-se da WDM pelo facto de conferir um menor espaçamento entre
comprimentos de onda, aumentado assim a capacidade da fibra. Esta tecnologia tem outras facetas
interessantes tais como o facto de permitir amplificar comprimentos de onda de forma imediata, sem
ser necessária a conversão para o domínio elétrico, e também a possibilidade de transportar sinais de
diferentes débitos e tipos em simultâneo e de forma transparente ao longo da fibra [6].
Para as redes DWDM foi definido um standard que estabelece que todos os canais óticos devem ter
um espaçamento uniforme entre si (ITU-T G.694.1). Os espaçamentos entre canais podem variar desde
12,5 GHz até 100 GHz, e estão ancorados na frequência central de 193,1 THz (1552,52 nm). A grelha
mais usada consiste num espaçamento de 50 GHz. Ainda assim, para permitir o transporte de sinais
de diferentes débitos e formatos, foi também definida uma norma de grelha flexível. Neste caso, o
espaçamento entre canais deixa de ser constante, e passa a existir um intervalo elementar de 12,5
GHz, passando cada canal a usar um número variável destes intervalos, de acordo com os seus
requisitos. A Figura 2.2 ilustra cada uma das grelhas estabelecidas pela ITU-T, e destaca as diferenças
entre as duas [7].
9
Figura 2.2. Grelhas normalizadas pela ITU-T: (a) Grelha Fixa - espaçamento de 50GHz entre
canais; (b) Grelha Flexível - espaçamento variável entre canais. (adaptada de [7])
2.2 Redes OTN
2.2.1 Modelo de camadas OTN O funcionamento da tecnologia OTN baseia-se na utilização de um modelo cliente-servidor entre
subcamadas. Cada uma das subcamadas oferece uma gama de serviços bem definidos às suas
“camadas cliente”, tendo cada uma delas as suas funções, características de funcionamento e
monitorização [8]. Na Figura 2.3 pode ser visualizado, de forma sumária, o processo de formação de
cabeçalhos OTN. Como mostra a Figura, este processo ocorre em dois domínios principais: o domínio
ótico e o domínio elétrico.
Figura 2.3. Adição de cabeçalhos nos domínios ótico e elétrico (extraída de [9])
10
Em cada um dos domínios, existe um processo de adição de cabeçalhos que confere determinadas
funcionalidades no processo de transporte. A próxima subsecção descreve com mais detalhe o
processo de formação da trama OTN no domínio elétrico.
2.2.2 Domínio elétrico: estrutura das subcamadas No domínio elétrico, a trama OTN passa pelo processo de adição dos seguintes cabeçalhos [9]:
1. Payload (corpo de dados) OPU;
2. Cabeçalho OPU (Optical channel Payload Unit);
3. Cabeçalho ODU (Optical channel Data Unit);
4. Cabeçalho OTU (Optical channel Transport Unit);
5. FEC (Forward Error Correction).
O processo de formação de uma trama OTN começa com a inserção do sinal cliente na área de payload
da OPU. A OPU aceita vários tipos de sinais CBR (Constant bit rate) tais como ATM, SONET/SDH,
bem como sinais de débito variável baseado em transporte por pacotes (packet based), tais como
IP/MPLS (Internet Protocol/Multi Protocol Label Switching), SAN (Storage Area Network) e tramas
Ethernet. A OPU é responsável não só pelo mapeamento do sinal cliente, mas também por adicionar o
cabeçalho da primeira subcamada elétrica. O cabeçalho OPU consiste no identificador da estrutura de
payload, o qual inclui o tipo de payload e os bits de cabeçalho associados ao mapeamento dos sinais
na payload [10].
Ao se adicionar o cabeçalho seguinte, é formada a ODU. Esta última inclui informação sobre OAM
(Operations, Administration and Maintenance) para o correto suporte de sinais óticos. A ODU tem a
particularidade de assegurar várias estratégias de mapeamento para acomodar novos sinais cliente
(alguns exemplos são AMP (Asynchronous Mapping Procedure), BMP (Bit-synchronous Mapping
Procedure) e GFP (Generic Framing Procedure)). Assim sendo, as tramas ODU formam a base para
um mapeamento e multiplexagem flexíveis, no que concerne ao processo de comutação em redes
OTN. Sinais de diferentes granularidades são assim convertidos para tramas ODU e direcionados para
o seu destino, sendo então convertidos em OTUs para serem transmitidos na camada ótica [3].
Seguem-se as tramas ODU disponíveis atualmente, os rimos de tráfego, bem como uma breve
descrição das suas aplicações típicas (ver Figura 2.4):
• ODU0 – Suporte para débitos de até 1,25 Gbits/s. Transporte de sinais 1000BASE-x ou de
sinais sob a tecnologia de pacotes como MPLS ou IP, usando para o efeito a estratégia de
mapeamento GFP;
• ODU1 – Suporte para débitos de até 2,5 Gbit/s. Transporte um sinal STM-16, bem como
pacotes IP/MPLS, usando GFP;
11
• ODU2 – Suporte para débitos de até 10 Gbit/s. Transporte de 4 sinais ODU1 bem como sinais
STM-64, WAN PHY (10GBASE-W), ou pacotes IP/MPLS, usando GFP;
• ODU2e – Suporte para débitos de até 10,4 Gbit/s. Transporte de um sinal 10 Gigabit Ethernet
ou um sinal Fiber Channel 10GFC;
• ODU3 - Suporte para débitos de até 40,32 Gbit/s. Transporte de um sinal STM-256 ou um sinal
40 Gigabit Ethernet, bem como um conjunto de pacotes Ethernet, MPLS ou IP, usando GFP;
• ODU4 - Suporte para débitos de até 104,8 Gbit/s. Transporte de um sinal 100 Gigabit Ethernet.
A trama OTU, consiste numa ODU com um cabeçalho adicional. Este encontra-se na camada mais
baixa do domínio elétrico e permite o transporte dos dados no meio ótico. Aqui, também se introduz a
técnica de correção de erros designada FEC (Forward Error Correction).
Para atender aos diferentes serviços e sinais cliente requeridos, foram criadas várias tramas OTU com
diferentes capacidades, tirando proveito da flexibilidade da tecnologia OTN. Mais recentemente criou-
se também a trama OTU5 (400 Gbit/s) que permite uma maior eficiência espectral no transporte dos
dados, mas para distâncias mais curtas.
As Tabelas 2.1 e 2.2 apresentam a variedade de sinais ODU e OTU existentes atualmente, bem como
os respetivos débitos.
Tabela 2.1 - Tramas OTU e débito disponibilizado Tabela 2.2 - Tramas ODU e débito disponibilizado
Tipo de Trama (ODUk) Débito [Gbit/s]
ODU0 1,25 ODU1 2,5 ODU2 10
ODU2e 10,4
ODU3 40,32 ODU3e2 41,8
ODU4 104,8
Uma faceta importante da tecnologia OTN é a possibilidade de ODUs de ordem baixa poderem ser
agregadas e encapsuladas na área de payload de sinais OPU de maior ordem, sendo que este último
é submetido a um processo de adição de cabeçalhos, derivando novamente num sinal ODU de maior
ordem. As várias opções de multiplexagem disponíveis estão representadas na Figura 2.4.
Tipo de Trama (OTUk) Débito [Gbit/s]
OTU1 2,66 OTU2 10,7
OTU2e 11,09 OTU3 43,01
OTU3e2 44,58 OTU4 112 OTU5 400
12
Figura 2.4. Opções de multiplexagem nas redes OTN (extraída de [7])
2.2.3 Domínio ótico: subcamadas e elementos de rede No domínio ótico, uma rede OTN é composta de ligações de transmissão sob a tecnologia DWDM
(fibras óticas) e elementos de rede. Esta oferece a possibilidade de ligação de circuitos óticos por meio
do estabelecimento de lightpaths. Cada lightpath consiste numa ligação entre dois pontos de conversão
O/E/O (Optical-to-Electrical-to-Optical). Cada lightpath atravessa os elementos de comutação ótica
existentes na rede (ROADMs) e requer um comprimento de onda por cada ligação física que utiliza.
No que concerne aos elementos da rede, destacam-se os Amplificadores Óticos (OA), Optical Add and
Drop Multiplexers (OADMs), OTM (Optical Terminal Multiplexers) e também os ROADMs
(Reconfigurable Optical Add and Drop Multiplexers) (ou, em alternativa, os Optical Cross Connects
(OXCs)). Estes interligam-se na rede por meio de fibra ótica segundo uma dada topologia física.
Os dados são mapeados na rede OTN através de transponders e muxponders. Os transponders
convertem os sinais, que geralmente são gerados na banda O (~1310 nm), como é o caso dos sinais
do tipo GbE (Gigabit Ethernet), para a banda C (~1550nm), onde as redes DWDM operam. É também
nos transponders/muxponders que ocorre o encapsulamento de sinais cliente. Embora tanto os
transponders como os muxponders tenham a finalidade de transmitir/receber sinais óticos, o
muxponder tem a particularidade de permitir agregar sinais de granularidades mais baixas num sinal
de maior débito, providenciando uma combinação de encapsulamentos e opções de agregação. Estes
possuem portos de entrada que recebem sinais de baixo débito e portos de saída que que transmitem
o sinal devidamente agregado [5].
Quanto aos OTMs (ver Figura 2.5), estes são compostos por transponders, multiplexers WDM e OAs.
A sua função é multiplexar diferentes comprimentos de onda numa fibra ótica e também desmultiplexar
um sinal DWDM em diferentes comprimentos de onda. Estes são utilizados nas terminações de cada
13
ligação ponto-a-ponto. Os OAs são implementados ao longo da ligação ótica em sítios estratégicos
com vista à amplificação dos sinais óticos.
Figura 2.5. Representação do Optical terminal Multiplexer
Cada lightpath existente na rede DWDM deve ser encaminhado até ao seu destino através de nós
intermediários que, por sua vez, deverão direcionar um dado comprimento de onda até ao seu destino.
A tarefa de encaminhar os lightpaths é desempenhada pelo OADM (Optical Add/Drop Multiplexer) ou
pelo ROADM (Reconfigurable Optical Add/Drop Multiplexer), que é uma versão reconfigurável do
OADM. Os princípios de funcionamento dos ROADMs são abordados em mais detalhe na secção 2.2.5.
Finalmente, os OXCs permitem a implementação de redes mesh, executando o encaminhamento de
vários comprimentos provenientes das fibras de ingresso. Contudo, atualmente, a tecnologia presente
nos ROADMs permite desempenhar as mesmas funções que um OXC, nomeadamente, para
implementar redes mesh. Os OXCs poderão, ainda assim, continuar a ser implementados em
aplicações de baixo custo, onde não é exigível uma constante reconfiguração dos lightpaths presentes
na rede.
As camadas (ou secções) que definem o domínio ótico são as seguintes:
• OCh (Optical Channel);
• OMS (Optical Multiplexing Section);
• OTS (Optical Trasmitting Section).
Os Canal Óticos (OCh) consistem nas implementações físicas dos lightpaths. Estes têm como função
o transporte do sinal cliente entre pontos de regeneração 3R. Os OCh também incluem um cabeçalho
no domínio ótico que permite o suporte para gestão e monitorização de vários comprimentos de onda.
Os OChs são por sua vez agrupados nas OMSs usando a tecnologia DWDM. Nesta camada ótica está
também incluído um comprimento de onda separado referente ao OSC (Optical Supervisory Channel),
o qual transporta os cabeçalhos OCh, OMS e OTS. Finalmente, a Secção de Transmissão Ótica (OTS)
é responsável pela gestão e monitorização dos amplificadores óticos. A representação das camadas
14
presentes em cada domínio físico, bem como os elementos de rede presentes em cada um, estão
ilustrados na rede OTN simplificada da Figura 2.6. A transição entre o domínio ótico e o elétrico é
situada onde a trama OTU modela um laser resultando num sinal ótico na saída, ou seja, o OCh.
Figura 2.6. Rede Simplificada; Camadas, elementos de rede e separação entre domínios ótico e elétrico (extraída de [9])
Nos OChs, a tecnologia atualmente preponderante é a DWDM. Por motivos tanto económicos como de
natureza técnica, a possibilidade de providenciar transmissão de capacidade potencialmente ilimitada
é a grande vantagem da tecnologia DWDM relativamente às anteriores. Assim, o presente investimento
na infraestrutura de fibra ótica pode não só ser preservado como otimizado em grande escala [6]. À
medida que os requisitos de tráfego aumentem, mais capacidade poderá ser adicionada à rede. Isso
pode ser conseguido através de melhoramentos no equipamento ou por aumentar o número de
comprimentos de onda presentes na fibra.
2.2.4 Arquitetura dos elementos da rede É importante referir que, uma vez que as OTN têm a particularidade de operar tanto a nível ótico como
a nível elétrico, são designadas redes translucidas. Trata-se, portanto, de uma rede hibrida em que os
nós (ou elementos da rede) são constituídos por ROADMs (Reconfigurable Optical Add and Drop
Mltiplexer), que operam integralmente no domínio ótico, em conjunto com ODU switches, que operam
no domínio elétrico.
Os ODU switches são compatíveis com uma grande variedade de sinais cliente. Uma vez que os ODU
são gerados, os ODU switches fazem com que estes sejam comutados e agregados de modo dinâmico
de forma a otimizar o tráfego na rede (traffic grooming), permitindo por isso a agregação intermédia dos
sinais cliente. Os sinais que se originam na rede DWDM também atravessam os ODU switches para
serem entregues às respetivas cartas de cliente. As cartas de linha são constituídas por OTN
multiplexers/demultiplexers e transceivers (unicamente responsáveis pela conversão O/E e E/O). Estes
componentes juntam os sinais provenientes do domínio elétrico e geram a OTU para que possa ser
transportada no domínio ótico, gerando assim o OCh, sendo que, na direção oposta, convertem o sinal
ótico para que seja transportado no domínio elétrico. O elemento de rede da Figura 2.7 que está
presente no domínio ótico é designado ROADM (Reconfigurable Add and Drop Multiplexer). Este último
15
permite que vários OChs possam ser adicionados e extraídos, mas também permite que estes o
atravessem, sem nunca saírem do domínio ótico. Esta operação dá-se através da comutação de OChs
desde a entrada até à saída do dispositivo.
Figura 2.7. Arquitetura do nó de uma rede translucida (OTN/WDM Switch)
Apesar do modelo genérico das redes OTN terem uma arquitetura translucida, é possível a
implementação de duas outras configurações alternativas [11]:
• Opaca;
• Transparente.
Nas arquiteturas opacas (ver Figura 2.8) os nós são equipados somente com ODU switches ligados à
rede WDM, através das cartas de linha e mux/demux DWDM. Neste cenário, a rede DWDM deverá ter
como objetivo o suporte para ligações ponto-a-ponto entre nós. Os canais óticos podem abranger
apenas uma linha de fibra e o número de lightpaths existente numa ligação desde origem até destino
é dado pelo número de saltos obtidos pelo algoritmo de encaminhamento utilizado sob a topologia
física.
16
Nas arquitecturas transparentes, são usados apenas ROADMS e não ODU switches, e como tal, a
comutação é feita somente no domínio ótico. As cartas de cliente estão ligadas às cartas de linha, onde
os transponders/muxponders convertem o sinal para que seja transmitido no domínio ótico. Os
comprimentos de onda resultantes atravessam o ROADM que realiza a comutação, redirecionando-os
para os respetivos portos. Os comprimentos de onda dirigem-se desde a origem até ao destino
atravessando no domínio ótico todos os nós intermédios, utilizando para o efeito um único lightpath.
Tal como se mostra na Figura 2.9, existem três configurações possíveis para as cartas de linha. Uma
é composta por um ODU multiplexer/demultiplexer e um transciever, outra por um muxponder e ainda
outra por um transponder apenas. As primeiras duas configurações permitem a multiplexagem de vários
fluxos de tráfego de baixa granularidade em fluxos de maior débito. A solução que usa o muxponder
geralmente restringe os sinais de cliente a um subconjunto de débitos possíveis (por exemplo,
agregação de 10 sinais de 10 Gb/s num sinal de 100 Gb/s ou agregação de 4 sinais de 2.5 Gb/s num
de 10 Gb/s). Por outro lado, o a solução que usa o ODU multiplexer/demultiplexer com transceiver
permite que quaisquer combinações de sinais de menor débito sejam agregadas desde que a banda
disponível o permita [11]. A terceira configuração, na qual existe um único transponder, é indicada para
sinais de cliente cujo débito seja igual ao da fibra. Assim, o sinal é convertido diretamente para ser
transportado no domínio ótico [11].
Figura 2.8 - Arquitetura do nó de uma rede opaca
17
Figura 2.9. Arquitetura do nó de uma rede transparente
Nesta dissertação considera-se que todos os elementos da rede têm a arquitetura presente na Figura
2.7, ou seja, a arquitetura correspondente às redes translucidas.
2.2.5 ROADMs – Reconfigurable Add and Drop Multiplexers Como mencionado anteriormente, em redes transparentes e translucidas, quando um comprimento de
onda ingressa num nó, este pode ser encaminhado para a parte elétrica para ser processado (canais
add/drop), ou atravessar várias OMS. Um elemento da rede que permite desempenhar estas operações
essenciais é o ROADM.
Apesar de o ROADM poder ser visto como um multiplexer/demultplexer WDM associado a um optical
switch, a arquitetura mais usada hoje em dia consiste no uso de 1 × 𝑁𝑁 WSS (Wavelenght Selective
Switch, 𝑁𝑁 denota o número de portos de entrada). Os WSS permitem fazer permutas entre
comprimentos de onda nos seus portos de entrada e de saída e implementam simultaneamente as
funcionalidades de multiplexagem e comutação ótica.
A tecnologia recente tornou possível que os ROADMs baseados na utilização de WSS se tornassem
financeiramente atrativos, promovendo a sua utilização não só nas redes long haul, como também nas
redes metro. A utilização de ROADMs nestes pontos da rede são de enorme importância, uma vez que
as mudanças de configuração são frequentes [12].
Atualmente, os ROADMs conferem um elevado grau de versatilidade e flexibilidade, podendo ser
implementados de várias formas. A flexibilidade que caracteriza o ROADM prende-se com o facto de
este possibilitar configuração remota (por meio de software) do encaminhamento, frequência central de
operação e direção que cada comprimento de onda pode tomar. Assim, estes podem ser classificados
em uma ou mais do que uma das seguintes categorias:
18
• contentionless – Evita que comprimentos de onda sejam bloqueados ao convergirem para a
mesma entrada de um dispositivo WSS;
• colorless – permite remotamente, por meio de software, que o ROADM automatize os
processos de associação de comprimentos de onda a qualquer porto de adição/extração;
• directionless – permite encaminhar os comprimentos de onda em todas as direções suportadas
pelo nó de comutação.
2.3 RWA, agregação e planeamento multiperiodo O planeamento das redes OTN depende fortemente de três processos fundamentais: O
encaminhamento, a atribuição de comprimentos de onda e a agregação do tráfego cliente.
Nas redes OTN, o encaminhamento consiste na definição da sequência de ligações atribuída a cada
lightpath na rede. Por sua vez a atribuição de comprimentos de onda consiste na atribuição de um
comprimento de onda a cada lightpath. Uma vez que seja atribuído um comprimento de onda a esse
lightpath, este passa a constituir um OCh. Este problema conjunto é designado de Encaminhamento e
Atribuição de Comprimentos de Onda (Routing and Wavelength Assignment - RWA). Quanto à
agregação do tráfego, esta consiste no agrupamento de vários sinais cliente num único lightpath de
forma a conseguir um aproveitamento eficiente da capacidade disponível na rede.
O planeamento depende também do tipo de tráfego que se pretende encaminhar na rede (ver Secção
2.1). Tipicamente, o tráfego é considerado dentro de três tipos diferentes:
1. Tráfego estático;
2. Tráfego incremental;
3. Tráfego dinâmico.
Como referido na secção 2.1, com tráfego estático, o inteiro conjunto de ligações é conhecido
antecipadamente, e o problema resume-se a estabelecer lightpaths de forma a atender a todos os
pedidos e ao mesmo tempo minimizando os recursos da rede, tais como o número de comprimentos
de onda e o número de fibras utilizados. Alternativamente, poder-se-á configurar o máximo de ligações
possíveis para um número fixo de comprimentos de onda. Ao problema de RWA para tráfego estático
dá-se o nome de Static Lightpath Establishment (SLE) [13].
No caso de tráfego incremental, os pedidos de tráfego chegam sequencialmente, os lightpaths são
estabelecidos para cada ligação, e o lightpath permanece na rede indefinidamente. No caso de tráfego
dinâmico, os lightpaths são estabelecidos para cada pedido de ligação que chega à rede. Estes são
posteriormente libertados após um período de tempo. O objetivo dos planeamentos incremental e
dinâmico é estabelecer lightpaths e atribuir comprimentos de onda de forma a minimizar o número de
pedidos de tráfego bloqueados, ou maximizar o número de pedidos atendidos pela rede. O problema
de RWA no cenário de tráfego dinâmico é designado Dynamic Lightpath Establishment (DLE) [13].
19
Nesta dissertação, utilizar-se-ão tráfego estático e dinâmico para a comparação de diferentes
estratégias de agregação. No caso de tráfego dinâmico, para cada pedido que surja, caso não exista
uma solução de encaminhamento na rede de lightpaths corrente, estabelece-se um novo lightpath.
Caso todos os ODUs presentes num dado lightpath tenham deixado a rede (quando termina o seu
tempo de duração), então esse lightpath é libertado.
2.3.1 Encaminhamento Existe uma ampla gama de estudos no âmbito do encaminhamento do tráfego no contexto das redes
WDM. De entre as estratégias às quais geralmente se tem dado mais atenção e maior aplicabilidade
estão as seguintes [14]:
• Encaminhamento fixo (fixed routing);
• Encaminhamento fixo alternado (fixed-alternate routing);
• Encaminhamento Adaptativo.
No encaminhamento fixo, as conexões são sempre encaminhadas através de rotas fixas e predefinidas,
para cada par de nós. Por exemplo, a determinação de caminhos mais curtos offline através do
algoritmo de Dijkstra, está dentro desta gama de estratégias.
O algoritmo de Dijkstra garante que se encontre o caminho mais curto entre um nó de origem e qualquer
dos nós de destino [15]. Este escolhe a solução ótima a cada iteração, sem considerar os passos
posteriores. Esta é obviamente uma estratégia que se afigura muito simples. No entanto, o
desempenho desta poderá não ser o melhor, uma vez que pode fazer com que muitas ligações da rede
se congestionem desnecessariamente. Neste caso, o mesmo caminho será sempre usado para um
dado par origem – destino, o que faz com que seja impossível uma adaptação ao estado atual da rede.
Consequentemente, poderá ocorrer o bloqueio de vários pedidos de tráfego, ainda que existam
recursos suficientes noutros caminhos para os atender.
No encaminhamento fixo e alternado, para cada pedido de tráfego, são consideradas múltiplos
caminhos fixos entre origem e destino. Nesta abordagem cada nó da rede deverá guardar uma tabela
de encaminhamento, onde terá à disposição uma lista ordenada de caminhos (por exemplo,
organizados por ordem decrescente em termos de caminho mais curto). Por cada pedido de tráfego, o
nó irá tentar estabelecer a ligação em cada caminho, em sequência, até conseguir encontrar recursos
suficientes para o fazer.
Por exemplo, o algoritmo de procura dos 𝑘𝑘 caminhos mais curtos, que se encontra dentro desta gama
de estratégias, pode também ser utilizado no contexto das redes óticas com o fim de encontrar os
caminhos que exigem menor regeneração. Neste caso, o custo de adicionar um pedido de tráfego na
rede é em grande parte influenciado pelo número de terminações elétricas (ou seja, regeneradores)
20
necessárias para suportar esse pedido sob um dado caminho. Por exemplo, no caso de uma rede
opaca, os caminhos que tenham o mesmo número de saltos têm um custo equivalente porque o número
de terminações elétricas intermediárias é o mesmo, já nas redes transparentes, a métrica utilizada no
algoritmo é a distância, pois o fator determinante neste caso será a degradação do sinal ótico [15].
Uma outra abordagem possível é a utilização de estratégias de encaminhamento adaptativo. Nesta
gama de estratégias, a rota desde a origem até ao destino é escolhida de forma dinâmica, e depende
do estado atual da rede. O estado da rede é determinado pelo conjunto de todas as ligações que estão
correntemente estabelecidas. Embora esta seja uma abordagem interessante e obtenha em geral bons
resultados, não será objeto de estudo nesta dissertação. Para uma consulta do desempenho e
comparação de algumas estratégias de encaminhamento adaptativo, poder-se-á consultar [16].
Nesta dissertação, recorreu-se ao uso dos algoritmos de encaminhamento fixo, e fixo alternado, mais
especificamente, o algoritmo de Dijkstra e o algoritmo de procura dos 𝑘𝑘 caminhos mais curtos. Estes
são usados de forma independente do processo de mapeamento do tráfego na rede e ditam o conjunto
de caminhos possíveis que cada pedido de tráfego pode tomar entre dois pares de nós.
2.3.2 Ordenação de caminhos e atribuição de comprimentos de onda Tal como referido anteriormente, o tráfego é transportado através de circuitos óticos chamados
lightpaths. Os lightpaths consistem em ligações entre nós origem e destino sem conversão
intermediária O/E/O. Nestas redes existe a limitação de que dois lightpaths não podem partilhar o
mesmo comprimento de onda numa ligação em comum (wavelength continuity constraint). Ainda assim,
existe a liberdade de se permitir a reutilização do mesmo comprimento de onda em fibras diferentes.
Sempre que existem vários comprimentos de onda disponíveis para utilização entre nós de origem e
destino, deverá ser utilizada uma estratégia de atribuição de comprimentos de onda de forma a
selecionar um comprimento de onda para um dado lightpath. A determinação do comprimento de onda
a utilizar deverá ser feita em paralelo com os algoritmos de encaminhamento, ou antes dos caminhos
serem determinados.
Devido às limitações do número comprimentos de onda por fibra e da continuidade dos comprimentos
de onda, na ausência de conversores de comprimento de onda, a rede pode não ter recursos suficientes
para atender a todos os pedidos de tráfego. Assim, com tráfego dinâmico, pretende-se aplicar os
algoritmos de atribuição de comprimentos de onda de forma a minimizar o bloqueio dos pedidos de
ligação. Já para tráfego estático, o problema consiste em calcular todos os comprimentos de onda
necessários para acomodar o tráfego. Contudo, antes de se proceder à atribuição de comprimentos de
onda, poder-se-á levar em conta o comprimento dos lightpaths aos quais de pretende fazer essa
atribuição. Por exemplo, a aplicação da estratégia Shortest Path First estabelece que os lightpaths mais
curtos deverão ser priorizados em relação aos mais longos. Já a estratégia Longest First, determina
21
que os lightpaths mais longos devem ser sujeitos à atribuição de comprimentos de onda em primeiro
lugar.
Uma vez que se ordenem os caminhos, poder-se-á proceder à atribuição de comprimentos de onda
propriamente dita. As três estratégias implementadas na ferramenta elaborada no âmbito desta
dissertação foram as seguintes:
1. First-fit
2. Random;
3. Most Used/Least Used.
Na estratégia First-fit os comprimentos de onda são ordenados, e cada lightpath irá tentar selecionar o
comprimento de onda de menor ordem. Se o de menor ordem não puder ser utilizado, este irá tentará
selecionar o próximo, e assim sucessivamente. Ao se atribuir os comprimentos de onda desta forma,
as ligações existentes usarão, no seu conjunto, um pequeno número de comprimentos de onda,
deixando um maior número de comprimentos de onda disponíveis para serem utilizados por lightpaths
mais longos.
A estratégia de atribuição aleatória de comprimentos de onda (Random), tal como o nome indica, atribui
os comprimentos de onda a cada lightpath de forma aleatória, depois de pesquisar o conjunto de
comprimentos de onda disponíveis para cada lightpath. Geralmente, a estratégia first-fit gera melhores
resultados quando se tem pleno conhecimento do estado atual da rede, como é o caso de tráfego
estático [17]. No entanto, se a atribuição de comprimentos de onda é gerada através de um algoritmo
distribuído com pequeno conhecimento sobre o estado da rede, então a estratégia de atribuição
aleatória poderá obter melhores resultados. Isto pode dar-se se, na utilização do first-fit, vários pedidos
de tráfego tentarem estabelecer um lightpath em simultâneo. Neste caso é mais provável que escolham
o mesmo comprimento de onda, tendo como consequência um maior número de ligações bloqueadas.
Contudo, este caso nunca se daria na utilização da ferramenta desenvolvida nesta dissertação pois o
algoritmo desenvolvido é totalmente sequencial.
Na estratégia most-used, o comprimento de onda atribuído será o mais utilizado em toda a rede. Esta
estratégia visa uma maior reutilização dos comprimentos de onda na rede. Já a estratégia least-used
visa espalhar a carga uniformemente por toda a rede, e nesse sentido, atribui o comprimento de onda
com menor utilização a cada lightpath.
Embora o software de planeamento elaborado nesta dissertação suporte a utilização das três
estratégias de atribuição de comprimentos de onda atrás enunciadas, utiliza-se sempre a estratégia
First-Fit na obtenção dos resultados presentes no Capítulo 5.
22
2.3.3 Agregação de tráfego À medida que a tecnologia WDM vai evoluindo, o fosso entre a capacidade de um canal, que neste
momento chega a alcançar os 400Gb/s em ligações de curtas distâncias (OTU5), e os requisitos de
largura de banda de um pedido tráfego típico vai aumentando.
Se toda a banda de um canal associado a um dado comprimento de onda for dedicada a uma ligação
com um ritmo binário baixo, uma grande parte da capacidade de transmissão é desperdiçada, o que se
torna altamente ineficiente. Para solucionar este problema, é necessário multiplexar (ou agregar) os
fluxos de tráfego de forma eficiente.
Assim, dados os seguintes parâmetros:
• topologia física, em que cada aresta consiste numa ligação física;
• número de transponders em cada nó;
• número máximo de comprimentos de onda suportados em cada fibra;
• capacidade de cada comprimento de onda
• conjunto de pedidos de tráfego com diferentes granularidades;
a agregação do tráfego consiste em estabelecer lightpaths de forma a satisfazer os requisitos de ligação
de forma eficiente.
Os algoritmos de agregação são tipicamente divididos em quatro sub-problemas [18]:
1. Determinação da topologia virtual, que consiste em lightpaths;
2. Encaminhar os lightpaths na topologia física;
3. Fazer atribuição de comprimentos de onda nos lightpaths;
4. Encaminhar os pedidos de tráfego cliente na topologia virtual.
De facto, é possível fazer agregação de tráfego resolvendo simplesmente cada um destes sub-
problemas separadamente. Contudo, embora seja possível atingir uma solução ótima para cada um
deles, isso não garante uma solução ótima global, devido à sua interdependência [18]. Ou seja, uma
solução ótima de para um sub-problema poderá afetar a optimalidade com que outro sub-problema é
resolvido.
Uma abordagem alternativa é resolver os quatro sub-problemas como um todo, o que torna possível
levar em conta todas as restrições, associadas a cada um deles, simultaneamente. Esta última
alternativa permite alcançar melhores resultados, mas sofre de problemas de escalabilidade.
No caso em que o tráfego se considera estático, e caso existam recursos suficientes na rede para
suportar todos os pedidos de tráfego existentes (rede sem bloqueio), o objetivo é minimizar o custo da
23
rede (por exemplo, minimizar o número de comprimentos de onda utilizados). Caso os recursos sejam
insuficientes (rede com bloqueio), o objetivo passará por maximizar o fluxo de tráfego cliente na rede
[14].
Como referido anteriormente, no cenário em que o tráfego é estático, os pedidos de tráfego são
conhecidos todos à partida. Ou seja, o algoritmo de agregação poderá funcionar tendo já todos os
dados de entrada predeterminados. Neste caso, o problema pode ser formulado matematicamente por
um conjunto de restrições ILP [18]. Contudo, um modelo ILP apresenta limitações de escalabilidade, e
por isso não é fácil aplica-lo diretamente a redes de grande dimensão. Em [14], é proposto um modelo
ILP que visa agregar tráfego em redes WDM do tipo mesh, de pequenas dimensões. Os resultados
obtidos são posteriormente utilizados para encontrar algoritmos heurísticos escaláveis, e adequados a
redes de maior dimensão.
Em [18], os autores propõem um método heurístico escalável, o qual designam de IGABAG (Integrated
Grooming Algorithm Based on the Auxiliary Graph), que resolve os quatro sub-problemas enunciados
anteriormente de forma integrada com base num grafo auxiliar. Este permite resolver o problema da
agregação em ambos os cenários, estático e dinâmico.
Note-se que o IGABAG é usado para encaminhar apenas um pedido de cada vez. No cenário estático,
em que se tem, à priori, conhecimento de todos os pedidos de tráfego, ao escolher-se uma seleção
apropriada de pedidos de tráfego, procede-se ao algoritmo IGABAG, sendo que, para pedidos de
tráfego que não possam ser encaminhados, estes sê-lo-ão mais tarde, se possível. Ou seja, o IGABAG
deverá ser usado consecutivamente até que seja possível encaminhar o tráfego correspondente a todos
os pedidos, ou até que se esgotem todos os recursos da rede. No caso de tráfego dinâmico, o objetivo
principal passará por minimizar os recursos da rede utilizados para atender a cada pedido. Como
referido anteriormente, o algoritmo IGABAG pode também ser usado no cenário dinâmico. A única
diferença é que, neste caso, o algoritmo é usado sempre que surge um novo pedido.
A descrição do algoritmo IGABAG, conforme descrito em [18], está presente na Figura 2.10. É de
salientar que este não é o algoritmo de agregação utilizado nesta dissertação. Contudo existem
algumas semelhanças (por exemplo, o estabelecimento e preenchimento da capacidade dos lightpaths
com os sinais cliente, bem como a formação de um grafo de lightpaths), e uma vez que o leitor entenda
o IGABAG será mais fácil perceber como funciona o algoritmo implementado neste trabalho.
IGABAG
Definições e terminologia:
• Determina-se uma rede auxiliar 𝐺𝐺(𝑉𝑉,𝐸𝐸) com base na configuração da rede real.
• A rede real é representada por um grafo 𝐺𝐺0(𝑉𝑉0,𝐸𝐸0), em que 𝑉𝑉0 representa os vértices e 𝐸𝐸0, o conjunto de arestas que a caracterizam.
24
• O grafo auxiliar é composto por 𝑊𝑊 +2 camadas. As camadas 1 até 𝑊𝑊 acomodam as “𝑊𝑊 comprimentos de onda”. A camada 𝑊𝑊 + 1 é chamada “camada de lightpath” e a camada 𝑊𝑊 + 2 é designada “camada de acesso” onde o fluxo de tráfego começa e acaba.
• Cada nó tem dois portos em cada camada, um de entrada e outro de saída.
• 𝑁𝑁𝑖𝑖
𝑙𝑙,𝑝𝑝 refere-se ao porto 𝑝𝑝 na camada 𝑙𝑙 do nó 𝑖𝑖.
• 𝑉𝑉 = { 𝑁𝑁𝑖𝑖𝑙𝑙,𝑝𝑝: 𝑝𝑝 ∈ {0,1}, 1 ≤ 𝑙𝑙 ≤ 𝑊𝑊 + 2,∀ 𝑖𝑖 ∈ 𝑉𝑉0 }
• Cada ligação do grafo auxiliar 𝐺𝐺 tem uma tupla de propriedades 𝑃𝑃𝑃𝑃(𝑐𝑐,𝑤𝑤) associado, onde 𝑐𝑐
se refere à capacidade da ligação, e 𝑤𝑤 refere-se ao seu peso.
Construção do grafo auxiliar:
• Wavelength Bypass Edges – 𝑊𝑊𝑊𝑊𝐸𝐸(𝑖𝑖, 𝑙𝑙): < 𝑁𝑁𝑖𝑖𝑙𝑙,0,𝑁𝑁𝑖𝑖
𝑙𝑙,1 > ∈ 𝐸𝐸, 1 ≤ 𝑙𝑙 ≤ 𝑊𝑊, com capacidade ∞.
• Grooming Edges - 𝐺𝐺𝐺𝐺𝐺𝐺𝐸𝐸(𝑖𝑖): < 𝑁𝑁𝑖𝑖𝑊𝑊+2,0,𝑁𝑁𝑖𝑖
𝑊𝑊+2,1 > ∈ 𝐸𝐸, ∀𝑖𝑖 ∈ 𝑉𝑉0, com capacidade ∞.
• Mux Edges - 𝑀𝑀𝑀𝑀𝑁𝑁𝐸𝐸(𝑖𝑖): < 𝑁𝑁𝑖𝑖𝑊𝑊+2,1,𝑁𝑁𝑖𝑖
𝑊𝑊+1,1 > ∈ 𝐸𝐸, ∀ 𝑖𝑖 ∈ 𝑉𝑉0, com capacidade ∞.
• Deux Edges - D𝑀𝑀𝑁𝑁𝐸𝐸(𝑖𝑖): < 𝑁𝑁𝑖𝑖𝑊𝑊+1,0,𝑁𝑁𝑖𝑖
𝑊𝑊+2,0 > ∈ 𝐸𝐸, ∀ 𝑖𝑖 ∈ 𝑉𝑉0, com capacidade ∞.
• Transmitter Edges - 𝑃𝑃𝑁𝑁𝐸𝐸(𝑖𝑖, 𝑙𝑙) : < 𝑁𝑁𝑖𝑖𝑊𝑊+2,0,𝑁𝑁𝑖𝑖
𝑙𝑙,0 > ∈ 𝐸𝐸, ∀ 𝑖𝑖 ∈ 𝑉𝑉0, 1 ≤ 𝑙𝑙 ≤ 𝑊𝑊, com capacidade ∞.
• Receiver Edges - 𝑅𝑅𝑁𝑁𝐸𝐸(𝑖𝑖, 𝑙𝑙) : < 𝑁𝑁𝑖𝑖𝑙𝑙,0,𝑁𝑁𝑖𝑖
𝑊𝑊+2,0 > ∈ 𝐸𝐸, ∀ 𝑖𝑖 ∈ 𝑉𝑉0, 1 ≤ 𝑙𝑙 ≤ 𝑊𝑊, com capacidade ∞.
• Converter Edges - 𝐶𝐶𝐶𝐶𝐶𝐶𝐸𝐸(𝑖𝑖, 𝑙𝑙1, 𝑙𝑙2): < 𝑁𝑁𝑖𝑖𝑙𝑙1,0,𝑁𝑁𝑖𝑖
𝑙𝑙2,1 > ∈ 𝐸𝐸, ∀ 𝑖𝑖 ∈ 𝑉𝑉0 com capacidade ∞.
• Wavelength-Link Edges - 𝑊𝑊𝐿𝐿𝐸𝐸(𝑖𝑖, 𝑗𝑗, 𝑙𝑙): < 𝑁𝑁𝑖𝑖𝑙𝑙,1,𝑁𝑁𝑖𝑖
𝑙𝑙,0 > ∈ 𝐸𝐸, (𝑖𝑖, 𝑗𝑗) ∈ 𝐸𝐸0, com o comprimento de onda λ𝑙𝑙 não utilizado.
• Lightpath Edges - 𝐿𝐿𝑃𝑃𝐸𝐸(𝑖𝑖, 𝑗𝑗): < 𝑁𝑁𝑖𝑖
𝑊𝑊+1,1,𝑁𝑁𝑖𝑖𝑊𝑊+1,0 > ∈ 𝐸𝐸, e existe um lightpath de 𝑖𝑖 até 𝑗𝑗.
Finalmente, atribuem-se os pesos a cada aresta do grafo auxiliar, com base na política de agregação que se queira aplicar. Algoritmo: Input: Pedido de tráfego 𝐷𝐷(𝑠𝑠,𝑑𝑑,𝑔𝑔,𝐺𝐺) onde 𝑠𝑠 e 𝑑𝑑 são os nós de origem e destino, 𝑔𝑔 designa a granularidade do tráfego (p. ex. OC-12), e 𝐺𝐺 é a quantidade de tráfego em unidades de 𝑔𝑔.
1. Eliminar as arestas com capacidade menor que a banda ocupada por 𝐷𝐷.
2. Encontrar caminho mais curto, 𝑝𝑝, desde o porto de saída da camada de acesso do nó origem, até ao porto de entrada da camada de acesso do nó de destino de 𝐷𝐷. Caso não haja solução, restaura as arestas anteriormente removidas e retorna -1.
3. Se 𝑝𝑝 contém uma ligação 𝑊𝑊𝑊𝑊𝐸𝐸𝑠𝑠, então será necessário ativar um ou mais lightpaths. Um lightpath começa sempre que 𝑝𝑝 viaja através de uma 𝑃𝑃𝑁𝑁𝐸𝐸, passa por uma 𝑊𝑊𝑊𝑊𝐸𝐸, e termina na primeira 𝑅𝑅𝑁𝑁𝐸𝐸.
4. Encaminhar 𝐷𝐷 ao longo dos lightpaths ativos ao longo de 𝑝𝑝. Se a capacidade do caminho,
que é dada pelo mínimo das capacidades dos lightpaths ao longo de 𝑝𝑝, for menor que a quantidade requerida por 𝐷𝐷, então encaminha a maior quantidade de tráfego possível (por exemplo, 𝑛𝑛 unidades de tráfego com granularidade 𝑔𝑔.
25
5. Restaurar arestas anteriormente eliminadas no passo 1.
6. Atualização do grafo auxiliar, 𝐺𝐺, da seguinte forma:
a. Por cada lightpath acabado de ativar, um 𝐿𝐿𝑃𝑃𝐸𝐸 é adicionado desde o porto de saída do nó de origem do lightpath até ao porto de entrada do nó de destino.
b. As 𝑊𝑊𝐿𝐿𝐸𝐸𝑠𝑠 usadas pelos lightpaths (que representam os comprimentos de onda utilizados pelos lightpaths) são removidas.
c. Se não existir nenhum recetor/transmissor disponível no nó 𝑖𝑖, no comprimento de
onda λ𝑙𝑙, então o 𝑃𝑃𝑁𝑁𝐸𝐸/𝑅𝑅𝑁𝑁𝐸𝐸 será removido de 𝐺𝐺, ou seja, o nó não poderá mais receber ou providenciar um lightpath no comprimento de onda λ𝑙𝑙 e apenas poderá ser atravessado por um lightpath.
d. Se não existir nenhuma aresta de conversão de comprimento de onda, 𝐶𝐶𝐶𝐶𝐶𝐶𝐸𝐸, que
possa converter λ𝑙𝑙1 em λ𝑙𝑙2, disponível em 𝑖𝑖, a aresta de conversão 𝐶𝐶𝐶𝐶𝐶𝐶𝐸𝐸(𝑖𝑖, 𝑙𝑙1, 𝑙𝑙2) será removida de 𝐺𝐺.
e. Atualização da tupla de propriedades de cada aresta do grafo auxiliar. Para os
lightpaths que transportem o trafego 𝐷𝐷, as capacidades das 𝐿𝐿𝑃𝑃𝐸𝐸𝑠𝑠 que o transportam sofrem um decréscimo correspondente ao tráfego encaminhado.
7. Se todo o tráfego for acomodado com sucesso, retorna 0, Caso contrário, retorna 𝐺𝐺 − 𝑛𝑛
(correspondente à quantidade de tráfego que não é transportada, em unidades de 𝑔𝑔).
Figura 2.10. Algoritmo de agregação IGABAG (retirado de [18] )
No Anexo D apresenta-se um exemplo adaptado do funcionamento de [18].
Nos últimos anos, o tópico da agregação de tráfego tem recebido muita atenção por parte de diversos
investigadores. Aqui são apresentados alguns artigos, nos quais os autores propõem o uso de uma
versão adaptada de algumas das ferramentas já existentes.
Os autores do artigo [19], reconhecendo que algoritmos genéricos não costumam ser utilizados para
resolver problemas de agregação em redes mesh, propõem um novo GA (Genetic Algorithm) que visa
resolver o problema da agregação em redes mesh transparentes. O algoritmo apresentado combina o
uso clássico de GAs com uma nova heurística que visa suportar custos de otimização para combinar
vários fluxos de tráfego num único lightpath. Neste artigo, os autores afirmam ter conseguido
desenvolver um conjunto de novas ferramentas para investigação, incluindo a codificação de matrizes
com base em posição, operadores genéticos heurísticos e uma função de avaliação de adaptação,
usando um método de clustering. No artigo [20], os autores têm como objetivo resolver o problema de
agregação de tráfego dinâmico em redes WDM mesh, por formularem uma topologia lógica estática
dadas certas quantidades de tráfego previamente estimadas. Posteriormente, é realizado o
encaminhamento do tráfego na topologia lógica previamente estabelecida. Os autores referem a
realização de dois estudos no seu artigo: a minimização dos recursos na topologia física com
dependência na probabilidade de bloqueio do tráfego; e a maximização do tráfego atendido pela rede
(desempenho da agregação), dependendo este último na topologia física e dos recursos (número de
26
comprimentos de onda ou portos em cada nó cliente). Os autores também apresentam formulações de
programação linear inteira e heurísticas para obter soluções para os problemas enunciados e
demonstram que, com base nos resultados obtidos por simulação, o uso de recursos da rede decresce
drasticamente quando se diminui o bloqueio de pedidos de tráfego e que o desempenho da agregação
vai lentamente aumentando à medida que se aumentam os recursos da rede. Também referem que o
número de portos nos nós tem um maior impacto na agregação do que o número de comprimentos de
onda.
2.3.4 Estratégias de planeamento multiperiodo Normalmente o processo de administração de equipamento e recursos na rede é feito sob vários
períodos de tempo devido a limitações em termos de CapEx (Capital Expenditures) e ao crescimento
gradual do tráfego. No tempo de funcionamento da rede podem ocorrer mudanças nos custos de
equipamento, na tecnologia disponível, e no tipo de tráfego a encaminhar na rede. Estas mudanças
podem influenciar o desempenho das arquiteturas inicialmente implementadas. Assim, o
desenvolvimento de abordagens que permitam o planeamento em múltiplos períodos de tempo é vital
no processo de desenvolvimento das redes óticas de transporte [5].
No planeamento multiperiodo é tido em consideração o período de tempo de operação da rede. A rede
é dimensionada de forma a suportar os requisitos de tráfego cliente até ao fim do período de
planeamento. Em cada período, novos serviços de cliente são implementados, preferencialmente em
locais em que os recursos da rede estejam já alocados. Só se procede à implementação de novo
equipamento se os recursos alocados não forem suficientes para atender os serviços. Assim, é
importante decidir qual o cliente que deve reutilizar equipamento instalado e aquele que deve instalar
novo equipamento. Neste sentido, poder-se-ão usar várias estratégias de planeamento multiperiodo. A
maior diferença entre as várias estratégias consiste essencialmente na quantidade de informação que
se consegue prever acerca do tráfego [21]. De facto, neste tipo de análise é de maior importância ter
conhecimento sobre a evolução do tráfego cliente ao longo dos vários períodos de tempo. Contudo,
atualmente o tráfego nas redes de transporte é muito incerto [22]. Esta incerteza pode levar a erros nas
previsões do tráfego cliente e consequentemente à implementação de equipamento insuficiente ou em
demasia. As três estratégias de planeamento multiperiodo abordadas nesta dissertação são as
seguintes:
1. Planeamento sob todos os períodos (All Periods Planning);
2. Planeamento de fim de vida (End-of-Life Planning);
3. Planeamento incremental (Incremental Planning);
No planeamento sob todos os períodos a otimização é feita para todos os períodos ao mesmo tempo,
em apenas um passo. Esta abordagem necessita do conhecimento sobre o tráfego cliente sob todos
os períodos em estudo. A abordagem de fim de vida também necessita de informação sobre o tráfego
em todos os períodos de tempo, contudo, a rede é dimensionada de forma a atender ao tráfego
27
cumulativo existente no último período. A rede é então implementada de forma a que se convirja para
a solução encontrada para o último período. No planeamento incremental, a otimização é realizada em
cada período, sequencialmente. Os parâmetros de entrada deverão ser o tráfego do período sob
planeamento e o estado atual da rede [21].
A Figura 2.11 mostra um esquema das três estratégias multiperiodo para 5 períodos de planeamento,
sendo que marcas a vermelho indicam quando o planeamento é efetuado em cada uma das
abordagens.
Figura 2.11. Abordagens de planeamento multiperiodo (retirado de [5])
28
29
3 Algoritmos para Encaminhamento e Cálculo do
Número Mínimo de Regeneradores Nesta secção serão apresentados alguns algoritmos de encaminhamento utilizados no estabelecimento
de caminhos estáticos para o encaminhamento do tráfego. São também apresentados resultados
relativamente ao número mínimo de regenerações 3R necessárias para cada alternativa de
encaminhamento. De faco, o número de lightpaths que cada pedido de tráfego terá que estabelecer
para que o tráfego possa chegar ao nó destino, deverá ser equivalente ao número de regenerações 3R
necessárias.
3.1 Algoritmos de encaminhamento Antes do processo de agregação, é conveniente utilizar-se algoritmos de encaminhamento com o fim
de se obterem várias rotas candidatas para cada par de nós. Tal como mencionado na secção 2.2.1,
as estratégias de encaminhamento que foram implementadas para estudo nesta dissertação estão no
centram-se no encaminhamento fixo, e fixo e alternado.
Para o encaminhamento fixo, implementou-se simplesmente um algoritmo para a determinação do
caminho mais curto entre pares de nós, que neste caso é o algoritmo de Dijkstra, o qual se encontra
descrito na Figura 3.1.
Algoritmo de Dijkstra
Definições e terminologia:
𝑤𝑤 (𝑀𝑀, 𝐶𝐶) - Custo de uma aresta que liga o nó u ao nó v.
𝑠𝑠 - Nó fonte.
B - Estrutura de dados do tipo árvore balanceada.
S - Conjunto de nós analisados.
𝑑𝑑(𝑀𝑀) Custo do nó 𝑠𝑠 para o nó 𝑀𝑀, e corresponde à soma dos custos das várias arestas
incluídas no caminho do nó 𝑠𝑠 para o nó 𝑀𝑀.
(𝑀𝑀) Nó predecessor a 𝑀𝑀, pertencente ao caminho de 𝑠𝑠 para 𝑀𝑀.
Algoritmo: 1. Inicialização: 2. S = Ø. 3. 𝑑𝑑(𝑠𝑠) = 0, 𝑑𝑑(𝑀𝑀) = ∞ (para ∀ 𝑀𝑀 ≠ 𝑠𝑠), 𝑝𝑝(𝑀𝑀) = 0 (para ∀ 𝑀𝑀). 4. Inserir todos os nós na estrutura B. 5. Ciclo (enquanto B não ficar vazia):
30
6. Seja 𝑀𝑀 o vértice pertencente à ligação com o custo menor; 7. Se 𝑑𝑑(𝑀𝑀) = ∞, sair do ciclo; 8. S = S U { 𝑀𝑀 }, B = B - { 𝑀𝑀 }; 9. Para todo o vértice 𝐶𝐶 adjacente de 𝑀𝑀, fazer: 10. Se 𝑑𝑑(𝐶𝐶) > 𝑑𝑑(𝑀𝑀) + 𝑤𝑤 (𝑀𝑀, 𝐶𝐶), então fica 𝑑𝑑(𝐶𝐶) = 𝑑𝑑(𝑀𝑀) + 𝑤𝑤 (𝑀𝑀, 𝐶𝐶), 𝑝𝑝(𝐶𝐶) = 𝑀𝑀.
Figura 3.1. Algoritmo de Dijkstra
Para a implementação do encaminhamento fixo e alternado, optou-se por uma versão semelhante à do
artigo [23], em que se propõe um algoritmo cujo objetivo genérico é classificar caminhos ótimos, de
acordo com um dado critério de custo. Uma abordagem possível é a classificação de 𝑘𝑘-caminhos mais
curtos, em que 𝑘𝑘 é o número máximo de caminhos possíveis, sem ciclos, que é possível tomar entre 2
pares de nós, segundo alguns critérios. Este algoritmo é descrito na Figura 3.2 conforme [23].
Algoritmo dos 𝒌𝒌 caminhos mais curtos
Definições e terminologia: • Rede 𝐺𝐺(𝑉𝑉,𝐸𝐸) com um conjunto finito de nós: 𝑉𝑉 = {𝐶𝐶1,𝐶𝐶2, … , 𝐶𝐶𝑛𝑛}; e um conjunto finito de
arestas: 𝐸𝐸 = {𝑒𝑒1, 𝑒𝑒2, … , 𝑒𝑒𝑚𝑚} ⊂ 𝑉𝑉 × 𝑉𝑉;
• Cada arco 𝑎𝑎𝑘𝑘 pode ser identificado como (𝐶𝐶𝑖𝑖 , 𝐶𝐶𝑖𝑖), com 𝐶𝐶𝑖𝑖 ≠ 𝐶𝐶𝑖𝑖; • Um caminho de 𝑠𝑠 para 𝐶𝐶 em 𝐺𝐺 é uma sequencia de nós e arestas da forma 𝑝𝑝 =< 𝐶𝐶1′ =
𝑠𝑠, 𝐶𝐶2′ , … , 𝑒𝑒𝑙𝑙−1′ ,𝐶𝐶𝑙𝑙′ = 𝐶𝐶 > com 𝐶𝐶𝑘𝑘′ ∈ 𝐺𝐺, ∀ 𝑘𝑘 ∈ {1, … , 𝑙𝑙} e 𝑒𝑒𝑘𝑘′ = (𝐶𝐶𝑘𝑘′ ,𝐶𝐶𝑘𝑘+1′ ) ∈ 𝐸𝐸 , ∀ 𝑘𝑘 ∈ {1, … , 𝑙𝑙 −1}; Um caminho pode também ser representado apenas pelos nós que o constituem;
• Dados dois nós, 𝑁𝑁 e 𝑦𝑦, de um caminho 𝑝𝑝 ∈ 𝑃𝑃𝑠𝑠𝑠𝑠, 𝑞𝑞 ∈ 𝑃𝑃𝑥𝑥𝑥𝑥 é definido como um subcaminho de 𝑝𝑝 se este coincidir com 𝑝𝑝 desde 𝑁𝑁 até 𝑦𝑦. Este é identificado como 𝑠𝑠𝑀𝑀𝑠𝑠𝑝𝑝(𝑁𝑁,𝑦𝑦);
• A concatenação de dois caminhos, 𝑝𝑝 ∈ 𝑃𝑃𝑖𝑖𝑖𝑖 e 𝑞𝑞 ∈ 𝑃𝑃𝑖𝑖𝑙𝑙, é identificada por 𝑝𝑝 ⋄ 𝑞𝑞; • A função de custo é dada por: 𝑐𝑐 = ∑ 𝑐𝑐𝑖𝑖𝑖𝑖(𝑖𝑖,𝑖𝑖)∈𝑃𝑃 , com 𝑐𝑐𝑖𝑖𝑖𝑖 sendo a distância entre os nós 𝑖𝑖 e 𝑗𝑗. • O algoritmo em causa baseia-se na construção de uma pseudo-árvore, em que cada ramo
representa um caminho distinto. Note-se que, dados 𝑘𝑘 caminhos 𝑞𝑞1,𝑞𝑞2, … , 𝑞𝑞𝑘𝑘, definidos entre os mesmos pares de nós, cada caminho 𝑞𝑞𝑖𝑖 coincide com os anteriores 𝑞𝑞1, … , 𝑞𝑞𝑖𝑖−1, desde 𝑠𝑠 até um outro nó. De entre estes nós, o mais distante de 𝑠𝑠 é identidicado como 𝑑𝑑(𝑞𝑞𝑖𝑖) e é designado nó de desvio (onde um ou mais caminhos divergem). Inicialmente, assume-se 𝑑𝑑(𝑞𝑞1) = 𝑠𝑠.
• 𝑋𝑋 representa o conjunto de caminhos candidatos que são armazenados até que sejam
analisados e eliminados do conjunto.
31
Algoritmo 𝑝𝑝 ← caminho ótimo de 𝑠𝑠 para 𝐶𝐶 em 𝐺𝐺; 𝑑𝑑(𝑞𝑞) ≔ 𝑠𝑠;𝑋𝑋 ← {𝑝𝑝};𝑘𝑘 ≔ 0; While (𝑋𝑋 ≠ ∅ and 𝑘𝑘 < 𝐾𝐾) Do // 𝐾𝐾 é escolhido pelo utilizador, à priori
𝑘𝑘 ≔ 𝑘𝑘 + 1 𝑝𝑝𝑘𝑘 ≔ < 𝐶𝐶1𝑘𝑘, … , 𝐶𝐶𝑙𝑙𝑘𝑘
𝑘𝑘 > // caminho ótimo sem ciclos 𝑋𝑋 ≔ 𝑋𝑋 − {𝑝𝑝𝑘𝑘} Remove nodes of loopless path 𝑠𝑠𝑀𝑀𝑠𝑠𝑝𝑝𝑘𝑘(𝑠𝑠, 𝐶𝐶𝑙𝑙𝑘𝑘
𝑘𝑘 ) from the network Remove links (𝑑𝑑(𝑝𝑝𝑘𝑘), 𝑖𝑖), 𝑖𝑖 ∈ 𝑉𝑉, of 𝑝𝑝1, … ,𝑝𝑝𝑘𝑘−1 from the network For (𝐶𝐶𝑖𝑖 ∈ �𝑑𝑑�𝑝𝑝𝑘𝑘 , … , 𝐶𝐶𝑙𝑙𝑘𝑘−1
𝑘𝑘 �� Do Remove link (𝐶𝐶𝑖𝑖𝑘𝑘 ,𝐶𝐶𝑖𝑖+1𝑘𝑘 ), from the network 𝑞𝑞 ← 𝑜𝑜𝑝𝑝𝐶𝐶𝑖𝑖𝐺𝐺𝑎𝑎𝑙𝑙 𝑙𝑙𝑜𝑜𝑜𝑜𝑝𝑝𝑙𝑙𝑒𝑒𝑠𝑠𝑠𝑠 𝑝𝑝𝑎𝑎𝐶𝐶ℎ 𝑓𝑓𝐺𝐺𝑜𝑜𝐺𝐺 𝐶𝐶𝑖𝑖𝑘𝑘 𝐶𝐶𝑜𝑜 𝑠𝑠 𝑝𝑝 ← 𝑠𝑠𝑀𝑀𝑠𝑠𝑝𝑝𝑘𝑘�𝑠𝑠, 𝐶𝐶𝑖𝑖𝑘𝑘� ⋄ 𝑞𝑞;𝑑𝑑(𝑞𝑞) ≔ 𝐶𝐶𝑖𝑖𝑘𝑘;𝑋𝑋 ≔ 𝑋𝑋 ∪ {𝑝𝑝} Remove nodes 𝐶𝐶𝑖𝑖𝑘𝑘 from the network
EndFor Restore deleted nodes and links in the original network
EndWhile Figura 3.2. Algoritmo dos 𝑘𝑘 caminhos mais curtos (adaptado de [23])
Para a consulta de um exemplo de funcionamento do algoritmo dos 𝑘𝑘 caminhos mais curtos, o leitor é
remetido ao Anexo C.
3.2 Cálculo do número mínimo de regenerações Numa rede opaca, as conexões são terminadas eletronicamente em todos os nós intermediários. Um
fator importante a levar em conta é que o equipamento exigível para cada terminação elétrica é um
componente essencial no custo do caminho. Devido aos elevados débitos binários que se conseguem
atingir na componente ótica, a implementação de componentes eletrónicos que sejam capazes de
operar nesses débitos é cara e de difícil construção. Além disso, uma vez que se podem utilizar dezenas
de comprimentos de onda, e para cada comprimento de onda é necessário um regenerador, é
necessária uma grande quantidade de equipamento para cada fibra. Assim, em redes opacas, a
procura de caminhos de menor número de saltos desde a origem até ao destino, é geralmente a
estratégia utilizada e a que gera o menor número de regenerações na rede. No entanto, em redes
translucidas a necessidade de regeneração é determinada pelo alcance máximo de transmissão do
sinal na fibra [15]. A título de exemplo, uma rede com um alcance máximo de sinal de 1800 km significa
que o sinal não pode viajar mais de 1800 km, a menos que seja regenerado. O alcance do sinal
dependerá das tecnologias subjacentes ao processo de transmissão, tais como a modulação do sinal,
as propriedades dos elementos da rede, bem como as características das fibras óticas instaladas.
Neste último cenário, é mais favorável uma estratégia que favoreça a procura de caminhos com
menores distâncias.
É bom clarificar que os amplificadores óticos não são regeneradores. A função dos amplificadores é
amplificar a potência do sinal, para compensar perdas de potência introduzidas pela fibra e outros
fatores. Já os regeneradores têm como função a “limpeza” do sinal e fazem isso por o re-amplificar,
reformatar e reajustar. Daí a designação de regeneração “3R”.
32
Na Figura 3.3 está representada de forma sucinta a arquitetura de um nó em que ocorre regeneração
3R. Após serem desmultiplexados, alguns dos sinais são sujeitos a regeneração, e como tal, são
encaminhados pelo ROADM até aos respetivos regeneradores. Após a regeneração, o ROADM
encaminha-os até aos respetivos portos para serem multiplexados e transmitidos novamente através
da fibra de saída.
Figura 3.3. Regeneração de sinais óticos num nó da rede (extraída de [24])
No estudo feito no âmbito desta dissertação, optou-se por implementar os algoritmos de
encaminhamento com base num dos seguintes critérios de custo:
1. Número mínimo de saltos;
2. Distância mínima;
3. Degradação mínima do sinal ótico.
O objetivo é conseguir resultados eficientes em termos de regeneração 3R para redes com diferentes
características. A utilização da primeira estratégia ocupa-se simplesmente de procurar os caminhos
com o menor número de saltos. A segunda estratégia tem como objetivo procurar os caminhos com
menores distâncias. A terceira foca-se em encontrar os caminhos com menor degradação de sinal.
Neste último caso, o custo associado a cada ligação consiste na soma da distância entre nós
intermédios (em km) e da penalidade de transmissão por salto do sinal (em km). De facto, esta última
estratégia trata-se de um meio termo entre a primeira e a segunda, uma vez que quantos mais saltos
tiver o caminho, maior o número de vezes a que o sinal está sujeito à penalidade de transmissão. Por
outro lado, à degradação do sinal por salto é somada a distância enquanto custo, em cada aresta.
Assim, o terceiro critério de custo foca-se em encontrar caminhos curtos, mas ao mesmo tempo,
minimizando o número de saltos. É claro que os resultados obtidos da aplicação de cada um dos
critérios apresentados depende fortemente da topologia física da rede em consideração.
33
Figura 3.4. Obtenção de caminhos de menor custo para cada um dos critérios numa rede
exemplo
A Figura 3.4 demonstra a obtenção dos caminhos de menor custo para cada um dos critérios
implementados. A aplicação do critério “Número mínimo de saltos” resulta na obtenção do caminho a
amarelo, o qual tem visivelmente o menor número de saltos desde a origem 𝑠𝑠 até ao destino 𝐶𝐶. A
aplicação do critério “Degradação mínima de sinal” resulta na obtenção do caminho a azul. Neste caso,
o custo do caminho é dado por (70+70+50) km + (8 km × 3 saltos) que dá um total de 214 km (enquanto
que o caminho verde tem custo de 218 km e o a amarelo, de 246 km). Finalmente, a aplicação do
critério “Distância mínima” resulta no caminho a verde, que é o de menor distância dos 3 possíveis (190
km).
Uma vez calculados os caminhos de menor custo através do algoritmo dos 𝑘𝑘 caminhos mais curtos, é
necessário determinar quais são os requisitos de regeneração entre cada par de nós. A Figura 3.5
explica o processo de validação dos caminhos em termos dos requisitos de regeneração, bem como o
cálculo do número mínimo de regeneradores necessários.
Algoritmo para o calculo do número mínimo de regeneradores
Definições e terminologia: • 𝑠𝑠𝑑𝑑 Par origem, 𝑠𝑠 ,e destino, 𝑑𝑑, com 𝑠𝑠,𝑑𝑑 𝜖𝜖 𝑉𝑉 • 𝑖𝑖𝑗𝑗 Ligação física 𝑒𝑒𝑖𝑖𝑖𝑖 ∈ 𝐸𝐸 • 𝑘𝑘 k-ésimo caminho de menor custo entre 𝑠𝑠 e 𝑑𝑑 • 𝑓𝑓𝑖𝑖𝑠𝑠𝑒𝑒𝐺𝐺_𝐺𝐺𝑒𝑒𝑎𝑎𝑐𝑐ℎ Alcance de transmissão máximo do sinal até necessitar de regeneração • 𝑑𝑑𝑖𝑖𝑖𝑖 Comprimento da ligação física 𝑒𝑒𝑖𝑖𝑖𝑖 • 𝑑𝑑𝑙𝑙𝑙𝑙𝑠𝑠𝑠𝑠_3𝑅𝑅 Comprimento do caminho desde a última regeneração • 𝐺𝐺𝑖𝑖𝑛𝑛𝑖𝑖𝐸𝐸𝑖𝑖𝑠𝑠𝑠𝑠,𝑘𝑘 Número mínimo de regenerações 3R necessárias no k-ésimo caminho mais
34
curto entre 𝑠𝑠 e 𝑑𝑑. • 𝑝𝑝ℎ𝐺𝐺𝑝𝑝 Penalidade de transmissão por salto Algoritmo: 1. 𝑑𝑑𝑙𝑙𝑙𝑙𝑠𝑠𝑠𝑠_3𝑅𝑅:= 0 2. 𝐺𝐺𝑖𝑖𝑛𝑛𝑖𝑖𝐸𝐸𝑖𝑖𝑠𝑠𝑠𝑠,𝑘𝑘 := 0 3. Determina 𝑘𝑘 caminhos alternativos entre 𝑠𝑠 e 𝑑𝑑 4. Ciclo - Para cada par 𝑠𝑠𝑑𝑑 5. Ciclo - Para cada caminho determinado entre 𝒔𝒔 e 𝒅𝒅 6. Ciclo - Para cada ligação física 𝒆𝒆𝒊𝒊𝒊𝒊 do caminho 7. Se 𝑑𝑑𝑖𝑖𝑖𝑖 + 𝑝𝑝ℎ𝐺𝐺𝑝𝑝 > 𝑓𝑓𝑖𝑖𝑠𝑠𝑒𝑒𝐺𝐺_𝐺𝐺𝑒𝑒𝑎𝑎𝑐𝑐ℎ 8. Caminho bloqueado e volta a 5 Caso contrário 9. Se 𝑑𝑑𝑙𝑙𝑙𝑙𝑠𝑠𝑠𝑠_3𝑅𝑅 + 𝑑𝑑𝑖𝑖𝑖𝑖 > 𝑓𝑓𝑖𝑖𝑠𝑠𝑒𝑒𝐺𝐺_𝐺𝐺𝑒𝑒𝑎𝑎𝑐𝑐ℎ 10. 𝐺𝐺𝑖𝑖𝑛𝑛𝑖𝑖𝐸𝐸𝑖𝑖𝑠𝑠𝑠𝑠,𝑘𝑘 = 𝐺𝐺𝑖𝑖𝑛𝑛𝑖𝑖𝐸𝐸𝑖𝑖𝑠𝑠𝑠𝑠,𝑘𝑘 + 1 e 𝑑𝑑𝑙𝑙𝑙𝑙𝑠𝑠_3𝑅𝑅 = 0 Caso contrário 11. 𝑑𝑑𝑙𝑙𝑙𝑙𝑠𝑠𝑠𝑠_3𝑅𝑅 = 𝑑𝑑𝑙𝑙𝑙𝑙𝑠𝑠𝑠𝑠_3𝑅𝑅 + 𝑑𝑑𝑖𝑖𝑖𝑖 + 𝑝𝑝ℎ𝐺𝐺𝑝𝑝
Figura 3.5. Algoritmo para o calculo do número mínimo de regeneradores necessário para cada conjunto de caminhos entre pares de nós.
Por cada caminho, calcula-se o número mínimo de regeneradores com base na distância (𝑑𝑑𝑖𝑖𝑖𝑖) desde
o nó inicial do caminho, nó a nó, até ao nó destino e na penalidade de transmissão do sinal por cada
salto (𝑝𝑝ℎ𝐺𝐺𝑝𝑝). No final do algoritmo, o número mínimo de regeneradores calculado (𝐺𝐺𝑖𝑖𝑛𝑛𝑖𝑖𝐸𝐸𝑖𝑖_3𝑅𝑅) é
atribuído a um campo da estrutura de dados dos caminhos entre cada par origem destino da rede.
Os resultados obtidos resultantes da aplicação deste algoritmo serão uteis no processo de agregação
para que se tenha um conhecimento antecipado do número mínimo de regeneradores necessários
entre cada par de nós. Assim, quando chega um pedido de tráfego para ser mapeado na rede, sabe-
se antecipadamente qual o caminho que exige menor regeneração para o estabelecimento de canais
óticos. Salienta-se que o algoritmo descrito na Figura 3.5 apenas calcula o número mínimo de
regeneradores para cada par de nós origem destino. O algoritmo que se encarrega do processo de
colocação dos regeneradores durante a agregação do tráfego não será alvo de estudo nesta
35
dissertação, apesar desta funcionalidade ter sido implementada e ser executada na produção dos
resultados do mapeamento do tráfego.
3.3 Resultados e conclusões Para um estudo comparativo dos critérios de custo implementados em termos de requisitos de
regeneração 3R, foram feitas algumas simulações usando o programa implementado em MatLab e
recolhidos os respetivos resultados. Achou-se também de interesse a comparação da utilização dos
critérios de custo em termos de número de altos. A análise do número médio de saltos para cada 𝑘𝑘-
caminho encontrado ajuda a perceber o funcionamento do algoritmo para cada um dos critérios de
custo. Espera-se que o primeiro critério obtenha, média, um menor número de saltos, que o segundo
critério obtenha o maior número de saltos e que o terceiro obtenha resultados que se encontrem, em
geral, entre os dois anteriores.
Parâmetros da Simulação:
Redes COST239; NSFNET e UBN (Anexo A);
Variação do alcance máximo do sistema:
o COST239: 1100 km, 1500 km;
o NSFNET: 3000 km, 3500 km;
o UBN: 3000 km, 3500 km.
Variação do número máximo de caminhos alternativos com 1<𝑘𝑘<10;
Penalidade de transmissão por salto: 80 km.
Escolheram-se estes alcances tendo em conta que o programa apenas aceita redes cujo alcance
máximo do sistema mais a penalidade de transmissão por salto tem que ser maior do que cada uma
das ligações físicas da rede. No caso da rede COST239, o alcance máximo do sistema considerou-se
menor para impor a existência de regeneração. Caso se considerasse um alcance máximo de 3000 km
no caso da COST239, então não seria necessária qualquer regeneração 3R.
Figura 3.6. Número médio de saltos de cada k-caminho alternativo - Rede COST239
1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
CAMINHO K
NÚ
MER
O M
ÉDIO
DE
SALT
OS Número de Saltos Distância Degradação do Sinal
36
A determinação do número de saltos para cada 𝑘𝑘-caminho, depende apenas da topologia física da rede
e da penalidade de transmissão por salto, e não do alcance de transmissão de sinal. Portanto, esta
simulação executou-se apenas uma vez para cada uma das redes, e para cada um dos critérios de
custo, com uma penalidade de transmissão por salto de 80 km (para todas as redes).
Figura 3.7. Número médio de saltos de cada k-caminho - Rede NSFNET
Figura 3.8. Número médio de saltos de cada k-caminho alternativo – Rede UBN
A partir da análise das figuras, percebe-se que a execução do algoritmo para determinação de
caminhos alternativos, independentemente do critério de custo utilizado, tende a encontrar caminhos
com cada vez maior número de saltos, à medida que 𝑘𝑘 aumenta, o que é natural, pois tendencialmente
quanto maior a distância do caminho encontrado, maior o número de saltos. Embora excepcionalmente
possa não ser esse o caso, em média, é isso que se reflete nos gráficos apresentados.
Confirma-se também que o critério de custo que leva em conta a penalidade de transmissão por salto
tende a dar mais prioridade aos caminhos com menor número de saltos do que o critério de custo que
apensas tem em conta a distância. Os gráficos referentes à rede COST239 e UBN mostram que, para
cada 𝑘𝑘, o número médio de saltos obtidos pelo terceiro critério de custo é sempre inferior ou igual ao
obtido para o segundo critério de custo. No caso da rede NSFNET, percebe-se que, inicialmente, o
número de saltos obtidos para o segundo critério é menor. Contudo, a partir de 𝑘𝑘=7, existem alguns
casos para os quais o número médio de saltos obtidos com o terceiro critério ultrapassa os do segundo
critério. Isto resulta do facto do segundo critério “dar mais relevo” aos caminhos que tenham menor
número de saltos, relativamente ao terceiro, dando-lhes prioridade. Ao deixar para último os que têm
1 2 3 4 5 6 7 8 9 100
2
4
6
8
CAMINHO K
NÚ
MER
O M
ÉDIO
DE
SALT
OS
Número de Saltos Distância Degradação do Sinal
1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
6
CAMINHO K
NÚ
MER
O M
ÉDIO
DE
SALT
OS
Número de Saltos Distância Degradação do Sinal
37
um maior número de saltos, obtém-se uma média considerável a partir de um certo 𝑘𝑘, e que chega a
ultrapassar o segundo critério.
Os resultados obtidos considerando o número mínimo de regeneradores estão representados nos
gráficos das Figuras 3.9 a 3.14. Os resultados mostram que, como seria de esperar, para alcances
máximos de transmissão maiores, é necessário menos regeneração. Fazendo uma comparação entre
a utilização dos três critérios de custo, percebe-se que o que tem pior desempenho a nível de
regeneração é o que leva em conta o número de saltos dos caminhos, apesar dessa tendência se
desvanecer à medida que se vão encontrando mais caminhos alternativos pelo facto de que se vão
encontrando alguns caminhos com menor distância do que os que foram encontrados anteriormente.
Como estamos a considerar redes translucidas e a penalidade de transmissão por salto é relativamente
baixa face à distância entre os nós, este último parâmetro não tem grande relevância nos resultados, e
uma menor distância traduz-se em geral em menos regenerações 3R.
Dos gráficos, também se conclui que não existe diferença significativa em termos de regeneração entre
a utilização do segundo e terceiro critérios de custo. Essa diferença é pouco significativa porque uma
penalidade de 80 km não é suficiente para que os caminhos encontrados pelo segundo critério sejam
muito diferentes dos que são encontrados pelo terceiro. Nos resultados obtidos, apenas se verifica
diferença quando se considera uma penalidade de transmissão por salto de 120 km (o que é muito
exagerado, e apenas foi considerado para fins de comparação), e a diferença passa por necessitar
apenas de mais um regenerador (consultar a Figura 3.9 para 𝑘𝑘 = 1 e a Figura 3.13 para 𝑘𝑘 = 2, 3 e 4).
No contexto em que se consideram redes translucidas, de facto, a melhor solução é optar por um critério
que leve em conta a distância entre nós extremos. É claro que, em redes opacas, em que o sinal tem
que passar pelo domínio elétrico em cada salto, faz mais sentido usar outros critérios.
Figura 3.9. Número mínimo de regeneradores para um alcance máximo do sistema de 1100 km -
Rede COST239
É também de salientar que, apesar de terem sido feitas simulações para até 10 caminhos alternativos,
os resultados mostram que o número mínimo de regenerações tende a manter-se a partir de 𝑘𝑘=5,
independentemente do critério de custo utilizado.
0
5
10
15
20
25
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
80 km 120 km
NÚ
MER
O M
ÍNIM
O D
E RE
GEN
ERAÇ
ÕES
3R
DEGRADAÇÃO DO SINAL POR SALTO
Número de Saltos Distância Degradação de Sinal
38
Figura 3.10. Número mínimo de regeneradores para um alcance máximo do sistema de 1500 km -
Rede COST239
Figura 3.11. Número mínimo de regeneradores para um alcance máximo do sistema de 3000 km -
Rede NSFNET
Figura 3.12. Número mínimo de regeneradores para um alcance máximo do sistema de 3500 km -
Rede NSFNET
0
2
4
6
8
10
12
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
80 km 120 km
NÚ
MER
O M
ÍNIM
O D
E RE
GEN
ERAÇ
ÕES
3R
DEGRADAÇÃO DO SINAL POR SALTO
Número de Saltos Distância Degradação de Sinal
0
10
20
30
40
50
60
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
80 km 120 km
NÚ
MER
O M
ÍNIM
O D
E RE
GEN
ERAÇ
ÕES
3R
DEGRADAÇÃO DO SINAL POR SALTO
Número de Saltos Distância Degradação de Sinal
05
10152025303540
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
80 km 120 km
NÚ
MER
O M
ÍNIM
O D
E RE
GEN
ERAÇ
ÕES
3R
DEGRADAÇÃO DO SINAL POR SALTO
Número de Saltos Distância Degradação de Sinal
39
Figura 3.13. Número mínimo de regeneradores para um alcance máximo do sistema de 3000 km - Rede
UBN
Figura 3.14. Número mínimo de regeneradores para um alcance máximo do sistema de 3500 km - Rede
UBN
0
50
100
150
200
250
300
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
80 km 120 km
NÚ
MER
O M
ÍNIM
O D
E RE
GEN
ERAÇ
ÕES
3R
DEGRADAÇÃO DO SINAL POR SALTO
Número de Saltos Distância Degradação de Sinal
020406080
100120140160
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
80 km 120 km
NÚ
MER
O M
ÍNIM
O D
E RE
GEN
ERAÇ
ÕES
3R
DEGRADAÇÃO DO SINAL POR SALTO
Número de Saltos Distância Degradação de Sinal´
40
41
4 Descrição do Simulador de Redes OTN Nesta secção descreve-se a ferramenta implementada em MatLab que foi utilizada para recolher os
resultados presentes no Capítulo 5. Começa-se por introduzir o módulo de geração de recursos da
rede, bem como o de geração de tráfego cliente, o qual gera pedidos de tráfego que deverão ser
mapeados na rede. Posteriormente, é descrito o módulo de mapeamento do tráfego, cuja função é
agregar o tráfego, ou então mapeia-lo diretamente na rede, mediante o débito dos pedidos que forem
gerados no módulo de geração de tráfego. Neste sentido, são apresentados esquemas e fluxogramas
que têm como objetivo apresentar o funcionamento da ferramenta de uma forma mais elucidativa.
Relembra-se que a ferramenta tem como objetivo gerar tráfego estático ou dinâmico (segundo alguns
padrões probabilísticos tanto nível dos intervalos de chegada de cada pedido de tráfego, como ao nível
da sua duração). A Figura 4.1 ilustra o processo de criação dos pedidos de tráfego, evidenciando com
o auxilio de um diagrama temporal os intervalos entre tempos de chegada e a sua duração ao serem
encaminhados na rede de destino. No módulo de geração de pedidos de tráfego são definidos os
respetivos nós de origem e destino para cada pedido de tráfego. Cada um é caracterizado por uma
duração e um débito que terá que ser satisfeito pela rede à qual se destina. Assim, podemos dizer que
o ficheiro resultante do módulo de geração de tráfego representa uma matriz de tráfego, dinâmica ou
estática, que irá ser recebida por um outro programa, também ele implementado em MatLab, que se
encarregará de mapear o tráfego na rede destino.
4.1 Modulo de geração de recursos da rede Foi implementada em MatLab uma interface de utilizador que, ao receber como input uma matriz
representativa da topologia física de uma rede, visa tornar possível gerá-la com determinados recursos.
Para isso foi criada uma GUI (Graphical User Interface) com vários campos que o utilizador deve
preencher, de acordo com o cenário pretendido (ver Figura 4.2). Foram implementadas opções como:
• Número de comprimentos de onda disponíveis;
• Débito de linha (capacidade de cada comprimento de onda);
• Alcance máximo de transmissão;
• Percentagem de redução do alcance do sinal por cada salto;
• Opção de escolher, ou não, o mesmo rácio de adição/extração para todos os nós;
• Estratégia de colocação dos transponders;
• Tipo de arquitetura dos ROADMs.
No fim de preenchidos os campos da GUI, é gerado um ficheiro NetInfo_NetworkName.txt que contém
a informação da rede bem como a caracterização do bloqueio e uso das interfaces em cada nó (Ver
Figura 4.3).
42
No ficheiro NetInfo_NetworkName.txt, sob o título “Line Interface usage and blocking characterization
– Node 𝑛𝑛” onde 𝑛𝑛 designa o número do nó, encontra-se a caracterização do bloqueio e o uso de cada
interface através de uma matriz tridimensional, para cada nó. Por cada nó 𝑛𝑛 estão representados 𝑝𝑝
portos de adição/extração (dependendo da estratégia de colocação dos transponders). Cada coluna 𝑤𝑤
do porto 𝑝𝑝 representa um comprimento de onda, e cada linha 𝑑𝑑 representa uma direção de transmissão
no presente nó. Se a entrada 𝑑𝑑𝑤𝑤 da matriz do porto 𝑝𝑝 tem o número “1”, significa que este porto, que
opera no comprimento de onda 𝑤𝑤 , e que transmite na direção 𝑑𝑑, está disponível para transmissão.
Caso o número seja “0”, o porto em questão considera-se bloqueado e indisponível para transmissão.
As configurações possíveis dependem obviamente do tipo de arquitetura escolhida para os elementos
da rede. Na Figura 4.3 (à direita) é demonstrada a matriz para 7 portos do nó 1, que se caracteriza por
uma arquitetura colorless. Como se pode constatar, em cada um dos portos, existe uma linha (ou
direção de transmissão) com todas as entradas a “1”. Estando as restantes, totalmente a “0”. Isso
significa que, para cada porto, o elemento da rede pode transmitir em todos os comprimentos de onda,
mas apenas segundo uma dada direção.
Figura 4.1. Tempos entre pedidos de tráfego e a sua duração.
43
Figura 4.2. GUI para geração de recursos da rede
Figura 4.3. Ficheiro NetInfo_NetworkName
44
4.2 Modulo de geração de tráfego A implementação de um gerador de tráfego é fundamental para possibilitar o planeamento da rede para
vários cenários possíveis. Neste módulo o utilizador tem a opção de escolher gerar tráfego estático ou
dinâmico, tal como se apresenta na Figura 4.4.
Figura 4.4. Interface que permite ao utilizador
escolher entre tráfego estático e dinâmico
Caso o utilizador escolha gerar tráfego estático, aparecer-lhe-á a interface presente na Figura 4.5.
Nesta GUI, permite-se escolher uma de três estratégias de planeamento multiperiodo. Existe a opção
de planeamento em todos os períodos (All Periods Planning), planeamento incremental (Incremental
Planning), ou planeamento de fim de vida (End of Life Planning). Ao escolher qual a estratégia de
planeamento que se pretende, dever-se-á escolher o número de períodos que se pretende planear.
Finalmente, o utilizador poderá escolher a quantidade de tráfego que pretende gerar para cada um dos
sinais ODU disponíveis.
Figura 4.5. Interface que permite ao utilizador escolher os parâmetros
do tráfego estático
Caso o utilizador escolha gerar tráfego dinâmico, este terá acesso a outra GUI, a qual está representada
na Figura 4.6. Em cada um dos campos o utilizador deverá colocar as características do tráfego que
pretende gerar. Entre elas estão:
45
• Os tipos de sinais gerados (ODU0, ODU1, …, ODU5);
• O rácio, sob o tráfego total gerado, que cada tipo de sinal ocupa;
• Distribuição estatística representativa dos tempos entre chegadas dos pedidos de tráfego;
• Distribuição estatística representativa dos tempos de duração dos pedidos de tráfego;
• Número de pedidos a gerar;
• Número de simulações (traffic traces) que se pretende fazer.
Na maioria dos casos, o número de pedidos de tráfego bem como as suas características (tempos de
chegada, duração, débito, etc.) são imprevisíveis [22], daí serem disponibilizadas várias distribuições
estatísticas, cujo objetivo é descrever tanto os tempos entre chegadas, como a duração dos pedidos.
Para simular a variabilidade dos tempos de intervalo entre as “chegadas” de cada pedido, foram
implementadas várias distribuições estatísticas (ver Anexo D).
4.3 Módulo de mapeamento e agregação do tráfego Ao serem gerados todos os pedidos de tráfego de acordo com as especificações pretendidas, é
formado um ficheiro com as características do tráfego com o nome TrafficTrace_NetworkName.txt (ver
Figura 4.7).
Figura 4.6. Interface do gerador de tráfego
46
Uma vez geradas as características da rede escolhida, bem como os pedidos de tráfego, estes terão
que ser encaminhados na rede para que sejam transportados até ao seu destino. Esse processo é
tratado no módulo de mapeamento do tráfego. O diagrama da Figura 4.8 demonstra o seu
funcionamento por meio de um fluxograma.
Após a utilização do modulo de geração dos recursos da rede e de tráfego cliente são gerados os
ficheiros NetInfo_NetworkName.txt e TrafficTrace_NetworkName_SimNumber.txt, sendo que
NetworkName refere-se ao nome da rede e SimNumber ao número da simulação a ser executada.
O simulador começa por ler os ficheiros NetworkName.txt e NetInfo.txt, formando uma estrutura de
dados relativa às características da rede. Posteriormente, a rede é validada, ou seja, certifica-se de que
nenhuma OMS tenha uma distância que ultrapasse o alcance máximo da fibra (incluído para o efeito a
distância correspondente à penalidade de transmissão por salto). Se tal não acontecesse, poderiam
haver pedidos de tráfego bloqueados, pois o respetivo tráfego não poderia chegar ao seu destino (além
disso, nesta dissertação admite-se que apenas se faz regeneração nos nós da rede). Após a validação
da rede, o utilizador deve introduzir os parâmetros e critérios referentes ao encaminhamento,
regeneração, e agregação do tráfego.
O passo seguinte consiste na determinação dos caminhos que no processo de mapeamento do tráfego
serão candidatos a serem utilizados para o estabelecimento de lightpaths. Após o cálculo dos caminhos
são geradas estatísticas sobre o encaminhamento e um ficheiro .txt com a discriminação de todos os
caminhos determinados. A fase seguinte consiste na ordenação dos pedidos de tráfego e no seu
mapeamento e agregação. A ordenação do tráfego é efetuada simplesmente por dar prioridade aos
pedidos de tráfego de maior débito, deixando os ODUs de menor ordem para serem mapeados por
Figura 4.7. Ficheiro TrafficTrace_NetworkName.txt
47
último. É claro que a ordenação do tráfego apenas tem lugar no caso em que estamos na presença de
tráfego estático, caso esse em que se tem conhecimento de todos os pedidos de forma antecipada. A
ordenação no caso de tráfego dinâmico não pode ocorrer, uma vez que os pedidos chegam à rede de
forma completamente imprevisível. Após esta fase, o tráfego poderá ser agregado, caso o débito dos
pedidos de tráfego seja menor que a capacidade dos lightpaths, ou poderá ser mapeado diretamente
na rede, caso o débito dos pedidos seja equivalente à capacidade dos lightpaths. Para uma descrição
mais detalhada sobre estes dois processos o leitor é remetido para o cap.5, onde se abordam o
mapeamento direto e a agregação do tráfego, conforme a implementados no âmbito desta dissertação.
Figura 4.8. Diagrama de funcionamento do programa de mapeamento e agregação do
tráfego
48
4.4 Mapeamento em cenário multiperiodo
A extensão do programa existente para suportar planeamento multiperiodo do tráfego cliente exigiu que
se procedesse à formação de diferentes divisões de ficheiros de tráfego, mediante a estratégia de
planeamento multiperiodo que se queira utilizar. A Figura 4.9 mostra o conteúdo destes ficheiros. Neles
é especificado o período em que cada pedido de tráfego chega à rede para ser encaminhado, bem
como a sua duração. Esta adaptação fez-se no módulo de geração de tráfego. Além disso, adaptou-se
o módulo de mapeamento e agregação de forma a possibilitar o mapeamento do tráfego em períodos
discretos de tempo.
Figura 4.9 - Ficheiro de tráfego estático para planeamento multiperiodo
Figura 4.10 - Divisão dos ficheiros e execuções do programa de mapeamento e agregação - Planeamento de
Todos os Períodos
A Figura 4.10 ilustra a forma como os ficheiros de tráfego são gerados para a estratégia de planeamento
de todos os períodos no caso em que se pretende planear cinco períodos. Como referido na secção
49
2.3.4, o planeamento de todos os períodos tem como objetivo otimizar o planeamento para todos os
períodos em estudo. Assim, para este caso, são gerados cinco ficheiros, cada um contendo o tráfego
desde o período inicial até cada um dos outros períodos. Cada um destes ficheiros corresponde a uma
execução do programa de mapeamento e agregação do tráfego. No fim de cada execução, são
recolhidos os respetivos resultados.
Figura 4.11 - Divisão dos ficheiros e execuções do programa de mapeamento e agregação - Planeamento
Incremental
A divisão de ficheiros para a execução da estratégia de planeamento incremental está ilustrada na
Figura 4.11. Neste caso, são produzidos cinco ficheiros, mas cada um contendo tráfego referido a cada
um dos períodos individualmente. Cada execução do programa corresponde ao planeamento do
tráfego existente apenas nesses períodos individuais.
Figura 4.12 - Divisão dos ficheiros e execuções do programa de mapeamento e agregação - Planeamento
de Fim de Vida
Por fim, para o caso em que se pretende executar o planeamento de fim de vida, não é necessária a
divisão do tráfego em vários ficheiros. Como mostra a Figura 4.12, para este caso é apenas necessário
gerar um ficheiro com todo o tráfego desde o período inicial até ao período final. No caso em que se
pretende planear cinco períodos, o ficheiro contém o tráfego desde o período 1, até ao período 5. Assim
sendo, é necessária apenas uma execução do programa de mapeamento e agregação de tráfego. Para
50
efeitos de comparação com as estratégias anteriores, a recolha de resultados ocorre em fases
intermédias da execução.
51
5 Mapeamento do Tráfego Cliente – Mapeamento Direto
e Agregação Neste capitulo abordar-se-ão os processos de mapeamento direto e de agregação do tráfego. Além
disso, são apresentadas algumas estratégias de seleção de lightpaths que o utilizador poderá utilizar
no processo de agregação.
Na ferramenta implementada no âmbito desta dissertação admite-se que os pedidos de tráfego de
tráfego cliente possuem um débito igual ou inferior ao débito suportado pela fibra. No caso em que o
pedido de tráfego tem um débito inferior, os ODUs são agregados de forma a preencher a capacidade
da fibra de maneira mais eficiente. Optou-se por se implementar multiplexagem flexível, ou seja, é
possível agregar qualquer conjunto de pedidos de tráfego de diferentes débitos (ou granularidades)
desde que não se ultrapasse a capacidade do lightpath em que se pretende agregar o tráfego. Já no
caso em que o débito do pedido corresponde ao do lightpath, procede-se ao mapeamento direto do
tráfego. O mapeamento direto consiste no estabelecimento de um ou mais lightpaths utilizados somente
para transportar tráfego relativo a um único pedido, bem como na alocação de recursos (interfaces de
linha, comprimentos de onda, regeneradores, etc.) para o suporte do mesmo. Assim sendo, neste último
caso não é necessária a multiplexagem de ODUs.
Os processos de mapeamento direto do tráfego, bem como a agregação recorrendo a multiplexagem
flexível dos ODUs estão ilustrados de forma simples na Figura 5.1.
Figura 5.1. Mapeamento do tráfego cliente: (a) Mapeamento direto; (b) Agregação do tráfego recorrendo a
multiplexagem flexível.
O fluxograma representado na Figura 5.2 demonstra o processo de decisão entre o mapeamento do
tráfego cliente diretamente na rede, e a agregação do tráfego. Caso o débito do pedido corresponda
ao débito de transmissão da fibra, este é mapeado diretamente na rede (bloco DirectMapping()), caso
o pedido corresponda a um ritmo ODU de baixa ordem, este será agregado num lightpath (bloco
MuxMapping()).
52
Figura 5.2. Processo de decisão entre mapeamento direto e agregação do
tráfego
5.1 Mapeamento direto de ODUs
Figura 5.3. Processo de mapeamento direto do tráfego (ritmo ODU = ritmo de linha)
Na Figura 5.3 está representado um fluxograma que ilustra o principio de funcionamento do
mapeamento direto do tráfego cliente. Como já foi referido, este processo ocorre apenas quando o
débito do pedido corresponde ao débito da fibra.
Sabendo-se os pares de nós origem e destino do pedido, são inicialmente analisados os caminhos
estáticos (obtidos por meio dos processos descritos no capítulo 3) entre esses pares de nós com vista
à possibilidade de utilização de um desses caminhos para o estabelecimento dos lightpaths que
conduzam o tráfego até ao seu destino. Nesta fase, calculam-se e atribuem-se os regeneradores aos
nós do caminho. É de notar que, neste caso, se for necessário, por exemplo, uma regeneração, então
terão que haver dois lightpaths para que o tráfego seja transportado até ao seu destino.
Os caminhos estáticos são analisados em sequencia, desde o de menor custo, até ao de maior. Se
neste processo for encontrado um caminho válido, são posteriormente atribuídos os comprimentos de
onda, segundo a estratégia escolhida inicialmente pelo utilizador. O próximo passo, consiste na reserva
de interfaces e dos comprimentos de onda utilizados em cada elemento da rede que esteja incluído no
53
caminho dos lightpaths estabelecidos. Se não existirem caminhos disponíveis para o transporte do
tráfego, então o pedido é bloqueado, e o programa tratará o próximo.
5.2 Agregação/Multiplexagem de ODUs O fluxograma representado na Figura 5.4 representa o processo de agregação de tráfego que foi
implementado em MatLab para o caso específico em que o rimo de ODU característico do pedido a ser
tratado é menor do que o rimo de transmissão suportado pela fibra. Recebido o pedido de tráfego, e
sabendo o par de nós origem e destino, o processo inicia-se com a construção de um grafo auxiliar
composto pelos lightpaths previamente estabelecidos na rede, ativados por pedidos de tráfego
anteriores. Nesta fase, são retirados da rede todos os ODUs cuja duração já tenha expirado e é feita a
multiplexagem flexível do pedido. Caso os recursos sejam suficientes e a capacidade residual dos
lightpaths suporte o pedido, então estes são incluídos no grafo auxiliar. Após a construção do grafo
auxiliar, este é sujeito ao processo de procura de caminhos de menor custo. Caso não existam
caminhos disponíveis, o grafo auxiliar de lightpaths é aumentado de forma a permitir o encaminhamento
do tráfego. Neste processo, os caminhos estáticos cuja origem e destino coincidam com os do pedido,
são percorridos em sequência até que se encontre um em que haja recursos para atende-lo. Uma vez
que haja um caminho eleito, este é utilizado para estabelecer novos lightpaths (tantos quantos o número
de regenerações necessárias) até ao destino. Posteriormente, o grafo auxiliar de lightpaths é sujeito
novamente ao processo de procura de caminhos de menor custo. Caso não exista uma solução de
encaminhamento, o pedido é bloqueado. Caso contrário, todos os recursos que são necessários para
encaminhar os novos lightpaths passam a ser reservados e utilizados. Se inicialmente, com apenas os
lightpaths previamente estabelecidos, se conseguir encontrar uma solução de encaminhamento, então
os ODUs de baixa ordem são simplesmente encaminhados nestes lightpaths.
54
Figura 5.4. Processo de Agregação do tráfego cliente (ritmo ODU < ritmo de linha)
5.3 Estratégias para seleção de lightpaths No processo de agregação, e em particular, na construção do grafo auxiliar de lightpaths, foi
implementada a possibilidade de se estabelecer um critério para a determinação dos lightpaths
candidatos ao encaminhamento do tráfego. Este processo poderá vir a ter impacto no número de
interfaces utilizadas e no número pedidos de tráfego bloqueados uma vez concluído o processo de
agregação, e como tal, considerou-se de interesse apresentar os diferentes critérios para lightpaths
candidatos e estudar o impacto que cada um pode eventualmente representar no processo de
agregação.
Foram implementados os seguintes quatro critérios para a seleção dos lightpaths candidatos:
1. Lightpaths sobre caminhos estáticos end-to-end pré-estabelecidos;
2. Quaisquer lightpaths, sem limitações;
3. Quaisquer lightpaths com limitação referente ao número de regenerações;
4. Quaisquer lightpaths com limitação referente ao número de regenerações, mais um número de
lightpaths candidatos disponíveis (número definido pelo utilizador).
55
O primeiro critério define que os lightpaths devem estar cingidos aos caminhos estáticos gerados
offline através do algoritmo dos 𝑘𝑘 caminhos mais curtos. Na Figura 5.5 pode observar-se a
utilização desta estratégia numa rede exemplo. A preto carregado representam-se os caminhos
estáticos gerados pelos algoritmos de encaminhamento sobre os quais é permitida a utilização de
lightpaths, representados a amarelo. Como mostra a figura, esta estratégia não permite que se
utilizem lightpaths onde não existam caminhos estáticos pré-estabelecidos. Assim, qualquer outro
lightpath anteriormente estabelecido, mesmo que tenha capacidade suficiente para transportar o
pedido de tráfego, não deverá ser incluído no grafo auxiliar de lightpaths.
A segunda estratégia permite o uso de quaisquer lightpaths que tenham sido anteriormente
estabelecidos na rede e cuja capacidade residual permita acomodar o pedido de tráfego. A Figura 5.6
mostra que quer os lightpaths tenham sido estabelecidos em caminhos estáticos pré-estabelecidos,
quer não, é permitida a sua utilização. A terceira e quarta estratégias são semelhantes a esta última. A
diferença é que existe um limite de lightpaths que se permite utilizar para transportar o pedido desde a
origem até ao destino. Esse limite prende-se com o número mínimo de regeneradores fixado
previamente para cada conjunto de caminhos (o algoritmo para o calculo do número mínimo de
regeneradores pode ser consultado na Secção 3.2) mais dois lightpaths de tolerância. A quarta
estratégia acrescenta a este limite um valor adicional predefinido pelo utilizador.
Figura 5.5. Ilustração da utilização da estratégia 1 numa rede exemplo
56
Figura 5.6. Ilustração da utilização da estratégia 2 numa rede exemplo
É expectável que a utilização da primeira estratégia tenda a encontrar caminhos com um menor número
de lightpaths entre a origem e o destino do pedido. Uma desvantagem evidente da utilização desta
estratégia é que, ao restringir o número de lightpaths candidatos, também restringe o número de
alternativas possíveis para o encaminhamento do tráfego. Por outro lado, a utilização da segunda
estratégia visa que se consigam mais soluções, para um menor número de lightpaths estabelecidos na
rede, mas poderá gerar caminhos com um número inusitado de lightpaths. Para que o número de
lightpaths não seja demasiado grande, a terceira e quarta estratégias restringem o número de lightpaths
que se podem utilizar para o encaminhamento do tráfego.
5.4 Resultados – tráfego dinâmico Nesta secção apresentam-se os resultados com o simulador descrito no capítulo 5 utilizando para o
efeito as redes do anexo A, com cenário de tráfego dinâmico e variando o número de pedidos de tráfego
a serem encaminhados na rede. Os resultados irão permitir tirar algumas conclusões sobre como a
variação destes parâmetros influencia o processo de agregação e são analisados em função de
parâmetros como o número de interfaces de linha, e a probabilidade de bloqueio dos pedidos de
tráfego.
5.4.1 Impacto do critério de custo para o estabelecimento dos caminhos estáticos
Caracterização das redes:
Número de comprimentos de onda:
o COST239: 50;
o NSFNET: 50;
o UBN: 50;
O número de comprimentos de onda utilizado foi escolhido para cada rede de forma a garantir que não
existe bloqueio de pedidos de tráfego.
57
Débito de linha: OTU-4 (100 Gb/s);
Penalidade de transmissão por salto: 80 km;
Rácio de portos de adição/extração por nó:
o Rede COST239: 100%;
o Rede NSFNET: 100%;
o Rede UBN: 100%.
Colocação uniforme de transponders;
Arquitetura dos ROADMS: Colorless and Directionless.
Parâmetros da geração de tráfego:
Tipo de sinais: ODU-0 (1.25 Gb/s) e ODU-1 (2.5 Gb/s);
Distribuições para geração do tráfego:
o Tempos de chegada entre pedidos: exponencial;
o Tempos de duração dos pedidos: exponencial;
Pedidos de tráfego: 1000, 2000, 3000, 4000 e 5000;
Parâmetros da Simulação:
𝑘𝑘 = 1;
Critérios de Custo (parâmetro em estudo):
1. Número de Saltos;
2. Distância;
3. Degradação de Sinal.
Estratégia para lightpaths candidatos: lightpaths sob caminhos estáticos end-to-end pré-
estabelecidos;
Nesta análise foi considerado como instrumento de comparação o número de interfaces de linha. O
estudo em causa tem como objetivo perceber como cada um dos critérios de custo utilizados no
algoritmo de encaminhamento influencia o processo de agregação num cenário em que não existe
bloqueio, ou seja, a rede tem bastante capacidade disponível e um número de portos add/drop
suficientemente grande para que se consiga atender a todos os pedidos de tráfego.
Os resultados obtidos para as três redes estão presentes nas Figuras 5.7 a 5.9, onde se representa a
variação do número de interfaces de linha em função do número de pedidos de tráfego. Estas mostram
que, em qualquer uma das redes consideradas, não existe uma diferença assinalável no número de
interfaces de linha obtidas. A variação do número de interfaces deve-se essencialmente à diferença no
número de regenerações e à utilização de pontos de agregação diferentes.
58
Figura 5.7. Número de Interfaces de linha em função do nº de pedidos de tráfego – Rede COST239
Figura 5.8. Número de Interfaces de linha em função do nº de pedidos de tráfego – Rede NSFNET
Figura 5.9. Número de Interfaces de linha em função do nº de pedidos de tráfego – Rede UBN
No caso da rede NSFNET e da UBN, como se viu no cap. 3 existem diferenças nos requisitos de
regeneração mediante o critério de custo utilizado. Em particular, os resultados mostraram que o critério
de custo que leva em conta o número de saltos apresenta um número mínimo de regeneradores maior
do que os outros dois critérios. Isso reflete-se nos resultados obtidos nas Figura 5.8 e Figura 5.9 em
0
50
100
150
200
250
1000 2000 3000 4000 5000Nº
de In
terf
aces
de
Linh
a
Nº de pedidos de tráfego
Número de Saltos Distância Degradação do Sinal
0
50
100
150
200
250
300
1000 2000 3000 4000 5000
Nº
de In
terf
aces
de
Linh
a
Nº de pedidos de tráfego
Número de Saltos Distância Degradação do Sinal
0
100
200
300
400
500
1000 2000 3000 4000 5000
Nº
de In
terf
aces
de
Linh
a
Nº de pedidos de tráfego
Número de Saltos Distância Degradação do Sinal
59
que em geral se obtém um maior número de interfaces de linha utilizadas pelo primeiro critério de custo,
embora a diferença não ultrapasse os 3%.
Além disso, tendo em conta que se considerou que na estratégia de seleção de lightpaths se utilizam
apenas os que estão sob os caminhos estáticos estabelecidos pelos algoritmos de encaminhamento,
se coincidentemente muitos pedidos de tráfego forem gerados com pares de nós origem e destino que
podem atravessar os lightpaths estabelecidos sem ter que se criar novos lightpaths, isso também
poderá trazer poupanças em termos de interfaces de linha utilizadas. Essa pode ser a razão que leva
a que na Figura 5.9 o primeiro critério de custo gere menos interfaces de linha para 1000 e 2000 pedidos
de tráfego, apesar dos maiores requisitos de regeneração.
5.4.1.1 Conclusões Os resultados obtidos permitem concluir que qualquer um dos critérios de custo tem pouco impacto ao
nível das de interfaces de linha requeridas para os pedidos de tráfego que chegam à rede. Note-se que
tal acontece pelo facto de os requisitos de regeneração serem semelhantes, independentemente do
critério de custo utilizado. Se houvesse uma grande diferença em termos de regeneração, seria de
esperar que para o método em que esses requisitos são mais elevados também houvesse um maior
número de interfaces de linha utilizadas, e como tal, um maior custo. Isto reflete-se nos resultados
obtidos para as redes NSFNET e UBN, mas de forma muito tímida, precisamente pelo facto de haverem
poucas diferenças em termos de requisitos de regeneração.
O impacto que os requisitos de regeneração têm no estabelecimento das interfaces de linha (LI – Line
Interfaces) pode ser observado pelos resultados da simulação das redes NSFNET e UBN com e sem
penalidade de transmissão por salto, que designamos como 𝑝𝑝ℎ𝐺𝐺𝑝𝑝 (per hop reach penalty) para cada
um dos critérios de custo: 1, 2 e 3 (ver Tabelas5.1 e 5.2).
Tabela 5.1. Número de Interfaces com e sem penalidade de
transmissão por salto (impacto da regeneração) - rede NSFNET
NSFNET
5000 pedidos de tráfego
com 𝑝𝑝ℎ𝐺𝐺𝑝𝑝 sem 𝑝𝑝ℎ𝐺𝐺𝑝𝑝
3R LI 3R LI
1 47 267 41 265
2 34 268 26 252
3 34 272 26 252
60
Tabela 5.2. Número de Interfaces com e sem penalidade de transmissão por salto (impacto da regeneração) - rede UBN
UBN
5000 pedidos de tráfego
com 𝑝𝑝ℎ𝐺𝐺𝑝𝑝 sem 𝑝𝑝ℎ𝐺𝐺𝑝𝑝
3R LI 3R LI
1 234 422 174 414
2 201 419 138 388
3 201 419 138 388
Os resultados presentes nas Tabelas 5.1 e 5.1 mostram que, como seria de esperar, existe uma relação
evidente entre o número de regenerações necessárias e o número de interfaces utilizadas. Esta é uma
constatação óbvia uma vez que cada regeneração 3R corresponde à utilização de mais 2 interfaces de
linha. A diferença torna-se mais saliente nos casos da utilização da segunda e terceira estratégias. Por
exemplo, para o caso da utilização da segunda estratégia na rede NSFNET, com 𝑝𝑝ℎ𝐺𝐺𝑝𝑝 obtém-se o
mínimo de 34 regeneradores, enquanto que sem 𝑝𝑝𝐺𝐺ℎ𝑝𝑝 se obtêm 26. Esta diferença reflete-se no número
de interfaces de linha utilizadas, neste caso concreto, para o encaminhamento de 5000 pedidos de
tráfego.
5.4.2 Impacto das diferentes estratégias de seleção de lightpaths Caracterização das redes:
Número de comprimentos de onda: 30;
Débito de linha:
o Rede COST239: OTU-4 (100 Gb/s);
Rácio de portos de adição/extração por nó de 30%;
Colocação uniforme de transponders;
Arquitetura dos ROADMS: Colorless and Directionless.
Parâmetros da geração de tráfego:
Tipo de sinais:
o Rede COST239:
ODU-0 (1.25 Gb/s) e ODU-1 (2.5 Gb/s);
Padrão de geração de tráfego:
o Tempos de chegada entre pedidos: exponencial;
o Tempos de duração dos pedidos: exponencial;
Pedidos de tráfego:
o Rede COST239: 5000, 6000, 7000, 8000, 9000, 10000;
Parâmetros da Simulação:
𝑘𝑘 = 3 caminhos alternativos;
61
Estratégia para lightpaths candidatos (parâmetro em estudo):
1. Lightpaths sobre caminhos estáticos E2E pré-estabelecidos;
2. Quaisquer lightpaths, sem limitações;
3. Quaisquer lightpaths com limitação referente ao número de regenerações;
4. Quaisquer lightpaths com limitação referente ao número de regenerações, mais um
número de lightpaths candidatos disponíveis.
Neste estudo, as características da rede foram escolhidas por forma a que exista bloqueio de pedidos
de tráfego e se possam tirar conclusões sobre qual a estratégia de lightpaths candidatos que gera uma
menor probabilidade de bloqueio. Há que salientar que não podemos dissociar o número de interfaces
obtidas por cada uma das estratégias da probabilidade de bloqueio de pedidos de tráfego. Para cada
uma das abordagens faremos uma comparação com base nestes dois parâmetros.
5.4.2.1 Resultados para a rede COST239: Os resultados obtidos para a rede COST239, relativos a cada uma das estratégias em consideração,
estão representados nas Figura 5.10 aFigura 5.13. Observa-se para esta rede em particular que a
utilização da primeira estratégia não gera bloqueio de pedidos de tráfego, ao contrário do que sucede
nas demais. A utilização da segunda estratégia resultou não só numa maior utilização de interfaces de
linha como num ligeiro aumento da probabilidade de bloqueio, que chega a atingir os 4% para o caso
em que se consideram 10000 pedidos. Estes resultados são curiosos, uma vez que seria esperado que
havendo mais soluções para o encaminhamento do tráfego também haveria menos bloqueio. Mas o
que sucede é que uma vez que a utilização da segunda estratégia tende a preencher os lightpaths
uniformemente em toda a rede, quando a rede já se encontra parcialmente preenchida, os pedidos de
tráfego que “tentam” estabelecer um ou mais lightpath entre dois nós, podem já não encontrar soluções
de encaminhamento, tendo que estabelecer novos lightpaths (e como consequência, utilizar mais
interfaces de linha). Dito de outra forma, a segunda estratégia tende a preencher a capacidade de mais
lightpaths na rede, por cada pedido de tráfego, enquanto que a primeira, apesar de inicialmente ter que
estabelecer mais lightpaths, acaba por ter mais soluções diretas (caminhos com menos lightpaths), e,
portanto, tende também a preencher a capacidade de menos lightpaths já estabelecidos na rede.
62
Figura 5.10. Interfaces de linha (OTU-4) utilizadas e probabilidade de bloqueio - Estratégia 1 - Rede
COST239
Figura 5.11. Interfaces de linha (OTU-4) utilizadas e probabilidade de bloqueio - Estratégia 2 - Rede
COST239
Figura 5.12. Interfaces de linha (OTU-4) utilizadas e probabilidade de bloqueio - Estratégia 3 - Rede
COST239
Figura 5.13. Interfaces de linha (OTU-4) utilizadas e probabilidade de bloqueio - Estratégia 4 (+3
caminhos) - Rede COST239
A Figura 5.12 mostra os resultados obtidos para a terceira estratégia. Como já foi explicado
anteriormente, esta limita o número de saltos em termos de lightpaths, ou seja, se por exemplo num
dado caminho entre um par de nós são necessárias no mínimo duas regenerações (o que equivale a
duas conversões do sinal ótico para o domínio elétrico), então esta estratégia restringe as soluções de
encaminhamento àquelas cujo caminho tem um número de lightpaths menor ou igual a quatro (num
caminho com duas regenerações são necessários três lightpaths, e a estratégia estabelece mais dois
lightpaths de tolerância). Assim sendo, e tendo em conta que a rede COST239 não tem requisitos de
regeneração nestas condições, permitem-se apenas soluções de encaminhamento com um número
igual ou inferior a 2 lightpaths. Se o operador pretender limitar o número de interfaces utilizadas, esta
é a estratégia indicada a utilizar. Note-se que, de entre todas as estratégias, esta é a que limita mais a
utilização do número de interfaces. Por outro lado, e como consequência deste último facto, também é
a que resulta numa maior probabilidade de bloqueio, que nos casos considerados ronda os 50%. A
quarta e última estratégia, conforme se observa na Figura 5.13, permite ao operador obter um equilíbrio
entre limitar o número de interfaces e ao mesmo tempo diminuir a probabilidade de bloqueio. É obvio
0%10%20%30%40%50%60%70%80%90%100%
050
100150200250300350
Prob
abili
dade
de
Boqu
eio
Nº
de In
terf
aces
de
Linh
a
Nº de pedidos de tráfego
Interfaces de Linha Bloqueio
0%1%1%2%2%3%3%4%4%5%
050
100150200250300350400450500
Prob
abili
dade
de
Bloq
ueio
Nº
de In
terf
aces
de
Linh
a
Nº de pedidos de tráfego
Interfaces de Linha Bloqueio
0%10%20%30%40%50%60%
0
50
100
150
200
250
5000 6000 7000 8000 9000 10000 Prob
abili
dade
de
Bloq
ueio
Nº
de In
terf
aces
de
Linh
a
Nº de pedidos de tráfego
Interfaces de Linha Bloqueio
0%
1%
2%
3%
4%
5%
6%
050
100150200250300350400450500
5000 6000 7000 8000 9000 10000
Prob
abili
dade
de
Bloq
ueio
Nº
de In
terf
aces
de
Linh
a
Nº de pedidos de tráfego
Interfaces de Linha Bloqueio
63
que no limite, se se permitir que um número elevado de lightpaths seja utilizado para o encaminhamento
nesta ultima estratégia, então os resultados tenderão a ser iguais aos da segunda estratégia.
5.4.2.2 Resultados para as redes NSFNET e UBN: Os resultados anteriores apontam no sentido de que a primeira estratégia estabelece mais lightpaths
inicialmente, mas depois acaba por preenche-los aos poucos, gerando menor utilização de interfaces
de linha (OTU-4) e de bloqueios. Contudo, é um facto que a segunda estratégia gera inicialmente mais
soluções de encaminhamento, tendo acesso a mais lightpaths para encaminhar o tráfego. Assim, nesta
subsecção achou-se interessante simular as redes NSFNET e UBN com sinais de menor débito (ODU-
0) e com sinais de maior débito (ODU-3), com um débito de linha elevado, equivalente a OTU-5 (400
Gbit/s). A previsão é que, na fase em que a rede ainda tem muita capacidade disponível, com sinais de
menor débito, a segunda estratégia gere um menor número de interfaces uma vez que em cada fibra
existirá espaço suficiente para agregar até 320 sinais ODU-0. Com sinais de maior débito, prevê-se
que a primeira estratégia tenha um melhor desempenho.
Caracterização das redes:
Débito da linha:
o Redes NSFNET e UBN: OTU-5.
Parâmetros de geração do tráfego:
Número de pedidos de tráfego:
o Rede NSFNET: 100, 1000, 10000;
o Rede UBN: 100, 1000, 10000;
Tipos de sinais:
o Rede NSFNET:
ODU-0 (1.25 Gb/s);
ODU-3 (40 Gb/s).
o Rede UBN:
ODU-0 (1.25 Gb/s);
ODU-3 (40 Gb/s).
Parâmetros da Simulação:
Estratégia para lightpaths candidatos (parâmetro em estudo):
1. Lightpaths sobre caminhos estáticos E2E pré-estabelecidos;
2. Quaisquer lightpaths, sem limitações;
Os restantes parâmetros são iguais aos que foram utilizados para a simulação da rede COST239. Os
resultados obtidos nesta subsecção são apenas relativos à primeira e segunda estratégias de seleção
de lightpaths. Isto porque a terceira e quarta não passam de variações da segunda, com a nuance de
que existem restrições em relação ao número de lightpaths que se permite utilizar para as soluções de
encaminhamento do tráfego.
64
Figura 5.14. Número de interfaces de linha (OTU-5) utilizadas para pedidos de tráfego com débito ODU-
0 – Rede NSFNET.
Figura 5.15. Número de interfaces de linha (OTU-5)
utilizadas para pedidos de tráfego com débito ODU-3 – Rede NSFNET.
Figura 5.16. Número de interfaces de linha (OTU-5) utilizadas para pedidos de tráfego com débito ODU-
0 – Rede UBN.
Figura 5.17. Número de interfaces de linha (OTU-5)
utilizadas para pedidos de tráfego com débito ODU-3 – Rede UBN.
Os resultados obtidos para as redes NSFNET e UBN, no que diz respeito ao número de interfaces de
linha (OTU-5), estão representados nos gráficos das Figuras 5.14 e 5.17. Observa-se que para tráfego
de débito equivalente a ODU-0 a primeira estratégia obtém melhores resultados para 100 e 1000
pedidos de tráfego, nas duas redes. No cenário em que se consideram 5000 pedidos de tráfego, a
primeira estratégia já obtém menos interfaces para a rede NSFNET, e na rede UBN existe um grande
equilíbrio, havendo uma diferença de 4 interfaces apenas. Este comportamento indicia que nesta fase
os lightpaths da rede começam a ficar totalmente “preenchidos”, o que faz com que a primeira estratégia
comece a ter um melhor desemprenho à medida que mais pedidos de tráfego chegam à rede. Isso
pode ser verificado pelo número de interfaces obtidas para 10000 pedidos de tráfego. Nesta fase, a
primeira estratégia “consegue” já um número consideravelmente menor de interfaces.
0
50
100
150
200
250
100 1000 5000 10000Nº
de In
terf
aces
de
Linh
a
Nº de pedidos de tráfegoEstratégia 1 Estratégia 2
0
100
200
300
400
100 1000 5000 10000Nº
de In
terf
aces
de
Linh
a
Nº de pedidos de tráfegoEstratégia 1 Estratégia 2
0100200300400500600700
100 1000 5000 10000
Nº
de In
terf
aces
de
Linh
a
Nº de pedidos de tráfego
Estratégia 1 Estratégia 2
0
200
400
600
800
100 1000 5000 10000Nº
de In
terf
aces
de
Linh
a
Nº de pedidos de tráfego
Estratégia 1 Estratégia 2
65
Figura 5.18 – Nº de pedidos de tráfego com débito
ODU-3 bloqueados – rede NSFNET
Figura 5.19 - Nº de pedidos de pedidos de tráfego com
débito ODU-3 bloqueados – rede UBN
O cenário em que se consideram pedidos com débito equivalente a ODU-3 confirma que a primeira
estratégia tem em geral um melhor desempenho em cenários em que os lightpaths têm capacidade
para agregar menos sinais. Para 100 pedidos de tráfego estamos na fase em que os lighpats têm ainda
capacidade disponível para agregar tráfego, e daí se justifica o facto da primeira estratégia ainda
conseguir um melhor desempenho nesta fase.
Para os sinais ODU-0 não existe bloqueio para qualquer uma das redes, independentemente da
estratégia de seleção de lightpaths que se utilize. Para sinais ODU-3, os resultados obtidos em termos
de probabilidade de bloqueio estão presentes nos gráficos das Figuras 4.27 e 4.28. De facto, tal como
previsto, para cargas elevadas a tendência é que a primeira estratégia consiga melhores resultados do
que a segunda. Isto confirma a previsão que se fez no inicio desta subsecção.
5.4.2.3 Conclusões Os resultados para a rede COST239 permitiram perceber o comportamento de cada uma das
estratégias de seleção de lightpaths que foram implementadas, bem como fazer previsões em relação
ao comportamento de cada uma, tanto no cenário de sinais de débitos baixos como de débitos altos.
As simulações das redes NSFNET e UBN permitiram confirmar que a primeira estratégia tem um melhor
desempenho para débitos de tráfego elevados relativamente ao débito de linha. Já a segunda estratégia
garante mais soluções de encaminhamento numa fase inicial, e um melhor desempenho ao nível das
interfaces em cenários em que o débito do tráfego cliente é pequeno relativamente ao débito de linha.
A segunda e terceira estratégias, as quais são variantes da segunda, permitem restringir o número de
lightpaths que podem ser utilizados no encaminhamento, e, como consequência, também o número de
interfaces utilizadas. Contudo, a probabilidade de bloqueio de pedidos de tráfego também pode
aumentar consideravelmente com esta restrição.
0100020003000400050006000
100 1000 5000 10000
Prob
abili
dade
de
Bloq
ueio
Nº de pedidos de tráfegoEstratégia 1 Estratégia 2
0
1000
2000
3000
4000
5000
6000
100 1000 5000 10000Prob
abili
dade
de
Bloq
ueio
Nº de pedidos de tráfegoEstratégia 1 Estratégia 2
66
5.5 Análise comparativa de estratégias de planeamento multiperiodo –
Tráfego Estático Nesta secção serão apresentados resultados relativos a três estratégias de planeamento multiperíodo,
usando a rede COST239: planeamento de todos os períodos, planeamento de fim de vida e
planeamento incremental. Este estudo foi realizado com recurso a tráfego estático, ou seja, o tráfego
deixa de ser imprevisível e passa a ser completamente conhecido em cada período de planeamento.
Os resultados obtidos permitir-nos fazer um estudo sobre qual a estratégia mais indicada para se
planear a rede nos cenários em que a previsão dos pedidos de tráfego é perfeita e para o caso em que
não corresponde à realidade. Conforme salientado na Secção 2.3.4, é difícil hoje em dia fazer previsões
fidedignas em relação à evolução do tráfego cliente ao longo do tempo. Assim, o cenário que será
estudado nesta dissertação prende-se com a incerteza em relação aos pedidos.
Caracterização das redes:
Número de comprimentos de onda: 80;
Débito de linha: OTU-4 (100 Gb/s);
Rácio de portos de adição/extração por nó de 100%;
Colocação uniforme de transponders;
Arquitetura dos ROADMS: Colorless and Directionless.
Parâmetros da geração de tráfego:
Número de períodos: 4.
Tipo de sinais:
o Tráfego previsto:
Sinais ODU-2: 1000 pedidos;
Sinais ODU-3: 200 pedidos;
Sinais ODU-4: 40 pedidos.
o Tráfego real:
Cenário 1: Correspondente ao tráfego previsto
Cenário 2: Alteração dos nós origem e destino, face ao tráfego previsto
• Alteração de 30% dos pedidos;
• Alteração de 70% dos pedidos.
Cenário 3: Alteração dos débitos, face ao tráfego previsto
• Diminuição do débito de metade dos sinais ODU-4 para ODU-3
(Sobrestimação);
• Aumento do débito de metade dos sinais ODU-3 para ODU-4
(Subestimação).
Parâmetros da Simulação:
𝑘𝑘 = 3 caminhos alternativos;
67
Critério de custo: Degradação do sinal ótico;
Estratégia para lightpaths candidatos: lightpaths sob caminhos estáticos pré-estabelecidos;
Para o Cenário 1, considerou-se que o tráfego previsto é coincidente com o real. Os resultados obtidos
presentes na Figura 5.20 permitem-nos confirmar o que foi descrito na secção 2.3.4. De facto, vemos
que em geral o planeamento de todos os períodos (“AP” no gráfico) gera bons resultados em todos os
períodos. Tal acontece porque a organização dos pedidos de tráfego é efetuada de forma a que o
resultado final seja o melhor desde o período 1 até cada um dos outros. Já o planeamento de fim de
vida (“EOL” no gráfico) visa obter o menor custo para o último período de vida da rede. Isso reflete-se
nos resultados, uma vez que se observa que no primeiro período o EOL obtém mais interfaces de linha,
mas nos posteriores começa a melhorar, sendo que no último é efetivamente aquele que gera menos
interfaces de linha juntamente com o planeamento de todos os períodos.
Como referido na Secção 2.3.4, o planeamento incremental (“Inc” no gráfico) tem como objetivo o
planeamento dos períodos de forma individual. Tendo isto em conta, antecipava-se que os resultados
fossem melhores para o primeiro período. Tal acontece porque os pedidos são ordenados de forma a
que se atinjam melhores resultados a curto prazo.
Figura 5.20. Número de interfaces de linha OTU-4 obtidas para cada um dos
tipos de planeamento multiperiodo – Cenário 1
No Cenário 2 considerou-se que a previsão de tráfego a ser mapeado na rede não corresponde ao
tráfego real. Neste caso, procedeu-se à mudança de 30% e 70% dos pares origem-destino dos pedidos
de tráfego. O impacto da mudança dos pares origem-destino é evidente no número de interfaces de
linha utilizadas. Para 30% de mudanças, existe um aumento de 13% das interfaces de linha. Para 70%
de mudanças, esse número sobe para 18%. Isso confirma que a imprevisibilidade do tráfego afeta
consideravelmente o processo de planeamento.
Os resultados relativos ao Cenário 2 para o número de interfaces de linha utilizadas estão
representados na Figura 5.21. Nota-se que a tendência se mantém para cada uma das estratégias,
0100200300400500600700
1 2 3 4
previsão perfeita
Nº
de In
terf
aces
de
Linh
a
AP Inc EOL
68
contudo, o planeamento incremental neste cenário obtém melhores resultados que o EOL não só para
o primeiro período como para o segundo, ao contrário do que acontecia para a previsão perfeita.
Figura 5.21. Número de interfaces de linha OTU-4 obtidas para cada um dos
tipos de planeamento multiperiodo – Cenário 2
A Figura 5.22 mostra que, de facto, a estratégia que menos “sofre” com a mudança dos pares origem-
destino dos pedidos de tráfego é a de planeamento incremental. Tal dever-se-á ao facto de esta
estratégia cingir a alocação dos recursos a períodos individuais, portanto, as alterações são
circunscritas a esses períodos e não se repercutem a longo prazo. Por outro lado, o EOL é a que lida
pior com a mudança dos pares origem-destino dos pedidos. Ainda assim, tal como para a previsão
perfeita, a longo prazo, o AO e EOL são as que obtêm um menor número de interfaces de linha, e como
tal, um menor custo.
Figura 5.22. Aumento relativo do número de interfaces de linha OTU-4 relativamente
à previsão perfeita para cada uma das estratégias de planeamento multiperiodo
No Cenário 3 optou-se por mudar o débito dos pedidos. Ou seja, os pares origem-destino são
coincidentes aos do tráfego real, contudo, o débito irá diferir. Os resultados obtidos para o Cenário 3
estão representados na Figura 5.23. A longo prazo a tendência verificada nos cenários anteriores
mantém-se, uma vez que tanto para o aumento como para diminuição do débito, no quarto período as
estratégias de planeamento de todos os períodos e de fim de vida produzem melhores resultados. A
0
200
400
600
800
1 2 3 4 1 2 3 4
30% de mudanças 70% de mudanças
Nº
de In
terf
aces
de
Linh
a
AP Inc EOL
0%
5%
10%
15%
20%
25%
30%
30 % de mudanças 70% de mudanças
Varia
ção
rela
tiva
do
núm
ero
de in
terf
aces
AP Inc EOL
69
curto prazo a tendência também se mantém, com a estratégia de planeamento incremental a gerar
melhores resultados no primeiro período, juntamente com o AP.
Figura 5.23. Número de interfaces de linha OTU-4 obtidas para cada um dos tipos de
planeamento multiperiodo – Cenário 3
0200400600800
10001200
1 2 3 4 1 2 3 4
Aumento do débito Diminuição do débito
Nºo
de
Inte
rfac
es d
e Li
nha AP Inc EOL
70
71
6 Conclusões Com os requisitos do tráfego cliente a aumentarem de forma vertiginosa, e com a evolução das
tecnologias que têm potenciado esse aumento, cada vez mais é necessário que as operadoras
procedam a um cuidadoso planeamento da rede de forma a atender às exigências, ao mesmo tempo
que garantem uma boa qualidade de serviço e uma utilização eficiente dos recursos disponíveis. Esse
planeamento é executado muitas vezes recorrendo-se a pacotes de software que geram de forma
virtual o tráfego para que seja mapeado nas redes que se pretendem planear.
Nesta dissertação, adaptou-se para a linguagem de programação MatLab um programa da autoria do
Dr. João Pedro, co-orientador nesta dissertação, e criou-se uma GUI para facilitar a introdução das
especificações da rede e das características dos pedidos de tráfego a serem mapeados.
No capítulo 3 procedeu-se ao estudo dos algoritmos de encaminhamento implementados na fase de
procura dos caminhos estáticos para o estabelecimento dos lightpaths entre pares nós. Além disso,
abordaram-se 3 critérios de custo para a procura dos caminhos e obteve-se resultados no sentido de
se poder fazer uma comparação em termos do número de regeneradores necessários na utilização de
cada um. Concluiu-se que para 𝑘𝑘 < 5 caminhos, a estratégia com pior desempenho é a que leva em
conta apenas o número de saltos, enquanto que as outras duas, nos cenários considerados, geram um
número idêntico de regenerações.
No capítulo 4 são feitas considerações sobre o funcionamento do software implementado em MatLab
e que visa o planeamento do tráfego na rede. São descritos os módulos de geração e de mapeamento
do tráfego cliente e é feita uma breve explicação sobre a forma como é implementada a funcionalidade
que permite o planeamento em cenário multiperíiodo.
No capítulo 5 descreveram-se os algoritmos de mapeamento direto e de agregação que foram
adaptados para MatLab. Além disso, são apresentadas algumas estratégias que podem ser utilizadas
pelo operador, de acordo com as suas intenções. Por fim, são apresentados resultados sobre o impacto
que cada uma destas estratégias pode eventualmente ter no processo de agregação:
• A comparação dos critérios de custo no estabelecimento dos caminhos estáticos leva a crer
que a estratégia que produz melhores resultados seja aquela que efetivamente gera um menor
número de regeneradores necessários. Como nesta dissertação se consideram apenas redes
translucidas, o critério de custo que gerou pior desempenho ao nível das interfaces utilizadas
foi a que leva em conta apenas o número de saltos. Por outro lado, a outras duas estratégias
produzem resultados ligeiramente melhores, mas muito semelhantes, o que seria expectável,
uma vez que a penalidade de transmissão por salto não é grande o suficiente para proporcionar
uma discrepância significativa.
• A resultados obtidos para as diferentes estratégias de seleção de lightpaths levam-nos às
seguintes conclusões:
72
o A estratégia que estabelece lightpaths apenas sob caminhos estáticos pré-
estabelecidos, começa por estabelecer um grande número de lightpaths numa fase
inicial devido à inexistência de soluções de encaminhamento, contudo, à medida que
os pedidos de tráfego chegam à rede, esta garante que um número relativamente
pequeno de lightpaths sejam utilizados para encaminhar os pedidos de tráfego,
evitando assim um maior desperdício de capacidade da rede.
o A estratégia que permite o uso de quaisquer lightpaths, sem restrições, começa por
gerar um número menor de lightpaths pelo facto de permitir encontrar mais soluções
de encaminhamento no grafo auxiliar de lightpaths numa fase inicial, contudo, a
capacidade da rede é utilizada de modo mais ineficiente do que na primeira estratégia,
uma vez que esta utiliza um grande número de lightpaths para fazer o
encaminhamento.
o Os dois pontos anteriores permitiram concluir que para o cenário em que o débito dos
pedidos é elevado face à capacidade dos lightpaths a primeira estratégia gera
melhores resultados, enquanto que no cenário em que o débito dos pedidos é pequeno,
a segunda gera uma utilização menor de interfaces de linha. Isso ficou confirmado
pelos resultados das Figuras 5.14 a 5.17.
• Em relação à análise dos resultados obtidos para as três estratégias de planeamento
multiperiodo implementadas, conclui-se que para o cenário em que o tráfego previsto
corresponde ao tráfego real, a estratégia de planeamento de todos os períodos permite
alcançar melhores resultados em todos os períodos em estudo. O planeamento incremental
permite um planeamento eficiente nos primeiros períodos, mas o facto de este se focar na
alocação de recursos em períodos individuais faz com que não se atinja uma solução eficiente
a longo prazo, enquanto que o planeamento de fim de vida, tal como esperado, gera bons
resultados, mas apenas nos últimos períodos de planeamento. Quando se impôs discrepâncias
no tráfego previsto face ao real, conclui-se que no caso em que se alteram os pares de nós
extremos dos pedidos de tráfego, o planeamento torna-se ineficiente, dado o aumento
considerável de interfaces de linha necessárias face às obtidas na previsão perfeita.
Como trabalho futuro sugere-se o estudo dos algoritmos de colocação de regeneradores durante o
processo de agregação e do eventual impacto que elas poderão ter no mesmo. Também se sugere
uma análise comparativa entre políticas de agregação diferentes (para cada política, as intenções do
operador são refletidas nos pesos do grafo auxiliar de lightpaths – ver [25]).
Para além disso, também se sugere uma análise das estratégias de planeamento multiperiodo para
cenários mais variados, como por exemplo o crescimento progressivo do débito ao longo dos períodos
de planeamento como forma de simular uma exigência progressiva dos serviços cliente ao nível do
débito exigido, entre outros cenários.
73
ANEXO
A. Topologias Físicas das Redes Analisadas
Figura A.1. Topologia física da rede
COST239(extraída de [26])
Figura A.2. Topologia física da rede NSFNET (extraída de
[26])
Figura A.3. Topologia física da rede UBN (extraída de [24])
74
75
B. Algoritmo dos 𝑘𝑘 Caminhos Alternativos (exemplo de
execução) Segue-se um exemplo de execução do algoritmo dos 𝑘𝑘 caminhos alternativos com uma rede simples,
representada na Figura B.1. Para o efeito, escolhe-se 𝑘𝑘 = 3, 𝑠𝑠 = 1, e 𝐶𝐶 = 6.
Figura B.1. Rede G
O algoritmo começa por determinar o caminho de menor custo, sem ciclos, desde 1 até 6, o qual será
𝑝𝑝1 = < 1, 2, 3, 6 >. Ficamos com 𝑋𝑋 = {< 1, 2, 3, 6 >}. Iniciamente, 𝑘𝑘 = 1, e 𝑝𝑝1 é analisado e retirado de
𝑋𝑋. Uma vez que 𝑑𝑑(𝑝𝑝1) = 𝑠𝑠 = 1, os nós 1, 2 e 3 serão analisados. O nó 1 não contém nenhum caminho
divergente a não ser o contido em 𝑝𝑝1. A análise ao nó 2 resulta na eliminação do nó 1, bem como da
aresta que liga o nó 2 ao nó 3, 𝑙𝑙𝑖𝑖𝑛𝑛𝑘𝑘(2,3). A rede remanescente está representada na Figura B.2.
Figura B.2. Rede remanescente após análise do nó 1; k=1.
O caminho encontrado a partir do nó 2 é 𝑝𝑝2 = < 1, 2 > ⋄ < 2,4,6 > = < 1, 2, 4, 6 >. Este caminho é, por
sua vez, inserido no conjunto 𝑋𝑋. Na análise ao nó 3 a rede remanescente (ver Figura B.3) resulta da
eliminação acrescida do nó 2 e da aresta que liga o nó 3 ao nó 6, 𝑙𝑙𝑖𝑖𝑛𝑛𝑘𝑘(3,6).
Figura B.3. Rede remanescente após análise do nó 2; k=1.
76
É visível que não existem caminhos alternativos a partir do nó 3. Assim, após a análise nó a nó do
primeiro caminho de menor custo, ficamos com 𝑋𝑋 = {< 1, 2, 4, 6 >}. O procedimento repete-se para 𝑘𝑘 =
2. A rede inicial é restaurada, e o caminho em 𝑋𝑋 é retirado e analisado. Como 𝑑𝑑(𝑝𝑝2) = 2, os nós 2 e 4
serão analisados. Na análise ao nó 2, procede-se à eliminação do nó 1 e das arestas que ligam o nó 2
ao nó 3 e do que liga o nó 2 ao 4, 𝑙𝑙𝑖𝑖𝑛𝑛𝑘𝑘(2, 3) e 𝑙𝑙𝑖𝑖𝑛𝑛𝑘𝑘(2, 4). A rede remanescente está representada na
Figura B.4.
Verifica-se que o caminho mais curto nestas condições é dado por 𝑞𝑞 =< 2, 5, 6 >, logo 𝑝𝑝3 = < 1, 2 > ⋄
< 2,5,6 > = < 1, 2, 5, 6 > e portanto 𝑋𝑋 = {< 1, 2, 5, 6 >}. Seguidamente, procede-se da mesma forma,
analisando-se o nó 4. Contudo, não existem caminhos alternativos a partir do nó 4. Finalmente, para
𝑘𝑘 = 3, o caminho é retirado de 𝑋𝑋 e a rede remanescente dada pela análise de cada um dos nós não
permite a determinação de mais caminhos. Consequentemente, o algoritmo termina.
Figura B.4. Rede remanescente ao analisar nó 2; k=2.
Em suma, os caminhos encontrados pelo algoritmo são os seguintes:
1. 𝑝𝑝1 =< 1, 2, 3, 6 >;
2. 𝑝𝑝2 =< 1, 2, 4, 6 >;
3. 𝑝𝑝3 =< 1, 2, 5, 6 >.
77
C. Distribuições Estatísticas na Geração de Tráfego
Dinâmico
Distribuição exponencial A distribuição exponencial, por definição, é dada por:
𝑦𝑦 = 𝑓𝑓(𝑁𝑁|𝜇𝜇) = 1𝜇𝜇𝑒𝑒−𝑥𝑥𝜇𝜇 .
A simulação resultante da geração de 1000 pedidos de tráfego ODU-0 (1.25 Gb/s), com a média dada
por
𝜇𝜇 =(𝐴𝐴𝐶𝐶𝑒𝑒𝐺𝐺𝑎𝑎𝑔𝑔𝑒𝑒_𝐷𝐷𝑀𝑀𝐺𝐺𝑎𝑎𝐶𝐶𝑖𝑖𝑜𝑜𝑛𝑛(𝑠𝑠) × 1.25𝐺𝐺𝑠𝑠/𝑠𝑠)
𝐴𝐴𝐶𝐶𝑒𝑒𝐺𝐺𝑎𝑎𝑔𝑔𝑒𝑒_𝐿𝐿𝑜𝑜𝑎𝑎𝑑𝑑,
pode ser consultada na Figura C.1.
Figura C.1. Distribuição do tempo de chegada dos pedidos de tráfego com uma distribuição Exponencial (à
esquerda); Distribuição cumulativa (à direita)
Distribuição de pareto generalizada A distribuição de Pareto dada por:
𝑦𝑦 = 𝑓𝑓(𝑁𝑁|𝑘𝑘,𝜎𝜎,𝜃𝜃) = 𝛼𝛼𝑥𝑥𝑚𝑚𝑥𝑥𝛼𝛼+1
,
onde 𝑁𝑁𝑚𝑚 é chamado o parâmetro de escala, e 𝛼𝛼 é o parâmetro de forma.
A simulação resultante da geração de 1000 pedidos de tráfego ODU-0, com 𝛼𝛼 = 5 e
𝑁𝑁𝑚𝑚 =𝐴𝐴𝐶𝐶𝑒𝑒𝐺𝐺𝑎𝑎𝑔𝑔𝑒𝑒_𝐷𝐷𝑀𝑀𝐺𝐺𝑎𝑎𝐶𝐶𝑖𝑖𝑜𝑜𝑛𝑛 ∗ (𝛼𝛼 − 1)
𝛼𝛼,
78
está representada na Figura C.2.
Figura C.2. Distribuição do tempo de chegada dos pedidos de tráfego com uma distribuição de Pareto (à
esquerda); Distribuição cumulativa (à direita).
Log-Normal Estamos na presença de uma distribuição Log-Normal quando o logaritmo de uma variável aleatória
tem uma distribuição normal. Esta distribuição é dada por:
𝑦𝑦 = 𝑓𝑓(𝑁𝑁; 𝜇𝜇;𝜎𝜎) =1
𝑁𝑁𝜎𝜎√2𝜋𝜋exp �−
(ln(𝑁𝑁) − 𝜇𝜇)2
2𝜎𝜎2�,
onde 𝜎𝜎 é a variância e 𝜇𝜇, a média.
A simulação resultante da geração de 1000 pedidos de tráfego ODU-0, com 𝜎𝜎 = 1 e média dada por
𝜇𝜇 =(𝐴𝐴𝐶𝐶𝑒𝑒𝐺𝐺𝑎𝑎𝑔𝑔𝑒𝑒_𝐷𝐷𝑀𝑀𝐺𝐺𝑎𝑎𝐶𝐶𝑖𝑖𝑜𝑜𝑛𝑛(𝑠𝑠) × 1.25𝐺𝐺𝑠𝑠/𝑠𝑠)
𝐴𝐴𝐶𝐶𝑒𝑒𝐺𝐺𝑎𝑎𝑔𝑔𝑒𝑒_𝐿𝐿𝑜𝑜𝑎𝑎𝑑𝑑,
está representada na Figura C.3.
Figura C.3. Distribuição do tempo de chegada dos pedidos de tráfego com uma distribuição Log-Normal (à
esquerda); Distribuição cumulativa (à direita)
79
Constante Os pedidos de tráfego gerados com tempo de chegada constante, ficam uniformemente distribuídos ao
longo do tempo, ou seja, não existe variação entre tempos de chegada. Isso pode ser constatado pelo
gráfico da esquerda, presente na Figura C.4, em que apenas existe uma sobreposição de 1000 pedidos
de tráfego num único tempo de chegada 𝐶𝐶 = 0.0003252, com rácio igual a 1. Os tempos de chegada,
neste caso, são todos dados por:
𝐶𝐶 =(𝐴𝐴𝐶𝐶𝑒𝑒𝐺𝐺𝑎𝑎𝑔𝑔𝑒𝑒_𝐷𝐷𝑀𝑀𝐺𝐺𝑎𝑎𝐶𝐶𝑖𝑖𝑜𝑜𝑛𝑛(𝑠𝑠) × 1.25𝐺𝐺𝑠𝑠/𝑠𝑠)
𝐴𝐴𝐶𝐶𝑒𝑒𝐺𝐺𝑎𝑎𝑔𝑔𝑒𝑒_𝐿𝐿𝑜𝑜𝑎𝑎𝑑𝑑,
Figura C.4. Distribuição do tempo de chegada dos pedidos de tráfego (à esquerda); Distribuição cumulativa (à
direita)
A distribuição cumulativa confirma que todos os pedidos de chegada demoram, de facto, o mesmo
tempo a serem gerados. É evidente uma variação brusca em 𝐶𝐶 = 0.0003252, em que a distribuição salta
para o rácio de valor 1.
80
81
D. Algoritmo IGABAG (exemplo de execução) A topologia física da rede a que se pretende aplicar o algoritmo de agregação IGABAG está
representada na Figura D.1.
Figura D.1. Topologia física da rede exemplo
Parte-se do pressuposto de que todos os nós possuem ODU switches, ou seja, que todos eles têm
capacidade de agregar tráfego cliente e que cada um tem dois transponders (capacidade para operar
em dois comprimentos de onda diferentes). Considera-se também que a capacidade de cada
comprimento de onda é ODU1 (2.5 Gb/s).
Tendo estes dados, constrói-se o grafo auxiliar de acordo com as especificações e instruções
encontradas na Figura D.1. O grafo auxiliar resultante está representado na Figura D.2. O primeiro
pedido 𝐷𝐷1é D(1, 0,𝑖𝑖𝐷𝐷𝑂𝑂0, 1).
Figura D.2. Grafo auxiliar da rede exemplo
Para tratar este pedido, é necessário encontrar um caminho de 𝑁𝑁14,1para 𝑁𝑁0
4,0. É visível no grafo auxiliar
que existe um caminho ao longo das arestas 𝑃𝑃𝑁𝑁𝐸𝐸(1,1),𝑊𝑊𝐿𝐿𝐸𝐸(1,0,1)𝑒𝑒 𝑅𝑅𝑁𝑁𝐸𝐸(0,1). Este caminho está
representado a negrito na Figura D.3. Uma vez que este caminho contém uma wavelength-link edge,
𝑊𝑊𝐿𝐿𝐸𝐸(1, 0, 1), é necessário estabelecer um lightpath 𝐿𝐿1 usando 𝜆𝜆1na ligação da fibra que liga o nó 1 ao
nó 0. Consequentemente, há que adicionar uma lightpath edge, 𝐿𝐿𝑃𝑃𝐸𝐸(1,0), no grafo auxiliar. Isto significa
que passa a existir um lightpath do nó 1 para o nó 0. Além disso, há que eliminar a aresta 𝑊𝑊𝐿𝐿𝐸𝐸(1, 0, 1),
dado que esta deixa de poder ser utilizada para estabelecer um outro lightpath.
82
Figura D.3. Grafo auxiliar antes de tratar o pedido de tráfego 𝐷𝐷1
Uma vez estabelecido 𝐿𝐿1, é possível encaminhar o pedido 𝐷𝐷1. A capacidade residual de 𝐿𝐿1 terá então
que ser atualizada: ODU1 – (1 x ODU0) = ODU0. Assim, a capacidade da aresta 𝐿𝐿𝑃𝑃𝐸𝐸(1,0) passa a ser
ODU0. O grafo auxiliar resultante passa a ser o da Figura D.4. O novo lightpath estabelecido está
destacado a cor laranja.
Figura D.4. Grafo auxiliar após encaminhar o pedido de tráfego 𝐷𝐷1.
Supondo que surge um segundo pedido 𝐷𝐷2 = 𝐷𝐷(2, 0,𝑖𝑖𝐷𝐷𝑂𝑂0, 1), seguindo o mesmo procedimento que
anteriormente, é necessário encontrar o caminho de 𝑁𝑁24,1 para 𝑁𝑁0
4,0. Neste caso, o caminho a escolher
depende da política utilizada para a agregação do tráfego.
Tipicamente, a utilização da estratégia de agregação de múltiplo salto (multihop grooming), apesar de
utilizar de forma mais eficiente os lightpaths já estabelecidos na rede, também aumenta o peso na
componente elétrica, onde reside o maior custo. A estratégia de único salto (single hop), permite
estabelecer um lightpath diretamente do nó 2 para o nó 0, permitindo realizar a operação num único
salto.
Para encaminhar 𝐷𝐷2 usando a estratégia de único salto, estabelecemos o caminho
𝑃𝑃𝑁𝑁𝐸𝐸(2,2),𝑊𝑊𝐿𝐿𝐸𝐸(2,1,2),𝑊𝑊𝑊𝑊𝐸𝐸(1,2),𝑊𝑊𝐿𝐿𝐸𝐸(1, 0, 2) e 𝑅𝑅𝑁𝑁𝐸𝐸(0,2), representado a negrito na Figura D.5.
Verifica-se no caminho escolhido que este atravessa a 𝑊𝑊𝐿𝐿𝐸𝐸(1, 0, 2) e 𝑊𝑊𝐿𝐿𝐸𝐸(2,1,2) que significa que o
83
comprimento de onda 𝜆𝜆2 é utilizado nas ligações de fibra do nó 2 para o nó 1 e do nó 1 para o nó 0,
respetivamente. Estabelece-se assim um lightpath entre o nó 2 e o nó 0, 𝐿𝐿𝑃𝑃𝐸𝐸(2, 0), que consiste na
utilização destas duas ligações. Mais uma vez, há que remover os 𝑊𝑊𝐿𝐿𝐸𝐸 utilizados para este efeito.
Além disso, note-se que o nó 0 deixa de poder receber mais comprimentos de onda, pelo que também
se deverá proceder à eliminação das arestas de receção 𝑅𝑅𝑁𝑁𝐸𝐸(0, 1) e 𝑅𝑅𝑁𝑁𝐸𝐸(0, 2). O grafo auxiliar
resultante é o da Figura D.6.
Figura D.5. Grafo auxiliar antes de tratar pedido 𝐷𝐷2 – Single Hop
Figura D.6. Grafo auxiliar após encaminhar 𝐷𝐷2 – Single Hop
Note-se que a ligação entre os nós 0 e 2 dá-se através de um único lightpath, 𝐿𝐿2, sendo que a
capacidade residual deste último é ODU0 (ODU1 – ODU0). Se por outro lado se pretender utilizar a
estratégia de agregação por múltiplo salto, o caminho escolhido será
𝑃𝑃𝑁𝑁𝐸𝐸(2,1),𝑊𝑊𝐿𝐿𝐸𝐸(2, 1, 1),𝑅𝑅𝑁𝑁𝐸𝐸(1, 1),𝐺𝐺𝐺𝐺𝐺𝐺𝐸𝐸(1),𝑀𝑀𝑀𝑀𝑁𝑁𝐸𝐸(1),𝐿𝐿𝑃𝑃𝐸𝐸(1,0) e 𝐷𝐷𝐺𝐺𝑁𝑁𝐸𝐸(0), representado a negrito na
Figura D.7. Este caminho contém a aresta 𝑊𝑊𝐿𝐿𝐸𝐸(2, 1, 1) que representa a ligação de fibra do nó 2 para
o nó 1, bem como o lightpath 𝐿𝐿𝑃𝑃𝐸𝐸(1, 0) anteriormente estabelecido e que liga o nó 1 ao nó 0. Será
então necessário estabelecer um novo lightpath 𝐿𝐿3 do nó 2 para o nó 1, que utiliza o comprimento de
onda 𝜆𝜆1.
Seguindo o mesmo procedimento, remove-se 𝑊𝑊𝐿𝐿𝐸𝐸(2, 1, 1) e adiciona-se 𝐿𝐿𝑃𝑃𝐸𝐸(2, 1). Poderemos agora
encaminhar o pedido 𝐷𝐷3 pelos lightpaths 𝐿𝐿1 e 𝐿𝐿3 até ao nó 2. A capacidade residual de 𝐿𝐿1 será nula, e
a de 𝐿𝐿3, ODU0.
84
Note-se que o pedido de tráfego 𝐷𝐷2 é encaminhado através de dois lightpaths, mas apenas um
comprimento de onda é utilizado para o efeito. O grafo auxiliar que resulta após o encaminhamento de
𝐷𝐷2está representado na Figura D.8.
Figura D.7. Grafo auxiliar antes de tratar pedido 𝐷𝐷2 – Multihop
Figura D.8. Grafo auxiliar após encaminhar 𝐷𝐷2 – Multihop
85
Bibliografia
[1] M. Carroll, “The Operator's View of OTN Evolution,” ITU-T Optical Transport Network, 2010.
[2] Steve Gorshe, “A Tutorial on ITU-T G.709 Optical Transport Networks (OTN),” p. 8, 2010.
[3] Nokia Siemens Networks, “Creating efficient and cost-effective optical transport networks,” em
Optical Transport Networks Switching, 2011.
[4] Cisco, “Global Mobile Data Traffic Forecast Update 2015-2020,” Cisco Visual Networking Index,
pp. 2,3, 2016.
[5] R. Morais, Planeamento e Dimensionamento de Redes de Multicamada, Tese de Doutoramento,
Universidade de Aveiro, 2015.
[6] Cisco Systems, Introduction to DWMD Technology, 2000.
[7] J. Pires, “Optical Transport Networks,” em Redes de Telecomunicações - Apontamentos , Chapter
5, 2015.
[8] R. Vaez-Ghaemi, “Next-Generation Optical Transport Networks,” JDSU, 2010.
[9] S. Whitehead, OTN - What is it and how does it work?, Anritsu, 2014.
[10] P. H. Knudsen-Baas, OTN Switching, Norwegian University of Science and Technology, 2011.
[11] A. C. P. Martins, “Traffic Grooming, Routing and Wavelength Assignment in Metropolitan Transport
Networks,” Tese de Mestrado, 2014.
[12] Transmode, WDM The Transmode Way, Transmode, 2015.
[13] Hui Zang e. al., “A Review of Routing and Wavelength Assignment Approaches for Wavelength
Routed Optical WDM Networks,” SPIE/Baltzer Science Publishers, 2000.
[14] K. Zhu, “Traffic Grooming in an Optical WDM Mesh Network,” IEEE JOURNAL ON SELECTED
AREAS IN COMMUNICATIONS, vol. 20, 2002.
[15] J. M. Simmons, “Routing Algorithms” em Optical Network Design and Planning, Springer, Chapter
3, p. 62, 2008.
[16] L. e. A. Somani, “Dynamic Wavelength Routing Using Congestion and Neighborhood Information,”
IEEE/ACM Transactions on Networking, 1999.
[17] Lu Ruan, Ding-Zhu , Optical Networks - Recent Advances, Kluwer Academic Publishers, 2001.
[18] H. Zhu, “A Novel Generic Graph Model for Traffic Grooming in Heterogeneous WDM Mesh
Networks,” IEEE/ACM TRANSACTIONS ON NETWORKING,, vol. 11, 2003.
[19] L. Chiewon e. al., “A Genetic Algorithm for Traffic Grooming in All-Optical Mesh Networks,” 2002.
[20] X. Chunsheng e. al., “Formulation of Multi-Hop Dynamic Traffic Grooming in WDM Optical
Networks,” 2006.
[21] S. A. Dominic, “Multiperiod Planning for Optical Networks,” Nokia Siemens Networks, 2010.
86
[22] S. Yang, F.Kuipers, “Traffic uncertainty models in network planning,” IEEE Communications
Magazine, vol. 52, pp. 172-177, 2014.
[23] E. Martins, “An Algorithm for Ranking Optimal Paths,” 2000.
[24] M. Loureiro, Planeamento de rede e análise de custos para redes de transporte óticas com
diferentes soluções de comutação, Instituto Superior Técnico, 2014.
[25] Z. Hongyue e. al., “Dynamic Traffic Grooming in WDM Mesh Networks Using a Novel Graph
Model,” 2003.
[26] J. Santos, “Optimized Design of Optical Transport Networks for Ethernet Traffic,” Tese de
Doutoramento, Instituto Superior Técnico, 2014.
[27] M. Tornatore, “WDM Network Optimization by ILP Based on Source Formulation,” IEEE
INFOCOM, 2002.
[28] M. Pickavet, “Long-Term Planning of WDM Networks: A Comparison between Single-Period and
Multi-Period Techniques,” Kluwer Academic Publishers, Boston, 1999.
[29] B. Alan. a. J. Rouse, “Optical Transport Networks - Evolution, Not Revolution,” OPTera Metro
Solutions White Paper, 2000.
[30] K. Ramasamy, Deepankar Medhi, “Algorithms, Protocols and Archtectures,” em Network Routing,
Morgan Kaufman, p. 50, 2007.
![3 Compensador estático de reativo [2]](https://img.document.onl/doc/110x75/5870c5cc1a28abb8548bf528/3-compensador-estatico-de-reativo-2.jpg)
