A Fast-ReRoute Algorithm with Backtracking and Based on Maximum Flow Evaluation
DOI:
https://doi.org/10.5753/reic.2025.6081Keywords:
Routing, Fault Tolerance, Fast-ReRoute (FRR), Internet, Maximum Flow EvaluationAbstract
This paper presents the MaxFlowRouting algorithm, a Fast-ReRoute (FRR) strategy with backtracking. For each destination, a router maintains alternative routes alongside the primary route. FRR actives an alternative route, after the primary route fails. The MaxFlowRouting algorithm employs maximum flow evaluation to compute routes that have more alternative route options that can be activated in case of failure. If there is no working alternative route, the algorithm backtracks to the previous router. Extensive simulation results have been computed for multiple topologies and metrics. This paper presents an evaluation of the number of alternative routes and the number of backtracks for small world graphs, preferential attachment graphs, and four Internet topologies: RNP (Brazil), Internet2 (USA), Géant (Europe) and Wide (Japan).
Downloads
References
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
How to Cite
Issue
Section
License
Copyright (c) 2025 The authors
This work is licensed under a Creative Commons Attribution 4.0 International License.
