An Algorithm For Fast-ReRoute Using Maximum Flow Evaluation and Backtracking

• Leon Okida UFPR http://orcid.org/0009-0008-1520-2111
• Elias P. Duarte Jr. UFPR https://orcid.org/0000-0002-8916-3302

DOI: https://doi.org/10.5753/wtf.2025.8854

Abstract

This paper presents the MaxFlowRouting algorithm for fault-tolerant routing. The algorithm proposes a Fast-ReRoute (FRR) strategy to deal with network failures. A router maintains a primary route and alternative routes to each destination. When a failure is detected in the primary route, an alternative route is employed to bypass the point where the failure occurs. The MaxFlowRouting algorithm uses maximum flow evaluation to compute routes that have more alternative route options that can be activated in case of failure. If there is no functional alternative route, the algorithm backtracks to the previous router. Experimental results obtained with simulation confirm that the MaxFlowRouting algorithm produces routes with up to 1.54 times more alternative routes per vertex.

Keywords: Group communication, Multicast and Routing, Fault Tolerance

References

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.