This study analyzes the influence of the variability of topological characteristics of optical networks in their desirable performance, with respect to the requirement of wavelengths. The studies were focused on real-world networks and random graphs with characteristics of realworld networks. It was observed that some topological features exalted in the literature may not necessarily be good representatives of the behavior of optical networks.
As redes ópticas de transporte (OTN - Optical Transport Networks ) se tornaram o ramo central da imensa malha de redes de comunicações da sociedade atual devido a vários fatores, como a sua grande capacidade de tráfego, velocidade e alcance. Vários canais independentes podem compartilhar a mesma fibra óptica, aumentado a taxa de dados sobre a mesma infraestrutura. Nas redes convencionais utiliza-se a tecnologia de Wavelength Division Multiplexing (WDM), permitindo assim a implementação de redes com roteamento de tráfego por comprimentos de onda (WRON - Wavelength Routed Optical Networks ). Todavia, as redes da nova geração, chamadas de Elastic Optical Networks (EON), são baseadas em Optical Orthogonal Frequency Division Multi-plexing (OOFDM). Essa tecnologia se diferencia por permitir um uso mais flexível do espectro óptico, com canais de tamanho variado, alcançando uma maior eficiência espectral [ZDLMM13].
Em redes WRON, temos o problema de Routing and Wavelength Assignment (RWA) que envolve o roteamento das demandas e a alocação de comprimentos de onda aos canais ópticos. Neste problema há a restrição de continuidade de comprimentos de onda, que o torna um problema NP-Hard. Cada canal deve utilizar o mesmo comprimento de onda do início ao fim da rota. Isso gera uma fragmentação do espectro disponível, onde se pode ter comprimentos de onda disponíveis em vários enlaces, mas sem continuidade entre enlaces consecutivos, impedindo que rotas de mais de um salto sejam criadas. O termo número mínimo de comprimentos de onda será daqui em diante chamado apenas de número de comprimentos de onda, e será denotado por .
Por sua vez, nas redes EON temos o respectivo Routing, Modulation, and Spectrum Assignment (RMSA) Copyright c held by the authors. problem, que acrescenta ao RWA a restrição de não sobreposição (non-overlapping ) [ZDLMM13]. O espectro óptico é subdividido em slots e canais de tamanho variado são criados combinando os slots para atender demandas de taxa e requisitos distintos. Ainda há a restrição de continuidade para os canais, mas a combinação de canais de diferentes tamanhos cria outro tipo de fragmentação, pois os canais só podem ser formados por slots contíguos em cada enlace. Uma estratégia mais comum para se tratar esse problema é subdividindo o espectro em partições, e em cada uma alocar apenas canais do mesmo tamanho. Deste modo, em cada partição o problema se reduz ao RWA clássico [WM14]. De todo modo, como o RMSA é um problema ainda mais complexo, seria ideal que a rede tenda a ter um baixo requisito para a quantidade de comprimentos de onda necessária para atender a restrição de continuidade [TAK+14].
O uso de mais comprimentos de λ = 5 λ = 3 onda diminui a 1 3 3 5 disponibilidade da rede, pois 6 5 1 6 reduz a quantidade de canais 4 2 4 2 disponíveis para novas conexões. Figura 1: Redes com mesmo núAumentar a mero de nós (n = 6), enlaces quantidade de (m = 8) e, logo, mesmo grau mécanais dispo- dio (2m=n = 2:66), mas com diníveis é muito ferente. dispendioso devido ao alto custo dos equipamentos ópticos. Portanto, o ideal é que a topologia da rede facilite a alocação de comprimentos de onda. Por exemplo, na Figura 1 vemos redes com mesma quantidade de nós e arestas, e logo mesmo grau médio (onde o grau de um vértice é definido como a quantidade de arestas que se ligam a esse vértice), mas com um requisito de diferente, sendo que a diferença entre as duas redes é basicamente a topologia. Ao se planejar uma topologia de rede óptica, entre as múltiplas formas de se conectar nós e arestas, não é fácil se controlar o , pois seu cálculo envolve um a resolução de um problema N P Hard. Daí surge o interesse em invariantes topológicos que sejam bem correlacionados com e também mais fáceis de se calcular, e que possam assim ser usados no projeto da rede, como indicadores de topologia que propiciarão um 60 menor na rede.
Ao longo do tempo, alguns trabalhos na literatura tem se debruçado a trabalhar no cálculo de invariantes topológicos que se relacionam com e que não envolvam a resolução de outro problema N P [BB97, FLGM00, YX10]. No presente trabalho são então calculados (usando o pacote igraph do programa R) dois invariantes de grafos com o objetivo de verificar, de forma mais abrangente, como a variabilidade de características topológicas das redes podem influenciar no número de comprimentos de onda. 2
Os estudos foram concentrados em grafos aleatórios que simulavam redes reais, com número de nós n = 10; :::; 20, e para cada n foram gerados aleatoriamente 200:000 deles, resultando assim numa amostra com 2; 2 106 grafos aleatórios simples, 2-conexos, de arestas com peso unitário, não isomorfos entre si, e ainda com grau médio de cada grafo assumindo valores entre 2 e 4, que é o esperado em redes reais [PMFdRP10]. Foram geradas redes aleatórias com no mínimo 10 nós, para evitar possíveis efeitos de borda em grafos muito pequenos, e no máximo 20 nós, em função do custo computacional de tratar toda a amostra. Os grafos aleatórios foram gerados utilizando o modelo de Erdös-Rényi [ER60], onde, com a hipótese do grau médio estar entre 2 e 4, a probabilidade encontrada de existir uma aresta ligando cada par de nós foi de 3=(n 1). Dos grafos gerados, foram considerados apenas os 2-conexos, até se chegar a quantidade de 200:000 por tamanho de rede, resultando nos 2; 2 106 grafos aleatórios.
A título de comparação, foram incluídas na análise 15 redes reais disponívies em Pavan et al. [PMFdRP10]. O RWA foi resolvido para cada grafo da amostra pelo método dado em Cousineau et al [CPC+15]. Para isso foi considerada uma demanda lógica bidirecional estática entre cada par de nós, com roteamento feito utilizando apenas os caminhos mais curtos (geodésicas). 3
Em [BB97] é dito que decresce fortemente com o crescimento do invariante densidade de arestas ( ), que é dado pela razão entre o número de arestas que o grafo possui e o maior número de arestas que ele poderia ter (grafo completo). Para visualizar esse relacionamento, a densidade de arestas foi calculada para nossas amostras e pode ser 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 descrito em [BB97], inclusive dentre as redes reais. Porém, analisando os mesmos dados de forma mais detalhada, na Figura 2b a amostra aleatória foi separada para cada n e comparada com todas as redes reais, representadas nos losangos pretos. O decaimento visto inicialmente já não é mais observado, e não há uma relação clara entre e . O relacionamento visualizado inicialmente na Figura 2a aparenta ser apenas o acoplamento dos comportamentos para cada n. Ou seja, o comportamento de em função de não é muito claro e nem único ao se variar o n, ou pelo menos não tão evidente quanto se afirmou em [BB97].
Counts
Outra análise que podemos fazer é quanto ao grau médio. Em [FLGM00] é defendido que o grau médio tem grande correlação com o número de comprimentos de onda; porém, ao buscar esse mesmo comportamento em nossos dados, não é o que observamos. Na Figura 3, vê-se que o grau médio não está explicando satisfatoriamente o , nem para todas as redes juntas (Figura 3a), nem separadas por n (Figura 3b). 4
Diante do aqui exposto, concluímos que um cuidado ainda maior deve ser tomado, no sentido de verificar quais características topológicas podem ser mais ou menos importantes para o planejamento de redes ópticas. Para trabalhos futuros, investigaremos outras métricas também sugeridas na literatura para explicar o , como a variância do grau e o número de árvores geradoras mínimas ([FLGM00]), além da distância média e a conectividade algébrica ([CBT+09]). Serão buscados ainda invariantes que expliquem de uma forma mais robusta do que os apurados na literatura. Figura 3: Grau médio de todas a redes aleatórias e reais analisadas (em losangos) versus o número de comprimentos de onda. O número em cima do losango é seu n, e o número de baixo é seu grau médio. Em (a) todas as redes estão num mesmo gráfico, e em (b) há um gráfico para cada n.
[CBT+09] [CPC+15] [ER60]
velength requirements in arbitrarily connected wavelength-routed optical networks. Lightwave Technology, Journal of, 15(2):242–251, 1997. 52072 43394 34715 26037 17358 8680 [TAK+14] [YX10]
rik Gliese, and Cathal J Mahon. Statistical study of the correlation between topology and wavelength usage in optical networks with and without conversion. In Networking 2000 Broadband Communications, High Performance Networking, and Performance of Communication Networks, pages 168–175. Springer, 2000.
Mohamed Khamis, Reda Salama, and George N Rouskas. Spectrum management techniques for elastic optical networks: A survey. Optical Switching and Networking, 13:34–48, 2014.
Spectrum management in heterogeneous bandwidth optical networks. Optical Switching and Networking, 11:83–91, 2014.