=Paper=
{{Paper
|id=Vol-1727/ssn16-final15
|storemode=property
|title=The Average Number of Hops for Working and Backup Paths in Telecommunication Networks
|pdfUrl=https://ceur-ws.org/Vol-1727/ssn16-final15.pdf
|volume=Vol-1727
|authors=Marina Girolimetto,Claunir Pavan
|dblpUrl=https://dblp.org/rec/conf/ssn/GirolimettoP16
}}
==The Average Number of Hops for Working and Backup Paths in Telecommunication Networks==
https://ceur-ws.org/Vol-1727/ssn16-final15.pdf
The Average Number of Hops for Working and Backup
Paths in Telecommunication Networks
Marina Girolimetto
marina.girolimetto@aluno.ufes.br
Laboratory of Telecommunications – LabTel
Federal University of Espírito Santo – UFES, Vitória, Brazil
Claunir Pavan
claunir.pavan@uffs.edu.br
Federal University of Fronteira Sul – UFFS, Chapecó, Brazil
mantenham seu serviço disponível mesmo com falhas.
Para isso, técnicas e algoritmos podem ser úteis.
Resumo Encontram-se disponíveis em [RMdRP13] um pe-
queno conjunto de redes de telecomunicações reais que
This work analyzes the average number of contém entre 9 e 100 nodos, 12 a 171 arestas, com grau
hops needed to route working and backup médio entre 2 e 4, 7, e que são redes 2-aresta-conexas.
paths in telecommunication networks, poin- Nestas redes reais, caminhos de trabalho carregam o
ting out differences in its behavior when using tráfego normal e caminhos de proteção providenciam
two routing methods based on the Dijkstra’s a sobrevivência através de uma rota alternativa para
algorithm and on the Suurballe’s algorithm, carregar o tráfego em caso de falhas ou manutenção
respectively. da rede.
Uma variável que emprega caminhos de trabalho e
Em redes de telecomunicações, o projeto topológico
de proteção é o número de saltos [PMdRP10]. Em um
deve garantir uma rede confiável, que seja tolerante a
caminho, cada aresta percorrida representa um salto,
alguns tipos de falhas, como a ruptura de uma ligação
portanto o número de saltos é o comprimento de um
ou a falta de energia em um nodo [MPPR11, Pav11].
caminho do nodo i ao nodo j. O hhw i é o número
Para dimensionar uma rede assim, é importante ter
médio de saltos, ou seja, é um valor relacionado a to-
informações detalhadas sobre a rede, incluindo as to-
dos os comprimentos de caminhos de nodos origens
pologias de rede, os volumes de tráfego a serem supor-
a nodos destinos de um determinado grafo, conside-
tados, as arquiteturas dos nodos e ligações e as dis-
rando o caminho de trabalho; e hhb i é o número médio
tâncias físicas entre nodos. Neste sentido, a caracteri-
de saltos considerando comprimentos de caminhos de
zação de redes e a identificação de variáveis de mérito
proteção. O caminho de trabalho é o menor caminho e
são recursos úteis para novos métodos de apoio ao di-
o caminho de proteção geralmente é o segundo menor
mensionamento de redes de telecomunicações que per-
caminho disjunto por arestas.
mitam prover, rapidamente, resultados aproximados
Existem algoritmos que podem ser utilizados para
sobre custos de capital e operação.
definir o número de saltos, dentre eles, o algoritmo de
Uma propriedade importante na caracterização de
Dijkstra, que tem o objetivo de encontrar o menor ca-
redes é a proteção a falhas de diferentes tipos para
minho de um nodo origem a um nodo destino em uma
evitar a interrupção do serviço oferecido pela rede e
topologia e o algoritmo de Suurballe, cujo objetivo é
a perda significativa de dados. Por estas razões, as
encontrar dois menores caminhos disjuntos por ares-
topologias físicas devem ser sobreviventes. Isto signi-
tas, ou seja, garantindo proteção e sem nenhum tipo
fica que a topologia de rede deve ter estratégias que
de compartilhamento de ligação. Contudo, os valores
Copyright c held by the author(s). Copying permitted for pri- obtidos pelos dois algoritmos podem ser diferentes.
vate and academic purposes. Por exemplo, para a topologia ilustrada na Figura 1
e Figura 2, considerando que o peso de cada aresta é roteamento pelo algoritmo de Suurballe (Figura 4). O
1, saindo do nodo origem s e indo para o nodo destino cálculo do número de saltos para ambas variáveis e seu
d, obtemos com o algoritmo de Dijkstra um caminho algoritmo de roteamento foi realizado através da ex-
de trabalho (linha tracejada) com 3 saltos, como pode pressão exata do número de saltos definida em [Pav11]
ser observado na imagem à esquerda. Entretanto, um e foi considerado que o peso de todas as arestas de
caminho de proteção não será encontrado, pois qual- cada rede tem valor 1.
quer outro caminho possível de s a d irá compartilhar
Infinity
uma aresta com o caminho de trabalho. Nas mesmas AlgoritmoDijkstraprotection(:,1)
AlgoritmoDijkstraprotection(:,2)
condições, ao usar o algoritmo de Suurballe, obtemos h backup Dijkstra
um caminho de trabalho com 4 saltos, i.e., um salto 14 h working Dijkstra
a mais que o caminho de trabalho obtido com o algo- 12
Number of hops
ritmo de Dijkstra, mas nesse caso obtemos ainda um 10
caminho de proteção disjunto por arestas com relação 8
ao caminho de trabalho, e também com 4 saltos. Am- 6
bos os caminhos são ilustrados na imagem à direita
4
(linha tracejada e pontilhada).
2
0
0 5 10 15 20 25 30 35 40
40 real-world telecommunication networks topologies
Figura 3: hhdw i e hhdb i: número médio de saltos para os
caminhos de trabalho e de proteção, respectivamente,
com o roteamento pelo algoritmo de Dijkstra.
16
h backup Suurballe
h working Suurballe
14
Figura 1: Caminho de trabalho obtido com o algoritmo
12
de Dijkstra.
Number of hops
10
8
6
4
2
0
0 5 10 15 20 25 30 35 40
40 real-world telecommunication networks topologies
Figura 4: hhsw i e hhsb i: número médio de saltos para os
caminhos de trabalho e de proteção, respectivamente,
Figura 2: Caminhos de trabalho e de proteção obtidos com o roteamento pelo algoritmo de Suurballe.
com o algoritmo de Suurballe.
No eixo horizontal das Figuras 3 e 4 temos
Uma estratégia que utiliza o algoritmo de Dijkstra um conjunto de 40 redes reais de telecomunica-
para o roteamento do número de saltos é apresentada ções [RMdRP13] que estão organizadas a partir do
em [Pav11] onde as expressões são exatas, e outra uti- número de nodos (da rede com menor número de no-
lizando o algoritmo de Suurballe [Oli10] é apresentada dos até a rede com maior número de nodos), e no eixo
em [Gir14], onde expressões semi-empíricas que depen- vertical temos o número médio de saltos de cada rede
dem apenas do número de nodos e do número de liga- calculado a partir da técnica de roteamento utilizada.
ções foram obtidas para o número médio de saltos pelo A partir dos gráficos, se verifica que em 40% das
caminho de trabalho e para o número médio de saltos redes, o algoritmo de Dijkstra não encontrou um cami-
pelo caminho de proteção. nho de proteção (infinito), ainda que isto fosse possível,
Com base no conjunto de redes reais disponíveis, foi já que todas as redes estudadas são 2-aresta-conexas.
calculado o número médio de saltos para os caminhos Nas redes em que o algoritmo de Dijkstra encontrou
de trabalho e de proteção com roteamento pelo algo- um caminho de proteção, a diferença do caminho de
ritmo de Dijkstra (Figura 3) e o número médio de sal- trabalho para o caminho de proteção foi de em mé-
tos para os caminhos de trabalho e de proteção com o dia 66% (média entre todas as redes), sendo 25% no
melhor caso e 149% no pior caso. Já o algoritmo de Federal da Fronteira Sul, Curso de Ciên-
Suurballe encontrou ambos os caminhos e teve uma cia da Computação, Chapecó, SC, 2014.
diferença entre o caminho de trabalho e o de proteção
de em média 68% (média entre todas as redes), sendo [MPPR11] R. M. Morais, C. Pavan, A. N. Pinto, and
23% no melhor caso e 122% no pior caso. C. Requejo. Genetic algorithm for the
Comparando a diferença do caminho de trabalho topological design of survivable optical
para ambos os algoritmos, os resultados do algoritmo transport networks. IEEE/OSA Journal
de Suurballe foram iguais aos do algoritmo de Dijks- of Optical Communications and Networ-
tra no melhor caso, 21% maiores no pior caso, e 3% king, 3:17–26, 2011.
maiores na média entre todas as redes. Já para o ca- [Oli10] J. M. S. dos S. Oliveira. Protecção má-
minho de proteção, considerando somente as redes que xima de redes de telecomunicações. Mes-
encontraram caminho de proteção, os resultados do al- trado, Universidade de Aveiro, 2010.
goritmo de Dijkstra foram iguais aos do algoritmo de
Suurballe no melhor caso, 6% maiores no pior caso, [Pav11] Claunir Pavan. Dimensioning of Multi-
e 2% maiores na média entre todas as redes. Estes layer Optical Networks. Doutorado, Uni-
resultados estão resumidos na Tabela 1. versidade de Aveiro, Aveiro, Portugal,
hhd d
b i−hhw i hhs s
b i−hhw i hhs d
w i−hhw i hhd s
b i−hhb i
2011.
Caso hhd i hhs i hhd i hhs i
w w w b
Melhor 25% 23% 0% 0% [PMdRP10] C. Pavan, R. M. Morais, J. R. F. da Ro-
Médio 66% 68% 3% 2% cha, and A. N. Pinto. Generating realis-
tic optical transport network topologies.
Pior 149% 122% 21% 6%
IEEE/OSA Journal of Optical Commu-
Tabela 1: Resultados das observações dos gráficos das nications and Networking, 2:80–90, 2010.
Figuras 3 e 4. [RMdRP13] S. K. Routray, R. M. Morais, J. R. F.
da Rocha, and A. N. Pinto. Statistical
Devido à elevada quantidade de redes que não en- model for link lengths in optical transport
contraram um segundo caminho no roteamento pelo networks. IEEE/OSA Journal of Op-
algoritmo de Dijkstra, existem grandes chances de fu- tical Communications and Networking,
turos problemas na rede em momentos de falhas nas 5(7):762–773, 2013.
arestas. Portanto, em termos de robustez de rede, a
opção ideal seria o roteamento pelo algoritmo de Su-
urballe.
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 de-
finiçã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 investi-
gado em trabalhos futuros é a influência dos diferentes
pares de caminho obtidos pelo algoritmo de Suurballe
no processo de roteamento.
Referências
[Gir14] M. Girolimetto. Variáveis de mérito de
topologias de redes ópticas de transporte
de telecomunicações. Trabalho de conclu-
são de curso (graduação) - Universidade