Algoritmos para Roteamento e Alocação de Espectro em … · ALEX FERREIRA DOS SANTOS Algoritmos para Roteamento e Alocação de Espectro em Redes Ópticas Elásticas Tese de doutorado

UNIVERSIDADE FEDERAL DA BAHIA

ESCOLA POLITÉCNICA DA UNIVERSIDADE FEDERAL DA BAHIA

DEPARTAMENTO DE ENGENHARIA ELÉTRICA

PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA

ALEX FERREIRA DOS SANTOS

Algoritmos para Roteamento e Alocação de Espectro em Redes

Ópticas Elásticas

Salvador – BA

2015


Algoritmos para Roteamento e Alocação de Espectro em Redes

Ópticas Elásticas

Tese de doutorado apresentada ao Programa de Pós-

Graduação em Engenharia Elétrica (PPGEE), da

Escola Politécnica da Universidade Federal da Bahia –

UFBA, como parte dos requisitos para a obtenção do

título de Doutor em Engenharia Elétrica.

Linha de Pesquisa: Processamento e Transmissão

da Informação

Orientador: Prof. Dr. Karcius Day Rosário Assis

Co-Orientador: Prof. Dr. Raul Camelo de Andrade

Almeida Júnior

Salvador – BA

2015

UNIVERSIDADE FEDERAL DA BAHIA – UFBA

DEPARTAMENTO DE ENGENHARIA ELÉTRICA – DEE

PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA – PPGEE

Algoritmos para Roteamento e Alocação de Espectro em Redes Ópticas Elásticas

Por:


Tese de doutorado submetida à banca examinadora designada pelo Colegiado do Programa de Pós-graduação em

Engenharia Elétrica, com vistas à obtenção do título de Doutor em Engenharia Elétrica.

Aprovada em 13 / 01/ 2015

BANCA EXAMINADORA

Prof. Dr. Karcius Day Rosário Assis (Orientador)

Universidade Federal da Bahia – UFBA

Prof. Dr. Raul Camelo de Andrade Almeida Júnior (Co-orientador)

Universidade Federal de Pernambuco – UFPE

Prof. Dr. Gustavo Bittencourt Figueiredo


Prof. Dr.Vitaly Félix Rodríguez Esquerre


Prof. Dr. José Valentim dos Santos Filho

Universidade Federal do Recôncavo da Bahia – UFRB

Prof. Dr. Darli Augusto de Arruda Mello

Universidade Estadual de Campinas – UNICAMP

Salvador/2015

RESUMO

Em uma rede óptica elástica, também conhecida como SLICE (Spectrum-Sliced

Elastic Optical Path Network), os recursos espectrais são divididos em slots de frequência

com fina granularidade. Isto é feito para atender de forma mais eficiente às requisições de

diferentes larguras de banda da Internet. Para o estabelecimento de uma conexão é necessário

definir os caminhos ópticos e realizar a alocação dos recursos espectrais. Então, é essencial

para a inserção dos caminhos ópticos na rede resolver o problema de roteamento e alocação

de espectro (RSA – Routing and Spectrum Allocation). Este pode ser resolvido utilizando

heurística, que tem o intuito de melhorar a utilização dos recursos, bem como reduzir o

desperdício de banda. O problema RSA pode ser classificado, quanto ao tráfego, como

estático ou dinâmico. Em relação ao RSA estático, duas heurísticas foram propostas no

sentido de reduzir a quantidade de slots utilizados na rede, para topologias de pequena e

grande dimensão, com tráfego uniforme e não uniforme. Estas heurísticas tentam balancear a

carga da rede, de forma que os recursos espectrais sejam minimamente utilizados, com o

intuito de preservar a capacidade da rede para demandas futuras. Para este cenário, foi

desenvolvido um simulador, com interface gráfica, para facilitar o estudo sobre redes ópticas

elásticas. Para o RSA dinâmico, três heurísticas foram propostas para rede SLICE, duas para o

roteamento e uma para alocação de espectro. As heurísticas de roteamento tentam balancear a

carga da rede e, com isso, obtêm melhores caminhos para estabelecer as conexões. A

heurística de alocação de espectro calcula a perda de capacidade na alocação de slots, e os

resultados mostram sua eficiência, quando comparada a outros algoritmos na literatura. Ao

final, foram analisadas diversas topologias de redes, com o intuito de verificar a relação entre

estas e as probabilidades de bloqueio.

Palavras-chave: Redes SLICE, Roteamento e Alocação de Espectro, Redes Ópticas,

Otimização.

ABSTRACT

In Elastic Optical Network, also known as SLICE (Spectrum-sliced Elastic Optical

Path Networks), the spectrum resources are divided in frequency slots with fine granularity.

This is done to respond more efficiently to requests for different Internet bandwidths. To

establish a connection, it is necessary to define the optical paths and making the allocation of

spectrum resources. So, it is essential to insert the optical paths in the network to solve the

Routing and Spectrum Allocation problem (RSA). This can be solved using heuristics, which

aims to improve the use of resources and reduce the waste of bandwidth. The RSA problem

can be classified, as the traffic, such as static or dynamic. Regarding the static RSA two

heuristics have been proposed to reduce the number of slots used in network for small and

large topologies with uniform and non-uniform traffic. These heuristics try to balance the

network load, so that the spectrum resources are minimally used, in order to preserve the

ability of the system to future demands. For this scenario, a simulation was developed with a

graphical interface to facilitate the study of elastic optical networks. For dynamic RSA three

heuristics have been proposed for SLICE network, two for routing and one for spectrum

allocation. The routing heuristics try to balance the network load and thereby achieve better

ways to establish connections. The heuristic of spectrum allocation calculates the loss of

capacity allocation slots, and the results show its efficiency as compared to other algorithms

in the literature. At the end, several network topologies were analyzed, in order to verify the

relationship between them and the blocking probabilities.

Keywords: SLICE Networks, Routing and Spectrum Assignment, Optical Networks,

optimization.

SUMÁRIO

1. INTRODUÇÃO .................................................................................................................. 12

1.1 Artigos publicados durante a realização desta pesquisa ................................................. 18

2. REDES ÓPTICAS ELÁSTICAS ...................................................................................... 20

2.1 REDES ÓPTICAS ELÁSTICAS ................................................................................... 20

2.2 REDE SLICE .................................................................................................................. 21

2.2.1 Comparação entre as Redes Ópticas SLICE e WDM.............................................. 25

2.2.2 Problema de Roteamento e Alocação de Espectro em Redes SLICE ..................... 27

2.2.2.1 Roteamento de Espectro em Rede SLICE ......................................................... 27

2.2.2.2 Alocação de Espectro em Rede SLICE ............................................................. 29

3. ROTEAMENTO E ALOCAÇÃO DE ESPECTRO PARA TRÁFEGO ESTÁTICO 31

3.1 RSA ESTÁTICO ............................................................................................................ 31

3.2 HEURÍSTICAS PARA O PROBLEMA RSA ESTÁTICO ........................................... 32

3.2.1 BSR (Best among the Shortest Routes) ................................................................... 32

3.2.2 ILR (Iterative Load Routing) ................................................................................... 35

3.3 RESULTADOS NUMÉRICOS ................................................................................ 37

3.3.1 Simulação para Redes de Pequena Dimensão ......................................................... 37

3.3.2 Simulação para Redes de Grande Dimensão ........................................................... 39

3.3.2.1Demanda de Tráfego Uniforme ......................................................................... 40

3.3.2.2 Demanda de Tráfego Não Uniforme ................................................................ 42

4. ROTEAMENTO E ALOCAÇÃO DE ESPECTRO PARA TRÁFEGO DINÂMICO 44

4.1 RSA DINÂMICO ........................................................................................................... 44

4.2 HEURÍSTICAS PARA O ROTEAMENTO DE ESPECTRO ....................................... 46

4.2.1 BSR .......................................................................................................................... 46

4.2.2 BSR Adaptado ......................................................................................................... 46

4.2.2.1 Resultados Numéricos do BSR Adaptado ......................................................... 48

4.2.3 YBS (Yen-BSR-SLICE) .......................................................................................... 52

4.2.3.1 Resultados Numéricos ...................................................................................... 55

4.3 HERUÍSTICAS PARA ALOCAÇÃO DE ESPECTRO ................................................ 58

4.3.1 MSCL (Min Slot-Continuity Capacity Loss) ........................................................... 58

4.3.1.1Resultados Numéricos ....................................................................................... 64

5. CONCLUSÕES .................................................................................................................. 67

5.1 TRABALHOS FUTUROS ............................................................................................. 68

REFERÊNCIAS...................................................................................................................... 71

APÊNDICE A ......................................................................................................................... 81

A. SimRSA: SIMULADOR DE ROTEAMENTO E ALOCAÇÃO DE ESPECTRO

PARA REDES ÓPTICAS SLICE ......................................................................................... 81

APÊNDICE B .......................................................................................................................... 90

B. ANÁLISE DE TOPOLOGIAS ......................................................................................... 90

LISTA DE FIGURAS

Figura 1.1. Tráfego global de Internet (adaptada de [2]). Copyright © 2014 Cisco. ............... 12

Figura 1.2. Arquitetura de uma rede óptica elástica (adaptada de [6] e [49]). Copyright ©

2009 IEEE................................................................................................................................. 14

Figura 1.3. Arquitetura ROADM de grau 3 com colorless e directionless (adaptada de [48]).

Copyright © 2008 IEEE. .......................................................................................................... 15

Figura 1.4. Alocação de espectro da rede WDM tradicional e SLICE (adaptada de [6]).

Copyright © 2009 IEEE. .......................................................................................................... 16

Figura 2.1. Exemplo do diagrama de constelação da modulação QAM (adaptado de [53]).

Copyright © 2010 IEEE. .......................................................................................................... 21

Figura 2.2. Alcance de transmissão por taxa de bits (adaptado de [10]). Copyright © 2014

Springer .................................................................................................................................... 22

Figura 2.3. Taxa de transmissão em função do número de slots alocados (adaptado de [4]).

Copyright © 2014 IEEE. .......................................................................................................... 23

Figura 2.4. Esquema de especificação de recursos espectrais (a) grade de frequência ITU-T

WDM [54] (b) slots de frequência (adaptado de [55]). Copyright © 2010 IEEE. ................... 24

Figura 2.5. Representação funcional de um WSS (adaptado de [56]). Copyright © 2008

JDSU. ........................................................................................................................................ 25

Figura 2.6. Conceito de BV-WSS (adaptado de [6]). Copyright © 2009 IEEE. ...................... 25

Figura 2.7. Espectro de rede (a) WDM tradicional (b) SLICE (adaptado de [35]). Copyright ©

2013 IEEE................................................................................................................................. 26

Figura 2.8. Um exemplo de alocação de espectro em uma rede SLICE (adaptado de [16]).

Copyright © 2013 IEEE. .......................................................................................................... 30

Figura 3.1. Algoritmo BSR (a) quatro possíveis caminhos entre o nó origem 1 e destino 4 (b)

número de slots alocados na rede SLICE (c) valor c(l)i para cada enlace da rede (d) custo para

cada caminho (e) caminho escolhido........................................................................................ 34

Figura 3.2. Fluxograma do algoritmo BSR .............................................................................. 35

Figura 3.3. Algoritmo ILR (a) Caminhos roteados na rede (b) o caminho de espectro de cor

azul tem a maior quantidade de caminhos compartilhados (c) caminho de espectro de cor azul

foi removido (d) número de slots alocados na rede SLICE (e) caminho de espectro de cor azul

foi realocado. ............................................................................................................................ 36

Figura 3.4. Topologias de redes pequenas ................................................................................ 37

Figura 3.5. Número máximo de slots alocados em uma fibra da rede, para o tráfego não

uniforme, pela demanda de tráfego (slots). .............................................................................. 39

Figura 3.6. Topologias das redes NSFNet e EON. ................................................................... 40

Figura 3.7. Número máximo de slots alocados em uma fibra da rede com uma banda de

guarda entre caminhos de espectro distintos. ........................................................................... 40

Figura 3.8. Número máximo de slots alocados em uma fibra da rede com duas bandas de

guarda entre caminhos de espectro distintos. ........................................................................... 41

Figura 3.9. Número máximo de slots alocados em uma fibra da rede com três bandas de

guarda entre caminhos de espectro distintos. ........................................................................... 41 Figura 3.10. Número máximo de slots alocados em uma fibra das redes NSFNet e EON para o

tráfego não uniforme. ............................................................................................................... 42

Figura 3.11. Número de slots alocados, em cada enlace da rede NSFNet, das heurísticas BSR

e ILR. ........................................................................................................................................ 43

Figura 3.12. Número de slots alocados, em cada enlace da rede EON, das heurísticas BSR e

ILR. ........................................................................................................................................... 43

Figura 4.1. BSR adaptado. ........................................................................................................ 47

Figura 4.2. Topologias das redes, Brasileira e Abilene. ........................................................... 49

Figura 4.3. Probabilidade de Bloqueio de Caminhos (a) e Probabilidade de Bloqueio de Slots

(b) em função da carga da rede para os algoritmos Dijkstra, BSR e BSR Adaptado na rede

NSFNet. As requisições são de 1, 2, 3, ..., 8 slots e há um total de 128 slots disponíveis por

enlace. ....................................................................................................................................... 49



EON. As requisições são de 1, 2, 4 ou 8 slots e há um total de 128 slots disponíveis por

enlace. ....................................................................................................................................... 50



Brasileira. As requisições são de 1, 2, 3,..., 16 slots, e há um total de 256 slots disponíveis por

enlace. ....................................................................................................................................... 51



Abilene. As requisições são de 1, 2, 4, 8 ou 16 slots, e há um total de 256 slots disponíveis por

enlace. ....................................................................................................................................... 51

Figura 4.7. Algoritmo YBS (a) quatro possíveis caminhos entre o nó origem 1 e destino 4 (b)

número de slots alocados na rede SLICE (c) valor c(l)i para cada enlace da rede (d) custo para

cada caminho (e) caminhos escolhidos. ................................................................................... 53

Figura 4.8. Fluxograma do algoritmo YBS .............................................................................. 55

Figura 4.9. Probabilidade de bloqueio para os valores de k igual a 2, 4, 6, 8 e 10 ................... 56

Figura 4.10. Número de slots alocados por fibra para k=10 ..................................................... 57

Figura 4.11. Evolução da probabilidade de bloqueio do algoritmo YBS para cada valor de k.

.................................................................................................................................................. 58

Figura 4.12. Probabilidade de bloqueio por k. .......................................................................... 58

Figura 4.13. Vetor disponibilidade de uma rota r..................................................................... 60

Figura 4.14. Possibilidades de alocação de slots ...................................................................... 61

Figura 4.15. Número de possibilidades de alocação de slots requisitados no exemplo da

Figura 4.14 ................................................................................................................................ 61

Figura 4.16. Exemplo de dois caminhos que interferem com r ................................................ 62

Figura 4.17. Exemplo da operação booleana e (and) realizada na Equação (4.2) .................... 63

Figura 4.18. Exemplo da perda de capacidade ......................................................................... 64


(b) em função da carga da rede para os algoritmos RD, First-Fit, e MSCL na rede NSFNet.

As requisições são de 1, 2, 3,..., 32 slots, e há um total de 256 slots disponíveis por enlace. .. 65


(b) em função da carga da rede para os algoritmos RD, First-Fit, e MSCL na rede EON. As

requisições são de 1, 2, 4, 8, 16 slots, e há um total de 128 slots disponíveis por enlace. ....... 66

Figura A.1: Fluxo de processo do SimRSA ............................................................................. 81

Figura A.2. Tela inicial do SimRSA......................................................................................... 82

Figura A.3. Grupo de modelagem do SimRSA ........................................................................ 82

Figura A.4. Grupo de parâmetros de enlace do SimRSA ......................................................... 83

Figura A.5. Lista de heurísticas disponíveis no SimRSA......................................................... 83

Figura A.6. Grupo de parâmetros das heurísticas do SimRSA ................................................ 83

Figura A.7. Tela de configuração da matriz de tráfego do SimRSA. ....................................... 84

Figura A.8. Agrupamento por GB do relatório do SimRSA .................................................... 84

Figura A.9. Primeira tabela do relatório do SimRSA ............................................................... 85

Figura A.10. Segunda tabela do relatório do SimRSA ............................................................. 85

Figura A.11. Gráfico de slots alocados por enlace do relatório do SimRSA ........................... 86

Figura A.12. Gráfico comparativo dos resultados das heurísticas do relatório do SimRSA .... 86

Figura A.13. Topologia da rede NFSNet pré-definida no SimRSA ......................................... 87

Figura A.14. Gráfico comparativo da rede NFSNet com tráfego igual a 1 slot gerado pelo

SimRSA .................................................................................................................................... 87

Figura A.15: Gráfico comparativo da rede NFSnet com tráfego igual a 2 slots gerado pelo

SimRSA .................................................................................................................................... 88

Figura A.16: Gráfico comparativo da rede NFSnet com tráfego igual a 3 slots gerado pelo

SimRSA .................................................................................................................................... 88

Figura A.17. Número máximo de slots alocados na rede pelo tráfego da rede [16]. Copyright

© 2011 IEEE. ........................................................................................................................... 88

Figura A.18. Topologias pré-definidas no simulador. .............................................................. 89

Figura B.1. Topologia Física da rede EON (European Optical Network). Copyright © 2010

IEEE.......................................................................................................................................... 90

Figura B.2. Probabilidade de Bloqueio para topologias de redes analisadas utilizando o

algoritmo BSR Adaptado.......................................................................................................... 92

Figura B.3. Distribuição dos graus dos nós na rede. ................................................................ 92

LISTA DE TABELAS

Tabela 2.1. Comparação entre diferentes tecnologias propostas (fonte [9]) ............................ 21

Tabela 2.2. Comparação entre formatos de modulação, capacidade de slots e alcance de

transmissão (adaptado de [24]). Copyright © 2012 IEEE. ...................................................... 23

Tabela 3.1. Resultados das Simulações para Redes Pequenas: R4 e R5 (anel), R6 (Malha) ... 38

Tabela 3.2. Resultados da alocação de slots para cada enlace da rede de 5 nós em anel ......... 38

Tabela 3.3. Matriz de Tráfego para Rede de 5 Nós .................................................................. 39

Tabela 3.4. Matriz de Tráfego para Rede NSFNet e EON ....................................................... 42

Tabela 4.1. Caminhos específicos por slots .............................................................................. 47

Tabela 4.2. Dados de alocação do algoritmo de Yen ............................................................... 57

Tabela 4.3. Dados de alocação do algoritmo de YBS .............................................................. 57

Tabela B.1. Topologias de redes analisadas [81], [82]. ............................................................ 91

Tabela B.2. Topologias de redes analisadas. ............................................................................ 93

LISTA DE ACRÔNIMOS

BLSA Balanced Load Spectrum Allocation

BPSK Binary Phase Shift Keying

BSR Best among the Shortest Routes

BV Bandwidth-Variable

BVT Bandwidth-Variable Transponders

BV-WSS Bandwidth-Variable Wavelength-Selective Switch

BV-WXC Bandwidth-Variable Wavelength Cross-Connects

CAGR Compound Annual Growth Rate

CSS Cascading Style Sheets

DJK Dijkstra

DWDM Dense Wavelength Division Multiplexing

EON European Optical Network

FF First-Fit

FWDM Flexible Optical Wavelength Division Multiplexing

FWM Four-Wave Mixing

GB Guard-Band

HDTV High Definition Television

HSMR Hybrid Single-/Multi-path Routing

HTML HyperText Markup Language

ILP Integer Linear Programming

ILR Iterative Load Routing

ISP Internet Service Provider

KSP k-Shortest Path

LCoS Liquid Crystal on Silicon

LP Linear Programming

LUSF Least Unusable Spectrum First

MCP-ZBA Maximum Capacity Path and ZoneBased Assignment

MILP Mixed-Integer Linear Programming

MRSA Maximum Reuse Spectrum Allocation

MSCL Min Slot-Continuity Capacity Loss

NP Non-deterministic Polynomial time

NSFNet National Science Foundation Network

OFDM Orthogonal Frequency-Division Multiplexing

O-OFDM Optical Orthogonal Frequency-Division Multiplexing

OSNR Optical Signal-to-Noise Ratio

P2P Peer-to-Peer

QAM Quadrature Amplitude Modulation

QPSK Quadrature Phase Shift Keying

RC Rotas Candidatas

RD Random

RMSA Routing, Modulation-Level, and Spectrum Assignment

ROADM Reconfigurable Optical Add/Drop Multiplexer

RRT Restricted Routing Technique

RSA Routing and Spectrum Allocation

RWA Routing and Wavelength Assignment

SLICE Spectrum-Sliced Elastic Optical Path Network

SPSR Shortest Path with Maximum Spectrum Reuse

VoIP Voice over Internet Protocol

WDM Wavelength Division Multiplexing

WSS Wavelength-Selective Switch

WXC Wavelength Cross-Connects

XPM Cross-Phase Modulation

YBS Yen-BSR-SLICE

12

CAPÍTULO 1

1. INTRODUÇÃO

Cada vez mais os diversos serviços existentes ou emergentes na Internet (e.g. televisão

via Internet, vídeo sob demanda, aplicações peer-to-peer e redes privadas virtuais) têm

impulsionado uma demanda crescente de largura de banda nos backbones dos sistemas de

comunicações [1]. Segundo a Cisco [2], o tráfego global da Internet atingirá 1,6 zettabytes1

por ano ou 131,9 exabytes2 por mês em 2018 (Figura 1.1). Este tráfego se eleva a uma taxa

composta de crescimento anual (CAGR – Compound Annual Growth Rate) de 21 por cento,

de 2013 a 2018.

Figura 1.1. Tráfego global de Internet (adaptada de [2]). Copyright © 2014 Cisco.

Para atender a esta demanda, os provedores de serviços de Internet (ISP – Internet

Service Provider) têm utilizado a tecnologia DWDM (Dense Wavelength Division

Multiplexing), que transmite alta taxa de bits com canais operando de 40 Gbps a 100 Gbps

[3]. Entretanto, essa tecnologia permite dividir o espectro em faixas de largura de banda fixa

de 50 GHz e, desta forma, impõe rigidez nas taxas de transmissão em cada comprimento de

onda [4].

Devido à Internet, novos aplicativos e tecnologias estão surgindo com necessidades

1 Unidade de medida de informação, cujo símbolo é ZB. 1 ZB equivale a 2

70 bytes ou aproximadamente 10

21

bytes. 2 Unidade de medida de informação, cujo símbolo é EB. 1 EB equivale a 2

60 bytes ou aproximadamente 10

18

bytes.

2013 2014 2015 2016 2017 20180

20

40

60

80

100

120

140

132

110

91

76

62

51

Exab

yte

s/m

ês

13

heterogêneas de largura de banda. Enquanto e-mails ou mensagens instantâneas requerem

pouca demanda de taxa de transmissão, outras aplicações como HDTV (High Definition

Television) e P2P (Peer-to-Peer) requerem taxas na ordem de Gbps. Essa diversidade exige

uma rede de transporte com alocação de banda flexível.

A alocação de slots de largura de banda fixa, empregada nas redes WDM (Wavelength

Division Multiplexing), reduz a eficiência na utilização dos recursos da rede. Por exemplo,

quando a demanda de tráfego é menor do que a capacidade de um comprimento de onda, toda

faixa de comprimento de onda será alocada para acomodar a demanda e, desta forma, uma

parte da banda é desperdiçada. Além disso, quando uma demanda de tráfego requer uma

largura de banda superior à disponibilizada por um comprimento de onda, não é possível

alocá-la na rede, já que a filtragem fixa presente nas redes WDM exige a largura máxima de

um comprimento de onda para as conexões na rede.

A técnica conhecida como agregação de tráfego (traffic grooming) possibilita às redes

WDM alocar múltiplas requisições, cada qual com baixas taxas de dados, em um caminho

com alta capacidade. No entanto, essa técnica não elimina completamente o desperdício de

largura de banda e implica em overhead e perda de transparência [5].

Recentemente, muitos estudos estão sendo realizados com uma nova estratégia para o

planejamento de redes ópticas [3]-[35]. Esta estratégia propõe um método mais flexível de

alocação de espectro para as redes ópticas. O método mostra que uma alocação de espectro

com largura de banda variada e espaçamento diferente entre os canais, ou seja, ―Gridless‖ é

mais eficiente que o método tradicional. Esta nova proposta, comumente baseada no sistema

de transmissão O-OFDM (Optical Orthogonal Frequency-Division Multiplexing) [14]-[23],

[35] e Nyquist-WDM [36]-[38], também é conhecida como SLICE (Spectrum-Sliced Elastic

Optical Path Network) [6] ou Redes Ópticas Elásticas [35].

As redes SLICE alocam a quantidade necessária dos recursos espectrais com uma

granularidade mais fina, ou seja, o espectro é dividido em um conjunto de slots com largura

espectral de 12,5 GHz [12], [39], [40], embora já existam pesquisas sobre a utilização de 6.25

GHz [11], [34]-[41] e 3.125 GHz [3], [46], [47]. Isto é feito para atender de forma mais

eficiente às requisições de diferentes larguras de banda. Assim, os canais podem conter

larguras de banda variáveis, podendo inclusive haver contração ou expansão de sua largura de

banda, na dependência da necessidade dos fluxos a serem transmitidos.

É importante ressaltar que um caminho óptico pode ser agora estabelecido por meio de

um determinado número de slots de frequência, a depender da taxa de transmissão desejada e

14

do formato de modulação utilizado. Para suportar o conceito desta nova arquitetura de rede,

duas tecnologias são utilizadas: Os BVTs (Bandwidth-Variable Transponders) e ROADMs

(Reconfigurable Optical Add/Drop Multiplexer). Os BVTs são responsáveis por ajustar os

recursos ópticos conforme a demanda requisitada e localizam-se na borda da rede. Os

ROADMs localizam-se no núcleo da rede e são encarregados de estabelecer um caminho

óptico fim-a-fim, que pode variar a largura de banda para acomodar flutuações nas larguras de

banda das conexões. Estas têm sido as propostas para permitir a flexibilidade na atribuição do

espectro no domínio óptico (Figura 1.2) [6], [28]-[30], [48]-[50].

Figura 1.2. Arquitetura de uma rede óptica elástica (adaptada de [6] e [49]). Copyright © 2009 IEEE.

Uma arquitetura ROADM com grau 3 pode ser observada na Figura 1.3. O grau de um

nó depende do número de enlaces de entrada e saída. Neste nó, tem-se dois conjuntos

add/drop ajustáveis (colorless), e os canais proveniente de uma direção são distribuídos para

as demais direções atráves de um splintter e selecionados por meio de um WSS (Wavelength-

Selective Switch). Desta forma, os canais adicionados ou retirados localmente podem seguir

ou vir de qualquer direção, por esse motivo essa arquitetura é chamada directionless.

ROADM

ClienteCliente BVT

15

Figura 1.3. Arquitetura ROADM de grau 3 com colorless e directionless (adaptada de [48]). Copyright © 2008

IEEE.

As principais características da rede SLICE são a segmentação e agregação de

recursos espectrais, acomodações eficientes de múltiplas taxas de dados, bem como a variação

elástica de recursos alocados, conforme pode ser observado na Figura 1.4. Para realizar a

alocação em uma rede WDM (Figura 1.4 (a)), deve-se utilizar a capacidade total da faixa

associada de um comprimento de onda no percurso fim-a-fim. Na rede SLICE (Figura 1.4

(b)), um sinal óptico é gerado com a utilização apenas dos recursos espectrais suficientes para

transmitir o sinal do cliente, o que permite melhorar a utilização dos recursos e reduzir o

desperdício de banda. Além disso, na rede SLICE, como também na WDM, pode-se utilizar

diferentes formatos de modulação e aumentar assim a eficiência espectral [13].

WSSSaída

Entrada

Splitter

WSS CombinadorE

ntr

ad

a

WS

SS

aíd

a

Oeste

Norte

Leste

WSSSaída

Entrada

Rx Rx Rx Rx

Drop

Tx Tx Tx Tx

Add

WSS Combinador

Rx Rx Rx Rx

Drop

Tx Tx Tx Tx

Add

16

Figura 1.4. Alocação de espectro da rede WDM tradicional e SLICE (adaptada de [6]). Copyright © 2009 IEEE.

Ao melhorar a estratégia de alocação de recursos às requisições, tem-se uma

quantidade maior de atendimento às demandas. Nas redes WDM, o problema de alocação de

recursos é conhecido como roteamento e alocação de comprimentos de onda (RWA – Routing

and Wavelength Assignment) [31]. Na rede SLICE, este problema é chamado de roteamento e

alocação de espectro (RSA – Routing and Spectrum Allocation) [16]-[22]. Nessa, é alocada

uma porção do espectro ou um conjunto de slots para atender a demanda de tráfego. O RSA é

diferente e mais desafiador do que o problema RWA, principalmente pelo fato de os caminhos

ópticos poderem utilizar diferentes granularidades espectrais. Em uma rede sem conversão

espectral, a restrição de continuidade de comprimento de onda é transformada em restrição de

continuidade de espectro e a porção do espectro alocada para a conexão deve ser mantida ao

longo dos enlaces da rota de forma contínua. Adicionalmente, o RSA apresenta a restrição de

contiguidade, cujos slots de um caminho óptico devem ser consecutivas, ou seja, os slots de

frequência atribuídos a uma conexão devem ser contíguos no espectro ao longo dos enlaces

em sua rota.

O problema RSA pode ser classificado em estático (off-line) e dinâmico (on-line). No

primeiro, as requisições são previamente conhecidas e, posteriormente, define-se por onde

encaminhar as demandas de tráfego, ou seja, qual a rota e a faixa de frequência a ser utilizada

para cada demanda. Neste caso, pode-se ter como objetivo reduzir a quantidade de slots

necessários para atender as demandas. No segundo, as requisições dos clientes chegam

dinamicamente, e os recursos espectrais são alocados e liberados com a rede óptica em

operação. Neste contexto de maior dinamismo, as requisições chegam sob demanda, e o

17

objetivo geral é reduzir a probabilidade de bloqueio das futuras requisições.

Assim como o RWA [31], o RSA é um problema NP-Completo [14]-[16] e, desta

maneira, várias heurísticas têm sido propostas para otimizar a alocação de espectro [14]- [22].

Nesta tese, são propostas heurísticas para o problema de roteamento e alocação de espectro

para os cenários estático e dinâmico.

A metodologia proposta neste trabalho, resumidamente, consiste em:

Para RSA estático: Propor duas heurísticas, que inicialmente foram

desenvolvidas para as redes WDM, e neste trabalho adaptadas para as redes

SLICE. Os resultados numéricos comprovam a eficiência destas heurísticas

para este novo cenário de rede. Para avaliar o desempenho, foi analisada a

quantidade de slots alocados na rede, para o tráfego uniforme e não uniforme,

com a variação da demanda de tráfego e a banda de guarda. Também foi

desenvolvido um simulador, com interface gráfica, para a rede óptica SLICE.

Para RSA dinâmico: Reduzir a probabilidade de bloqueio de requisições. Para

isso, foram propostas três heurísticas, duas para o roteamento e uma para a

alocação de espectro. Na primeira, os caminhos ópticos são definidos com

base nas requisições com diferentes larguras de banda, e desta forma, para

cada largura de banda solicitada, tem-se um caminho óptico específico. Na

segunda, é realizado o roteamento fixo-alternativo para k caminhos mais

curtos, buscando-se o valor máximo de k (k limite), ou seja, o valor cujo

aumento do número de caminhos entre a origem e destino não impacta na

probabilidade de bloqueio. Também foram analisadas outras métricas de

comparação para verificar a eficiência do algoritmo proposto. Por fim, foram

proposta uma heurística de alocação de espectro para reduzir a perda de

capacidade da rede, um novo conceito desenvolvido para redes SLICE, o que

permite melhorar a eficiência no uso dos recursos espectrais.

Ao final, são analisadas diversas topologias de rede, com o intuito de verificar

a influência destas na probabilidade de bloqueio. Para isto, foram

investigados a probabilidade de bloqueio, o grau médio dos nós e a

distribuição deles na rede.

Os próximos capítulos estão organizados da seguinte forma:

O Capítulo 2 aborda as principais características das redes ópticas SLICE. No Capítulo

3, é apresentado o problema de roteamento e alocação de espectro para o cenário estático.

18

Neste, são abordadas as duas heurísticas adaptadas para o roteamento em SLICE, além de

resultados numéricos que comprovam a eficiência das propostas. No Capítulo 4, são propostas

as heurísticas para o problema de roteamento e alocação de espectro no cenário dinâmico. Por

fim, o Capítulo 5 destina-se às conclusões e trabalhos futuros.

1.1 Artigos publicados durante a realização desta pesquisa

Artigos completos publicados em periódicos:

A. F. Santos, R.C. Almeida Jr and, K.D.R. Assis, ―YEN-BSR: A new approach for the choice

of routes in WDM networks‖. Journal of Optical Communications, v. 35, p. 293-296, 2014.

R.C. Almeida Jr, A.F. Santos, K.D.R. Assis, H. Waldman and J.F. Martins-Filho. ―Slot

assignment strategy to reduce loss of capacity of contiguous-slot path requests in flexible grid

optical networks‖. Electronics Letters (Online), v. 49(5), p. 359-361, Fevereiro, 2013.

Trabalhos completos publicados em anais de congressos:

A. F. Santos, G. S. Couto Júnior, R. H. C. Maniçoba, K.D.R. Assis, R.C. Almeida Jr,

―SimRSA: An Education Tool for Network Planning in Spectrum-Sliced Elastic Optical Path

Networks‖. 16th

International Conference on Transparent Optical Network (ICTON), Graz,

Austria, p. 1-4, Julho, 2014.

K.D.R. Assis, A. F. Santos, R. C. Almeida Jr, ―Optimization in spectrum-sliced optical

networks‖. SPIE Photonics West - Optical Metro Networks and Short-Haul Systems VI, São

Francisco, Estados Unidos, Fevereiro, 2014.

A. F. Santos, G. S. Couto Júnior, R. H. C. Maniçoba, K.D.R. Assis, R.C. Almeida Jr,

―SimRSA: Simulador de Roteamento e Alocação de Espectro para redes ópticas SLICE‖. In:

16º SBMO – Simpósio Brasileiro de Micro-ondas e Optoeletrônica e 11º CBMag – Congresso

Brasileiro de Eletromagnetismo (MOMAG), Curitiba, Brasil, 2014.

19

Alex F. Santos, Raul C. Almeida Jr, Karcius D. R. Assis, Gilvan M. Durães, André Soares e

William F. Giozza. ―Adaptação do Algoritmo BSR para Redes Ópticas SLICE‖. 31º Simpósio

Brasileiro de Redes de Computadores e Sistemas Distribuídos (SBRC), Florianópolis, Brasil,

2013.

Alex F. Santos, Clecio C. Santos, Gilvan M. Durães, Karcius D. R. Assis. ―Heuristics for

Routing in Spectrum-Sliced Elastic Optical Path Networks‖. 10th International Conference on

Optical Internet (COIN2012), Yokohama, Japão, 2012.

A. F. Santos, Clecio C. Santos, Gilvan M. Durães; Karcius D. R. Assis. ―Heurísticas para o

Roteamento e Alocação de Espectro em Redes Ópticas SLICE‖. MOMAG (15º SBMO

Simpósio Brasileiro de Micro-ondas e Optoeletrônica e o 10º CBMag Congresso Brasileiro de

Eletromagnetismo), 2012, João Pessoa, Brasil, 2012.

A. F. Santos, Clecio C. Santos, Gilvan M. Durães, Karcius D. R. Assis, Raul C. Almeida Jr.

―Roteamento e Alocação de Espectro em Redes Ópticas: O Conceito SLICE‖. In: XXX

Simpósio Brasileiro de Telecomunicações (SBrT'12), Brasília, Brasil, 2012.

20

CAPÍTULO 2

2. REDES ÓPTICAS ELÁSTICAS

Nos últimos anos, as operadoras de telecomunicações têm mostrado interesse em

fornecer aos clientes diversos serviços que requerem grande largura de banda, dentre eles,

HDTV (High Definition Television), videoconferência e VoIP (Voice over Internet Protocol).

Para isto, é necessário utilizar uma arquitetura de rede óptica capaz de suportar essa grande

demanda de dados. Atualmente, as tecnologias de redes ópticas WDM e SLICE são apontadas

como os principais veículos para suportar essa demanda de tráfego. Logo, neste capítulo, será

apresentada a rede óptica SLICE e suas principais características.

2.1 REDES ÓPTICAS ELÁSTICAS

Para atender as futuras demandas de tráfego da Internet, que estão na ordem de Gbps,

chegando a Tbps, novas arquiteturas de redes ópticas surgem com o intuito de tornar flexível

a alocação dos recursos espectrais. Com isto, busca-se reduzir custos e melhorar a utilização

dos recursos da rede. Em [35] são apresentadas três principais tecnologias de redes que

utilizam o espectro óptico de forma flexível, são elas: SLICE (Spectrum-Sliced Elastic

Optical Path Network), FWDM (Flexible Optical Wavelength Division Multiplexing) e redes

ópticas com taxas de dados flexíveis.

Nas redes SLICE os recursos espectrais são divididos em slots de frequência com fina

granularidade e permite, devido aos transmissores/receptores adaptáveis, múltiplos formatos

de modulação, taxas de dados e espectro de largura de banda variada. Assim, um caminho

óptico pode alocar espectro suficiente de acordo com a taxa de dados transmitida [10], [13],

[35]. Um caminho óptico é equivalente a um caminho de espectro nas redes SLICE.

Em [51] foi proposta a rede FWDM, que tem conceito semelhante à rede SLICE

quanto à alocação flexível dos recursos espectrais. A sua principal diferença é que FWDM

evoluiu a partir da arquitetura de rede WDM e permite modulações por única ou múltiplas

portadoras.

As redes ópticas com taxas de dados flexíveis foram propostas para rede WDM em

[52] e caracterizam-se por utilizar várias taxas de dados para suportar diversos tipos de

21

demanda de tráfego. Esta arquitetura de rede permite modulações por única ou múltiplas

portadoras e utiliza alocação de recursos espectrais de forma fixa. A Tabela 2.1 apresenta a

diferença entre as três arquiteturas de rede.

Tabela 2.1. Comparação entre diferentes tecnologias propostas (fonte [9]) TECNOLOGIA TAXA DE DADOS LARGURA DO ESPECTRO MODULAÇÃO

SLICE

Flexível Flexível

Múltiplas portadoras

FWDM Única ou Múltiplas portadoras

Taxa de dados Flexíveis Fixa

2.2 REDE SLICE

Para transmitir informações nas redes SLICE, é utilizado um transmissor flexível

capaz de suportar distintos formatos de modulação [10]. Desta forma, é possível ter diversos

formatos de modulação coexistindo na rede, tais como: BPSK (Binary Phase-Shift Keying),

QPSK (Quadrature Phase Shift Keying), 8QAM (Quadrature Amplitude Modulation) e

16QAM [11]. Cada formato de modulação transmite uma determinada quantidade de bits por

símbolo e a constelação, pertencente ao formato de modulação, transporta no máximo log2(M)

bits de informação por símbolo, onde M é o número de símbolos da constelação de formatos

de modulação. A Figura 2.1 ilustra o diagrama de constelação da modulação QAM.

Figura 2.1. Exemplo do diagrama de constelação da modulação QAM (adaptado de [53]). Copyright © 2010

IEEE.

O formato de modulação a ser escolhido, para o estabelecimento de uma conexão,

depende da distância do caminho entre o nó origem e o nó destino. A Figura 2.2 ilustra o

alcance de transmissão por taxa de bits. Para a Figura 2.2, foram incluídas as restrições da

camada física como: atenuação na fibra, relação sinal ruído óptica (Optical Signal-to-Noise

Ratio – OSNR) e efeitos não lineares. Para estes, foram utilizadas a modulação de fase

cruzada (Cross-Phase Modulation – XPM) e a mistura de quatro ondas (Four-Wave Mixing –

2 bits/símbolo

4QAM

4 bits/símbolo

16QAM

5 bits/símbolo

32QAM

6 bits/símbolo

64QAM

22

FWM) [10]. O formato de modulação utilizado na Figura 2.2 foi o BPSK.

Como observado, há uma relação inversa entre a taxa de transmissão e o alcance.

Então, a depender da distância a ser alcançada, utilizam-se formatos de modulação

específicos. Para definir o formato de modulação adequado em uma conexão, um controlador

OpenFlow pode ser utilizado para gerenciar, de forma automática, as escolhas de: formato de

modulação, taxa de símbolo e rotas de caminhos ópticos [25].

Figura 2.2. Alcance de transmissão por taxa de bits (adaptado de [10]). Copyright © 2014 Springer

Para elucidar a relação entre formatos de modulação, alcance de transmissão e

eficiência espectral, considere o exemplo a seguir [23], [24]. Assuma que um amplo espectro

de 4 THz continha 320 faixas de frequência (slots) com uma largura de 12,5 GHz cada e que

estas possam ser utilizadas por diferentes formatos de modulação, como foi exposto

anteriormente. Cada formato de modulação proporciona uma eficiência espectral diferente

(bps/Hz). Portanto, a taxa de transmissão de um único slot em 12.5 GHz pode ser 12.5, 25,

37.5, 50, 62.5 e 75 Gbit/s para BPSK, QPSK, 8-QAM, 16-QAM, 32-QAM e 64-QAM,

respectivamente. Como o alcance máximo da transmissão depende do formato de modulação

utilizado, podem-se ter as distâncias de 4000, 2000, 1000, 500, 250 e 125 km para os

formatos de modulação BPSK, QPSK, 8-QAM, 16-QAM, 32-QAM e 64-QAM,

respectivamente. A Tabela 2.2 resume as informações supracitadas, com taxa de código fixa.

10 20 30 40 50 60 70 80 90 100

900

1050

1200

1350

1500

1650

1800

Alc

ance

de

tran

smis

são (

KM

)

Taxa de bits (Gb/s)

http://www.sinonimos.com.br/elucidar/

23

Tabela 2.2. Comparação entre formatos de modulação, capacidade de slots e alcance de transmissão (adaptado

de [24]). Copyright © 2012 IEEE.

Formato de modulação Capacidade de slots (Gbit/s) Alcance de transmissão (km)

BPSK 12.5 4000

QPSK 25 2000

8-QAM 37.5 1000

16-QAM 50 500

32-QAM 62.5 250

64-QAM 75 125

Caso seja necessário, vários slots podem ser combinados para criar um super-canal,

transportando múltiplas vezes a capacidade de um único canal OFDM, como pode ser visto na

Figura 2.3. Os dados a serem transmitidos são divididos em vários canais e são modulados em

canais ópticos OFDM contíguos sem banda de guarda entre si. Isto pode ser realizado devido

à ortogonalidade da transmissão OFDM que permite a sobreposição de canais adjacentes,

como mostrado na parte inferior da Figura 2.3. Esta compactação de espectro aumenta a

capacidade total do sistema, de forma a ocupar menos recursos espectrais que o método

correspondente de multiplexação WDM [4].

Figura 2.3. Taxa de transmissão em função do número de slots alocados (adaptado de [4]). Copyright © 2014

IEEE.

A Figura 2.4 ilustra um esquema de especificação de recursos espectrais em que o

espectro óptico é dividido em uma quantidade de slots contínuos, e a largura de cada slot

corresponde à largura do espectro de uma sub-portadora OFDM. Essa especificação segue a

grade de frequência do padrão ITU-T WDM (Figura 2.4a) [55]. A Figura 2.4b ilustra a

especificação flexível do slot de frequência utilizado na rede SLICE, que tem comprimento

12.5 GHz.

Taxa de

Transmissão

Número de

Slots

Frequência

1 2 3 4 5 6

24

Figura 2.4. Esquema de especificação de recursos espectrais (a) grade de frequência ITU-T WDM [54] (b) slots

de frequência (adaptado de [55]). Copyright © 2010 IEEE.

Para uma conexão fim-a-fim existir na rede SLICE, é necessário que cada WXC

(Wavelength Cross-Connects) pertencente ao caminho de espectro escolhido aloque uma

conexão cruzada de comprimento apropriado correspondente à largura de banda do espectro.

Para isso, o WXC deve configurar a janela de comunicação de forma flexível de acordo com a

largura espectral do sinal óptico recebido.

O tradicional WSS (Wavelength-Selective Switch) foi projetado para a rede WDM e

seu funcionamento consiste em uma estrutura 1xN (uma entrada e N saídas) ou Nx1 (N

entradas e uma saída), composta por multiplexadores e demultiplexadores cuja matriz de

comutação é formada por chaves ópticas seletoras. A representação funcional de um WSS

pode observado na Figura 2.5. Em um WSS, o sinal de entrada composto por vários

comprimentos de onda ao passar por um demultiplexador tem os comprimentos de onda

separados e podem ser direcionados para qualquer um dos multiplexadores de saída de acordo

com a posição das chaves ópticas. A seleção das chaves pode ser feita de forma remota em

algumas arquiteturas [48].

12.5 GHz

50 GHz

100 GHz

25GHz

F=193.0 THz

n=-1

F=193.1 THz

n=0

F=193.2 THz

n=1

0 1 2 3 4 5 6 7 8-1-2-3-4-5-6-7-8

12.5 GHz

(a)

(b)

25

Figura 2.5. Representação funcional de um WSS (adaptado de [56]). Copyright © 2008 JDSU.

O BV-WSS (Bandwidth-Variable Wavelength-Selective Switch) foi projetado para

agrupar granularidades de comutação próximas, com acomodação da largura do canal de

maneira flexível. Para WSS ter a funcionalidade de banda variável é utilizada a tecnologia

LCoS (Liquid Crystal on Silicon) [6], a qual combina cristal líquido e a tecnologia de

semicondutor. A Figura 2.6 ilustra o conceito de BV-WSS.

Figura 2.6. Conceito de BV-WSS (adaptado de [6]). Copyright © 2009 IEEE.

2.2.1 Comparação entre as Redes Ópticas SLICE e WDM

A Figura 2.7a ilustra a alocação de canais WDM, espaçados uniformemente, e com

capacidade de até 50 GHz de espectro disponível para cada canal. Evidentemente, esta

capacidade pode ser transformada em bps pela relação entre a taxa de transmissão e a banda

de frequência ocupada. Ao final da alocação, tem-se a utilização de 250 GHz, para a rede

WDM. Logo, um planejamento, com capacidade pré-fixada para os canais, pode desperdiçar

Demultiplexador

λ1

λ2

λ3

λ4

λn

Chave

Óptica

Entrada

Saída

12

34

n

Multiplexadores

BV

WSSFibra de Chegada

Fibra de Saída #1

Fibra de Saída #2

Fibra de Saída #3

Fibra de Saída #4

26

uma quantidade razoável de espectro. Ou seja, o planejamento tradicional (considerando a

situação hipotética acima) é feito para caminhos ópticos de comprimento fixo, no caso 50

GHz [33].

A proposta da arquitetura SLICE é realizar o planejamento da rede para suportar

caminhos ópticos de largura de banda variável. A Figura 2.7b apresenta a alocação de

espectro realizada na Figura 2.7a utilizando a rede SLICE. Nessa, é visualizada a frequência

utilizada e os slots alocados (cada slot tem capacidade de 12,5 GHz) [51]. Entre duas

alocações emprega-se a frequência de banda de guarda, ou simplesmente GB (Guard-Band)

que, neste exemplo, é 12.5 GHz, equivalente a um slot. Ao final das alocações, observa-se que

o espectro total utilizado foi de 175 GHz, contra 250 GHz da rede WDM (Figura 2.7a). Isto

ocorre porque o espectro é alocado de forma flexível.

Figura 2.7. Espectro de rede (a) WDM tradicional (b) SLICE (adaptado de [35]). Copyright © 2013 IEEE.

O uso da tecnologia O-OFDM, na qual o sinal pode ser composto por um conjunto de

canais ortogonais que se sobrepõem parcialmente no domínio da frequência, permite a

alocação mais flexível e uma eficiente utilização dos recursos espectrais. A largura de banda,

correspondente às várias sub-portadoras utilizadas para o caminho óptico, será alocada na

rede em forma de uma quantidade de slots (Figura 2.7b). Este caminho óptico formado por

slots contíguos é separado de outros caminhos ópticos pela banda de guarda, a qual pode ter a

largura de um ou mais slots [7], [16]. A partir daqui, por simplicidade, a demanda por largura

Frequência (GHz)

Canal 1 Canal 2 Canal 3 Canal 4 Canal 5

GB

Slots1 2 3 4 5 6 7

GB GB

Economia Espectral

50 GHz 10 GHz 20 GHz 10 GHz 20 GHz

GB

50 GHz 10 GHz 20 GHz 10 GHz 20 GHz

12,5 GHz

8 9 10 11 12 13 14

(a)

(b)

Frequência (GHz)

27

de banda será quantificada em termos de número de slots requisitados.

2.2.2 Problema de Roteamento e Alocação de Espectro em Redes SLICE

O problema RSA é dividido em dois subproblemas, o roteamento de caminhos ópticos

e a alocação de espectro. Estes podem ser representados por variáveis e um conjunto de

restrições a serem obedecidas. Desta forma, é possível resolver estes problemas com a técnica

de programação matemática. Caso as variáveis do problema sejam inteiras, busca-se resolver

com programação linear inteira (ILP –Integer Linear Programming). No entanto, ambos os

problemas, de roteamento e alocação de espectro, são NP (Non-deterministic Polynomial

time) [16], ou seja, o tempo de execução do problema cresce de maneira exponencial quando

o número de instâncias é grande.

Diante do exposto, os problemas acima (com muitas instâncias), quando calculados

computacionalmente, são considerados dispendiosos devido à amplitude do espaço de busca

por uma solução. Logo, percorrer todas as possibilidades seria inviável em um tempo

computacional razoável. Desta forma, tem-se a necessidade de utilizar métodos ou estratégias

que busquem bons resultados, eventualmente o melhor, em um tempo computacional

razoável. Para isto, utilizam-se heurísticas [33], [57].

As heurísticas buscam, em um conjunto de soluções, aquela mais próxima da solução

ótima, ou a própria solução ótima, em um tempo computacional reduzido. O objetivo é

resolver problemas reais, os quais teriam um custo de processamento elevado se calculados

por métodos matemáticos exatos.

Através das heurísticas, os problemas de roteamento e alocação de espectro podem ser

tratados de duas formas: individualmente, cuja complexidade seria menor, porém os recursos

da rede poderiam não ser utilizados de forma tão eficiente, ou conjuntamente, com uma

complexidade maior, mas com possibilidade de se ter uma maior eficiência no uso dos

recursos. Nesta tese, optou-se pelo tratamento individual, ou seja, são propostas heurísticas

para o sub-problema de roteamento e para o sub-problema de alocação de espectro.

2.2.2.1 Roteamento de Espectro em Rede SLICE

No RSA, os algoritmos de roteamento, de forma similar ao RWA, podem ser

separados em três classes: roteamento fixo, roteamento alternativo ou fixo alternativo, e

28

roteamento exaustivo ou dinâmico [58]-[60].

No roteamento fixo, cada par de nós (origem, destino) da rede óptica dispõe de apenas

uma rota que é computada previamente. Assim, antes mesmo de surgir uma requisição de

caminho óptico, o plano de controle responsável pelo roteamento já sabe qual rota deve ser

utilizada entre os pares de nós da rede. Isto significa que, após o surgimento da requisição, o

desafio passa a ser a alocação de uma faixa de espectro para a requisição, que considere a

largura desta.

No roteamento alternativo ou fixo alternativo [61], um conjunto com mais de uma rota

é definido previamente para cada par de nós (origem, destino). Isto representa mais de uma

alternativa, em termos de rota, na tentativa de estabelecer um caminho óptico. Nesse

roteamento, as rotas são previamente ordenadas, por exemplo, em função do número de

saltos. A seleção da rota é realizada de acordo com a ordem previamente definida. Se a

primeira rota não possui recursos disponíveis, as rotas seguintes são analisadas, uma a uma,

até ser encontrada uma rota com recursos disponíveis. Por exemplo, no problema em estudo,

se nenhuma das alternativas de rotas pré-definidas tiver uma faixa de espectro contínua livre e

de comprimento adequado em todos os enlaces da rota, a requisição é bloqueada.

Os algoritmos da classe de roteamento exaustivo têm como vantagem a capacidade de

utilizar qualquer rota possível da topologia na tentativa de estabelecer o caminho óptico. Com

isso, uma requisição de caminho óptico apenas será bloqueada se nenhuma rota, entre sua

origem e destino, dispuser de pelo menos uma faixa do espectro contínua livre e da largura da

requisição.

Em termos gerais, as classes de algoritmos de roteamento apresentam a seguinte

ordem crescente de desempenho em termos de probabilidade de bloqueio: fixo, fixo

alternativo e exaustivo [62], [63]. Entretanto, esse aumento do desempenho é acompanhado

também pelo incremento da complexidade de suas soluções. Algoritmos de roteamento, os

quais dependem de informações globais sobre o estado da rede, resultam em uma maior

complexidade dos protocolos do plano de controle. Tal complexidade pode ser traduzida em

um maior atraso no estabelecimento de um caminho óptico. Certamente, a solução prévia das

rotas, com o uso de algum algoritmo representante da classe de roteamento fixo, potencializa

a redução do tempo requerido para o estabelecimento dinâmico do caminho óptico. O

roteamento fixo proporciona uma menor complexidade para os protocolos do plano de

controle, uma vez que a escolha da rota para cada par de nós origem e destino é feita na fase

de planejamento da rede.

29

2.2.2.2 Alocação de Espectro em Rede SLICE

Em uma rede SLICE, a alocação de banda adaptada é possível devido aos ROADMs

(Reconfigurable Optical Add/Drop Multiplexer) e transmissores/receptores adaptáveis. Com a

utilização da OFDM a capacidade de uma sub-portadora é da ordem de Gbps, e esta é dividida

em slots com granularidade fina.

Na alocação, se a demanda de tráfego a ser transmitida por um nó for menor que a

capacidade do canal, utiliza-se OFDM para dividir o canal em diversos slots com

comprimentos menores, e assim alocar apenas a quantidade necessária de slots para a

demanda. Os slots restantes podem ser alocados para outra demanda, de forma a evitar o

desperdício de banda [6].

Para facilitar a filtragem do sinal óptico nos receptores, dois caminhos de espectro que

compartilham um ou mais enlaces de fibra em comum devem ser separados no domínio da

frequência por uma banda de guarda (GB – Guard Band). A exigência na largura da banda de

guarda, no entanto, não é trivial e pode ser da ordem de um ou múltiplos slots [7].

Um exemplo do RSA é ilustrado na Figura 2.8a. Nesta, existe uma rede em estrela

com enlaces bi-direcionais, GB=1 slot, um caminho de espectro SP1 com 2 slots de A para B e

um outro caminho de espectro SP2 com 1 slot de A para C. A Figura 2.8b ilustra a alocação de

espectro na Fibra F1 para SP1 e SP2. Como mostrado na Figura 2.8b, cada slot na fibra tem um

índice. Os slots com índices 1 e 2 são alocados para o SP1, que requer 2 slots consecutivos. O

slot com índice 4 é alocado para o SP2. O slot com índice 3 é reservado como banda de guarda

(GB) entre o SP1 e o SP2 na Fibra 1. Como os slots dentro do SP1 são consecutivos, não é

necessária uma banda de guarda entre eles. No entanto, para separar os sinais de SP1 e SP2 na

Fibra F1 é necessário utilizar uma GB. Assim, não pode ser utilizado o slot 3 para o SP2.

Como resultado, para alocar SP1 e SP2 são necessários 4 slots. Para representar o número

máximo de slots alocados em uma fibra na rede é utilizada a variável MS. Logo, para alocar a

demanda de tráfego desta rede o MS será 4.

30

(a) (b)

Figura 2.8. Um exemplo de alocação de espectro em uma rede SLICE (adaptado de [16]). Copyright © 2013

IEEE.

O problema RSA também pode ser classificado em estático ou dinâmico. No primeiro,

as rotas e o tráfego são previamente conhecidos e tem-se como objetivo reduzir o número de

slots alocados na rede. No segundo, as conexões e o tráfego não são previamente conhecidos e

o objetivo é reduzir a probabilidade de bloqueio das futuras requisições. Nos próximos

capítulos, serão abordados RSA estático e dinâmico.

A C

N

B

F5F2

F3

F6

F4

F1

SP1

SP2

GC ...

1 2 3 4 ... MS

Índice do Slot

F1

SP1 SP1 SP2

31

CAPÍTULO 3

3. ROTEAMENTO E ALOCAÇÃO DE ESPECTRO PARA TRÁFEGO

ESTÁTICO

Neste capítulo serão propostas duas heurísticas para realizar a alocação de rota em

redes ópticas SLICE. A primeira tem como objetivo encontrar as melhores rotas dentre um

conjunto de rotas possíveis. A segunda utiliza o re-rotamento de caminhos para balancear a

carga da rede. Como resultado, é analisada a quantidade de slots alocados por enlace na rede,

para tráfego uniforme e não uniforme, com a utilização de topologias de redes distintas. Os

resultados obtidos mostram a eficiência das heurísticas apresentadas.

3.1 RSA ESTÁTICO

No RSA estático, as rotas são definidas previamente (roteamento fixo), com o intuito

de estudar os melhores caminhos e a melhor estratégia para utilizar os espectros apropriados.

Depois de estabelecer o roteamento, o tráfego da rede será encaminhado através dele. Esses

caminhos ópticos são denominados permanentes, pois não serão removidos após a ativação,

podendo durar meses ou anos, a depender da necessidade do projeto da rede. Geralmente,

alocam-se os espectros, de forma estática, para transmitir informações que requerem

caminhos e tráfego de dados dedicados, como aplicações de vídeo e áudio.

Algumas estratégias de roteamento que utilizam heurísticas foram propostas com

vistas à melhoria do desempenho das redes SLICE em termos de economia do espectro, e

assim reduzir a quantidade de slots usados. Por exemplo, em [16], são apresentados dois

algoritmos, chamados SPSR (Shortest Path with Maximum Spectrum Reuse) e BLSA

(Balanced Load Spectrum Allocation), que escolhem a rota ―menos carregada‖ em termos de

slots utilizados, ou seja, a rota que possui mais slots disponíveis em todos os enlaces. Na

literatura, diversos trabalhos utilizam estas heurísticas para efeito de comparação de

resultados [20], [34], [64].

Para o RSA estático, foram utilizadas duas heurísticas: BSR (Best among the Shortest

Routes) e ILR (Iterative Load Routing). Apesar de terem sido inicialmente propostas para

rede WDM [62], [65], adaptamos para a rede SLICE com o intuito de reduzir a quantidade de

32

slots alocados na rede [66], [67]. Simulações foram realizadas para comparar estas heurísticas

com SPSR e BLSA e os resultados apresentam vantagem em termos de economia de espectro.

3.2 HEURÍSTICAS PARA O PROBLEMA RSA ESTÁTICO

Em [16], foram apresentadas duas heurísticas para resolver o problema RSA. A SPSR

(Shortest Path with Maximum Spectrum Reuse) utiliza três parâmetros para o roteamento e

alocação: 1) o roteamento é realizado utilizando o algoritmo de Dijkstra; 2) as demandas de

tráfego são classificadas em ordem crescente da quantidade de slots solicitados; 3) são

alocados os caminhos ópticos respeitando a restrição de continuidade e contiguidade de slots.

Este passo é similar ao First-Fit [60]. O BLSA (Balanced Load Spectrum Allocation)

determina o roteamento através do balanceamento de carga no interior da rede, com o intuito

de reduzir o número máximo de slots alocados em uma fibra. Este algoritmo é constituído por

três passos:

Passo 1: Gerar as caminhos. Para isto, é utilizado o algoritmo k–menores caminhos

[68], cujo k>=1;

Passo 2: Seleção de caminhos. Neste passo, escolhe-se o caminho de espectro de

forma sequencial com o objetivo de balancear a carga entre todas as fibras da rede. Este

balanceamento é realizado a partir do cálculo da carga de cada fibra da rede (Lj), como

apresentado na Equação (3.1).

)1(

IGCtLipj

ij (3.1)

onde, pi é o caminho da conexão, ti a quantidade de slots alocados, i o identificador do

caminho, GB a banda de guarda e Ij é o número total de caminhos de espectro que passam na

fibra j.

Passo 3: Alocação de slots. Para alocar todos os caminhos ópticos e respectivos slots é

utilizado o algoritmo MRSA (Maximum Reuse Spectrum Allocation), descrito em [16], que é

similar ao First-Fit [60]. O MRSA enumera todos os slots (1, 2, ..., n) e quando surge uma

requisição, este algoritmo aloca o slot disponível com menor índice.

3.2.1 BSR (Best among the Shortest Routes)

O BSR tem como objetivo encontrar as melhores rotas dentro de um conjunto de rotas

possíveis. Como cada par (origem, destino) pode ter mais de uma rota de menor caminho

33

(chamadas neste trabalho de Rotas Candidatas – RC), existem M soluções diferentes para o

planejamento das rotas fixas em uma determinada topologia de rede. O cálculo de M, que

representa o número de soluções possíveis, é dado pela Equação (3.2) [65].

NN

ji

jiparRCM,

1,1

),( (3.2)

em que, RCpar(i,j) indica o número de rotas de menor caminho candidatas para o par(i,j), com i

≠ j.

A seguir são listadas algumas notações utilizadas na apresentação do algoritmo BSR:

L é o conjunto de todos os enlaces da rede;

l é um enlace que pertence a L;

c(l) é o custo do enlace l;

c(l)i é o custo do enlace l na i-ésima iteração;

u(l)i é a utilização do enlace l obtida via simulação na i-ésima iteração, isto é, a

soma dos slots alocados no enlace l.

T é o número de iterações do BSR.

Cada iteração i do BSR simula uma solução de roteamento Si do universo de M

soluções possíveis. Os resultados da simulação realizada na i-ésima iteração são os valores da

utilização de cada enlace da rede (u(l)i) e o desempenho da rede em termos de alocação de

slots atribuídos com a solução de roteamento Si.

A ideia básica deste algoritmo é ajustar, na iteração i+1, o custo de cada enlace com

uma pequena ponderação (1 – α) proporcional ao valor da utilização do enlace obtido na

simulação da iteração i. O ajuste no custo de cada enlace é dado pela equação:

iii lulclc )()1()()( 1 (3.3)

onde, 1 ≤ i ≤ T e α tem valor muito próximo de 1 para que os custos dos enlaces sejam

minimamente alterados em função da utilização dos mesmos e assim as novas rotas

encontradas continuem como rotas com o menor número de saltos. O valor de α = 0,9999 foi

determinado empiricamente, após análises dos resultados obtidos com diferentes valores e

será este o valor utilizado em todas as nossas análises.

Após obter os custos c(l)i+1, utiliza-se um algoritmo de menor caminho simples

(Algoritmo de Dijkstra [69]) para encontrar a solução de roteamento Si+1, que será utilizada na

iteração i+1. Esse pequeno ajuste serve como um critério de desempate para que o algoritmo

34

(a) (b)

(c) (d)

(e)

Figura 3.1. Algoritmo BSR (a) quatro possíveis caminhos entre o nó origem 1 e destino 4 (b) número de slots

alocados na rede SLICE (c) valor c(l)i para cada enlace da rede (d) custo para cada caminho (e) caminho

escolhido.

de Dijkstra encontre uma solução Si+1 com rotas que representem um maior equilíbrio na

utilização dos enlaces da rede.

Para exemplificar o funcionamento do BSR, observe a Figura 3.1. Supõe-se que haja

uma requisição de um slot do nó origem 1 para o nó destino 4. Supõe-se também que o peso

de cada enlace seja igual a 1. Ao observar a Figura 3.1a, percebe-se que existem quatro

possíveis caminhos mais curtos por onde essa requisição pode ser estabelecida. Então, é

necessário escolher um, dentre estes, para disponibilizar à requisição. A Figura 3.1b apresenta

uma rede SLICE, com os respectivos slots alocados por enlace na iteração i do algoritmo.

Neste exemplo, cada enlace contém oito slots, dos quais aqueles marcados com ―x‖ estão

alocados. Ao aplicar a equação (3.3) tem-se os valores de c(l)i+1 para cada enlace (Figura

3.1c). Deve-se, portanto, escolher um caminho para alocar a requisição do nó 1 para o 4. Para

isto, o custo de cada caminho é computado (Figura 3.1d). Obtido o menor custo, é definido o

35

melhor caminho. Neste exemplo, o melhor caminho é 1-2-5-4, com custo de 3,0005 (Figura

3.1e).

O fluxograma do algoritmo BSR é ilustrado na Figura 3.2. Ao final do algoritmo, é

verificado, dentre as T iterações, qual a solução de roteamento que apresentou menor dentre

os maiores valores de utilização dos enlaces. Esta conterá o conjunto de caminhos escolhidos.

Figura 3.2. Fluxograma do algoritmo BSR

3.2.2 ILR (Iterative Load Routing)

A heurística ILR tem o principal objetivo de balancear a carga da rede. Isto é feito

através do re-roteamento dos caminhos sobre conjuntos de enlaces físicos menos

congestionados. Desta forma, consegue-se reduzir o número de slots alocados em um enlace

da rede. A seguir será apresentada uma descrição do pseudocódigo do algoritmo e uma

exemplificação é ilustrada na Figura 3.3.

Início

Inicializar os valores das variáveis: i =0, T (dado

de entrada) e c(l)0 =1

Calcular os caminhos para cada nó (origem,

destino) usando o algoritmo de Dijkstra

Atualizar os custos dos enlaces para a próxima

iteração utilizando a Eq. (3.3)

i=i+1

i<TSim

Fim

Encontrar a nova solução de roteamento Si+1

utilizando o algoritmo de Dijkstra.

Simular a rede com a solução de roteamento Si+1

Não

36

(a) (b)

(c) (d)

(e)

Figura 3.3. Algoritmo ILR (a) Caminhos roteados na rede (b) o caminho de espectro de cor azul tem a maior

quantidade de caminhos compartilhados (c) caminho de espectro de cor azul foi removido (d) número de slots

alocados na rede SLICE (e) caminho de espectro de cor azul foi realocado.

Passo 1: Realize o cálculo das rotas de todos os caminhos a partir do algoritmo de

Dijkstra. A Figura 3.3a ilustra um exemplo das rotas alocadas.

Passo 2: Encontre o caminho de espectro com maior quantidade de caminhos

compartilhados (Figura 3.3b) e o remova do roteamento (Figura 3.3c). Perceba que o caminho

de espectro de cor azul compartilha dois enlaces com outros quatro caminhos (Figura 3.3b).

Passo 3: Defina sumLOAD como a soma da quantidade de slots utilizados em cada

enlace ao longo do caminho em que o caminho de espectro removido estava roteado. No

exemplo da Figura 3.3d, o sumLOAD será a soma dos slots dos enlaces 6-5 e 5-2, referente ao

caminho removido, com valor igual a nove.

Passo 4: Ache dentre todos os possíveis caminhos para o caminho de espectro

removido (origem 6, destino 2) aquele com a menor quantidade de slots utilizados em seus

37

enlaces físicos. Esse valor é chamado de minLOAD. No exemplo da Figura 3.3d o minLOAD

é a soma dos slots dos enlaces 6-1 e 1-2.

Passo 5:

Se sumLOAD > minLOAD então

Re-roteie o caminho de espectro removido sobre o caminho com minLOAD e

volte ao passo 2. A Figura 3.3e ilustra a realocação do caminho de espectro de

cor azul para a rota 6-1-2.

Senão

Re-roteie o caminho de espectro removido sobre o mesmo caminho, no qual ele

estava roteado antes.

Passo 6: Encontre o próximo caminho de espectro com maior quantidade de caminhos

compartilhados, remova-o do roteamento e volte ao Passo 3. Se todos os caminhos de

espectro tiverem sido testados sem voltar ao passo 2, então o algoritmo está encerrado.

3.3 RESULTADOS NUMÉRICOS

3.3.1 Simulação para Redes de Pequena Dimensão

Para as simulações de redes de pequena dimensão foram utilizadas três topologias de

redes, duas em anel, contendo 4 nós (Figura 3.4a) e 5 nós (Figura 3.4b), e uma em malha

(Figura 3.4c). Os resultados foram analisados através da programação linear inteira (ILP) de

[16] e quatro heurísticas BSR, ILR, BLSA e SPSR.

(a) Rede em anel com

quatro nós (R4)

(b) Rede em anel com cinco

nós (R5)

(c) Rede em Malha com seis nós (R6)

Figura 3.4. Topologias de redes pequenas

Como pode ser observado na Tabela 3.1, as redes com maior quantidade de nós

demandam mais tempo de simulação. Nas simulações, a quantidade de banda de guarda (GB)

e a demanda de tráfego (X) foram variadas. A demanda de tráfego refere-se à quantidade de

slots requisitada em uma alocação.

1

4 3

2

5

1

2

34

1

6 5

2

4

3

38

Tabela 3.1. Resultados das Simulações para Redes Pequenas: R4 e R5 (anel), R6 (Malha) X =1, GB=1 X =1, GB=2 X =2, GB=1

Rede ILP BSR ILR BLSA SPSR ILP BSR ILR BLSA SPSR ILP BSR ILR BLSA SPSR

R4 MS 3 5 5 3 5 4 7 7 4 7 5 8 8 5 8

Tempo (7ms) (63ms) (13ms) (169ms) (35ms) (7ms) (63ms) (13ms) (169ms) (35ms) (7ms) (63ms) (13ms) (169ms) (35ms)

R5 MS 5 5 5 7 5 7 7 7 10 7 8 8 8 11 8

Tempo (17ms) (92ms) (38ms) (220ms) (40ms) (20ms) (92ms) (38ms) (220ms) (40ms) (15ms) (92ms) (38ms) (220ms) (40ms)

R6 MS 7 7 7 9 9 10 10 10 13 13 11 11 11 14 14

Tempo (32s) (125ms) (79ms) (286ms) (44ms) (473s) (125ms) (79ms) (286ms) (44ms) (13s) (125ms) (79ms) (286ms) (44ms)

Para a rede de 4 nós em anel, a heurística que conseguiu obter o resultado ótimo foi a

BLSA, com alocação de 3, 4 e 5 slots para X=1 e GB=1, X=1 e GB=2, e X=2 e GB=1,

respectivamente. No entanto, em relação ao tempo de simulação, esta heurística foi a pior

dentre todas, pois obteve 169 ms em todas as simulações. Para as redes de 5 nós, as

heurísticas que conseguiram obter resultados ótimos foram as BSR, ILR e SPSR. Todas

alocaram 5, 7 e 8 slots para X=1 e GB=1, X=1 e GB=2, e X=2 GB=1, respectivamente. Os

tempos de simulação foram em todos os cenários: ILR (38ms), SPSR (40ms) e BSR (92ms).

No entanto, para a rede de 6 nós, apenas as heurísticas BSR e ILR obtiveram resultados

ótimos com 7, 10 e 11 slots alocados para X =1 e GB=1, X=1 e GB=2, e X=2 GB=1,

respectivamente. Os tempos de simulação para as heurísticas ILR e BSR foram 79ms e

125ms. Estes tempos são muito bons, quando comparados com 32s, 473s e 13s, para X=1 e

GB=1, X=1 e GB=2, e X=2 GB=1, da solução ótima (ILP).

Em todos os cenários, percebe-se que a demanda maior no tempo das simulações se

deve à fase de roteamento do tráfego da rede. Nesta, são escolhidos os caminhos pelos quais

os slots devem ser alocados posteriormente.

A Tabela 3.2 ilustra os resultados da alocação de slots, em cada enlace da rede de 5

nós em anel, para a demanda de tráfego uniforme de um slot em cada caminho de espectro

alocado e uma banda de guarda entre caminhos de espectros distintos. As heurísticas ILR,

BSR e SPSR conseguiram obter o resultado ótimo na alocação de slots na rede. Os caminhos

encontrados por estas heurísticas foram iguais, apesar de as estratégias serem distintas.

Tabela 3.2. Resultados da alocação de slots para cada enlace da rede de 5 nós em anel Enlace ILP BSR ILR BLSA SPSR

1-2 5 5 5 5 5

1-5 5 5 5 5 5

2-1 5 5 5 5 5

2-3 5 5 5 5 5

3-2 5 5 5 5 5

3-4 5 5 5 7 5

4-3 5 5 5 7 5

4-5 5 5 5 7 5

5-1 5 5 5 5 5

5-4 5 5 5 7 5

39

Também é simulada a rede de 5 nós, com topologia em anel, através de uma demanda

de tráfego não uniforme gerada de forma aleatória entre 0 e 3 slots.

A Tabela 3.3 apresenta o tráfego da rede de 5 nós em anel para banda de guarda (GB)

igual a 1. Como pode-se perceber, na Figura 3.5, para a rede de 5 nós, as heurísticas BSR,

ILR e SPSR obtiveram o resultado ótimo (ILP). Esta simulação foi realizada para comparar as

heurísticas SPSR e BLSA, e a formulação linear apresentada em [16] com as heurísticas BSR

e ILR.

Tabela 3.3. Matriz de

Tráfego para Rede de 5 Nós -- 2 2 2 3

3 -- 3 1 1

1 0 -- 2 1

3 2 3 -- 2

2 1 0 1 --

Figura 3.5. Número máximo de slots alocados em uma fibra da rede, para o tráfego não uniforme, pela demanda

de tráfego (slots).

Para as redes maiores, não é viável utilizar o ILP devido à dispendiosa quantidade de

tempo gasto para obtenção dos resultados. Logo, são utilizadas apenas as heurísticas citadas.

3.3.2 Simulação para Redes de Grande Dimensão

Para verificar a eficiência das heurísticas em redes de grande dimensão, foram

realizadas simulações com a rede NSFNet (National Science Foundation Network) [16] e

EON (European Optical Network) [70], com tráfego uniforme e não uniforme. Essas redes,

ilustradas na Figura 3.6, contêm 14 nós, 42 enlaces e 19 nós, 76 enlaces, respectivamente.

1 20123456789

10111213141516171819

Nú

mero

Máxim

o d

e S

ub

-Po

rtad

ora

s e

m u

ma F

ibra

da R

ed

e

Número de Sub-portadoras

SPSR

BLSA

ILR

BSR

ILP

40

a. Rede NSFNet b. Rede EON

Figura 3.6. Topologias das redes NSFNet e EON.

3.3.2.1Demanda de Tráfego Uniforme

A Figura 3.7 ilustra os resultados de duas redes SLICE, NSFNet e EON, com uma

banda de guarda entre caminhos de espectros distintos. São simuladas as heurísticas BSR,

ILR, BLSA e SPSR, com valores de demanda de tráfego (slots) iguais a 1, 2 e 3. Ambas as

heurísticas BSR e ILR com demanda de tráfego de um slot alocaram 25 slots para a rede

NSFNet e 33 slots para a rede EON, com obtenção de melhores resultados que as heurísticas

BLSA e SPSR. Quando a quantidade de banda de guarda é incrementada, o número de slots

alocados aumenta em cada alocação entre caminhos de espectro. Logo, para GB = 2 (Figura

3.8), é observado que ambas as heurísticas BSR e ILR alocaram 37 slots para a rede NSFNet e

49 slots para a rede EON. Para GB = 3 (Figura 3.9), BSR e ILR alocaram 49 slots para a rede

NSFNet e 65 slots para a rede EON.


Figura 3.7. Número máximo de slots alocados em uma fibra da rede com uma banda de guarda entre caminhos

de espectro distintos.

1

3

24

5

6 8

79

10

11 12

14

13

1 2 30

10

20

30

40

50

60

70

80

90

Nú

mero

máxim

o d

e s

lots

alo

cad

os e

m u

ma f

ibra

da r

ed

e

Demanda de Tráfego (slots)

SPSR

BLSA

ILR

BSR

1 2 30

10

20

30

40

50

60

70

80

90

100

110

120

130

140

150

Nú

mero

máxim

o d

e s

lots

alo

cad

os e

m u

ma f

ibra

da r

ed

e


SPSR

BLSA

ILR

BSR

41


Figura 3.8. Número máximo de slots alocados em uma fibra da rede com duas bandas de guarda entre caminhos



Figura 3.9. Número máximo de slots alocados em uma fibra da rede com três bandas de guarda entre caminhos


Todos os resultados das simulações com BSR e ILR foram melhores que os das

heurísticas BLSA e SPSR. Isto ocorre porque as heurísticas BSR e ILR têm como objetivo

principal balancear a carga da rede, de forma a evitar os caminhos mais congestionados para

fazer a alocação de espectro. Desta forma, a alocação é realizada pelos caminhos menos

utilizados, a partir da divisão da demanda de tráfego de forma mais igualitária entre todos os

enlaces da rede.

Apesar de as heurísticas BSR e ILR serem distintas e realizarem a alocação por

caminhos diferentes, ambas conseguem obter resultados melhores que as heurísticas BLSA e

SPSR propostas por [16], para as topologias NSFNet e EON.

1 2 30

10

20

30

40

50

60

70

80

90

Nú

mero

máxim

o d

e s

lots

alo

cad

os e

m u

ma f

ibra

da r

ed

e


SPSR

BLSA

ILR

BSR

1 2 30

10

20

30

40

50

60

70

80

90

100

110

120

130

140

150

Nú

mero

máxim

o d

e s

lots

alo

cad

os e

m u

ma f

ibra

da r

ed

e


SPSR

BLSA

ILR

BSR

1 2 30

10

20

30

40

50

60

70

80

90

Nú

mero

máxim

o d

e s

lots

alo

cad

os e

m u

ma f

ibra

da r

ed

e


SPSR

BLSA

ILR

BSR

1 2 30

10

20

30

40

50

60

70

80

90

100

110

120

130

140

150

Nú

mero

máxim

o d

e s

lots

alo

cad

os e

m u

ma f

ibra

da r

ed

e


SPSR

BLSA

ILR

BSR

42

3.3.2.2 Demanda de Tráfego Não Uniforme

A Tabela 3.4 apresenta a demanda de tráfego gerada de forma aleatória entre 0 e 3

slots para as Redes NSFNet e EON. Os resultados podem ser observados na Figura 3.10.

Tabela 3.4. Matriz de Tráfego para Rede NSFNet e EON 0 1 3 3 0 3 0 3 1 1 3 3 1 0

0 0 0 3 0 0 3 3 0 3 3 2 2 1

3 0 0 3 1 3 2 1 3 2 0 3 3 3

2 0 0 0 1 0 3 1 2 3 0 1 1 0

3 0 2 3 0 1 0 3 3 3 1 0 2 0

0 2 3 3 0 0 2 1 1 1 2 2 1 3

3 0 1 1 2 2 0 1 0 2 2 1 0 2

0 2 2 1 2 0 0 0 3 2 1 0 1 3

0 1 3 3 2 2 0 1 0 0 2 1 3 0

0 2 1 0 2 1 2 1 3 0 0 0 3 3

3 3 1 0 0 0 2 2 3 2 0 3 0 0

2 0 1 2 1 1 2 1 3 2 1 0 0 2

2 1 2 0 2 2 3 2 3 1 1 0 0 0

0 0 1 0 0 2 3 3 3 2 2 2 1 0

0 3 3 3 1 2 2 2 1 3 1 1 0 3 3 3 2 2 0

3 0 3 0 2 1 0 0 1 0 0 3 1 3 2 1 3 3 3

2 2 0 1 2 1 0 2 3 0 2 3 1 3 1 2 0 1 1

2 0 0 0 3 2 3 2 0 2 2 3 3 3 2 1 0 0 3

0 0 2 0 0 0 0 0 0 3 1 3 1 3 0 0 0 0 2

1 1 2 3 0 0 3 2 3 1 2 3 3 1 0 0 3 3 0

0 1 3 1 3 2 0 0 2 0 1 0 3 0 0 2 0 1 3

0 1 2 1 1 0 3 0 1 2 0 0 2 1 1 0 0 2 1

2 2 1 1 0 2 3 1 0 0 0 2 0 0 0 2 2 2 0

0 1 2 2 0 3 3 2 0 0 2 0 1 0 3 2 2 1 0

0 3 2 2 1 3 0 3 0 1 0 0 1 3 1 3 2 2 3

2 0 2 3 2 2 2 0 1 1 1 0 3 2 0 1 2 1 3

1 2 3 0 0 0 3 3 0 2 2 3 0 3 0 0 1 3 0

3 0 1 3 2 3 3 0 0 3 2 1 3 0 3 3 1 3 3

3 2 0 2 1 0 3 3 1 1 2 2 1 0 0 1 1 0 0

2 0 2 0 3 2 1 1 1 0 1 3 0 2 2 0 1 3 2

2 3 1 2 0 1 3 0 0 1 1 3 0 2 1 3 0 1 0

1 2 0 3 1 3 1 3 1 3 2 0 3 2 0 0 3 0 2

2 2 0 0 3 2 3 0 1 1 1 1 3 2 2 3 0 0 0


Figura 3.10. Número máximo de slots alocados em uma fibra das redes NSFNet e EON para o tráfego não

uniforme.

Ao observar os gráficos anteriores, é verificado que as heurísticas BSR e ILR

continuaram a obter melhores resultados quando comparadas com as heurísticas BLSA e

SPSR simuladas com tráfego não uniforme com valores de GB iguais a 1, 2 e 3 slots.

Como em todas as simulações as heurísticas BSR e ILR obtiveram os mesmos

resultados, será analisada a alocação de slots por enlace, para GB = 1, com o intuito de

verificar que, apesar das quantidades de slots alocados na rede serem iguais (Figura 3.10), o

roteamento e a alocação são distintos. As Figuras 3.11 e 3.12 ilustram os resultados das

simulações para a rede NSFNet e EON, respectivamente. Pode-se observar que os enlaces

mais congestionados para a rede NSFNet (Figura 3.6a) são os de índice 9 (3-6) e 28 (10-9),

1 2 30

10

20

30

40

50

60

70

80

90

Nú

mero

máxim

o d

e s

lots

alo

cad

os e

m u

ma f

ibra

da r

ed

e

Banda de Guarda (GC)

SPSR

BLSA

ILR

BSR

1 2 30

10

20

30

40

50

60

70

80

90

100

Nú

mero

máxim

o d

e s

lots

alo

cad

os e

m u

ma f

ibra

da r

ed

e

Banda de Guarda (GC)

SPSR

BLSA

ILR

BSR

43

com 39 slots alocados em ambos. Já para a rede EON (Figura 3.6b), são os de índice 3 (1-6) e

12 (4-7), com 39 e 40 slots, respectivamente.

Figura 3.11. Número de slots alocados, em cada enlace da rede NSFNet, das heurísticas BSR e ILR.

Figura 3.12. Número de slots alocados, em cada enlace da rede EON, das heurísticas BSR e ILR.

Como observado, foram utilizadas diversas topologias, com tráfego uniforme e não

uniforme, e quatro heurísticas com o intuito de otimizar a alocação dos recursos para a rede

SLICE. Para facilitar os estudos, foi desenvolvida uma ferramenta de simulação com interface

gráfica para avaliar os diversos cenários das redes SLICE. O simulador SimRSA é

apresentado no apêndice A.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

0

5

10

15

20

25

30

35

40

45

Nú

mero

de s

lots

alo

cad

os

Enlace

ILR

BSR

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

0

5

10

15

20

25

30

35

40

45

50

Nú

mero

de s

lots

alo

cad

os

Enlace

ILR

BSR

44

CAPÍTULO 4

4. ROTEAMENTO E ALOCAÇÃO DE ESPECTRO PARA TRÁFEGO

DINÂMICO

Neste capítulo será abordado o problema de roteamento e alocação de espectro para o

tráfego dinâmico, bem como serão apresentadas três heurísticas. A primeira é uma adaptação

do algoritmo BSR para a rede SLICE, que utiliza requisições de diferentes larguras de banda

para rotear de maneira eficiente a demanda de tráfego da rede. A segunda aloca as requisições

a partir de caminhos alternativos e, em especial, verifica a quantidade máxima de caminhos

alternativos que se pode ter para reduzir a probabilidade de bloqueio na rede. A terceira foi

proposta para a alocação de espectro, com introdução da perda de capacidade para redes

SLICE.

4.1 RSA DINÂMICO

O problema RSA dinâmico deve ser resolvido com a rede em operação, cujas

requisições de caminhos ópticos chegam aleatoriamente à rede. Caso não haja recursos

suficientes para atender a uma determinada requisição de caminho óptico, ocorrerá um

bloqueio. Por esta razão, o objetivo de um provedor de serviços de transporte via rede SLICE,

face ao problema RSA dinâmico, é atender às requisições atuais de caminhos ópticos com

vistas a reduzir a probabilidade de bloqueio de futuras requisições de caminhos ópticos.

O problema RSA tem sido bastante estudado nos últimos anos. Várias estratégias

foram propostas para melhorar o desempenho das redes SLICE em termos de probabilidade

de bloqueio sob tráfego dinâmico ou outras métricas para tráfego estático [8]- [17], [21], [60],

[71].

Em [14], o problema RSA é subdividido em roteamento e alocação de espectro, onde

são apresentadas heurísticas para resolvê-lo de forma separada. Da mesma forma que no caso

estático, em [60], foram adaptados algoritmos tradicionais utilizados em redes WDM, para

aplicação em redes SLICE, sob tráfego dinâmico, e os resultados mostraram que a ordem de

desempenho dos algoritmos pode diferir nas duas arquiteturas.

45

A grande maioria dos trabalhos na literatura que estudam o problema RSA baseia-se

na classe de roteamento fixo em função de sua menor complexidade. Tais trabalhos

consideram o uso de algoritmos de menor caminho (menor número de saltos, isto é, o custo de

cada enlace é identico), para definir uma rota fixa para cada par de nós (origem, destino).

Dentre os algoritmos de menor caminho, o algoritmo de Dijkstra [69] é um dos mais citados.

Por simplicidade, o termo algoritmo de menor caminho de Dijkstra será denotado por DJK.

A opção pelo uso de algoritmos tradicionais de menor caminho (e.g., Dijkstra,

Bellman-Ford, etc) possui a tendência de limitar a capacidade de atendimento das requisições

na rede óptica, seja esta tradicional ou com a arquitetura SLICE. Nesses algoritmos, a escolha

da rota de menor caminho é feita sem avaliar o impacto que essa rota pode ocasionar nas rotas

que compartilham ao menos um enlace consigo. Como esses algoritmos tradicionais não têm

por objetivo balancear a carga entre os enlaces da rede óptica, é possível o surgimento de

enlaces ―gargalos‖ e o consequente comprometimento do desempenho no atendimento à

demanda de caminhos ópticos.

Como visto anteriormente, com o intuito de minimizar este problema, o algoritmo

BSR foi proposto em [62] para redes ópticas WDM. O BSR é da classe de roteamento fixo e,

portanto, requer uma menor complexidade computacional. Simulações foram realizadas para

redes WDM e os resultados comprovam sua eficiência quando comparado com DJK e uma

proposta chamada RRT (Restricted Routing Technique), que também se propõe a

descongestionar enlaces críticos da rede [72]. O BSR é caracterizado por escolher as rotas de

menor caminho e, ao mesmo tempo, buscar um melhor balanceamento de carga entre os

enlaces da rede. Cada requisição na rede WDM tem uma mesma largura, ou seja, solicita uma

faixa do espectro de comprimento fixo. Entretanto, em uma rede SLICE, requisições podem

demandar quantidades diversas de slots, para um par origem-destino. Consequentemente, a

escolha da rota adequada para cada requisição sugere uma nova estratégia para o cálculo das

rotas, aqui denominada BSR adaptado, e que também pertence à classe de roteamento fixo.

A seguir, são apresentadas as seguintes contribuições:

a) Um algoritmo BSR adaptado, o qual dá liberdade ao planejamento de rotas de

acordo com a largura de banda da requisição com o intuito de balancear de

forma mais efetiva a carga entre os enlaces da rede e assim reservar capacidade

aberta para futuras requisições que venham a surgir;

b) Simulações que comparam o desempenho dos algoritmos de roteamento BSR

adaptado, BSR e DJK, em termos de probabilidade de bloqueio de requisições,

46

considerando as topologias das redes NSFNET, EON, Abilene e Rede

Hipotética Brasileira, sob o plano de controle de uma arquitetura SLICE.

4.2 HEURÍSTICAS PARA O ROTEAMENTO DE ESPECTRO

4.2.1 BSR

O algoritmo BSR consegue obter resultados melhores que os algoritmos de DJK e

RRT em redes ópticas WDM, conforme apresentado em [62]. Logo, o seu emprego direto

para redes SLICE sugere uma melhora na probabilidade de bloqueio também para esta nova

arquitetura, o que foi confirmado por simulação. Porém, melhoras adicionais podem ser

alcançadas para redes SLICE sob roteamento fixo ao se utilizar da característica heterogênea

da largura de banda das requisições para assim gerar uma distribuição mais efetiva nos

enlaces da rede. O BSR foi apresentado no Capítulo 3, Seção 3.2.1. A próxima seção abordará

o algoritmo BSR adaptado para o problema RSA dinâmico.

4.2.2 BSR Adaptado

O BSR para a rede SLICE é adaptado a fim de realizar o roteamento (definir o

conjunto de caminhos) em que as requisições têm largura de banda variável. Logo, para cada

conexão, é definida a quantidade de slots que deverão ser alocados, os quais devem ser

contíguos (i.e. consecutivos) em relação ao índice dos slots e contínuos ao longo dos enlaces

da rota. Se esta condição for atendida ao longo da rota, a atribuição de espectro é realizada;

caso contrário, a conexão é bloqueada.

No BSR adaptado, cada conexão de largura de banda variável é analisada e pode ser

enviada por um caminho específico na rede. Para exemplificar o funcionamento do algoritmo,

observe a Figura 4.1. Suponha que seja solicitada uma conexão do nó 1 para o 4. Suponha

também que cada requisição seja por no máximo 4 slots. Logo, podem existir solicitações por

1, 2, 3 ou 4 slots por conexão. Neste exemplo, é suposto que a requisição solicitada seja por 3

slots. Na Figura 4.1 existem 4 formas de rotear as conexões entre os nós 1 e 4 utilizando o

caminho mais curto. A Tabela 4.1 ilustra o roteamento escolhido para cada demanda. Então,

como foram solicitados 3 slots, os dados serão enviados pelo ―caminho C‖ específico para as

47

requisições de 3 slots. A seguir, é apresentado um resumo das etapas do algoritmo BSR

adaptado.

Figura 4.1. BSR adaptado.

Tabela 4.1. Caminhos específicos por slots Identificação do Caminho Quantidade de slots por conexão Rota

A 1 1-2-3-4

B 2 1-2-5-4

C 3 1-6-3-4

D 4 1-6-5-4

Algoritmo BSR Adaptado

Para a explicação do BSR adaptado, suponha que cada fibra na rede possa transportar

no máximo B slots, e que os pedidos de conexão sejam para k=1,2,...M slots, sendo M o

número máximo de slots requisitados. Seja k

dsR ),( a rota fixa para todas as requisições entre os

nós s e d com pedido de k slots. Visto que o BSR adaptado busca uma melhor distribuição de

carga na rede pela escolha de rotas fixas convenientemente definidas para cada demanda de

tráfego, m

dsR ),( pode ser diferente de n

dsR ),( se m ≠ n. As etapas do BSR adaptado estão

elencadas a seguir:

1) Assuma i=1 e atribua o custo 1 para cada enlace da topologia de rede em questão.

2) Para k=1 até M faça:

2.1) Obtenha o conjunto de rotas mais curtas com o algoritmo de roteamento de

menor caminho (DJK), para as requisições de k slots entre todos os pares de

nós da rede. Defina este conjunto como {Rk}, e guarde-o na memória.

2.2) Atualize os custos dos enlaces, de acordo com a Equação (3.3).

1

2 3

4

6 5

Caminho A

Caminho D

Caminho B

Caminho C

48

3) Simule a rede com a solução de roteamento de todas as menores rotas encontradas no

passo 2.1 (Si=R1∪R

2∪...∪R

M). Faça i=i+1.

4) Se i < T, volte para o passo 2. Caso contrário, vá para o passo 5.

5) Verifique, dentre as T iterações, qual o conjunto de solução de roteamento Si que

apresentou a menor probabilidade de bloqueio. A solução de rotas fixas utilizadas na

simulação desta iteração representa as rotas escolhidas pelo algoritmo BSR adaptado

para as diferentes larguras de requisições.

Logo, após serem definidas as rotas por onde os caminhos ópticos poderão passar, o

próximo passo é usar esse padrão de roteamento na rede e atribuir slots contíguos e contínuos

para os pedidos de caminhos ópticos que surgem dinamicamente. Esta atribuição pode ser

feita aleatoriamente, ou através de algum algoritmo de alocação mais bem elaborado. Para as

simulações, escolheu-se um algoritmo de alocação de prioridade fixa, o First-Fit [60]-[62],

[77], por ser simples, relativamente eficiente e bastante utilizado na literatura, tanto para redes

ópticas WDM quanto para redes SLICE. O objetivo é comparar os algoritmos: BSR adaptado,

BSR e DJK em uma arquitetura SLICE em termos da probabilidade de bloqueio. Observe que

o foco destas simulações é comparar algoritmos de roteamento e não algoritmos de alocação

de espectro. Logo, a escolha de algoritmos de alocação mais sofisticados torna-se marginal.

4.2.2.1 Resultados Numéricos do BSR Adaptado

Para verificar a eficiência do BSR adaptado para redes ópticas SLICE, foram

realizadas simulações em cenários e topologias distintas como NSFNet [16], EON [70],

(Figura 3.6), Brasileira [73] e Abilene [74] (Figura 4.2). Para cada simulação são geradas 107

requisições de acordo com um processo de Poisson, com os pares (origem, destino)

uniformemente escolhidos. Em cada simulação são realizadas cinco replicações com

diferentes sementes de geração de variável aleatória. Os resultados gráficos apresentam os

intervalos de confiança calculados com um nível de confiança de 95%. Cada simulação é

realizada em média de 55 segundos, a partir da utilização do computador Pentium Dual Core

1.86GHz, 2GB de RAM, com Windows 7.

49

a. Rede Brasileira b. Rede Abilene

Figura 4.2. Topologias das redes, Brasileira e Abilene.

Na rede NSFnet, as simulações foram realizadas com requisições de 1, 2, 3,..., 8 slots e

um total de 128 slots disponíveis por enlace. A requisição é bloqueada se não existem slots

contíguos e contínuos disponíveis no caminho entre os pares (origem, destino) para acomodar

a mesma. Define-se a probabilidade de bloqueio de caminhos como o número total de

requisições bloqueadas dividido pelo número total de requisições geradas. De forma similar,

define-se a probabilidade de bloqueio de slots como o número total de slots bloqueados

dividido pelo número total de slots gerados.

A Figura 4.3a ilustra a probabilidade de bloqueio de caminhos e a Figura 4.3b a

probabilidade de bloqueio de slots, para a rede NSFNet. Como se pode observar, o BSR

adaptado consegue uma menor probabilidade de bloqueio que o DJK e o BSR. Em média,

obtém-se uma melhora na probabilidade de bloqueio de caminhos de 36,1% e 17,5% quando

se compara o algoritmo BSR adaptado com o DJK e o BSR, respectivamente. Para a

probabilidade de bloqueio de slots, obtém-se desempenho de forma alinhada com o bloqueio

de caminhos, só que os percentuais são de 35,6% e 17,2%.

(a) (b)

Figura 4.3. Probabilidade de Bloqueio de Caminhos (a) e Probabilidade de Bloqueio de Slots (b) em função da

carga da rede para os algoritmos Dijkstra, BSR e BSR Adaptado na rede NSFNet. As requisições são de 1, 2,

3, ..., 8 slots e há um total de 128 slots disponíveis por enlace.

12

1110

9

67

8

5

4

3

2

1

150 160 170 180 190 200 210 220 230 240 250 260 270

1E-3

0,01

0,1

Pro

bab

ilid

ad

e d

e B

loq

ueio

de C

am

inh

os

Erlang

Dijkstra

BSR

BSR Adaptado

150 160 170 180 190 200 210 220 230 240 250 260 270

1E-3

0,01

0,1

0,2

Pro

bab

ilid

ad

e d

e B

loq

ueio

de S

lots

Erlang

Dijkstra

BSR

BSR Adaptado

50

Para a rede EON, realizaram-se as simulações num cenário diferente, onde foram

assumidas requisições com 1, 2, 4 ou 8 slots e um total de 128 slots disponíveis por enlace. As

Figuras 4.4a e 4.4b apresentam a probabilidade de bloqueio de caminhos e a probabilidade de

bloqueio de slots, respectivamente. Para esta topologia, o BSR adaptado consegue novamente

uma menor probabilidade de bloqueio quando comparado aos algoritmos DJK e BSR. Em

média, a melhora na probabilidade de bloqueio de caminhos foi de 73,9% e 26,9%, quando se

compara o BSR adaptado com o DJK e o BSR, respectivamente. Para a probabilidade de

bloqueio de slots, os percentuais de desempenho foram semelhantes. Dado que a topologia

EON é muito mais conectada do que a NSFNet e, portanto, permite um conjunto maior de

soluções (rotas), o BSR adaptado operando na rede EON obteve melhores percentuais do que

na NSFNet.

(a) (b)


carga da rede para os algoritmos Dijkstra, BSR e BSR Adaptado na rede EON. As requisições são de 1, 2, 4

ou 8 slots e há um total de 128 slots disponíveis por enlace.

Na rede Brasileira (Figura 4.2a), que contém 12 nós e 40 enlaces, realizaram-se

simulações com requisições de 1, 2, 3, ..., 16 slots e um total de 256 slots disponíveis por

enlace. Novamente, observa-se na Figura 4.5 bom desempenho do BSR adaptado na

probabilidade de bloqueio de caminhos e na probabilidade de bloqueio de slots, com ganhos

de 37% e 18% em relação ao DJK e BSR, respectivamente.

240 260 280 300 320 340 360 380

5E-4

1E-3

0,01

0,1

Pro

bab

ilid

ad

e d

e B

loq

ueio

de C

am

inh

os

Erlang

Dijkstra

BSR

BSR Adaptado

240 260 280 300 320 340 360 380

1E-3

0,01

0,1

P

rob

ab

ilid

ad

e d

e B

loq

ueio

de S

lots

Erlang

Dijkstra

BSR

BSR Adaptado

51

(a) (b)


carga da rede para os algoritmos Dijkstra, BSR e BSR Adaptado na rede Brasileira. As requisições são de 1, 2,

3,..., 16 slots, e há um total de 256 slots disponíveis por enlace.

Por fim, foram realizadas simulações para a rede Abilene (Figura 4.2b), cuja topologia

contém 11 nós e 28 enlaces, assumindo-se requisições de 1, 2, 4, 8 ou 16 slots e um total de

256 slots disponíveis por enlace. Em média, a melhora na probabilidade de bloqueio de

caminhos, quando se usa o BSR adaptado, foi de 47,9% e 21,2% em relação ao DJK e BSR,

respectivamente (Figura 4.6a). De forma alinhada ao bloqueio de caminhos, o desempenho

para a probabilidade de bloqueio de slots obteve percentuais de melhora de 46,6% e 20,5%

(Figura 4.6b).

(a) (b)

Figura 4.6. Probabilidade de Bloqueio de Caminhos (a) e Probabilidade de Bloqueio de Slots (b) em função

da carga da rede para os algoritmos Dijkstra, BSR e BSR Adaptado na rede Abilene. As requisições são de

1, 2, 4, 8 ou 16 slots, e há um total de 256 slots disponíveis por enlace.

Com o intuito de analisar a influência das topologias de rede na probabilidade de

bloqueio, foram realizadas simulações para 33 distintas topologias, avaliando a relação entre a

distribuição dos graus dos nós da rede e a probabilidade de bloqueio, no Apêndice B.

160 180 200 220 240 260 280 300

1E-3

0,01

0,1

Pro

bab

ilid

ad

e d

e B

loq

ueio

de C

am

inh

os

Erlang

Dijkstra

BSR

BSR Adaptado

160 180 200 220 240 260 280 300

1E-3

0,01

0,1

0,2

Pro

bab

ilid

ad

e d

e B

loq

ueio

de S

lots

Erlang

Dijkstra

BSR

BSR Adaptado

120 130 140 150 160 170 180 190 200 210 220 230 240

1E-3

0,01

0,1

Pro

bab

ilid

ad

e d

e B

loq

ueio

de C

am

inh

os

Erlang

Dijkstra

BSR

BSR Adaptado

120 130 140 150 160 170 180 190 200 210 220 230 240

1E-3

0,01

0,1

0,2

Pro

bab

ilid

ad

e d

e B

loq

ueio

de S

lots

Erlang

Dijkstra

BSR

BSR Adaptado

52

Na próxima seção, é proposta a heurística YBS (Yen-BSR-SLICE), a qual realiza o

roteamento de espectro de forma fixo-alternativa, através do algoritmo de Yen [68]. No YBS,

para cada par (origem, destino), tem-se k caminhos mínimos que tentam realizar a alocação

dos recursos de forma a reduzir a probabilidade de bloqueio da rede.

4.2.3 YBS (Yen-BSR-SLICE)

Na literatura, diversos trabalhos foram propostos com o algoritmo k-menores

caminhos, também conhecido como algoritmo de Yen [68]. Em [16], o algoritmo BLSA

(Balanced Load Spectrum Allocation) utiliza o algoritmo de Yen para encontrar os k

caminhos mais curtos para cada par (origem, destino). O objetivo deste algoritmo é reduzir a

quantidade de slots alocados na rede. Jinno [13] propõe o RMSA (Routing, Modulation-Level,

and Spectrum Assignment), que examina os k caminhos mais curtos para cada requisição e os

escolhe com base na quantidade de slots contínuos disponíveis. Zhu [8] propôs o algoritmo

HSMR (Hybrid Single-/Multi-path Routing), e Wan [75] o KSP (k-Shortest Path), os quais

utilizam o algoritmo de Yen para calcular o conjunto de rotas entre os pares (origem, destino),

e assim, reduzir a probabilidade de bloqueio. Wan também analisou os resultados com os

valores de k iguais a 2, 4 e 6. Scaraficci [58] propõe o algoritmo MCP-ZBA (Maximum

Capacity Path and ZoneBased Assignment), que apresenta uma política de alocação de

espectro com base em zonas, e utiliza um mecanismo de roteamento de caminhos alternativos.

Nesta seção é apresentado o algoritmo YBS (Yen-BSR-SLICE), proposto para realizar

o roteamento de espectro de forma alternativa com objetivo de reduzir a probabilidade de

bloqueio da rede. Também é analisado o valor máximo de k (k limite), ou seja, o valor cujo

aumento do número de caminhos alternativos, entre a origem e o destino, não impacta na

probabilidade de bloqueio.

Algoritmo Proposto

Conforme apresentado anteriormente, diversos trabalhos na literatura utilizam o

algoritmo k-menores caminhos para encontrar um conjunto de caminhos para cada par

(origem, destino). No entanto, se todos os enlaces têm os mesmos pesos, por exemplo, iguais

a 1, pode haver diversas possibilidades de custo mínimo factíveis de serem utilizadas para

formar os k caminhos entre os pares (origem, destino) da rede. Para ilustrar essas

53

(a) (b)

(c) (d)

(e)

Figura 4.7. Algoritmo YBS (a) quatro possíveis caminhos entre o nó origem 1 e destino 4 (b) número de slots

alocados na rede SLICE (c) valor c(l)i para cada enlace da rede (d) custo para cada caminho (e) caminhos

escolhidos.

possibilidades veja o exemplo da Figura 4.7a, onde existem quatro caminhos mais curtos

entre os nós 1 e 4, todos com três saltos: 1-2-3-4; 1-2-5-4; 1-6-3-4 e 1-6-5-4. Portanto, se k =

2, deve-se escolher, dentre estes quatro caminhos, as duas melhores rotas entre os nós 1 e 4.

Nesta situação, como os pesos são iguais para todos os enlaces, é verificada a quantidade de

slots alocados em cada caminho.

Em [76], porpomos o algoritmo Yen-BSR para resolver o problema de roteamento de

comprimentos de onda em redes WDM, com o intuito de reduzir a probabilidade de bloqueio

de conexões. Posteriormente, foi proposto o Yen-BSR para a arquitetura de rede SLICE que,

além de analisar a probabilidade de bloqueio, avalia a evolução dos valores de k caminhos e a

alocação de slots por enlace. Novas métricas foram analisadas para avaliar os resultados. O

Yen-BSR-SLICE, ou simplesmente YBS, utiliza a estrutura do algoritmo BSR, descrito na

Seção 4.2.2, originalmente proposto para o roteamento fixo. No entanto, o YBS inclui o

54

roteamento fixo-alternativo, que possibilita o roteamento por k-caminhos mais curtos e reduz

a probabilidade de bloqueio de requisições quando comparado com outros algoritmos.

Para exemplificar o funcionamento do YBS, observe a Figura 4.7. Supõe-se que haja

uma requisição de um slot do nó origem 1 para o nó destino 4 e k=2, ou seja, há duas

possibilidades de caminhos para realizar a alocação dos recursos espectrais. Supõe-se também

que o peso de cada enlace seja igual a 1. Ao observar a Figura 4.7a, percebe-se que existem

quatro possíveis caminhos mais curtos por onde essa requisição pode ser estabelecida. Então,

é necessário escolher dois, dentre estes, para disponibilizar à requisição. A Figura 4.7b

apresenta uma rede SLICE, com os respectivos slots alocados por enlace na iteração i=0 do

algoritmo. Neste exemplo, cada enlace contém oito slots, nos quais os marcados com ―x‖

estão alocados. Ao aplicar a equação (3.3) tem-se os valores de c(l)i+1 para cada enlace

(Figura 4.7c). Então, deve-se escolher dois caminhos para tentar alocar a requisição do nó 1

para 4. Para isto, o custo de cada caminho é computado (Figura 4.7d). Obtido o menor custo,

são definidos os dois melhores caminhos (k=2). Neste exemplo, os melhores caminhos são 1-

2-5-4 e 1-6-5-4 (Figura 4.7e), com custos de 3,0005 e 3,0007, respectivamente.

O fluxograma do YBS é apresentado na Figura 4.8. Ao final do algoritmo, é

verificado, dentre as T iterações, qual a solução de roteamento com menor probabilidade de

bloqueio. Esta conterá o conjunto de k caminhos escolhidos para realizar o roteamento do

YBS.

55

Figura 4.8. Fluxograma do algoritmo YBS

4.2.3.1 Resultados Numéricos

As simulações foram realizadas para avaliar o desempenho do algoritmo YBS e os

resultados foram comparados aos dos algoritmos de Dijkstra, BSR e Yen. A topologia

utilizada foi a EON (Figura 3.6b) com 256 slots disponíveis por enlace com requisições

geradas aleatoriamente entre 1 a 16 slots. Para cada simulação são geradas 107 requisições de

acordo com um processo de Poisson, com os pares (origem, destino) uniformemente

escolhidos.

A Figura 4.9 mostra os resultados da probabilidade de bloqueio em função da carga de

rede para valores de k iguais a 2, 4, 6, 8 e 10. O YBS apresenta, em todas as simulações,

menor probabilidade de bloqueio quando comparado aos algoritmos de Dijkstra, BSR e Yen.

Para k=2, o BSR obteve o mesmo resultado em termos de probabilidade de bloqueio que o

algoritmo de Yen. Este resultado era esperado, visto que o BSR realiza o roteamento de forma

mais otimizado. Isto mostra o quão eficiente é o algoritmo BSR, pois com apenas uma

possibilidade de rota ele consegue o mesmo desempenho de um algoritmo com o dobro de

Início

Inicializar os valores das variáveis: i =0, T (dado

de entrada) e c(l)0 =1

Calcular os k-menores caminhos para cada

par(fonte, destino).

Atualizar os custos dos enlaces para a próxima

iteração utilizando a Eq. (3.3), Seção 3.2.1

i=i+1

i<TSim

Fim

Encontrar a nova solução de roteamento Si+1

utilizando o algoritmo de Yen.

Simular a rede com a solução de roteamento Si+1

Não

56

possibilidade de rota. Contudo, o algoritmo de Yen consegue reduzir significativamente a

probabilidade de bloqueio, para k>2.

A Figura 4.9e ilustra o valor efetivo máximo de k (k = 10), ou seja, o valor cujo

aumento do número de caminhos (k>10) não impacta na probabilidade de bloqueio. Para este,

percebe-se que as heurísticas YBS e Yen apresentam valores muito próximos. Isto ocorre

porque, para a topologia EON, alcançou-se a quantidade máxima de caminhos que

influenciam na probabilidade de bloqueio.

(a) (b)

(c) (d)

(e)

Figura 4.9. Probabilidade de bloqueio para os valores de k igual a 2, 4, 6, 8 e 10

175 200 225 250 275 300 325 350 375 400

1E-7

1E-6

1E-5

1E-4

1E-3

0,01

0,1

Pro

bab

ilid

ad

e d

e B

loq

ueio

Erlang

DIJKSTRA

BSR

Yen K=2

YBS K = 2

175 200 225 250 275 300 325 350 375 400

1E-7

1E-6

1E-5

1E-4

1E-3

0,01

0,1

Pro

bab

ilid

ad

e d

e B

loq

ueio

Erlang

DIJKSTRA

BSR

Yen K=4

YBS K = 4

175 200 225 250 275 300 325 350 375 400

1E-7

1E-6

1E-5

1E-4

1E-3

0,01

0,1

Pro

bab

ilid

ad

e d

e B

loq

ueio

Erlang

DIJKSTRA

BSR

Yen K=6

YBS K = 6

175 200 225 250 275 300 325 350 375 400

1E-7

1E-6

1E-5

1E-4

1E-3

0,01

0,1

Pro

bab

ilid

ad

e d

e B

loq

ueio

Erlang

DIJKSTRA

BSR

Yen K=8

YBS K = 8

175 200 225 250 275 300 325 350 375 400

1E-7

1E-6

1E-5

1E-4

1E-3

0,01

0,1

Pro

bab

ilid

ad

e d

e B

loq

ueio

Erlang

DIJKSTRA

BSR

Yen K=10

YBS K = 10

57

A Figura 4.10 ilustra o número de slots alocados por fibra para k = 10. Pode-se

observar que os algoritmos YBS e Yen alocam, em cada enlace, uma quantidade próxima de

slots, e assim obtêm resultados similares na simulação com k=10 (Figura 4.9e). A Tabela 4.2

e a Tabela 4.3 mostram outras métricas analisadas dos algoritmos de Yen e YBS para diversos

valores de k.

Ao analisar estas tabelas, é percebido que, quando se compara o número mínimo de

alocações, o YBS realiza mais alocações por enlace do que o Yen. No entanto, ao analisar o

número máximo de alocações por enlace, o YBS realiza menos que o Yen. O desvio padrão

das simulações mostra que a variação dos slots alocados por elace do YBS é menor, e isso

indica que as alocações por enlaces possuem tendência de estarem mais próximas da média,

ou seja, de realizar efetivamente uma melhor distribuição do tráfego na rede. Por fim, o

número total de alocações na rede do YBS é maior que o do Yen.

Figura 4.10. Número de slots alocados por fibra para k=10

Tabela 4.2. Dados de alocação do algoritmo de Yen

Tabela 4.3. Dados de alocação do algoritmo de YBS

A Figura 4.11 ilustra a evolução da probabilidade de bloqueio do algoritmo YBS para

cada valor de k em função do tráfego em Erlang. Pode-se observar que houve uma redução da

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

0

10

20

30

40

50

60

70

80

90

100

110

120

130

140

150

160

170

Nú

mero

de s

lots

alo

cad

os

Enlace

Yen

YBS

K

Número mínimo de

alocações por enlace

Número máximo de


Mediana de alocações

por enlace

Média de slots

alocados por enlace

Desvio padrão de


Número total de

alocação na rede

2 15,06 137,59 62,99 68,38 32,60 5196,70

4 10,91 147,56 66,90 69,60 35,85 5289,36

6 15,41 139,49 67,99 71,71 33,57 5449,76

8 14,14 142,46 64,88 71,41 36,27 5426,91

10 12,09 144,79 64,69 71,40 35,11 5426,39

K

Número mínimo de


Número máximo de


Mediana de alocações

por enlace

Média de slots

alocados por enlace

Desvio padrão de


Número total de

alocação na rede

2 16,18 123,24 64,92 69,26 28,37 5263,40

4 18,66 134,39 67,19 71,08 28,64 5402,28

6 16,05 127,34 68,88 71,80 28,33 5452,63

8 17,74 130,69 66,48 71,70 29,05 5449,45

10 18,90 132,28 68,29 71,52 28,66 5435,49

58

probabilidade de bloqueio de k = 2 até k = 10. A Figura 4.12 mostra a probabilidade de

bloqueio em função do aumento do valor de k. Note-se que, quanto maior for o valor de k

menor a probabilidade de bloqueio e k = 10 atinge o limite de melhorar entre o Yen e YBS.

Figura 4.11. Evolução da probabilidade de bloqueio do algoritmo YBS para cada valor de k.

Figura 4.12. Probabilidade de bloqueio por k.

Até o momento, foram apresentadas heurísticas para o roteamento de espectro em

redes SLICE. Na próxima seção, será apresentada uma heurística para a alocação de espectro.

4.3 HERUÍSTICAS PARA ALOCAÇÃO DE ESPECTRO

4.3.1 MSCL (Min Slot-Continuity Capacity Loss)

Em redes WDM, as heurísticas mais eficientes para roteamento e alocação de

comprimento de onda estão geralmente compreendidas na classe dos algoritmos First-Fit, ou

175 200 225 250 275 300 325 350 375 400

1E-7

1E-6

1E-5

1E-4

1E-3

0,01

0,1

Pro

bab

ilid

ad

e d

e B

loq

ueio

Erlang

YBS K = 2

YBS K = 4

YBS K = 6

YBS K = 8

YBS K = 10

2 4 6 8 10

1E-7

1E-6

1E-5

1E-4

1E-3

0,01

0,1

Pro

bab

ilid

ad

e d

e B

loq

ueio

K

Yen - 270 Erlang

YBS - 270 Erlang

Yen - 180 Erlang

YBS - 180 Erlang

59

na daqueles que efetivamente calculam a perda de capacidade de futuras requisições de

caminhos [60]-[62], [74], [78].

Os algoritmos da classe First-Fit são preferidos na prática devido à baixa

complexidade e ao pouco tempo computacional exigido na sua execução, mas os algoritmos

que calculam a perda da capacidade obtêm melhores resultados. A adaptação do algoritmo

First-Fit (FF) para a rede SLICE é trivial e vários trabalhos têm usado [29], [79].

Outro algoritmo muito utilizado que é composto de uma lista baseada na utilização dos

comprimentos de onda (referido na literatura como mais usado: MU) tem um desempenho

melhor do que o algoritmo First-Fit (FF) em redes WDM, o oposto é observado em redes

SLICE [80].

Uma nova atribuição de espectro, conhecida como LUSF (Least Unusable Spectrum

First), foi proposta em [60] para evitar o aparecimento de slots isolados que não podem ser

utilizados para estabelecer uma solicitação de caminho óptico com menor capacidade, mas o

seu desempenho é ligeiramente superior ao do FF. Outros algoritmos RSA que trabalham com

a importância da continuidade do espectro têm sido propostos em [75] e [80], mas eles

executam roteamento e alocação de espectro em conjunto.

Logo, nenhum algoritmo que calcula efetivamente a perda da capacidade de futuras

requisições de caminho com largura de banda variável foi adaptado a partir de WDM para

redes SLICE. O cálculo da perda de capacidade não é tão trivial e deve levar em consideração

que os pedidos são atribuídos com um número variável de slots.

Abaixo, é apresentada uma proposta de como a perda de capacidade pode ser

calculada em redes SLICE, e os resultados são comparados com os dos algoritmos First-Fit e

Random. Em todos os casos analisados, a heurística proposta, chamada de MSCL (Min Slot-

Continuity Capacity Loss), obteve melhores resultados.

Algoritmo Proposto

Nas redes SLICE, cujas solicitações por distintas larguras de banda ocorrem

dinamicamente na rede, se a alocação de slots não contemplar os slots usados e a

disponibilidade em espaços na rede, o comportamento benéfico de se deixar o máximo de

capacidade aberta para futuras solicitações não será completamente alcançado.

Na análise a seguir, suponha que cada fibra possa transportar no máximo S slots

(indexado como 1, 2, ..., S). Para uma requisição de n slots, deve-se encontrar um slot inicial

60

Si (1 ≤ i ≤ S – n +1), tal que os slots si, si+1, ... , si+n−1 estejam todos livres em todos os enlaces

do caminho. Para simplificar, sempre que o slot si for referido como o alocado para uma

requisição, ele é o primeiro slot do conjunto contíguo de slots si, si+1, ... , si+n−1 usados para

acomodar a requisição. Nas discussões a seguir, serão usadas as seguintes notações e

definições:

R é o conjunto de todas as possíveis rotas da rede;

r é a rota selecionada para a requisição de caminho;

Ir é o conjunto de todas as rotas que interferem com r, isto é, que têm ao menos

um enlace em comum r;

ψ é o estado atual da rede, isto é, o conjunto de rotas estabelecidas e seus

respectivos slots atribuídos;

ψ' é o próximo estado da rede uma vez que o caminho óptico é estabelecido;

D<r>

(ψ) é um vetor booleano, chamado de vetor de disponibilidade da rota r para

o estado da rede ψ. Di<r>

(ψ) (1 ≤ i ≤ S) indica a disponibilidade do slot i na rota r

para o estado de rede ψ.

Di<r>

(ψ) = 1, se o slot i está livre em todos os enlaces da rota r;

Di<r>

(ψ) = 0, caso contrário;

Identificação de Possíveis Alocações

Para o estado da rede ψ, cada vetor disponibilidade D<r>

(ψ) é composto por alguns

―buracos‖ (isto é, uma sequência máxima de slots adjacentes livres) que podem acomodar

algumas requisições de caminho. Seja h1<r>

, h2<r>

, ..., hm<r>

a existência de m buracos em

D<r>

(ψ). O comprimento de um buraco i, |hi<r>

|, 1 ≤ i ≤ m, é definido pelo número de slots

que o compõem. A Figura 4.13 ilustra o vetor disponibilidade, D<r>

(ψ), de uma rota r com

dois buracos, h1<r>

e h2

<r>, compostos, respectivamente, por quatro e dois slots.

Figura 4.13. Vetor disponibilidade de uma rota r

Note que uma requisição de n slots pode ser alocada na rota r em qualquer buraco de

comprimento |hi<r>

| ≥ n. Contudo, é importante observar que essa requisição pode ser alocada

1 1 1 1 0 1 1 0

h1<r> h2

<r>

D<r>(ψ)

61

de diferentes formas em cada um desses buracos. Por exemplo, seja um buraco hi<r>

qualquer

formado pelos slots , 11 nSj . A requisição de n slots pode ser

alocada em um dos seguintes conjuntos de slots: ( ), ( ), ...,

( | | |

| ). Ou seja, existem |hi

<r>| – n+1 formas de alocar a

requisição de n slots no buraco hi<r>

.

A Figura 4.14 ilustra as possibilidades de alocação de uma requisição de dois slots no

vetor disponibilidade apresentado na Figura 4.13. Como pode ser observado, para h1<r>

, pode-

se utilizar os slots das posições um e dois; dois e três; ou três e quatro. Já para h2<r>

, dado que

a requisição encaixa-se perfeitamente no buraco, há apenas uma forma de inseri-la, que é com

a utilização dos slots 6 e 7.

Figura 4.14. Possibilidades de alocação de slots

Finalmente, é fácil perceber que sob o estado da rede ψ, o número total de

possiblidades que uma requisição de comprimento n slots pode ser alocada na rota r com o

vetor disponibilidade D<r>

(ψ), composto por m buracos, h1<r>

, h2<r>

, ..., hm<r>

, é dado por:

( ) ∑ ( )

(4.1)

onde max(x,y) retorna o valor máximo entre x e y.

Para exemplificar o cálculo do número de possibilidades de alocação, observe a Figura

4.14. Note que, para uma requisição de dois slots existem quatro possibilidades de alocação,

três para h1<r>

e uma para h2<r>

. A Figura 4.15 ilustra o número de possibilidades de alocação

de requisições por 1 a 8 slots no vetor de disponibilidade apresentado na Figura 4.14. Para

este cálculo, utiliza-se a Equação (4.1).

Figura 4.15. Número de possibilidades de alocação de slots requisitados no exemplo da Figura 4.14

1 1 1 1 0 1 1 0

h1<r>

h2<r>

D<r>(ψ)

6 4 2 1 0 0 0 0

1 2 3 4 5 6 7 8Número de Possibilidade

de Alocação

Slots Requisitados

62

Perda de Capacidade

Como definido anteriormente, uma vez conhecido o conjunto de buracos em D<r>

(ψ),

o número de possibilidades que uma requisição de comprimento n pode ser alocada em r é

facilmente determinado por (4.1). Seja D

(ψ) o vetor disponibilidade de um caminho p Ir,

isto é, de um dos caminhos que interferem com r e suponha que o slot si seja o avaliado para

alocar uma requisição de k slots na rota r. Seja Xi,k um vetor booleano de comprimento S com

todos os elementos iguais a 1, exceto aqueles com índices correspondentes aos slots alocados

à requisição, isto é, índices i, i+1, ..., i+k – 1. O vetor disponibilidade de qualquer caminho p

Ir, após a requisição de k slots ser alocada no slot si da rota r pode ser determinado por:

( ) ( ) (4.2)

onde * representa a operação booleana ―e” (and).

A Figura 4.16 ilustra duas rotas P1 e P2 que interferem com a rota r. Para ambas, deve-

se empregar o cálculo da perda de capacidade.

Figura 4.16. Exemplo de dois caminhos que interferem com r

A Figura 4.17 representa a operação booleana da Equação (4.2) realizada no vetor de

disponibilidade de uma das rotas interferentes Ir. Supõe-se que a requisição seja composta

por três slots e que esteja sendo testada a alocação com início na segunda posição do vetor

disponibilidade da rota r, ou seja, s2, s3 e s4. O vetor booleano Xi,k é gerado com base no

primeiro slot que se esteja tentando alocar para a requisição. Posteriormente, utiliza-se este

vetor Xi,k através da operação booleana e (and) com o vetor disponibilidade de caminhos

interferentes D

(ψ). Ao final, é gerado o vetor disponibilidade após a alocação de k slots,

D

(ψ').

p1

p2

r

63

Figura 4.17. Exemplo da operação booleana e (and) realizada na Equação (4.2)

D

(ψ´) informa a disponibilidade dos slots na rota p durante o estado da rede ψ´, ou

seja, que ocorreria imediatamente após a alocação da requisição analisada. Essa informação

será usada para calcular o número de possibilidades para alocar futuras requisições de

comprimento variável nas rotas interferentes de Ir. Consequentemente, após a alocação da

requisição de k slots no slot si da rota r, a perda de capacidade de requisições de n slots é dada

por:

( ) ∑ ( ) ( ). (4.3)

Finalmente, a perda total de capacidade da rede é definida como:

n

nCC )(

,

(4.4)

onde a soma acima é realizada através de toda a demanda de tráfego existente.

Para exemplificar a perda de capacidade, observe o exemplo descrito na Figura 4.18.

A Figura 4.18a ilustra o estado inicial da rede. Supõe-se que foi gerada uma requisição (1r ) de

três slots do nó origem 3 para o nó destino 0, cujo caminho seja 3-2-1-0. Note que há várias

formas de alocar a requisição usando três slots contíguos dentre os slots 2 a 9, ao longo dos

enlaces de 1r . Obviamente, o caminho 3-2 (

2r ), por interferir com o caminho 3-2-1-0, sofrerá

uma perda de capacidade no número de formas de conexões que podem ser alocadas. Por

exemplo, se a requisição 1r for alocada do slot 2 ao 4 (Figura 4.18b), serão formados dois

buracos na disponibilidade do caminho 3-2, 2

1

rh e

2

2

rh . Note que, além do fato de futuros

caminhos de comprimento de 1 a 5 terem suas capacidades bastante reduzidas com tal

alocação, caminhos de comprimento de 6 e 7 slots sequer teriam possibilidade futura de

0

1

1

1

1

0

1

0

D<r>(ψ)

1

0

0

0

1

1

1

1

Xi,k

1

1

1

0

0

1

0

0

D(ψ)

1

0

0

0

0

1

0

0

D(ψ')

64

alocação. Contrariamente, se a requisição 1r for alocada do slot 7 ao 9 (Figura 4.18c), surgirá

apenas um buraco na disponibilidade de 2r ,

2

1

rh e, não apenas o número de possibilidades de

alocações futuras de comprimento de 2 a 5 slots serão maiores, como também possibilitará

que futuras requisições de 6 e 7 slots ainda consigam ser atendidas. Contudo, todos os

caminhos que interferem com a rota da requisição devem ser analisados.

(a) (b)

(c)

Figura 4.18. Exemplo da perda de capacidade

Dentre os possíveis slots a serem alocados para atender uma requisição, o algoritmo

proposto escolherá a alocação que proporciona a menor perda de capacidade do número de

formas de todas as rotas que interferem com a rota da requisição, como apresentado em (4.4).

4.3.1.1Resultados Numéricos

Esta seção apresenta alguns resultados de simulações para o algoritmo MSCL, além de

comparações com os algoritmos First-Fit (FF) e Random (RD).

Inicialmente, são mostradas as simulações para a rede NSFNet (Figura 3.6a) com

S=256 slots e demanda de tráfego uniforme entre cada par de nós. É utilizado o algoritmo de

menor caminho (Dijkstra [69]) para gerar os caminhos na fase de roteamento e um processo

de Poisson para gerar as requisições com tempo de duração Exponencial. Simula-se um

número permitido de slots por demanda entre 1 e 32, cujo número de slots para uma

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9

01

23

45

67

89

5

0 1 2

34

X X X X

1 2 3 4 5 6 7 8 9 1010 9 8 7 6 5 4 3 2 1

Número de possibilidade de

alocação no caminho 3-2

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9

01

23

45

67

89

5

0 1 2

34

X X X X

1 2 3 4 5 6 7 8 9 107 5 3 2 1 0 0 0 0 0



X X X X X X

XX

X

2

1

rh

2

2

rh

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9

01

23

45

67

89

5

0 1 2

34

X X X X

1 2 3 4 5 6 7 8 9 107 6 5 4 3 2 1 0 0 0



X X X X X X

XX

X

2

1

rh

65

requisição é selecionado aleatoriamente com igual probabilidade dentro do conjunto

considerado (distribuição uniforme). A requisição é bloqueada se não houver slots contíguos e

contínuos disponíveis no caminho mais curto para alocar a requisição.

A Figura 4.19 ilustra as métricas de comparação para o cenário de simulação descrito

acima. A primeira observação é que o algoritmo RD tem um desempenho muito ruim quando

comparado com o FF e o MSCL. Na verdade, ao utilizar um algoritmo simples, como o FF,

que apenas dá prioridade para slots em uma ordem estática pré-definida, é possível conseguir

reduções consideráveis na probabilidade de bloqueio. Efetivamente, o gráfico sugere que a

melhoria de desempenho entre os algoritmos FF e RD na rede SLICE seja consideravelmente

mais eminente do que em redes WDM [74].

Se a complexidade na alocação de slots pode ser aumentada, por usar um método de

alocação de slots mais sofisticado como o MSCL, as probabilidades de bloqueio de caminho e

de slots podem ser ainda mais reduzidas para qualquer valor de tráfego. O ganho de

desempenho entre MSCL e FF não é tão alto quanto o encontrado entre FF e RD, mas ainda é

notável o suficiente para justificar o aumento da complexidade introduzida pelo MSCL.

(a) (b)


da carga da rede para os algoritmos RD, First-Fit, e MSCL na rede NSFNet. As requisições são de 1, 2, 3,...,

32 slots, e há um total de 256 slots disponíveis por enlace.

Para mostrar que os resultados apresentados anteriormente não são casos isolados,

foram realizadas simulações com a rede EON (Figura 3.6b) com S=128 slots por enlace e um

diferente cenário de tráfego, onde os caminhos são requisitados com 1, 2, 4, 8 ou 16 slots. A

Figura 4.20 ilustra a probabilidade de bloqueio de caminhos e slots. Observe que conclusões

semelhantes podem ser inferidas com este novo cenário de rede.

55 60 65 70 75 80 85 90 95 1003E-3

0,01

0,1

Pro

bab

ilid

ad

e d

e B

loq

ueio

de C

am

inh

os

Erlang

Random

First-Fit

MSCL

55 60 65 70 75 80 85 90 95 1003E-3

0,01

0,1

0,2

Pro

bab

ilid

ad

e d

e B

loq

ueio

de S

lots

Erlang

Random

First-Fit

MSCL

66

(a) (b)


da carga da rede para os algoritmos RD, First-Fit, e MSCL na rede EON. As requisições são de 1, 2, 4, 8, 16

slots, e há um total de 128 slots disponíveis por enlace.

100 120 140 160 180 200

3E-3

0,01

0,1

Pro

bab

ilid

ad

e d

e B

loq

ueio

de C

am

inh

os

Erlang

Random

First-Fit

MSCL

100 120 140 160 180 200

3E-3

0,01

0,1

0,3

Pro

bab

ilid

ad

e d

e B

loq

ueio

de S

lots

Erlang

Random

First-Fit

MSCL

67

CAPÍTULO 5

5. CONCLUSÕES

Nesta tese estudou-se o problema de roteamento e alocação de espectros (RSA) em

redes ópticas elásticas, conhecidas como redes SLICE. Neste estudo, foram propostas

heurísticas para resolver o RSA e simulações computacionais foram realizadas para

comprovar a eficiência das estratégias propostas.

No Capítulo 2, apresentaram-se as principais características das redes ópticas elásticas

e foram realizadas comparações entre as redes WDM e SLICE. Em particular, na rede SLICE,

foi tratado o problema de roteamento e alocação de espectro.

No Capítulo 3, deram-se inicio às contribuições desta tese. Para o problema de RSA

estático, foram apresentadas duas heurísticas capazes de prover resultados ótimos para

algumas redes pequenas analisadas, com 5 e 6 nós. As heurísticas obtiveram tempos de

simulações aceitáveis, na ordem de milissegundos, e conseguirem melhores resultados que as

heurísticas SPSR e BLSA, com tráfego uniforme e não uniforme. Desta forma, percebe-se que

as heurísticas BSR e ILR utilizadas para balancear a carga melhoram o congestionamento e

dividem a demanda de tráfego nas redes SLICE de forma mais apropriada.

No Capítulo 4, com o intuito de dar suporte ao planejamento de redes ópticas no

cenário dinâmico (on-line), três heurísticas foram propostas: duas para o roteamento e uma

para alocação de espectro. O BSR adaptado teve sua eficiência demonstrada através de

comparações com o BSR e o algoritmo de Dijkstra, em diversos cenários. Percebe-se que a

estratégia utilizada para balancear a carga da rede reduziu a probabilidade de bloqueio e,

assim, os recursos espectrais foram preservados para futuras demandas de tráfego. O

algoritmo YBS foi proposto com o intuito de utilizar rotas alternativas para alocação de

espectro. Este obteve melhor desempenho que os algoritmos de Dijkstra, Yen e BSR. Para o

YBS, foi analisado, além da probabilidade de bloqueio, o valor máximo de k e outros

parâmetros, mostrando a eficiência do algoritmo.

Para a alocação de espectro, foi proposta uma nova heurística chamada de MSCL, que

introduz um novo conceito para as redes SLICE, a perda de capacidade. Nesta, objetiva-se

preservar os recursos espectrais para a alocação de futuras requisições. Nos cenários

apresentados, foram analisados os resultados das simulações, sendo demonstrado que o

MSCL é eficaz para reduzir tanto a probabilidade de bloqueio de caminhos quanto a

68

probabilidade de bloqueio de slots, quando comparada com os algoritmos First-Fit e Random.

Ou seja, a redução de perda de capacidade como proposta pelo MSCL, permite que a

utilização do espectro possa ser realizada de forma mais eficiente.

No Apêndice A, foi apresentado um simulador de redes ópticas SLICE para o cenário

estático, chamado de SimRSA. Este simulador foi desenvolvido com interface gráfica, para

possibilitar o estudo de redes ópticas elásticas. Nesse, foram implementas três heurísticas:

BSR, BLSA e SPSR.

No Apêndice B, foram analisadas diversas topologias de rede, com verificação da

probabilidade de bloqueio, grau médio dos nós e a distribuição deles na rede. Estas análises

foram realizadas com o intuito de observar o comportamento dos resultados dos algoritmos

relacionadas às topologias de rede.

5.1 TRABALHOS FUTUROS

Pesquisas na área de redes ópticas elásticas vêm, cada vez mais, despertando interesse

dos pesquisadores, devido ao tráfego da Internet ser heterogêneo e assim necessitar de largura

de banda variável.

Ao dar continuidade à abordagem utilizada nesta tese, o estudo de outras heurísticas,

principalmente para alocação de espectro, pode fazer parte de investigações futuras para este

trabalho. Nesta, pode-se investigar outros métodos para realizar a perda de capacidade da rede

e reduzir ainda mais a probabilidade de bloqueio de requisições. Outro aspecto importante a

ser analisado é a fragmentação causada pela introdução da elasticidade da rede, visto que o

processo de estabelecimento e encerramento de conexões inevitavelmente cria pequenos

fragmentos de espectro não-contíguos e grande parte das futuras requisições acabam não

sendo atendidas.

Para trabalhos futuros também poderá ser considerada a realização da alocação de

espectros baseada em distâncias. Uma vez que, nas redes SLICE diversos formatos de

modulação são utilizados para transmitir as informações. Logo, tem-se a necessidade de

estabelecer conexões com base no alcance e na taxa de dados dos formatos de modulação,

para assim conservar os recursos espectrais. Por exemplo, um formato de modulação como o

16QAM pode ser utilizado para caminhos mais curtos, sendo que pode transmitir mais

informações. Em contrapartida, o formato de modulação QPSK tem alcance maior, mas

transmite menos informações, quando comparada com o 16QAM.

69

Outra possibilidade de trabalhos futuros é estudar as Redes Definidas por Software.

Devido ao crescimento exponencial do tráfego da Internet e sua característica heterogênea que

suporta aplicações como VoIP, e-mail, videoconferência, IPTV e HDTV, um eficiente plano

de controle torna-se essencial para o gerenciamento da rede. No entanto, à medida que

aumenta a quantidade de equipamentos na rede, sendo produzido por distintos fabricantes, a

complexidade do controle e gerenciamento cresce consideravelmente. Ao pensar nisto, é

necessário que os equipamentos existentes na Internet possam interagir de forma eficiente,

permitindo às operadoras gerenciar o tráfego da rede de forma eficaz e possibilitar aos

clientes qualidade de serviço (QoS – Quality of Service).

Recentemente, diversos pesquisadores da área de telecomunicações e empresas

voltadas para o desenvolvimento de equipamentos e sistemas de gerência de redes têm

voltado suas atenções para o paradigma de Redes Definidas por Software (SDN – Software-

Defined Networking). Este novo paradigma é caracterizado pela existência de um sistema de

controle (software) que pode controlar o mecanismo de encaminhamento dos elementos de

comutação da rede por uma interface de programação bem definida. Desta forma, a

comutação de pacotes não precisa mais ser definida pelo princípio de roteamento de redes

Ethernet ou IP, mas pode ser controlado por aplicações (software) desenvolvidas

independentemente do hardware de rede.

As redes definidas por software são vistas como o novo paradigma da Internet do

futuro, pois possibilita resolver problemas como: segurança da informação, gerenciamento do

tráfego da rede, multi-casting, balanceamento de carga e eficiência energética. Assim,

diversas pesquisas estão sendo realizadas com o intuito de analisar e propor melhores

controladores, implementar os algoritmos propostos na literatura para este novo cenário,

implementar SDN nas redes sensores sem fio como também em Internet das coisas, dentre

outras. Com este novo paradigma, surge uma grande gama de novas possibilidades para a

pesquisa em redes de computadores.

Por fim, outro aspecto que deve ser estudado é a eficiência energética. Esta consiste

em obter o melhor desempenho na produção de um serviço com o menor gasto de energia. No

que diz respeito às infraestruturas de telecomunicações, tendo em vista os grandes volumes de

tráfegos atualmente presentes nas redes, a busca por elementos de redes energeticamente

eficientes torna-se a cada dia um imperativo para a sustentabilidade desse setor essencial da

atividade humana.

70

A Internet consome cerca de 1% do fornecimento de energia elétrica do mundo e este

consumo está crescendo à medida que mais pessoas se conectam a Internet [86]. Além disso,

o consumo de energia da infraestrutura de computação em nuvem e data centers está

aumentando em resposta à crescente demanda por mais serviços em nuvem [87]. Projeções

futuras de consumo de energia sugerem que, se as tendências atuais de crescimento continuar

e se os recursos energéticos não forem utilizados de forma otimizados o consumo de energia

da Internet poderá se aproximar de 10% em 10 a 20 anos [88]. Ao pensar nisso, diversas

pesquisas estão sendo realizadas com o intuito de reduzir o consumo de energia nos

equipamentos, componentes ópticos e eletrônicos, como também propor heurísticas para

monitorar redes e reduzir os recursos ociosos.

71

REFERÊNCIAS

[1] S. Talebi, F. Alam, I. Katib, M. Khamis, R. Salama e G. N. Rouskas, ―Spectrum

management techniques for elastic optical networks: A survey‖. Optical Switching and

Networking, v. 13, p. 34–48, Julho, 2014.

[2] Cisco, ―The Zettabyte Era: Trends and Analysis‖. Disponível em

(http://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-

index-vni/VNI_Hyperconnectivity_WP.pdf), 2014.

[3] O. Gerstel, M. Jinno, A. Lord e S. J. Yoo, ―Elastic optical networking: a new dawn for

the optical layer?‖. IEEE Communications Magazine, v. 50(2), p. s12–s20, Fevereiro,

2012.

[4] L. Ruan e Y. Zheng, ―Dynamic survivable multipath routing and spectrum allocation in

OFDM-based flexible optical networks‖. Journal of Optical Communications and

Networking, v. 6, p. 77–85, Janeiro, 2014.

[5] J. H. L. Capuchol e C. R. Leandro, ―ILP model and Effective Genetic Algorithm for

Routing and Spectrum Allocation in Elastic Optical Networks‖. SBMO/IEEE MTT-S

International Microwave & Optoelectronics Conference (IMOC), Rio de Janeiro, Brasil,

p. 1-5, Agosto, 2013.

[6] M. Jinno, H. Takara, B. Kozicki, Y. Tsukishima, Y. Sone e S. Matsuoka, ―Spectrum-

Efficient and Scalable Elastic Optical Path Network: Architecture, Benefits, and

Enabling Technologies‖. IEEE Communications Magazine, v. 47, p. 66-73, Novembro,

2009.

[7] B. Kozicki, H. Takara, T. Yoshimatsu, K. Yonenaga e M. Jinno, ―Filtering

Characteristics of Highly-Spectrum Efficient Spectrum-Sliced Elastic Optical Path

(SLICE) Network‖. Conference on Optical Fiber Communication, (OFC/NFOEC’09),

San Diego, Estados Unidos, p. 1-3, Março, 2009.

[8] Z. Zhu, W. Lu, L. Zhang e N. Ansari, ―Dynamic Service Provisioning in Elastic Optical

Networks With Hybrid Single-/Multi-Path Routing‖. Journal of Lightwave Technology,

vol. 31(1), p. 15-22, Janeiro, 2013.

[9] A. K. Horota, G. B. Figueiredo e N. L. S. Fonseca, ―Algoritmo de Roteamento e

Atribuição de Espectro com Minimização de Fragmentação em Redes Ópticas

72

Elásticas‖. 32º Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos

(SBRC), Florianópolis, Brasil, v. 1, p. 1-14, 2014.

[10] J. Zhao, Q. Yao, X. Liu, W. Li e M. Maier, ―Distance-adaptive routing and spectrum

assignment in OFDM-based flexible transparent optical networks‖. Photonic Network

Communications, v. 27(3), p. 119-127, Junho, 2014.

[11] Y. Cai, J. Cheng e Y. Yan, ―Spectrum-efficient optical drop-add-drop network with a

centralized multi-carrier light source‖. Photonic Network Communications v. 27, p. 89-

98, Fevereiro, 2014.

[12] S. Huang, Y. Zhou, S. Yin, Q. Kong, M. Zhang, Y. Zhao, J. Zhang e W. Gu,

―Fragmentation assessment based on-line routing and spectrum allocation for intra-data-

center networks with centralized control‖. Optical Switching and Networking, v. 14, p.

274-281, Agosto, 2014.

[13] M. Jinno, M. Jinno, B. Kozicki, H. Takara, A. Watanabe, Y. Sone, T. Tanaka e A.

Hirano, ―Distance-Adaptive Spectrum Resource Allocation in Spectrum-Sliced Elastic

Optical Path Network‖. IEEE Communications Magazine, v. 48(8), p. 138-145, Agosto,

2010.

[14] K. Christodoulopoulos, I. Tomkos e E. A. Varvarigos, ―Routing and spectrum allocation

in OFDM-based optical networks with elastic bandwidth allocation‖. IEEE Global

Telecommunications Conference (GLOBECOM 2010), Miami, Estados Unidos, p. 1-6,

Dezembro, 2010.

[15] M. Klinkowski e K. Walkowiak, ―Routing and Spectrum Assignment in Spectrum

Sliced Elastic Optical Path Network‖. IEEE Communications Letters, v. 15(8), p. 884-

886, Agosto, 2011.

[16] Y. Wang, X. Cao e Y. Pan, ―A Study of the Routing and Spectrum Allocation in

Spectrum-sliced Elastic Optical Path Networks‖. IEEE International Conference on

Computer Communications (INFOCOM), Shanghai, China, p. 1503-1511, Abril, 2011.

[17] Z. Zhang, M. Xiao, M. Wu e F. Xie, ―Adaptive subcarrier-distribution algorithm for

routing and spectrum allocation in OFDM-based elastic optical networks‖. Photonic

Network Communications, v. 28(3), p. 225-231, Junho de 2014.

[18] R. Goscien, M. Klinkowski e K. Walkowiak, ―A tabu search algorithm for routing and

spectrum allocation in elastic optical networks‖. 16th International Conference

on Transparent Optical Networks (ICTON), Graz, Áustria, p. 1-4, Julho, 2014.

73

[19] S. Shirazipourazad, Z. Derakhshandeh e A. Sen, ―Analysis of on-line routing and

spectrum allocation in spectrum-sliced optical networks‖. IEEE International

Conference on Communications (ICC), Budapeste, Hungria, p. 3899-3903, Junho,

2013.

[20] G. Feng, C. Douligeris e M. Klinkowki, ―A heuristic for routing, modulation and

spectrum allocation in spectrum sliced elastic optical path network‖. IEEE

Communications Letters, 2nd revision in review, disponível em

http://people.uwplatt.edu/~fengg/paper/coml-6a.pdf, 2014.

[21] S. Huang, Y. Zhou, S. Yin, Q. Kong, M. Zhang, Y. Zhao, J. Zhang e W. Gu,

―Fragmentation assessment based on-line routing and spectrum allocation for intra-data-

center networks with centralized control‖, Optical Switching and Networking, v.14, p.

274–281, 2014.

[22] M. Zhang, C. You, H. Jiang e Z. Zhu, ―Dynamic and Adaptive Bandwidth

Defragmentation in Spectrum-Sliced Elastic Optical Networks With Time-Varying

Traffic‖. Journal of Lightwave Technology, v. 32(5), p. 1014-1023, Janeiro, 2014.

[23] W. Ramirez, X. Masip-Bruin, M. Yannuzzi, D. Montero, A. Martinez e V. Lopez,

―Network coding-based protection scheme for Elastic Optical Networks‖. 10th

International Conference on the Design of Reliable Communication Networks (DRCN),

Ghent, Bélgica, p. 1-8, Abril, 2014.

[24] J. López, Y. Ye, V. López, F. Jimenez, R. Duque, P. Krummrich, F. Musumeci, M.

Tornatore e A. Pattavina, ―Traffic and power-aware protection scheme in elastic optical

networks‖. XVth International Telecommunications Network Strategy and Planning

Symposium (NETWORKS), Roma, Itália, p. 1-6, Outubro, 2012.

[25] H.Y. Choi, L. Liu, T. Tsuritani e I. Morita, ―Demonstration of BER-adaptive WSON

employing flexible transmitter/receiver with an extended OpenFlow-based control

plane‖. Photonics Technology Letters, v. 25(2), p. 119–121, Janeiro, 2013.

[26] Y. Zhang, X. Zheng, Q. Li, N. Hua, Y. Li e H. Zhang, ―Traffic Grooming in Spectrum-

Elastic Optical Path Networks‖. Optical Fiber Communication Conference and

Exposition and the National Fiber Optic Engineers Conference (OFC/NFOEC), Los

Angeles, Estados Unidos, p. 1-3, Março, 2011.

[27] Y. Sone, A. Watanabe, W. Imajuku, Y. Tsukishima, B. Kozicki, H. Takara e M. Jinno,

―Bandwidth Squeezed Restoration in Spectrum-Sliced Elastic Optical Path Networks

74

(SLICE)‖. Journal of Optical Communications and Networking, v. 3(3), p. 223-233,

Março, 2011.

[28] M. Jinno, H. Takara e Y. Sone, ―Elastic optical path networking: Enhancing network

capacity and disaster survivability toward 1 Tbps era‖. 16th OptoeElectronics and

Communications Conference (OECC), Kaohsiung, Taiwan, p. 401 - 404, Julho, 2011.

[29] T. Takagi, H. Hasegawa, K. Sato, Y. Sone, B. Kozicki, A. Hirano e M. Jinno, ―Dynamic

Routing and Frequency Slot Assignment for Elastic Optical Path Networks that Adopt

Distance Adaptive Modulation‖. Optical Fiber Communication Conference and

Exposition and the National Fiber Optic Engineers Conference (OFC/NFOEC), Los

Angeles, Estados Unidos, p. 1-3, Março, 2011.

[30] L. Velasco, O. González de Dios, V. López, J. Fernández-Palacios e G. Junyent,

―Finding an Objective Cost for Sliceable Flexgrid Transponders‖, Optical Fiber

Communications Conference and Exhibition (OFC), São Francisco, Estados Unidos, p.

9-13, Março, 2014.

[31] R. T. Kogantia e D. Sidhua, ―Analysis of Routing and Wavelength Assignment in Large

WDM Networks‖. The 9th International Conference on Future Networks and

Communications (FNC'14)/The 11th International Conference on Mobile Systems and

Pervasive Computing (MobiSPC'14)/Affiliated Workshops, Procedia Computer

Science, v. 34, p. 71–78, 2014.

[32] F. Lezama, G. Castanon, A. M. Sarmiento e I. B. Martins, ―Routing and spectrum

allocation in flexgrid optical networks using differential evolution optimization‖. 16th

International Conference on Transparent Optical Networks (ICTON), Graz, Áustria, p.

1-4, Julho, 2014.

[33] E. A. Varvarigos e K. Christodoulopoulos, ―Algorithmic Aspects in Planning Fixed and

Flexible Optical Networks With Emphasis on Linear Optimization and Heuristic

Techniques‖. Journal of Lightwave Technology, v. 32(4), p. 681-693, Fevereiro, 2014.

[34] A. Cai, G. Shen, L. Peng e M. Zukerman, ―Novel Node-Arc Model and Multiiteration

Heuristics for Static Routing and Spectrum Assignment in Elastic Optical

Networks‖. Journal of Lightwave Technology, v. 31(21), p. 3402-3413, Novembro,

2013.

[35] G. Zhang, M. De Leenheer, A. Morea e B. Mukherjee, ―A survey on OFDM-based

elastic core optical networking‖. IEEE Communications Surveys & Tutorials, v. 15(1),

p. 65-87, 2013.

http://www.sciencedirect.com/science/journal/18770509/34/supp/C

75

[36] S. Yao, S. Fu, H. Wang, M. Tang, P. Shum e D. Liu, ―Performance comparison for

NRZ, RZ, and CSRZ modulation formats in RS-DBS Nyquist WDM system‖. Journal

of Optical Communications and Networking, v. 6(4), p. 355-361, Abril, 2014.

[37] P. Torres-Ferrera, J. M. Rivas-Moscoso, D. Klonidis, D. M. Marom e I. Tomkos,

―Filtering effects of cascaded flex-grid roadms with high spectral resolution filters on

the transmission of Nyquist and quasi-Nyquist WDM super-channels‖. 13th

International Conference on Optical Communications and Networks (ICOCN), Suzhou,

China, p. 1-4, Novembro, 2014.

[38] V. Vujicic, J. Pfeifle, R. Watts, P. C. Schindler, C. Weimann, R. Zhou, W. Freude, C.

Koos e L. P. Barry, ―Flexible Terabit/s Nyquist-WDM Superchannels with net SE>

7bit/s/Hz using a Gain-Switched Comb Source‖. Conference on Lasers and Electro-

Optics (CLEO), Optical Society of America, p. 1-2, San Jose, Estados Unidos, Junho,

2014.

[39] ITU-T C1288, ―Extension of Rec. G.694.1 by a new clause to address flexible

frequency grids‖. Janeiro, 2011.

[40] ITU-T G.694.1, ―Spectral grids for WDM applications: DWDM frequency grid‖. (ed.

2.0), 2012.

[41] C. Colombo e S. Morganti, ―Transmission aspects of optical superchannels using

reconfigurable DP-16QAM/QPSK transponders in a flexgrid arrangement‖. Fotonica

AEIT Italian Conference on Photonics Technologies, Nápoles, Itália, p. 1-4, Maio,

2014.

[42] Z. Shen, H. Hasegawa e K. Sato, ―A novel flexible grid/semi-flexible grid optical path

network design algorithm that reserves exclusive frequency slots for high bitrate

signals‖. International Conference on Optical Network Design and Modeling,

Estocolmo, Suécia, p. 287-292, Maio, 2014.

[43] X. Wang, Q. Zhang, I. Kim, P. Palacharla e M. Sekiya, ―Blocking performance in

dynamic flexible grid optical networks-What is the ideal spectrum granularity?‖.

European Conference and Exposition on Optical Communications. Optical Society of

America, Genebra, Suíça, p. 1-3, Setembro, 2011.

[44] L. Velasco, P. Wright, A. Lord e G. Junyent, ―How national IP/MPLS networks can

benefit from flexgrid optical technology?‖. Optical Fiber Communication Conference

and Exposition and the National Fiber Optic Engineers Conference (OFC/NFOEC).

Optical Society of America, Anaheim, Estados Unidos, p. 1-3, Março, 2013.

76

[45] L. Velasco, M. Ruiz, A. Castro e J. Comellas, ―Extending the flexgrid optical core

towards the edges‖. 15th International Conference on Transparent Optical Networks

(ICTON), Cartagena, Colômbia, p. 1-4, Junho, 2013.

[46] X. Cai, K. Wen, R. Proietti, Y. Yin, D. J. Geisler, R. P. Scott, C. Qin, L. Paraschis, O.

Gerstel e S. J. B. Yoo, ―Experimental demonstration of adaptive combinational QoT

degradation restoration in elastic optical networks‖. Journal of Lightwave

Technology, v. 31(4), p. 664-671, 2013.

[47] A. Carmona, M. Klinkowski, M. Ruiz, V. Lopez, A. Castro, L. Velasco e J. Comellas,

―Impact of aggregation level on the performance of dynamic lightpath adaptation under

time-varying traffic‖. Optical 17th International Conference on Network Design and

Modeling (ONDM), Brest, França, p. 184-189, Abril, 2013.

[48] P. Roorda e B. Collings, ―Evolution to colorless and directionless ROADM

architectures‖. National Fiber Optic Engineers Conference. Optical Society of America,

San Diego, Estados Unidos, p. 1-3, Fevereiro, 2008.

[49] N. Amaya, G. Zervas e D. Simeonidou, ―Introducing node architecture flexibility for

elastic optical networks‖. Journal of Optical Communications and Networking, v. 5(6)

p. 593- 608, 2013.

[50] P. Pavon-Marino e M.V. Bueno-Delgado, ―Add/drop contention-aware RWA with

directionless ROADMs: The offline lightpath restoration case‖. Journal of Optical

Communications and Networking, v. 4(9), p. 671-680, 2012.

[51] A. N. Patel, P. N. Ji, J. P. Jue e T. Wang, ―Routing, Wavelength Assignment, and

Spectrum Allocation in Transparent Flexible Optical WDM (FWDM) Networks‖.

Photonics in Switching, Optical Society of America, p. 25-28, 2010.

[52] O. Rival e A. Morea, ―Elastic optical networks with 25–100G format-versatile WDM

transmission systems‖. 15th IEEE OptoeElectronics and Communications Conference

(OECC), Sapporo, Japão, p. 100-101, Julho, 2010.

[53] R. J. Essiambre, G. Kramer, P. J. Winzer, G. J. Foschini e B. Goebel, ―Capacity limits

of optical fiber networks‖. Journal of Lightwave Technology, v. 28(4), p. 662-701,

2010.

[54] I.T.U.-T. Recommendations, ―Spectral grids for WDM applications: DWDM frequency

grid,‖ G.694.1, 2012, disponível em: http://www.itu.int/rec/T-REC-G.694.1/

77

[55] M. Jinno, B. Kozicki, H. Takara, A. Watanabe, Y. Sone, T. Tanaka e A. Hirano,

―Distance adaptive spectrum resource allocation in spectrum-sliced elastic optical path

network‖. IEEE Communications Magazine, v. 48(8), pp. 138-145, Agosto, 2010.

[56] M. Adams, ―ROADM and Wavelength Selective Switches: Perspectives for Fiber Optic

Manufacturing Test Engineering‖. JDSU 2008. Disponível em:

http://www.jdsu.com/ProductLiterature/ROADM_and_Wavelength_Selective_Switches

.pdf, acessado em 05 de Janeiro de 2015.

[57] T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stei, ―Introduction to Algorithms‖,

Terceira edição, 2009.

[58] R. A. Scaraficci e N. L. da Fonseca, ―Alternative routing and zone-based spectrum

assignment algorithm for flexgrid optical networks‖. IEEE International Conference

on Communications (ICC), Sydney, Austrália, p. 3295-3300, Junho, 2014.

[59] R. Kumar e N. Kaur, ―Restorable routing algorithm in optical networks by reducing

blocking probability‖. Recent Advances Engineering and Computational Sciences

(RAECS), Chandigarh, Índia, p. 1-7, Março, 2014.

[60] R. J. Durán, I. Rodríguez, N. Fernández, I. de Miguel, N. Merayo, P. Fernández, J.C.

Aguado, T. Jiménez, R. M. Lorenzo e E. J. Abril, ―Performance Comparison of

Methods to Solve the Routing and Spectrum Allocation Problem‖. 14th International

Conference on Transparent Optical Networks (ICTON), Coventry, Inglaterra, p. 1-4,

Julho, 2012.

[61] R. Yumer, N. Akar e E. Karasan, ―Class-based first-fit spectrum allocation with

fragmentation avoidance for dynamic flexgrid optical networks‖. Optical Switching and

Networking, v. 15, p. 44-52, 2014.

[62] G. M. Durães, A. Soares, J.R. Amazonas, e W. Giozza, ―The choice of the best among

the shortest routes in transparent optical networks‖. Computer Networks, v. 54(14), p.

2400-2409, 2010.

[63] H. C. Lin, S. W. Wang e C. Tsai, ―Traffic intensity based fixed-alternate routing in all-

optical WDM networks‖. IEEE International Conference on Communications (ICC),

Istanbul, Turquia, p. 2439 - 2446, Junho, 2006.

[64] W. Lu, X. Zhou, L. Gong, M. Zhang e Z. Zhu, ―Dynamic multi-path service

provisioning under differential delay constraint in elastic optical networks‖. IEEE

Communications Letters, v. 17(1), p. 158-161, Janeiro, 2013.

http://www.jdsu.com/ProductLiterature/ROADM_and_Wavelength_Selective_Switches.pdf

http://www.jdsu.com/ProductLiterature/ROADM_and_Wavelength_Selective_Switches.pdf

78

[65] C.C. Santos e K.D.R. Assis, ―Optical Networks Security: Design to avoid the Jamming

Attacks‖. 13th International Conference on Transparent Optical Networks (ICTON),

Estocolmo, Suécia, p. 1-4, Junho, 2011.

[66] A. F. Santos, C. C. Santos, G. M. Durães, K. D. R. Assis e R. C. Almeida Jr.

―Roteamento e Alocação de Espectro em Redes Ópticas: O Conceito SLICE‖. XXX

Simpósio Brasileiro de Telecomunicações (SBrT), Brasília, Brasil, Setembro, 2012.

[67] A. F. Santos, C. C. Santos, G. M. Durães e K.D.R. Assis, ―Heuristics for Routing in

Spectrum-Sliced Elastic Optical Path Networks‖. 10th International Conference on

Optical Internet (COIN2012), Yokohama, Japão, 2012.

[68] J. Y. Yen, ―Finding the k shortest loopless paths in a network‖, Management Science, v.

17(11), p. 712-716, 1971.

[69] E. W. Dijkstra. ―A Note on Two Problems in Connection with Graphs‖. Numerical

Mathematics, v. 1(1), p. 269-271, 1959.

[70] M. J. Mahony, ―A european optical network: design considerations‖. IEE Colloquium

on Transparent Optical Networks: Applications, Architectures and Technology,

Londres, Inglaterra, p. 1-16, Abril, 1994.

[71] K. Christodoulopoulos, I. Tomkos e E. A. Varvarigos, ―Elastic bandwidth allocation in

flexible OFDM-based optical networks‖, Journal of Lightwave Technology, v. 29(9), p.

1354-1366, Maio, 2011.

[72] P. Rajalakshmi e A. Jhunjhunwala, ―Load Balanced Routing to Enhance the

Performance of Optical Backbone Networks‖. 5th IFIP International Conference on

Wireless and Optical Communications Networks (WOCN 2008), Surabaya, Indonésia,

p. 1-5, Maio, 2008.

[73] K.D.R. Assis, J. Maranhao, A. F. Santos e W. Giozza, ―Heuristic to Maximize the Open

Capacity of OBS Networks with Initial Static Traffic‖. Telecomunicações (Santa Rita

do Sapucaí), v. 12, p. 18-23, Abril, 2009.

[74] K.D.R. Assis, A. F. Santos e R. C. Almeida Jr, ―Optimization in spectrum-sliced optical

networks‖. SPIE Photonics West - Optical Metro Networks and Short-Haul Systems VI,

São Francisco, Estados Unidos, Fevereiro, 2014.

[75] X. Wan, L. Wang, N. Hua, H. Zhang e X. Zheng, ―Dynamic routing and spectrum

assignment in flexible optical path networks‖. Optical Fiber Communication

Conference and Exposition (OFC/NFOEC) and the National Fiber Optic Engineers

Conference, Los Angeles, Estados Unidos, p. 1-3, Março, 2011.

79

[76] A. F. Santos, R.C. Almeida Jr and K.D.R. Assis, ―YEN-BSR: A new approach for the

choice of routes in WDM networks‖. Journal of Optical Communications, v. 35, p. 293-

296, 2014.

[77] R.C. Almeida Jr, A.F. Santos, K.D.R. Assis, H. Waldman e J.F. Martins-Filho. ―Slot

assignment strategy to reduce loss of capacity of contiguous-slot path requests in

flexible grid optical networks‖. Electronics Letters (Online), v. 49(5), p. 359-361,

Fevereiro, 2013.

[78] H. Waldman, D. R. Campelo e R. C. Almeida, ―Dynamic priority strategies for

wavelength assignment in WDM rings‖. IEEE Global Telecommunications Conference,

São Francisco, Estados Unidos, p.1288-1292, 2000.

[79] K. Christodoulopoulos, I. Tomkos e E. Varvarigos, ―Dynamic bandwidth allocation

inflexible OFDM-based networks‖. Optical Fiber Communication Conference and

Exposition (OFC/NFOEC) and the National Fiber Optic Engineers Conference, 2011,

Los Angeles, Estados Unidos, p. 1-3, Março, 2011.

[80] Y. Sone, A. Hirano, A. Kadohata, M. Jinno e O. Ishida, ―Routing and spectrum

assignment algorithm maximizes spectrum utilization in optical networks‖. 37th

European Conference and Exhibition on Optical Communication (ECOC), Genebra,

Switzerland, Suíça, p. 1-3, Setembro, 2011.

[81] C. Pavan, R. M. Morais, J. R. Ferreira da Rocha e A. N. Pinto, ―Generating realistic

optical transport network topologies‖. Journal of Optical Communications and

Networking, v. 2(1), p. 80-90, 2010.

[82] http://www.av.it.pt/anp/on/refnet2.html, acessado em 09 de outubro de 2014.

[83] A. F. Santos, C. C. Santos, G. M. Durães, K.D.R. Assis e R. C. A. A. Júnior,

―Heurísticas para o Roteamento e Alocação de Espectro em Redes Ópticas SLICE‖.

MOMAG (15º SBMO Simpósio Brasileiro de Micro-ondas e Optoeletrônica e o 10º

CBMag Congresso Brasileiro de Eletromagnetismo), João Pessoa, Brasil, 2012.

[84] P. K. Keshwani, R. S. Shukla e A. Agarwal, ―Performance Analysis of Mesh, Torus and

Folded Torus under Broadcasting, using Distance Vector Algorithm‖. International

Journal of Engineering and Computer Science, v. 3, (6), p. 6593-6597, 2014.

[85] ―Rede Nacional de Ensino e Pesquisa - RNP‖. Disponível em:

http://www.rnp.br/servicos/conectividade/rede-ipe, acessado em 01 de Novembro de

2014.

http://www.av.it.pt/anp/on/refnet2.html

http://www.rnp.br/servicos/conectividade/rede-ipe

80

[86] J. Baliga, R. Ayre, K. Hinton, W. V. Sorin e R. S. Tucker, ―Energy consumption in

optical IP networks‖. Journal of Lightwave Technology, v. 27(13), p. 2391-2403, 2009.

[87] J. Baliga, R. W. Ayre, K. Hinton e R. S. Tucker, ―Green cloud computing: Balancing

energy in processing, storage, and transport‖. Proceedings of the IEEE, v. 99(1), p. 149-

167, 2011.

[88] R. S. Tucker, ―Towards an Energy-Efficient Internet‖. Optical Instrumentation for

Energy and Environmental Applications. Optical Society of America, Camberra,

Austrália, Dezembro, p. 2-5, 2014.

[89] A. Whitmore, A. Agarwal e L. Da Xu, ―The Internet of Things—A survey of topics and

trends‖. Information Systems Frontiers, p. 1-14, 2014.

[90] NFC BRASIL. Projeto de São Paulo testa NFC em ônibus da Baixada Santista. 2013.

Disponível em: http://nfcbrasil.wordpress.com/2013/01/18/projeto-de-sao-paulo-testa-

nfc-em-onibus-da-baixada-santista/, acessado em 30 Novembro de 2014.

http://nfcbrasil.wordpress.com/2013/01/18/projeto-de-sao-paulo-testa-nfc-em-onibus-da-baixada-santista/

http://nfcbrasil.wordpress.com/2013/01/18/projeto-de-sao-paulo-testa-nfc-em-onibus-da-baixada-santista/

81

APÊNDICE A

A. SimRSA: SIMULADOR DE ROTEAMENTO E ALOCAÇÃO DE ESPECTRO

PARA REDES ÓPTICAS SLICE

Com o intuito de facilitar o estudo de redes ópticas elásticas, foi desenvolvido um

simulador chamado SimRSA. Este permite comparar as heurísticas sob diferentes condições

de tráfego a partir da utilização de diversas topologias de rede. Adicionalmente, a interface

gráfica possibilita ao usuário configurar diferentes variáveis e visualizar a alocação de

espectro, por enlace e na rede, como resultado das simulações.

O SimRSA foi desenvolvido na linguagem de programação Java, e sua interface

gráfica foi desenvolvida em HTML (HyperText Markup Language), CSS (Cascading Style

Sheets), JavaScript, com utilização do jQuery. Logo, o SimRSA é uma ferramenta web

gratuita para simulação de redes SLICE.

Na Figura A.1 é ilustrado o fluxo de processo de utilização do SimRSA.

Figura A.1: Fluxo de processo do SimRSA

A Figura A.2 exibe a tela principal do SimRSA. Na parte superior da tela fica

posicionado o menu do simulador. A área destacada em vermelho representa o local onde é

realizada a modelagem das redes.

Como é possível visualizar na Figura A.2, o menu do SimRSA é subdividido em

alguns grupos. As funcionalidades de cada grupo serão discutidas a seguir.

82

Figura A.2. Tela inicial do SimRSA

Existem três maneiras de realizar a modelagem de uma rede no SimRSA: com o

carregamento de um arquivo de projeto salvo, com o carregamento de uma topologia de rede

predefinida no simulador ou com a modelagem de uma nova topologia de rede. A Figura A.3

exibe os grupos do menu responsáveis por essas funcionalidades. O menu ―redes

predefinidas‖ exibe uma lista de redes incluídas no simulador.

Figura A.3. Grupo de modelagem do SimRSA

Depois de efetuada a modelagem da rede, é possível definir pesos para os enlaces e

também definir o sentido do tráfego de cada enlace. Para isso, basta ―clicar‖ sobre uma aresta

e configurar estes itens no grupo do menu, como ilustrado na Figura A.4.

O valor do peso implica no resultado do roteamento realizado pelos algoritmos de

Dijkstra e Yen. Para apagar uma aresta, basta clicar duas vezes sobre uma aresta na área de

modelagem.

83

Figura A.4. Grupo de parâmetros de enlace do SimRSA

Na Figura A.5, é possível visualizar as opções de heurísticas, disponíveis para a

simulação.

Figura A.5. Lista de heurísticas disponíveis no SimRSA

A Figura A.6 exibe um grupo do menu do SimRSA, no qual o usuário define os

valores para os parâmetros das heurísticas relevantes à simulação.

O valor da banda de guarda (GB) deve ser um número inteiro e positivo. É permitido

ao usuário informar mais de um valor para o GB, para a mesma simulação. Para isto, basta o

usuário informar os valores separados por vírgula (―,‖), como exemplificado na Figura A.6.

Figura A.6. Grupo de parâmetros das heurísticas do SimRSA

O valor de k representa a quantidade de caminhos, para cada rota que será analisada

pelo algoritmo BLSA (esse valor interfere apenas na heurística BLSA). A quantidade de

iterações é definida para o algoritmo BSR. Os valores referentes aos campos das propriedades

das heurísticas devem ser um número inteiro e positivo.

Ao clicar no botão ―Gerar Matriz de Tráfego‖, da Figura A.2, uma caixa é aberta sobre

o menu, como exibido na Figura A.7, na qual é permitido ao usuário informar o valor do

tráfego em cada enlace. É possível informar um único valor para todas as rotas, gerar os

valores automaticamente, a partir de um valor mínimo e um valor máximo, ou informar

84

diferentes valores para as diversas rotas da rede. Os valores informados devem ser números

inteiros não negativos.

Figura A.7. Tela de configuração da matriz de tráfego do SimRSA.

Ao clicar no botão ―Executar Simulação‖, da Figura A.2, o sistema coleta todas as

informações adicionadas (rede, parâmetros, heurísticas, etc), e executa as simulações

requeridas pelo usuário. Uma barra de processamento é exibida enquanto o sistema executa as

simulações.

Ao concluir as simulações, um relatório é aberto, em uma nova janela do navegador do

usuário. Neste relatório, os resultados das heurísticas são agrupados por cada GB informado,

como é exibido na Figura A.8.

Figura A.8. Agrupamento por GB do relatório do SimRSA

Ao clicar no botão ―+‖, as informações geradas por cada heurística, para aquele GB,

são exibidas em duas tabelas e um gráfico. Na primeira tabela, é exibido o slot alocado em

cada caminho, como mostrado na Figura A.9.

85

Figura A.9. Primeira tabela do relatório do SimRSA

A Figura A.10 ilustra a segunda tabela, na qual são exibidos os slots alocados em cada

enlace (incluindo a banda de guarda), a quantidade total de slots alocadas em cada enlace e o

maior valor entre a quantidade de slots alocados. Este último valor representa a quantidade de

slots alocadas pela heurística.

Figura A.10. Segunda tabela do relatório do SimRSA

No fim de cada grupo de GB é exibido um gráfico comparativo, que indica a

quantidade de slots alocados em cada enlace, por cada heurística, como ilustrado na Figura

A.11. Ao direcionar o ponteiro do mouse sobre um item do gráfico é exibido um balão para

informar a quantidade de slots alocados.

86

Figura A.11. Gráfico de slots alocados por enlace do relatório do SimRSA

No fim da página de relatório, é exibido um gráfico de barras verticais, que compara a

quantidade total de slots utilizados por cada heurística, agrupadas pelos GBs, como é possível

visualizar na Figura A.12.

Figura A.12. Gráfico comparativo dos resultados das heurísticas do relatório do SimRSA

Validação do SimRSA

Com o objetivo de validar a ferramenta, foram realizadas simulações e seus resultados

foram comparados com os de alguns trabalhos na literatura [16], [65], [67], [83]. Em todas as

simulações realizadas, são obtidos os mesmos resultados apresentados na literatura.

87

Nas simulações, é abordada a quantidade de slots alocados em uma fibra, e este

resultado determina qual heurística apresenta o melhor desempenho. A heurística que aloca

menos slots na fibra é apontada como a melhor dentre as comparadas na simulação.

Para ilustrar a validação dos resultados, foram realizadas simulações na rede NSFNet

(Figura A.13), com os valores de tráfego (fixo) iguais a 1, 2, 3 slots, banda de guarda (GB)

iguais a 1, 2, 3 slots, e com as heurísticas BSR, SPSR e BLSA. Estes resultados foram

apresentados por [16], [83].

Figura A.13. Topologia da rede NFSNet pré-definida no SimRSA

As Figuras A.14, A.15 e A.16 ilustram os resultados gerados pelo SimRSA, para

valores de tráfego iguais a 1, 2 e 3 slots, respectivamente. Os resultados equivalem aos da

Figura A.17 [16], com o valor do tráfego igual a 1, 2 e 3 slots, para as heurísticas SPSR e

BLSA. Todas as topologias pré-definidas no simulador estão na Figura A.18.

Figura A.14. Gráfico comparativo da rede NFSNet com tráfego igual a 1 slot gerado pelo SimRSA

88

Figura A.15: Gráfico comparativo da rede NFSnet com tráfego igual a 2 slots gerado pelo SimRSA

Figura A.16: Gráfico comparativo da rede NFSnet com tráfego igual a 3 slots gerado pelo SimRSA

Figura A.17. Número máximo de slots alocados na rede pelo tráfego da rede [16]. Copyright © 2011 IEEE.

89

Rede Abilene [74] Rede NSFNet [16]

Rede EON [70] Rede Brasileira [73]

Torus [84] RNP [85]

Figura A.18. Topologias pré-definidas no simulador.

90

APÊNDICE B

B. ANÁLISE DE TOPOLOGIAS

Como em muitos trabalhos da literatura utilizam diversas topologias de rede para

realizar simulações e análise de algoritmos. Neste apêndice, como uma forma de contribuição,

foi aplicado um algoritmo de roteamento de espectros em várias topologias de rede para

verificar a influência das topologias na probabilidade de bloqueio.

Em geral, uma topologia de rede pode ser vista como uma representação gráfica sobre

um plano bidimensional. Os nós são distribuídos de acordo com a demanda de tráfego

esperada em cada área geográfica. Em muitas topologias, os nós são representados por

cidades, estados ou países (dependendo da extensão geográfica), e os enlaces por cabo de

fibra óptica, par trançado, dentre outros. A Figura B.1 ilustra um possível conjunto de regiões

da topologia da rede europeia EON (European Optical Network). Algumas regiões são mais

densamente povoadas que outras e, por isso, contêm clusters. Estas regiões, no exemplo da

figura, estão representadas com enlaces fortes.

Figura B.1. Topologia Física da rede EON (European Optical Network). Copyright © 2010 IEEE.

Neste apêndice, foram analisadas 33 redes com quantidades distintas de nós e enlaces.

A Tabela B.1 ilustra as topologias de rede analisadas com as respectivas quantidades de nós,

enlaces e o grau médio. As topologias podem ser visualizadas em [82].

91

Tabela B.1. Topologias de redes analisadas [81], [82].

Número Redes Nós Enlaces Grau Médio*

1 VIA Network 9 12 2,67

2 BREN 10 11 2,20

3 RNP 10 12 2,40

4 LEARN 10 11 2,20

5 Abilene Core 10 13 2,60

6 CompuServe 11 14 2,55

7 vBNS 12 17 2,83

8 CESNET 12 19 3,17

9 NSFNET 14 21 3,00

10 Italy 14 29 4,14

11 Mzima 15 19 2,53

12 ARNES 17 20 2,35

13 Germany 17 26 3,06

14 RedIRIS (SPAIN) 17 28 3,29

15 NLR 19 23 2,42

16 MEMOREX 19 24 2,53

17 CANARIE 19 26 2,74

18 EON 19 37 3,89

19 Optosunet (SWEDEN) 20 24 2,40

20 ARPANET 20 32 3,20

21 PIONIER 21 25 2,38

22 BULGARIA 23 24 2,09

23 COX 24 40 3,33

24 SANET 25 28 2,24

25 NEWNET 26 31 2,38

26 Portugal 26 36 2,77

27 RENATER 27 35 2,59

28 CERNET 29 45 3,10

29 IBN31 31 47 3,03

30 LONI 33 37 2,24

31 Metrona 33 41 2,48

32 Cost37 37 57 3,08

33 Omnicom 38 54 2,84

A Figura B.2 ilustra a probabilidade de bloqueio para as 33 topologias de rede

analisadas ao se utilizar o algoritmo BSR. Percebe-se que, quanto maior o grau médio da rede,

menor será probabilidade de bloqueio. Isso advém do fato de que, quanto maior a

conectividade entre os nós, maior será a possibilidade de roteamento na rede. Ao observar as

redes com pouca conectividade (grau médio <= 4), elencadas na primeira coluna da legenda

das redes da Figura B.2, de BULGARIA até CompuServe, a probabilidade de bloqueio é mais

92

alta em relação às demais redes com maior grau médio, elencadas na segunda coluna da

legenda das redes da Figura B.2, de Portugal até Italy.

A Figura B.3 ilustra a distribuição dos graus dos nós para cada topologia de rede

analisada. Perceba que a maioria dos nós são predominantemente de grau dois a quatro e,

desta forma, a rede tem poucas opções de roteamento. Para redes que contêm um número

expressivo de nós com grau acima de cinco, tem-se uma melhor distribuição das rotas e uma

menor probabilidade de bloqueio (Figura B.2).

Figura B.2. Probabilidade de Bloqueio para topologias de redes analisadas utilizando o algoritmo BSR

Adaptado.

Figura B.3. Distribuição dos graus dos nós na rede.

A partir da escolha dos melhores caminhos, os algoritmos de roteamento tentam

otimizar a alocação dos recursos a serem utilizados pelas solicitações de conexão. A depender

da topologia utilizada, tem-se uma determinada probabilidade de bloqueio associada. As

heurísticas BSR e ILR, utilizadas na fase de roteamento, conseguiram obter resultados ótimos

70 80 90 100 110 120 130 140 150 160 170 180

1E-9

1E-8

1E-7

1E-6

1E-5

1E-4

1E-3

0,01

0,1

1

2

3

4

56

78

a

b

c

d

ef

gh

Pro

bab

ilid

ad

e d

e B

loq

ueio

Erlang

BULGARIA Portugal

LEARN Via Network

BREN CANARIE

SANET vBNS 1 LONI Omnicom

NEWNET IBN31 a PIONIER Germany

ARNES Cost37

RNP CERNET

SWEDEN ARPANET

NLR NSFNET

Metrona CESNET

Mzima RedIRIS (SPAIN)

MEMOREX COX

RENATER EON

Abilene Core Italy

CompuServe

1 2 3 4 5 6 7 8 9 10

0

2

4

6

8

10

12

14

16

18

20

22

24

26

28

30

32

34

1

2

3 4 5

6

a

b

c

d

Dis

trib

uiç

ão

do

gra

u n

od

al

Grau nodal

BULGARIA Portugal

LEARN Via Network

BREN CANARIE

SANET vBNS 1 LONI Omnicom

NEWNET IBN31 a PIONIER Germany

ARNES Cost37

RNP CERNET

SWEDEN ARPANET

NLR NSFNET

Metrona CESNET

Mzima RedIRIS (SPAIN)

MEMOREX COX

RENATER EON

Abilene Core Italy

CompuServe

93

em termos de alocação de slots, para redes pequenas com 5 e 6 nós (Capítulo 3, Seção 3.3.1).

Para redes grandes, em relação à probabilidade de bloqueio, a heurística BSR obteve bons

resultados (Capítulo 4 Seção 4.2.2.1).

A Tabela B.2 ilustra a redução da probabilidade de bloqueio do BSR adaptado em

relação ao BSR e ao Dijkstra. Nesta tabela, pode-se observar que a redução da probabilidade

de bloqueio do BSR adaptado em realçao ao Dijkstra aumenta para as topologias com melhor

distribuição dos graus dos nós na rede.

Tabela B.2. Topologias de redes analisadas.

ID Rede Dijkstra (%) BSR (%)

1 VIA Network 68,1 48,4

2 BREN 56,2 29,0

3 RNP 66,5 45,1

4 LEARN 55,6 28,9

5 Abilene Core 67,2 40,6

6 CompuServe 67,3 44,1

7 vBNS 72,0 46,9

8 CESNET 92,3 64,7

9 NSFNET 89,3 65,5

10 Italy 98,3 63,5

11 Mzima 67,0 37,1

12 ARNES 66,9 45,6

13 Germany 77,9 59,4

14 RedIRIS (SPAIN) 95,9 68,5

15 NLR 66,7 37,3

16 MEMOREX 67,0 42,2

17 CANARIE 70,4 55,7

18 EON 98,1 64,8

19 Optosunet (SWEDEN) 66,7 44,4

20 ARPANET 88,3 47,3

21 PIONIER 65,7 45,5

22 BULGARIA 55,3 28,7

23 COX 96,3 56,3

24 SANET 57,5 35,5

25 NEWNET 64,4 40,6

26 Portugal 67,8 47,0

27 RENATER 67,2 43,9

28 CERNET 85,4 65,6

29 IBN31 77,9 49,0

30 LONI 57,8 33,1

31 Metrona 66,9 40,0

32 Cost37 84,7 64,0

33 Omnicom 72,1 44,9

Documents

Algoritmos para Roteamento e Alocação de Espectro em … · ALEX FERREIRA DOS SANTOS Algoritmos para Roteamento e Alocação de Espectro em Redes Ópticas Elásticas Tese de doutorado