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.