Analysis of the Relationship Between Topological
Characteristics of Optical Networks and their Number of
Wavelengths
Depizzol, Daniela Bertolini1 , Paiva, Marcia Helena Moreira2 , Segatto, Marcelo Eduardo Vieira3
Laboratory of Telecommunications – LabTel, Federal University of Espírito Santo – UFES, Vitória, Brazil.
1
ddepizzol@ifes.edu.br, 2 marcia.paiva@ufes.br, 3 segatto@ele.ufes.br
Abstract problem, que acrescenta ao RWA a restrição de não sobre-
posição (non-overlapping) [ZDLMM13]. O espectro óp-
This study analyzes the influence of the variability of
tico é subdividido em slots e canais de tamanho variado
topological characteristics of optical networks in their
são criados combinando os slots para atender demandas
desirable performance, with respect to the requirement
de taxa e requisitos distintos. Ainda há a restrição de
of wavelengths. The studies were focused on real-world
continuidade para os canais, mas a combinação de canais
networks and random graphs with characteristics of real-
de diferentes tamanhos cria outro tipo de fragmentação,
world networks. It was observed that some topological
pois os canais só podem ser formados por slots contíguos
features exalted in the literature may not necessarily be
em cada enlace. Uma estratégia mais comum para se tra-
good representatives of the behavior of optical networks.
tar esse problema é subdividindo o espectro em partições,
e em cada uma alocar apenas canais do mesmo tamanho.
1 Introdução Deste modo, em cada partição o problema se reduz ao
As redes ópticas de transporte (OTN - Optical Transport RWA clássico [WM14]. De todo modo, como o RMSA é
Networks) se tornaram o ramo central da imensa malha um problema ainda mais complexo, seria ideal que a rede
de redes de comunicações da sociedade atual devido a tenda a ter um baixo requisito para a quantidade de com-
vários fatores, como a sua grande capacidade de tráfego, primentos de onda necessária para atender a restrição de
velocidade e alcance. Vários canais independentes podem continuidade [TAK+ 14].
compartilhar a mesma fibra óptica, aumentado a taxa de O uso de mais
comprimentos de λ=5 λ=3
dados sobre a mesma infraestrutura. Nas redes convenci-
onais utiliza-se a tecnologia de Wavelength Division Mul- onda diminui a 1 3 3 5
tiplexing (WDM), permitindo assim a implementação de disponibilidade
redes com roteamento de tráfego por comprimentos de da rede, pois 6 5 1 6
onda (WRON - Wavelength Routed Optical Networks). reduz a quanti-
Todavia, as redes da nova geração, chamadas de Elastic dade de canais 4 2 4 2
Optical Networks (EON), são baseadas em Optical Ortho- disponíveis para
gonal Frequency Division Multi-plexing (OOFDM). Essa novas conexões. Figura 1: Redes com mesmo nú-
tecnologia se diferencia por permitir um uso mais flexí- Aumentar a mero de nós (n = 6), enlaces
vel do espectro óptico, com canais de tamanho variado, quantidade de (m = 8) e, logo, mesmo grau mé-
alcançando uma maior eficiência espectral [ZDLMM13]. canais dispo- dio (2m/n = 2.66), mas com λ di-
Em redes WRON, temos o problema de Routing and níveis é muito ferente.
Wavelength Assignment (RWA) que envolve o roteamento dispendioso de-
das demandas e a alocação de comprimentos de onda aos vido ao alto custo dos equipamentos ópticos. Portanto,
canais ópticos. Neste problema há a restrição de conti- o ideal é que a topologia da rede facilite a alocação
nuidade de comprimentos de onda, que o torna um pro- de comprimentos de onda. Por exemplo, na Figura 1
blema NP-Hard. Cada canal deve utilizar o mesmo com- vemos redes com mesma quantidade de nós e arestas, e
primento de onda do início ao fim da rota. Isso gera uma logo mesmo grau médio (onde o grau de um vértice é
fragmentação do espectro disponível, onde se pode ter definido como a quantidade de arestas que se ligam a
comprimentos de onda disponíveis em vários enlaces, mas esse vértice), mas com um requisito de λ diferente, sendo
sem continuidade entre enlaces consecutivos, impedindo que a diferença entre as duas redes é basicamente a
que rotas de mais de um salto sejam criadas. O termo topologia. Ao se planejar uma topologia de rede óptica,
número mínimo de comprimentos de onda será daqui em entre as múltiplas formas de se conectar nós e arestas,
diante chamado apenas de número de comprimentos de não é fácil se controlar o λ, pois seu cálculo envolve
onda, e será denotado por λ. um a resolução de um problema N P − Hard. Daí
Por sua vez, nas redes EON temos o respectivo Rou- surge o interesse em invariantes topológicos que sejam
ting, Modulation, and Spectrum Assignment (RMSA) bem correlacionados com λ e também mais fáceis de se
calcular, e que possam assim ser usados no projeto da
Copyright c held by the authors. rede, como indicadores de topologia que propiciarão um
menor λ na rede. Counts
Ao longo do tempo, alguns trabalhos na literatura tem 67180
se debruçado a trabalhar no cálculo de invariantes topo-
60 19
lógicos que se relacionam com λ e que não envolvam a re- 2.42
57583
solução de outro problema N P [BB97, FLGM00, YX10].
Number of Wavelengths
19 47986
No presente trabalho são então calculados (usando o pa- 2.5319
cote igraph do programa R) dois invariantes de grafos 40
2.74
17 38389
com o objetivo de verificar, de forma mais abrangente, 2.35 20
15 28792
como a variabilidade de características topológicas das 3.20
2.53
17
redes podem influenciar no número de comprimentos de 3.06
17 19195
1519 12
20 3.29
onda. 2.93 2.83 12
3.8914 10 10 9598
3.17
3.00
2.20 2.40
2 Metodologia 1
Os estudos foram concentrados em grafos aleatórios que 0.15 0.20 0.25 0.30 0.35 0.40
simulavam redes reais, com número de nós n = 10, ..., 20, Density
e para cada n foram gerados aleatoriamente 200.000 de- (a)
les, resultando assim numa amostra com 2, 2 × 106 grafos
0.15 0.25 0.35 0.15 0.25 0.35
aleatórios simples, 2-conexos, de arestas com peso unitá- 10 11 12 13
rio, não isomorfos entre si, e ainda com grau médio de Counts
60
32674
cada grafo assumindo valores entre 2 e 4, que é o espe- 40
rado em redes reais [PMFdRP10]. Foram geradas redes 20 7401
aleatórias com no mínimo 10 nós, para evitar possíveis Number of Wavelengths 14 15 16 17 1677
efeitos de borda em grafos muito pequenos, e no máximo 60
380
20 nós, em função do custo computacional de tratar toda 40
a amostra. Os grafos aleatórios foram gerados utilizando 20 86
o modelo de Erdös-Rényi [ER60], onde, com a hipótese 18 19 20 19
do grau médio estar entre 2 e 4, a probabilidade encon- 60
4
trada de existir uma aresta ligando cada par de nós foi de 40
3/(n − 1). Dos grafos gerados, foram considerados ape- 20 1
nas os 2-conexos, até se chegar a quantidade de 200.000 0.15 0.25 0.35 0.15 0.25 0.35
por tamanho de rede, resultando nos 2, 2 × 106 grafos Density
aleatórios. (b)
A título de comparação, foram incluídas na análise 15
redes reais disponívies em Pavan et al. [PMFdRP10]. O Figura 2: Densidade de todas a redes aleatórias e reais
RWA foi resolvido para cada grafo da amostra pelo mé- analisadas (em losangos) versus o número de comprimen-
todo dado em Cousineau et al [CPC+ 15]. Para isso foi tos de onda. O número em cima do losango é seu n, e
considerada uma demanda lógica bidirecional estática en- o número de baixo é seu grau médio. Em (a) todas as
tre cada par de nós, com roteamento feito utilizando ape- redes estão num mesmo gráfico, e em (b) há um gráfico
nas os caminhos mais curtos (geodésicas). para cada n.
3 Resultados Outra análise que podemos fazer é quanto ao grau
médio. Em [FLGM00] é defendido que o grau médio
Em [BB97] é dito que λ decresce fortemente com o cresci- tem grande correlação com o número de comprimentos
mento do invariante densidade de arestas (α), que é dado de onda; porém, ao buscar esse mesmo comportamento
pela razão entre o número de arestas que o grafo possui e em nossos dados, não é o que observamos. Na Figura 3,
o maior número de arestas que ele poderia ter (grafo com- vê-se que o grau médio não está explicando satisfatoria-
pleto). Para visualizar esse relacionamento, a densidade mente o λ, nem para todas as redes juntas (Figura 3a),
de arestas foi calculada para nossas amostras e pode ser nem separadas por n (Figura 3b).
observada na Figura 2. Na Figura 2a, onde os losangos
vermelhos representam as redes reais, com a densidade
de todas as redes juntas, vê-se o decaimento de λ des- 4 Conclusões
crito em [BB97], inclusive dentre as redes reais. Porém,
analisando os mesmos dados de forma mais detalhada, na Diante do aqui exposto, concluímos que um cuidado
Figura 2b a amostra aleatória foi separada para cada n ainda maior deve ser tomado, no sentido de verificar quais
e comparada com todas as redes reais, representadas nos características topológicas podem ser mais ou menos im-
losangos pretos. O decaimento visto inicialmente já não portantes para o planejamento de redes ópticas. Para
é mais observado, e não há uma relação clara entre λ e α. trabalhos futuros, investigaremos outras métricas tam-
O relacionamento visualizado inicialmente na Figura 2a bém sugeridas na literatura para explicar o λ, como a
aparenta ser apenas o acoplamento dos comportamentos variância do grau e o número de árvores geradoras míni-
para cada n. Ou seja, o comportamento de λ em fun- mas ([FLGM00]), além da distância média e a conectivi-
ção de α não é muito claro e nem único ao se variar o dade algébrica ([CBT+ 09]). Serão buscados ainda inva-
n, ou pelo menos não tão evidente quanto se afirmou riantes que expliquem λ de uma forma mais robusta do
em [BB97]. que os apurados na literatura.
Counts
[FLGM00] Christian Fenger, Emmanuel Limal, Ul-
60751
rik Gliese, and Cathal J Mahon. Statis-
tical study of the correlation between to-
60 19
52072 pology and wavelength usage in optical
2.42
networks with and without conversion. In
Number of Wavelengths
19 43394
2.53 19 Networking 2000 Broadband Communica-
40 17
2.74 34715 tions, High Performance Networking, and
2.35 20 Performance of Communication Networks,
15 26037
2.53
3.20 pages 168–175. Springer, 2000.
17
17 17358
12 15 3.06 [PMFdRP10] Claunir Pavan, Rui Manuel Morais, José R
20 3.29 19
2.832.93 12
10 10 14
3.17
3.89 8680 Ferreira da Rocha, and Armando Nolasco
2.40 3.00
2.20 Pinto. Generating realistic optical trans-
1
port network topologies. Journal of Optical
2.5 3.0 3.5
Communications and Networking, 2(1):80–
Mean of Vertex Degree 90, 2010.
(a)
[TAK+ 14] Sahar Talebi, Furqan Alam, Iyad Katib,
2.5 3.0 3.5 2.5 3.0 3.5 Mohamed Khamis, Reda Salama, and Ge-
10 11 12 13
Counts orge N Rouskas. Spectrum management
60
35070 techniques for elastic optical networks: A
40
7864
survey. Optical Switching and Networking,
20
13:34–48, 2014.
Number of Wavelengths
14 15 16 17 1764
60
395
[WM14] Rui Wang and Biswanath Mukherjee.
40 Spectrum management in heterogeneous
20 89
bandwidth optical networks. Optical Swit-
18 19 20 20 ching and Networking, 11:83–91, 2014.
60
4
40 [YX10] Penghui Yuan and Anshi Xu. The
20 1 influence of physical network topologies
2.5 3.0 3.5 2.5 3.0 3.5
on wavelength requirements in optical
Mean of Vertex Degree networks. Journal of Lightwave Techno-
(b) logy, 28(9):1338–1343, 2010.
Figura 3: Grau médio de todas a redes aleatórias e reais [ZDLMM13] Guoying Zhang, Marc De Leenheer, An-
analisadas (em losangos) versus o número de comprimen- nalisa Morea, and Biswanath Mukherjee.
tos de onda. O número em cima do losango é seu n, e A survey on OFDM-based elastic core op-
o número de baixo é seu grau médio. Em (a) todas as tical networking. IEEE Communications
redes estão num mesmo gráfico, e em (b) há um gráfico Surveys & Tutorials, 15(1):65–87, 2013.
para cada n.
Referências
[BB97] Stefano Baroni and Polina Bayvel. Wa-
velength requirements in arbitrarily
connected wavelength-routed optical
networks. Lightwave Technology, Journal
of, 15(2):242–251, 1997.
[CBT+ 09] Benoît Châtelain, Michel P Bélanger, Ch-
ristine Tremblay, François Gagnon, and
David V Plant. Topological wavelength
usage estimation in transparent wide area
networks. Journal of Optical Communica-
tions and Networking, 1(1):196–203, 2009.
[CPC+ 15] Martin Cousineau, Sylvain Perron, Gilles
Caporossi, Marcia Paiva, and Marcelo Se-
gatto. RWA problem with geodesics in re-
alistic OTN topologies. Optical Switching
and Networking, 15:18–28, 2015.
[ER60] Paul Erdös and A Rényi. On the evolu-
tion of random graphs. Publ. Math. Inst.
Hungar. Acad. Sci, 5:17–61, 1960.