Two deterministic strategies for finding shortest pairs of edge-disjoint paths Marina Girolimetto1 , Marcia H. M. Paiva1 , Rodrigo S. Tessinari1 , Claunir Pavan2 , Fabio O. Lima3 1: LabTel – Laboratório de Telecomunicações, UFES, Vitória, Brazil, 29075-910; marina.girolimetto@aluno.ufes.br, marcia.paiva@ufes.br, stange@inf.ufes.br 2: Ciência da Computação, UFFS, Chapecó, Brazil, 89815-899; claunir.pavan@uffs.edu.br 3: Engenharia de Controle e Automação, IFES, Serra, Brazil, 29173-087; fabio.lima@ifes.edu.br cada par origem e destino da rede esteja interligado por pelo menos dois caminhos que não compartilhem Resumo nodos. Por sua vez, se há pelo menos dois caminhos que não compartilham enlaces interligando cada par From the observation that there may exist origem e destino, então a rede sobrevive a uma falha more than one shortest pair of edge-disjoint em um enlace. Neste trabalho, os dois caminhos defi- paths interconnecting a given pair of nodes in nidos para cada par origem e destino são denominados a network, and that the Suurballe and Tar- caminho de trabalho e caminho de proteção e as redes jan’s algorithm, which is usually used for fin- apresentadas são sobreviventes a falhas de enlace. ding them, is not deterministic, this work pro- poses two deterministic versions of that al- Há políticas de roteamento nas quais, para cada par gorithm, which can be used to exploit dif- de nodos origem-destino, há um caminho de trabalho ferent protection schemes for telecommunica- responsável por carregar o tráfego enquanto a rede es- tion networks. Given a network topology, the tiver operando em condições normais, e um caminho algorithms find what we call the more balan- de proteção responsável por carregar o tráfego em caso ced and the less balanced pairs of edge-disjoint de falhas ou manutenção da rede. Existem ainda polí- paths for each pair of nodes. ticas de roteamento nas quais o tráfego do nodo origem ao nodo destino é enviado simultaneamente pelos ca- 1 Introdução minhos de trabalho e de proteção, e apenas o sinal que chega no nodo destino com melhor qualidade é consi- Nas redes de telecomunicações, o projeto topológico derado [MBN99]. deve garantir uma rede confiável e tolerante a alguns As topologias de redes de telecomunicações podem tipos de falhas, como a ruptura de um enlace ou falta ser modeladas por grafos, onde os vértices representam de energia em um nodo [GP16]. Mecanismos de prote- os nodos, e as arestas representam os enlaces entre os ção contra falhas são importantes para evitar a suspen- nodos. Um grafo é dito conexo se e somente se existe são da transmissão de dados na ocorrência de algum pelo menos um caminho interligando cada par de no- problema na rede. Quando há uma falha em um nodo dos origem e destino. O comprimento de um caminho ou em um enlace, diversos pares de nodos origem e é a soma dos pesos das arestas que o constituem. A destino podem ser afetados. Por isso, as redes devem quantidade de arestas percorridas define o número de ser sobreviventes a falhas. Consideramos que uma rede saltos do caminho. Considerando arestas de peso uni- sobrevive a uma falha se houver caminhos alternativos tário, o comprimento do caminho equivale ao número para enviar o tráfego destes pares. de saltos. Quando existem pelo menos dois caminhos Para que uma rede sobreviva a uma falha em qual- disjuntos por arestas interligando qualquer par de no- quer um de seus nodos ou enlaces, é necessário que dos origem e destino da rede, o grafo é dito 2-aresta- Copyright c by the paper’s authors. Copying permitted for conexo [Net06]. Aqui, as topologias consideradas são private and academic purposes. 2-aresta-conexas com arestas de peso unitário. Para definir os caminhos de trabalho e de prote- origem e destino, ao ser executado mais de uma vez ção, geralmente é utilizado o algoritmo de roteamento dada uma mesma entrada, o algoritmo ST pode re- de Suurballe e Tarjan (ST ) [ST84], que tem a finali- tornar pares diferentes de caminhos de trabalho e de dade de encontrar, para cada par de nodos origem e proteção. No exemplo anterior, o algoritmo ST ora destino de uma rede, um par de caminhos disjuntos encontrava o par de caminhos de comprimentos 8 e 8, por arestas tais que a soma de seus comprimentos seja ora o par de caminhos de comprimentos 3 e 13. mínima. Estes pares de caminhos definem ciclos de A partir desta observação, e a fim de explorar dife- comprimento mínimo interligando cada par de nodos. rentes estratégias para a escolha dos caminhos de tra- Neste trabalho, consideramos o menor destes caminhos balho e proteção, este trabalho propõe duas versões como o caminho de trabalho e o outro como o caminho determinísticas do algoritmo ST para encontrar, para de proteção. uma determinada topologia, pares de caminhos de tra- Para certas topologias, pode haver mais de um ci- balho e de proteção mais balanceados e menos balan- clo de comprimento mínimo C interligando um deter- ceados para cada par de nodos. No melhor do nosso minado par de nodos, e estes ciclos podem ser des- conhecimento, este é o primeiro trabalho a propor ver- membrados em caminhos de trabalho e de proteção de sões determinísticas para o algoritmo de Suurballe e comprimentos diferentes. Por exemplo, dois ciclos de Tarjan. As versões propostas são denominadas: algo- comprimento mínimo C = 16 podem corresponder a: ritmo de Suurballe e Tarjan mais balanceado (Suur- i) um par mais balanceado, com um caminho de tra- balle and Tarjan More Balanced, ST M B) e algoritmo balho com 8 saltos e um caminho de proteção com 8 de Suurballe e Tarjan menos balanceado (Suurballe saltos (C = 8 + 8); ou ii) um par menos balanceado, and Tarjan Less Balanced, ST LB). com um caminho de trabalho com 3 saltos e um ca- minho de proteção com 13 saltos (C = 3 + 13). Esta 2 Algoritmo de Suurballe e Tarjan situação acontece em uma rede real, como será ilus- Seja G = (V, E) um grafo 2-aresta-conexo de ordem N , trado posteriormente, na Seção 4 (Figura 3). onde V = {v1 , v2 , . . . vN } é o conjunto de vértices e E A existência de mais de um ciclo de comprimento é o conjunto de arestas, de pesos unitários. Para cada mínimo associado a um mesmo par de nodos origem par origem e destino, o algoritmo ST encontra um ciclo e destino nos permite explorar diferentes estratégias de comprimento mínimo, C, contendo dois caminhos para a escolha dos caminhos de trabalho e de prote- disjuntos por arestas, a serem usados como caminhos ção, que podem ser utilizadas na definição de políticas de trabalho e de proteção. Isto é possível sempre que de roteamento apropriadas para redes com diferentes o grafo for 2-aresta-conexo, conforme o Teorema de tipos de serviço. Por exemplo, em caso de serviço sen- Menger [Net06]. O algoritmo ST segue os seguintes sível à latência, o ideal é que os caminhos de trabalho passos: e de proteção tenham o mesmo comprimento ou, pelo menos, que seus comprimentos sejam o mais próximo 1. Executa o algoritmo de Dijkstra, que encontra o possível. Neste caso, deve-se adotar a estratégia de menor caminho P1 interligando vi a vj ; buscar o que é denominado neste trabalho como o par 2. Os pesos das arestas de P1 são alterados. Esta de caminhos mais balanceado. Essa exigência costuma parte é conhecida como “transformação de custos” ocorrer quando não há, na prática, distinção entre ca- e ocorre da seguinte forma: minhos de trabalho e de proteção: ambos os sinais são  enviados simultaneamente para determinado destino   N , se (vi , vj ) ∈ P1  e apenas o de melhor qualidade é utilizado. Em ou- c + c − c ij i j , se (vi , vj ) 6∈ P1 tros cenários, o ideal é que o caminho de trabalho seja cij =   e (vj , vi ) 6∈ P1 o mais curto possível, pois o sinal é lançado somente  0 , se (vj , vi ) ∈ P1  nele, e o caminho de proteção é ativado apenas em caso de necessidade. Neste caso, a estratégia mais apropri- onde ci é o custo do nodo vi , e cij é o custo da ada seria buscar o que é chamado neste trabalho de aresta interligando vi a vj ; par de caminhos menos balanceado, de modo que o 3. Executa o algoritmo de Dijkstra mais uma vez, menor caminho do par seja utilizado como caminho com os pesos das arestas de P1 modificados e en- de trabalho e o maior fique como proteção. Ambas as contra o segundo menor caminho P2 ; estratégias de proteção são observadas em casos prá- ticos como, por exemplo, em redes ópticas de trans- 4. Por fim, identifica se P1 e P2 compartilham al- porte [MBN99]. guma aresta. Se sim, P1 e P2 são redefinidos como Em [GP16] foi observado que o algoritmo ST não é P10 e P20 , excluíndo-se a aresta em comum de am- determinístico, i.e., havendo mais de um ciclo de com- bos os caminhos. A redefinição dos caminhos é primento mínimo associado a um mesmo par de nodos apresentada com detalhes no exemplo a seguir. O par de caminhos resultante do algoritmo ST , seja duas versões determinísticas deste algoritmo, denomi- P1 e P2 ou P10 e P20 , é usado para definir os caminhos nadas: algoritmo de Suurballe e Tarjan mais balan- de trabalho e de proteção. Por exemplo, para o grafo ceado (Suurballe and Tarjan More Balanced, ST M B) ilustrado na Figura 1, considerando que o nodo origem e algoritmo de Suurballe e Tarjan menos balanceado é o nodo v1 , o nodo destino é o nodo v8 e o peso de (Suurballe and Tarjan Less Balanced, ST LB). cada aresta seja 1, o menor caminho P1 obtido com o O comprimento do caminho de trabalho no ST M B algoritmo de Dijkstra será: v1 ↔ v5 ↔ v4 ↔ v8 , com 3 será chamado de W + (Work Path More Balanced ) e o saltos. Em seguida, os pesos de todas as arestas de P1 comprimento do caminho de proteção será chamado de são alterados. Assim, é encontrado um segundo menor B + (Backup Path More Balanced ). De modo similar, caminho P2 com o algoritmo de Dijkstra, v1 ↔ v2 ↔ no ST LB, W − e B − representam os comprimentos v 3 ↔ v4 ↔ v5 ↔ v6 ↔ v7 ↔ v8 . dos caminhos de trabalho e de proteção. 3.1 Suurballe e Tarjan Mais Balanceado Para cada par origem e destino, o algoritmo ST M B encontra um ciclo de comprimento mínimo com pares de caminhos de trabalho e de proteção de comprimen- tos iguais ou com a mínima diferença possível em nú- mero de saltos entre eles. A sequência de passos do algoritmo é apresentada a seguir: Figura 1: Menor caminho (em linha tracejada azul) e 1. Executa o algoritmo ST padrão. A saída será, segundo menor caminho (em linha com ponto e traço para cada par de nodos origem e destino da to- rosa) do nodo origem v1 para o nodo destino v8 , obti- pologia, o tamanho do ciclo de comprimento mí- dos com o algoritmo de Dijkstra. nimo, C, interligando o nodo origem ao nodo des- tino; É identificado se P1 e P2 compartilham arestas. Neste exemplo, existe aresta compartilhada, v4 ↔ v5 , 2. Para cada par origem e destino, com base no ta- portanto P1 e P2 são redefinidos como P10 e P20 , respec- manho do ciclo de comprimento mínimo, as variá- tivamente. O caminho P10 será formado pelas arestas veis auxiliares R e S são definidas. O R definirá iniciais de P1 , até a última aresta antes da aresta com- o novo comprimento do W + e seu valor será o partilhada; seguidas pelas arestas finais de P2 , até a arrendondamento para baixo (piso) do resultado última aresta após a aresta compartilhada. A aresta da divisão de C por 2. O S definirá o novo com- compartilhada não é adicionada em nenhum dos ca- primento do B + e seu valor será o resultado da minhos P10 e P20 . O caminho P20 segue o mesmo es- subtração de C por R; quema, porém possui as arestas iniciais de P2 e fi- nais de P1 . Respectivamente, temos P10 dado por 3. Usando o algoritmo de Yen [Yen70], cria uma v1 ↔ v2 ↔ v3 ↔ v4 ↔ v8 , com 4 saltos, e P20 dado lista para armazenar todos os caminhos de com- por v1 ↔ v5 ↔ v6 ↔ v7 ↔ v8 , também com 4 saltos. primento R, para um dado par origem e destino; Ambos os caminhos são ilustrados na Figura 2. 4. Encontra um caminho de comprimento S, tam- bém utilizando o algoritmo de Yen; 5. Compara caminhos de comprimentos R e S. Para isso, é tomado um caminho da lista de compri- mento R e o caminho de comprimento S. É ve- rificado se há alguma aresta compartilhada entre eles. Se não há qualquer aresta compartilhada, os valores de R e S são atribuídos a W + e B + , res- pectivamente. Se há aresta compartilhada nesses Figura 2: Caminhos de trabalho e de proteção disjun- caminhos, testa-se o próximo caminho de compri- tos obtidos com o algoritmo ST do nodo origem v1 mento R da lista. Se nenhum caminho de compri- para o nodo destino v8 . mento R for disjunto ao de comprimento S, é veri- ficado se existe outro caminho de comprimento S. Em caso positivo, retorna ao Item 4. Caso contrá- 3 Algoritmos Propostos rio, R é decrementado e retorna ao Item 3. Este Como observado na Seção 1, o algoritmo de Suurballe procedimento será realizado até serem encontra- e Tarjan não é determinístico. Esta seção descreve dos dois caminhos disjuntos por arestas. Sempre que o algoritmo ST for bem sucedido, ou tados num conjunto de 40 redes de telecomunicações seja, se existirem na topologia dois caminhos disjuntos reais disponíveis em [RMdRP13]. por arestas para cada par origem-destino, os passos do algoritmo ST M B também serão. 5 Conclusão Neste trabalho foram propostos dois novos algoritmos 3.2 Suurballe e Tarjan Menos Balanceado que acrescentam previsibilidade ao algoritmo de Su- Para cada par origem e destino, o algoritmo ST LB en- urballe e Tarjan para obter, para cada par de nodos contra um ciclo de comprimento mínimo, C, com pares origem-destino de uma rede, caminhos de trabalho e de de caminhos de trabalho e de proteção em que o ca- proteção disjuntos por arestas tais que a soma de seus minho de trabalho tem o menor comprimento possível comprimentos seja mínima. Estas estratégias consis- em número de saltos. tem em encontrar os pares de caminhos mais e menos O algoritmo ST LB atua de maneira semelhante ao balanceados, o que permite explorar diferentes esque- algoritmo ST M B com duas pequenas diferenças: i) mas de proteção para aplicações em diferentes cená- para cada par origem e destino, o R inicia com o com- rios. Como trabalhos futuros, os algoritmos propostos primento do menor caminho encontrado pelo algoritmo serão testados em um conjunto de 40 topologias de de Dijkstra, para tentar obter o menor caminho de redes reais de telecomunicações. trabalho possível; e ii) quando não forem encontrados dois caminhos disjuntos por arestas de comprimentos Referências R e S, o R é incrementado. Assim como no ST M B, estes passos serão bem sucedidos sempre que o algo- [GP16] M. Girolimetto and C. Pavan. The ritmo ST padrão obtiver sucesso. average number of hops for working and backup paths in telecommunication networks. SSN 2016 Spring School on 4 Resultados Networks, 1727, 2016. Session 2: Posters. Os resultados dos algoritmos propostos são apresen- tados para a rede “Arnes”, ilustrada na Figura 3, que [MBN99] J. Manchester, P. Bonenfant, and tem 17 nodos e 20 arestas. C. Newton. The evolution of transport network survivability. IEEE Communi- cations Magazine, 37(8):44–51, 1999. [Net06] P. O. Boaventura Netto. Grafos: Teo- ria, Modelos, Algoritmos. Edgard Blu- cher, São Paulo, 4th edition, 2006. [RMdRP13] S. K. Routray, R. M. Morais, J. R. F. da Rocha, and A. N. Pinto. Statistical model for link lengths in optical transport networks. IEEE/OSA J. Opt. Commun. Figura 3: Caminhos de trabalho e de proteção defini- Netw., 5(7):762–773, 2013. dos pelos algoritmos ST M B e ST LB na rede “Arnes” para o par de nodos origem v8 e destino v17 . [ST84] J. W. Suurballe and R. E. Tarjan. A Dado o par de origem v8 e destino v17 , para o qual quick method for finding shortest pairs tem-se C = 16 arestas, a Figura 3 apresenta os cami- of disjoint paths. Networks, 14:325–336, nhos de trabalho e de proteção obtidos pelo ST M B 1984. e pelo ST LB. Tanto o caminho de trabalho como o [TPCG16] R. S. Tessinari, B. Puype, D. Colle, and de proteção obtidos pelo ST M B tem 8 saltos, ou seja, A. S. Garcia. ElasticO++ : An elas- temos W + = B + = 8. No ST LB, o caminho de tra- tic optical network simulation framework balho obtido tem 3 saltos, i.e., W − = 3, enquanto o de for OMNeT++. Optical Switching and proteção tem 13 saltos, i.e., B − = 13. Este é um dos Networking, 22:95–104, 2016. pares de nodos origem-destino para os quais ocorre a maior diferença entre o ST M B e o ST LB. O W + tem [Yen70] Jin Y. Yen. An algorithm for fin- 5 saltos a mais que o W − e consequentemente o B − ding shortest routes from all source no- tem 5 saltos a mais que o B + . des to a given destination in general As versões ST LB e ST M B serão implementadas networks. Quarterly of Applied Mathe- na linguagem C + +, utilizando o framework Elas- matics, 27:526–530, 1970. ticO++ [TPCG16], e ambos os algoritmos serão tes-