Um Algoritmo para Fast-ReRoute com Backtracking e Baseado em Avaliação de Fluxo Máximo
DOI:
https://doi.org/10.5753/reic.2025.6081Keywords:
Roteamento, Tolerância a Falhas, Fast-ReRoute (FRR), Internet, Avaliação de Fluxo MáximoAbstract
Este trabalho apresenta o algoritmo MaxFlowRouting, para Fast-ReRoute (FRR) com backtracking. Para cada destino, o roteador mantém rotas alternativas além da rota principal, que são utlizadas quando a rota principal falha. O algoritmo utiliza a avaliação de fluxo máximo para computar rotas que possuem mais opções de alternativas. Se não há rota alternativa funcional, o algoritmo faz backtracking para o roteador anterior. Foram obtidos resultados extensivos de simulação para diversas topologias e métricas. Este artigo inclui resultados para o número de rotas alternativas e quantidade de backtracks feitos em grafos de mundo pequeno, grafos de conexão preferencial e quatro topologias da Internet: RNP (Brasil), Internet2 (EUA), Géant (Europe) and Wide (Japan).
Downloads
Referências
Albert, R. and Barabási, A. (2002). Statistical mechanics of complex networks. Reviews of Modern Physics, 74(1):47. DOI: 10.1103/RevModPhys.74.47.
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 Proceedings of the ACM SIGCOMM 2023 Conference, pages 608–621. DOI: 10.1145/3603269.3604883.
Chiesa, M., Kamisiński, A., Rak, J., Rétvári, G., and Schmid, S. (2021). A survey of fast-recovery mechanisms in packet-switched networks. IEEE Communications Surveys & Tutorials, 23(2):1253–1301. DOI: 10.1109/COMST.2021.3063980.
Cohen, J., Duarte Jr, E., and Schroeder, J. (2011). Connectivity criteria for ranking network nodes. In Complex Networks: Second International Workshop, CompleNet 2010, pages 35–45. Springer. DOI: 10.1007/978-3-642-25501-4_4.
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. DOI: 10.1109/SBAC-PAD.2012.37.
Cohen, J., Rodrigues, L., and Duarte Jr, E. (2017). Parallel cut tree algorithms. Journal of Parallel and Distributed Computing, 109:1–14. DOI: 10.1016/j.jpdc.2017.04.007.
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 MIB’s using action semantics: The routing proxy case study. In The 6th IFIP/IEEE International Symposium on Integrated Network Management (IM), pages 417–430. DOI: 10.1109/INM.1999.770698.
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. DOI: 10.1109/DSN.2010.5544300.
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), 2004, pages 495–504. IEEE. DOI: 10.1109/DSN.2004.1311919.
Erdos, P. and Rényi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17–60. DOI: 10.1515/9781400841356.38.
Filsfils, C., Francois, P., Shand, M., Decraene, B., Uttaro, J., Leymann, N., and Horneffer, M. (2012). Loop-free alternate (LFA) applicability in service provider (SP) networks. RFC 6571. DOI: 10.17487/RFC6571.
GÉANT (2025). GÉANT network. Disponível em: [link]. Acessado em 28/03/2025.
Hagberg, A., Schult, D., and Swart, P. (2008). Exploring network structure, dynamics, and function using NetworkX. In Proceedings of the 7th Python in Science Conference, pages 11–15, Pasadena, CA, USA. DOI: 10.25080/TCWV9851.
Internet2 (2025). Layer 1 service. Disponível em: [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. DOI: 10.1002/cpe.8229.
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. DOI: 10.1007/s00453-019-00658-6.
Nassu, B., Nanya, T., and Duarte Jr, E. (2007). Topology discovery in dynamic and decentralized networks with mobile agents and swarm intelligence. In Seventh International Conference on Intelligent Systems Design and Applications (ISDA 2007), pages 685–690. IEEE. DOI: 10.1109/ISDA.2007.13.
Okida, L. (2024). Um Algoritmo Para Fast-ReRoute Utilizando Avaliação de Fluxo Máximo e Backtracking. Trabalho de Conclusão de Curso (TCC), BCC, UFPR. DOI: 10.13140/RG.2.2.28994.08646.
Pan, P., Swallow, G., and Atlas, A. (2005). Fast reroute extensions to RSVP-TE for LSP tunnels. RFC 4090. DOI: 10.17487/RFC4090.
RNP (2025). Ipê network. Disponível em: [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. DOI: 10.1007/978-3-540-75294-3_3.
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á. Disponível em: [link].
Shand, M. and Bryant, S. (2010). IP fast reroute framework. RFC 5714. DOI: 10.17487/RFC5714.
Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393(6684):440–442. DOI: 10.1038/30918.
WIDE Project (2025). WIDE internet official site. Disponível em: [link]. Acessado em 28/03/2025.
Downloads
Published
Como Citar
Issue
Section
Licença
Copyright (c) 2025 Os autores
Este trabalho está licenciado sob uma licença Creative Commons Attribution 4.0 International License.
