Um Algoritmo para Fast-ReRoute Utilizando Avaliação de Fluxo Máximo e Backtracking
Resumo
Este trabalho apresenta o algoritmo MaxFlowRouting para o roteamento tolerante a falhas. O algoritmo propõe uma estratégia de Fast-ReRoute (FRR) para lidar com falhas na rede. Um roteador mantém uma rota primária e rotas alternativas para cada destino. Quando uma falha é detectada na rota primária, uma rota alternativa é empregada para contornar o ponto em que ocorre a falha. O algoritmo MaxFlowRouting utiliza a avaliação de fluxo máximo para computar rotas que possuem mais opções de rotas alternativas que possam ser ativadas em caso de falha. Se não há rota alternativa funcional, o algoritmo faz backtracking para o roteador anterior. Resultados experimentais obtidos com simulação confirmam que o algoritmo MaxFlowRouting produz rotas com até 1,54 vezes mais rotas alternativas por vértice.
Palavras-chave:
Comunicação em Grupo, Multicast e Roteamento, Tolerância a Falhas
Referências
Bischof, Z. S., Pitcher, K., Carisimo, E., Meng, A., Bezerra Nunes, R., Padmanabhan, R., Roberts, M. E., Snoeren, A. C., and Dainotti, A. (2023). Destination unreachable: Characterizing internet outages and shutdowns. In ACM SIGCOMM, pages 608–621.
Cohen, J., Duarte Jr, E., and Schroeder, J. (2011a). Connectivity criteria for ranking network nodes. In Complex Networks: Second International Workshop (CompleNet), pages 35–45. Springer.
Cohen, J., Rodrigues, L., and Duarte Jr, E. (2012). A parallel implementation of Gomory-Hu’s cut tree algorithm. In 2012 IEEE 24th International Symposium on Computer Architecture and High Performance Computing, pages 124–131. IEEE.
Cohen, J., Rodrigues, L., and Duarte Jr, E. (2017). Parallel cut tree algorithms. Journal of Parallel and Distributed Computing, 109:1–14.
Cohen, J., Rodrigues, L., Silva, F., Carmo, R., Guedes, A. L., and Duarte, E. (2011b). Parallel implementations of Gusfield’s cut tree algorithm. In The 11th ICA3PP, pages 258–269. Springer.
Cormen, T., Leiserson, C., Rivest, R., and Stein, C. (2022). Introduction to Algorithms, fourth edition. MIT Press.
Duarte, E. and Musicante, M. A. (1999). Formal specification of SNMP MIBs using action semantics: The routing proxy case study. In The 6th IFIP/IEEE International Symposium on Integrated Network Management (IM), pages 417–430. IEEE.
Duarte Jr, E., Garrett, T., Bona, L., Carmo, R., and Züge, A. (2010). Finding stable cliques of PlanetLab nodes. In 2010 IEEE/IFIP International Conference on Dependable Systems & Networks (DSN), pages 317–322. IEEE.
Duarte Jr, E., Santini, R., and Cohen, J. (2004). Delivering packets during the routing convergence latency interval through highly connected detours. In International Conference on Dependable Systems and Networks (DSN), pages 495–504. IEEE.
Filsfils, C., Francois, P., et al. (2012). Loop-free alternate (LFA) applicability in service provider (SP) networks. RFC 6571.
GÉANT (2025). GÉANT network. [link]. Acessado em 28/03/2025.
Hagberg, A., Schult, D., and Swart, P. (2008). Exploring network structure, dynamics, and function using NetworkX. In 7th Python in Science Conference, pages 11–15.
Internet2 (2025). Layer 1 service. [link]. Acessado em 28/03/2025.
Liu, K., Fan, W., Xiao, F., Mao, H., Huang, H., and Zhao, Y. (2024). Secure paths based trustworthy fault-tolerant routing in data center networks. Concurrency and Computation: Practice and Experience, 36(23):e8229.
Maske, C., Cohen, J., and Duarte Jr, E. (2020). Speeding up the Gomory-Hu parallel cut tree algorithm with efficient graph contractions. Algorithmica, 82(6):1601–1615.
Nassu, B., Nanya, T., and Duarte Jr, E. (2007). Topology discovery in dynamic and decentralized networks with mobile agents and swarm intelligence. In The 7th Int. Conf. Intelligent Systems Design and Applications (ISDA), pages 685–690. IEEE.
Okida, L., Maverson, E., and Duarte Jr, E. (2024). Fast reroute with highly connected routes based on maximum flow evaluation. arXiv:2410.10528.
Pan, P. et al. (2005). Fast reroute extensions to RSVP-TE for LSP tunnels. RFC 4090.
RNP (2025). Ipê network. [link]. Acessado em 28/03/2025.
Schroeder, J. and Duarte Jr, E. (2007). Fault-tolerant dynamic routing based on maximum flow evaluation. In Latin-American Symposium on Dependable Computing, pages 7–24. Springer.
Schroeder, J., Guedes, A., and Duarte Jr, E. (2004). Computing the minimum cut and maximum flow of undirected graphs. Technical report, Federal University of Paraná.
Shand, M. and Bryant, S. (2010). IP fast reroute framework. RFC 5714.
Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393(6684):440–442.
WIDE Project (2025). WIDE internet official site. [link]. Acessado em 28/03/2025.
Cohen, J., Duarte Jr, E., and Schroeder, J. (2011a). Connectivity criteria for ranking network nodes. In Complex Networks: Second International Workshop (CompleNet), pages 35–45. Springer.
Cohen, J., Rodrigues, L., and Duarte Jr, E. (2012). A parallel implementation of Gomory-Hu’s cut tree algorithm. In 2012 IEEE 24th International Symposium on Computer Architecture and High Performance Computing, pages 124–131. IEEE.
Cohen, J., Rodrigues, L., and Duarte Jr, E. (2017). Parallel cut tree algorithms. Journal of Parallel and Distributed Computing, 109:1–14.
Cohen, J., Rodrigues, L., Silva, F., Carmo, R., Guedes, A. L., and Duarte, E. (2011b). Parallel implementations of Gusfield’s cut tree algorithm. In The 11th ICA3PP, pages 258–269. Springer.
Cormen, T., Leiserson, C., Rivest, R., and Stein, C. (2022). Introduction to Algorithms, fourth edition. MIT Press.
Duarte, E. and Musicante, M. A. (1999). Formal specification of SNMP MIBs using action semantics: The routing proxy case study. In The 6th IFIP/IEEE International Symposium on Integrated Network Management (IM), pages 417–430. IEEE.
Duarte Jr, E., Garrett, T., Bona, L., Carmo, R., and Züge, A. (2010). Finding stable cliques of PlanetLab nodes. In 2010 IEEE/IFIP International Conference on Dependable Systems & Networks (DSN), pages 317–322. IEEE.
Duarte Jr, E., Santini, R., and Cohen, J. (2004). Delivering packets during the routing convergence latency interval through highly connected detours. In International Conference on Dependable Systems and Networks (DSN), pages 495–504. IEEE.
Filsfils, C., Francois, P., et al. (2012). Loop-free alternate (LFA) applicability in service provider (SP) networks. RFC 6571.
GÉANT (2025). GÉANT network. [link]. Acessado em 28/03/2025.
Hagberg, A., Schult, D., and Swart, P. (2008). Exploring network structure, dynamics, and function using NetworkX. In 7th Python in Science Conference, pages 11–15.
Internet2 (2025). Layer 1 service. [link]. Acessado em 28/03/2025.
Liu, K., Fan, W., Xiao, F., Mao, H., Huang, H., and Zhao, Y. (2024). Secure paths based trustworthy fault-tolerant routing in data center networks. Concurrency and Computation: Practice and Experience, 36(23):e8229.
Maske, C., Cohen, J., and Duarte Jr, E. (2020). Speeding up the Gomory-Hu parallel cut tree algorithm with efficient graph contractions. Algorithmica, 82(6):1601–1615.
Nassu, B., Nanya, T., and Duarte Jr, E. (2007). Topology discovery in dynamic and decentralized networks with mobile agents and swarm intelligence. In The 7th Int. Conf. Intelligent Systems Design and Applications (ISDA), pages 685–690. IEEE.
Okida, L., Maverson, E., and Duarte Jr, E. (2024). Fast reroute with highly connected routes based on maximum flow evaluation. arXiv:2410.10528.
Pan, P. et al. (2005). Fast reroute extensions to RSVP-TE for LSP tunnels. RFC 4090.
RNP (2025). Ipê network. [link]. Acessado em 28/03/2025.
Schroeder, J. and Duarte Jr, E. (2007). Fault-tolerant dynamic routing based on maximum flow evaluation. In Latin-American Symposium on Dependable Computing, pages 7–24. Springer.
Schroeder, J., Guedes, A., and Duarte Jr, E. (2004). Computing the minimum cut and maximum flow of undirected graphs. Technical report, Federal University of Paraná.
Shand, M. and Bryant, S. (2010). IP fast reroute framework. RFC 5714.
Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393(6684):440–442.
WIDE Project (2025). WIDE internet official site. [link]. Acessado em 28/03/2025.
Publicado
19/05/2025
Como Citar
OKIDA, Leon; DUARTE JR., Elias P..
Um Algoritmo para Fast-ReRoute Utilizando Avaliação de Fluxo Máximo e Backtracking. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 25. , 2025, Natal/RN.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 99-112.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2025.8854.
