The analysis of an optical telecommunication network topology is very important when it is desired to minimize the impact of possible node failures in this network. In this paper, we analyse how to improve the resilience of the RNP (Rede Nacional de Pesquisa) network, a Brazilian optical backbone that interconnects research and education institutions throughout the country. In order to obtain an optimized topology in terms of resilience, and using the graph invariant called Nodal Wiener Impact (NWI) to quantify that, we propose a Variable Neighborhood Search (VNS) algorithm to add a limited number of links to provide the network with a lower impact resulting from possible failures, that is, to increase its resilience by minimizing the NWI.
É de grande importância que um projeto de topologia de redes de telecomunicações seja otimizado a fim de evitar grandes perdas devido a falhas pontuais na rede. Uma única falha em um nó qualquer da rede pode resultar no aumento do caminho que a informação terá que percorrer em relação ao original, concomitantemente, haverá um aumento na latência, podendo levar a perdas de informação, como descrito para a topologia anel em [Pai12].
A Teoria de Grafos vem como uma aliada no projeto de topologia de uma rede, de forma que é possível modelá-la via grafos e estabelecer comparativos entre parâmetros desejados em uma rede de telecomunicações e invariantes de grafos [FDP+19].
Este trabalho teve como intuito desenvolver um algoritmo objetivando o aumento da resiliência da rede por meio da adição de novos enlaces a ela. A fim de se aumentar a resiliência, propomos o cálculo dos impactos de cada vértice de grafos representativos de redes ópticas de telecomunicações. De [FDP+19] temos que o máximo NWI é usado para quantificar a resiliência de uma rede, onde NWI é dado pela fórmula: N W I(v) = W (G v)
W (G) + T (v); (1) onde W (G v) é o índice de Wiener do grafo sem o vértice v onde ocorreu a falha, W (G) é o índice de Wiener do grafo original e T (v) é a transmissão do vértice v. O somatório dos impactos é dado pela soma dos NWI de cada vértice do grafo, como na fórmula abaixo:
n = X N W I(v); v=1 (2) onde n é o número de vértices do grafo.
Para fins de otimização, utilizamos como parâmetro o máximo NWI dentre o conjunto de vértices de um dado grafo, de forma que ele representa o impacto mais crítico do grafo, e também utilizamos o somatório dos impactos de todos os vértices, já que este último apresenta o impacto de forma mais global. O NWI está ligado à resiliência devido ao fato que ele quantifica o impacto, em unidades de distância, da falha em um vértice sobre os demais pares de vértices do grafo. Assim, quanto menor for o NWI de um vértice, menor será o impacto caso ocorra uma falha nele e, portanto, mais resiliente a falhas é a rede.
Para a Rede Ipê [RNP16], por exemplo, temos que o máximo impacto é de 181 unidades de distância, referente ao nó de Fortaleza, e o somatório dos impactos é de 630 unidades como pode ser visualizado na Figura 1. Caso ocorra uma falha no vértice de maior impacto, haverá um aumento de 181 unidades nas distâncias entre os demais pares de vértices, o que é muito preocupante caso haja uma falha nele e isso resulte em uma má comunicação ou até em perdas de informação, visto que existem enlaces ligados a ele como uma taxa de transmissão de 10 Gb/s. Além disso, este mesmo nó possui conexão internacional. Em contrapartida, existem dois vértices com NWI igual a zero, ou seja, caso ocorra uma falha em um deles, não haverá aumento algum nas distâncias entre os demais pares de vértices.
Desta forma, a adição de arestas vem como um método que proporciona o encurtamento de caminhos em um grafo. Este encurtamento reduz o índice de Winer, logo pode proporcionar a redução do NWI.
Assim, foi desenvolvido um algoritmo utilizando a meta-heurística Variable Neighborhood Search (VNS) [MH97], meta-heurística amplamente utilizada no meio de telecomunicações baseada em buscas locais em distintas estruturas de vizinhanças, com intuito de achar uma solução cada vez melhor à medida que as vizinhanças são percorridas. Os resultados obtidos com a implementação da meta-heurística foram muito bons quando comparados com o método exaustivo, apresentando uma grande redução na quantidade de testes de adição de arestas realizados. 2
desenvolvido procura pela adição de aresta que minimiza o máximo NWI, Equação 1, ou o , Equação 2, de um grafo G, de acordo com a escolha do usuário do algoritmo.
O algoritmo inicializa selecionando como solução inicial o máximo NWI ou o se o objetivo for minimizar o máximo NWI ou o somatório dos impactos, respectivamente. Em seguida os vértices inicias v1 e v2 são escolhidos. As estruturas de vizinhança são construídas seguindo o padrão: [[0,0],[1,0],[0,1],[1,1], ..., [d1,d2], ..., [h(G), h(G)]], onde h(G) é a distância média de G. Em cada estrutura os vértices que estão distantes de v1 a uma distância d1 são combinados com os vértices que distam de v2 a uma distância d2. Ou seja, na estrutura de vizinhança de índice 0 ([0,0]) os vértices a distância 0 de v1 serão combinados com os vértices de distância 0 de v2, em especial, nessa vizinhança, a combinação resulta nos próprios vértices v1 e v2. Já na vizinhança de índice 1 ([1,0]), os vértices a distância 1 de v1 serão combinados com o vértice v2 e assim por diante. Cada combinação forma um par de vértices e, portanto, arestas para a realização dos testes de adição.
Em cada teste uma nova solução é encontrada. Se a menor solução dentro de uma estrutura for menor que a melhor solução, v1 e v2 são atualizados pelos vértices cuja adição da aresta correspondente proporcionou a solução melhorada e o algoritmo é reiniciado. Caso o algoritmo não encontre uma solução melhorada dentro de uma estrutura de vizinhança, ele passa para a vizinhança seguinte e continua a busca. O algoritmo para quando nenhuma solução melhor for encontrada nas estruturas de vizinhanças.
Para fins de análise, os vértices inciais v1 e v2 foram escolhidos de três formas distintas: (i) v1 e v2 são os vértices que possuem o maior NWI dentre todos os vértices do grafo G; (ii) v1 e v2 são escolhidos de forma aleatória pelo algoritmo; (iii) v1 e v2 são os vértices mais distantes da solução encontrada exaustivamente.
Devido ao fato de que existem adições de aresta que podem causar o aumento do máximo NWI e/ou do , a solução inicial foi escolhida como sendo o máximo NWI ou o da rede original de forma que o algoritmo não trabalhe com soluções ruins para o caso proposto de minimizar as invariantes em questão.
Com as rotinas computacionais já desenvolvidas e aplicadas foi quantificado o número de testes de adição de arestas que o algoritmo realizou a fim de estabelecer um comparativo entre o algoritmo VNS e o exaustivo, identificando a otimização obtida. 3
O VNS é baseado em uma série de buscas locais em diferentes estruturas de vizinhanças e o algoritmo O algoritmo foi testado na rede RNP e, apesar da meta-heurística não garantir que o resultado encontrado seja o melhor global, foi possível chegar neste resultado com um número muito reduzido de testes de adição de arestas realizados comparado ao método exaustivo.
Para a RNP foi possível obter 2 melhores configurações: uma que minimizou o máximo NWI para 111 unidades e o para 486 e outra que minimizou o para 457 unidades e o máximo NWI para 132, como pode ser observado na Figura 2. Assim sendo, foi possível reduzir o máximo NWI em aproximadamente 38% e o em aproximadamente 27% com a adição de uma única aresta.
Na Tabela 1 temos um comparativo entre o número de operações, ou testes de adição de arestas, realizados para os algoritmos exaustivo e utilizando VNS. Neste último temos ainda a comparação do número de operações realizadas pelo algoritmo para as 3 escolhas distintas dos vértices iniciais: (i) v1 e v2 são os vértices de maior NWI; (ii) v1 e v2 aleatórios; (iii) v1 e v2 são os vértices mais distantes da solução encontrada exaustivamente. 2Como pode existir um conjunto de mais de um par de vértices mais distantes da solução encontrada exaustivamente, o número de operações, deste caso, foi contabilizado como sendo a média aproximada das operações de todos os pares de vértices mais distantes.
Os resultados apresentados foram bastante satisfatórios, sendo possível chegar no melhor resultado global utilizando a meta-heurística VNS, além de reduzir bastante a quantidade de operações realizadas quando comparada ao método exaustivo. Foi possível, também, obter resultados bons adicionando apenas um enlace, de forma que o aumento da resiliência não acarretasse em um grande custo extra para a rede. Contudo, contabilizar o custo da adição de enlaces é um assunto ainda um pouco vago. De [Pai12] temos que a topologia de um grafo completo é a que apresenta a melhor configuração em termos de resiliência, haja vista que, nessa topologia, o NWI de todos os vértices é igual a zero. Porém, essa mesma topologia, apresenta um alto custo, porque todos os vértices estão conectados entre si. Portanto, faz-se necessário uma análise de quantos enlaces adicionais proporcionam uma boa resiliência para a rede de forma que não resulte em um custo muito maior para a rede. Em contrapartida, na mesma referência citada, temos que a topologia de grafos gêmeos também apresenta a melhor configuração em termos de resiliência, na qual todos os vértices tem NWI nulo. Além disso possui um custo mais reduzido em relação ao grafo completo, visto que não precisa que todos os vértices estejam interligados para ter um impacto nulo. Tomando como exemplo um grafo com 22 vértices, um grafo completo com essa quantidade de vértices tem 231 arestas e um grafo gêmeo tem 40 arestas, enquanto o grafo da rede RNP (Figura 1), que tem essa mesma quantidade de vértices, tem 31 arestas. Desta forma, é possível notar que o grafo gêmeo apresenta uma boa relação custo-resiliência. Portanto, vale questionar se adicionar novos enlaces à rede é a melhor alternativa para o problema de resiliência ou se realocar uma certa quantidade de enlaces da rede, de forma a se aproximar da configuração de grafos gêmeos, proporcionaria o melhor custo-benefício ou, ainda, aplicar ambas ações simultaneamente.
Inclusive, é interessante observar que, até o momento, sabemos que a rede suporta um enlace que tenha o tamanho do maior enlace da mesma. Contudo, será que ela tem suporte para um enlace maior? Caso essa informação não seja fácil de ser obtida, é viável que o algoritmo seja implementado de forma a restringir adições de arestas maiores do que sabemos que a rede suporta, de forma a garantir uma boa comunicação da mesma. 5
Este trabalho foi foi parcialmente financiado pelo CNPq, FAPES e Coordenação de Aperfeiçoamento de
em: Acesso