This work analyzes the average number of hops needed to route working and backup paths in telecommunication networks, pointing out differences in its behavior when using two routing methods based on the Dijkstra’s algorithm and on the Suurballe’s algorithm, respectively.
Em redes de telecomunicações, o projeto topológico deve garantir uma rede confiável, que seja tolerante a alguns tipos de falhas, como a ruptura de uma ligação ou a falta de energia em um nodo [MPPR11, Pav11]. Para dimensionar uma rede assim, é importante ter informações detalhadas sobre a rede, incluindo as topologias de rede, os volumes de tráfego a serem suportados, as arquiteturas dos nodos e ligações e as distâncias físicas entre nodos. Neste sentido, a caracterização de redes e a identificação de variáveis de mérito são recursos úteis para novos métodos de apoio ao dimensionamento de redes de telecomunicações que permitam prover, rapidamente, resultados aproximados sobre custos de capital e operação.
Uma propriedade importante na caracterização de redes é a proteção a falhas de diferentes tipos para evitar a interrupção do serviço oferecido pela rede e a perda significativa de dados. Por estas razões, as topologias físicas devem ser sobreviventes. Isto significa que a topologia de rede deve ter estratégias que Copyright c held by the author(s). Copying permitted for private and academic purposes. mantenham seu serviço disponível mesmo com falhas. Para isso, técnicas e algoritmos podem ser úteis.
Encontram-se disponíveis em [RMdRP13] um pequeno conjunto de redes de telecomunicações reais que contém entre 9 e 100 nodos, 12 a 171 arestas, com grau médio entre 2 e 4; 7, e que são redes 2-aresta-conexas. Nestas redes reais, caminhos de trabalho carregam o tráfego normal e caminhos de proteção providenciam a sobrevivência através de uma rota alternativa para carregar o tráfego em caso de falhas ou manutenção da rede.
Uma variável que emprega caminhos de trabalho e de proteção é o número de saltos [PMdRP10]. Em um caminho, cada aresta percorrida representa um salto, portanto o número de saltos é o comprimento de um caminho do nodo i ao nodo j. O hhwi é o número médio de saltos, ou seja, é um valor relacionado a todos os comprimentos de caminhos de nodos origens a nodos destinos de um determinado grafo, considerando o caminho de trabalho; e hhbi é o número médio de saltos considerando comprimentos de caminhos de proteção. O caminho de trabalho é o menor caminho e o caminho de proteção geralmente é o segundo menor caminho disjunto por arestas.
Existem algoritmos que podem ser utilizados para definir o número de saltos, dentre eles, o algoritmo de Dijkstra, que tem o objetivo de encontrar o menor caminho de um nodo origem a um nodo destino em uma topologia e o algoritmo de Suurballe, cujo objetivo é encontrar dois menores caminhos disjuntos por arestas, ou seja, garantindo proteção e sem nenhum tipo de compartilhamento de ligação. Contudo, os valores obtidos pelos dois algoritmos podem ser diferentes.
Por exemplo, para a topologia ilustrada na Figura 1 e Figura 2, considerando que o peso de cada aresta é 1, saindo do nodo origem s e indo para o nodo destino d, obtemos com o algoritmo de Dijkstra um caminho de trabalho (linha tracejada) com 3 saltos, como pode ser observado na imagem à esquerda. Entretanto, um caminho de proteção não será encontrado, pois qualquer outro caminho possível de s a d irá compartilhar uma aresta com o caminho de trabalho. Nas mesmas condições, ao usar o algoritmo de Suurballe, obtemos um caminho de trabalho com 4 saltos, i.e., um salto a mais que o caminho de trabalho obtido com o algoritmo de Dijkstra, mas nesse caso obtemos ainda um caminho de proteção disjunto por arestas com relação ao caminho de trabalho, e também com 4 saltos. Ambos os caminhos são ilustrados na imagem à direita (linha tracejada e pontilhada).
Figura 1: Caminho de trabalho obtido com o algoritmo de Dijkstra.
Figura 2: Caminhos de trabalho e de proteção obtidos com o algoritmo de Suurballe.
Uma estratégia que utiliza o algoritmo de Dijkstra para o roteamento do número de saltos é apresentada em [Pav11] onde as expressões são exatas, e outra utilizando o algoritmo de Suurballe [Oli10] é apresentada em [Gir14], onde expressões semi-empíricas que dependem apenas do número de nodos e do número de ligações foram obtidas para o número médio de saltos pelo caminho de trabalho e para o número médio de saltos pelo caminho de proteção.
Com base no conjunto de redes reais disponíveis, foi calculado o número médio de saltos para os caminhos de trabalho e de proteção com roteamento pelo algoritmo de Dijkstra (Figura 3) e o número médio de saltos para os caminhos de trabalho e de proteção com o Infinity 14 12 s p o10 h f ro 8 e b m6 u N4 2 00 16 14 s12 p fho10 o re 8 b m u 6 N 4 2 00 roteamento pelo algoritmo de Suurballe (Figura 4). O cálculo do número de saltos para ambas variáveis e seu algoritmo de roteamento foi realizado através da expressão exata do número de saltos definida em [Pav11] e foi considerado que o peso de todas as arestas de cada rede tem valor 1.
h backup Dijkstra h working Dijkstra
AlgoritmoDijkstraprotection(:,1)
AlgoritmoDijkstraprotection(:,2) 5 10 15 20 25 30 35 40 real-world telecommunication networks topologies 40 Figura 3: hhdwi e hhbdi: número médio de saltos para os caminhos de trabalho e de proteção, respectivamente, com o roteamento pelo algoritmo de Dijkstra. h backup Suurballe h working Suurballe 5 10 15 20 25 30 35 40 real-world telecommunication networks topologies 40 Figura 4: hhswi e hhbsi: número médio de saltos para os caminhos de trabalho e de proteção, respectivamente, com o roteamento pelo algoritmo de Suurballe.
No eixo horizontal das Figuras 3 e 4 temos um conjunto de 40 redes reais de telecomunicações [RMdRP13] que estão organizadas a partir do número de nodos (da rede com menor número de nodos até a rede com maior número de nodos), e no eixo vertical temos o número médio de saltos de cada rede calculado a partir da técnica de roteamento utilizada.
A partir dos gráficos, se verifica que em 40% das redes, o algoritmo de Dijkstra não encontrou um caminho de proteção (infinito), ainda que isto fosse possível, já que todas as redes estudadas são 2-aresta-conexas. Nas redes em que o algoritmo de Dijkstra encontrou um caminho de proteção, a diferença do caminho de trabalho para o caminho de proteção foi de em média 66% (média entre todas as redes), sendo 25% no melhor caso e 149% no pior caso. Já o algoritmo de Suurballe encontrou ambos os caminhos e teve uma diferença entre o caminho de trabalho e o de proteção de em média 68% (média entre todas as redes), sendo 23% no melhor caso e 122% no pior caso.
Comparando a diferença do caminho de trabalho para ambos os algoritmos, os resultados do algoritmo de Suurballe foram iguais aos do algoritmo de Dijkstra no melhor caso, 21% maiores no pior caso, e 3% maiores na média entre todas as redes. Já para o caminho de proteção, considerando somente as redes que encontraram caminho de proteção, os resultados do algoritmo de Dijkstra foram iguais aos do algoritmo de Suurballe no melhor caso, 6% maiores no pior caso, e 2% maiores na média entre todas as redes. Estes resultados estão resumidos na Tabela 1. Melhor Médio Pior hhbdi hhdwi hhdwi 25% 66% 149% hhbsi hhswi hhswi hhdwi hhbdi hhbsi hhswi hhdwi hhbsi 23% 0% 0% 68% 3% 2% 122% 21% 6% Tabela 1: Resultados das observações dos gráficos das Figuras 3 e 4.
Devido à elevada quantidade de redes que não encontraram um segundo caminho no roteamento pelo algoritmo de Dijkstra, existem grandes chances de futuros problemas na rede em momentos de falhas nas arestas. Portanto, em termos de robustez de rede, a opção ideal seria o roteamento pelo algoritmo de Suurballe.
Para encontrar um resultado ainda melhor, podem ser utilizadas estratégias que permitam ponderar as arestas com os pesos desejados, somar os pesos dos dois caminhos (de trabalho e de proteção) gerados a partir do algoritmo de Suurballe e verificar pela soma os menores caminhos com arestas disjuntas para a definição do roteamento. Também, outros algoritmos de roteamento podem ser utilizados com este objetivo e atingir resultados diferentes.
Deve-se observar que, mesmo usando o algoritmo de Suurballe e considerando arestas com peso unitário, não há garantia de que o mesmo par de caminhos será sempre escolhido. Assim, outro ponto a ser investigado em trabalhos futuros é a influência dos diferentes pares de caminho obtidos pelo algoritmo de Suurballe no processo de roteamento.
M. Girolimetto. Variáveis de mérito de topologias de redes ópticas de transporte de telecomunicações. Trabalho de conclusão de curso (graduação) - Universidade [MPPR11] [Oli10] [Pav11] R. M. Morais, C. Pavan, A. N. Pinto, and C. Requejo. Genetic algorithm for the topological design of survivable optical transport networks. IEEE/OSA Journal of Optical Communications and Networking, 3:17–26, 2011.
J. M. S. dos S. Oliveira. Protecção máxima de redes de telecomunicações. Mestrado, Universidade de Aveiro, 2010.