Fast Reroute with Highly Connected Routes Based on Maximum Flow Evaluation
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916438131867648 |
|---|---|
| author | Okida, Leon Schuze-Rosa, Maverson E. Duarte Jr, Elias P. |
| author_facet | Okida, Leon Schuze-Rosa, Maverson E. Duarte Jr, Elias P. |
| contents | Fault-tolerant routing allows the selection of alternative routes to the destination after the route being used fails. Fast Reroute (FRR) is a proactive strategy through which the protocol pre-configures backup routes that are activated when needed. In this work, we propose the MaxFlowRouting algorithm that employs maximum flow evaluation as well as the route size to select routes that are highly connected. The main advantage of the proposed algorithm is that if any component of such a route fails, there are more alternative paths to the destination in comparison with the route computed with Dijkstra's shortest path algorithm. Simulation results are presented in which we compare the two algorithms (Dijkstra's and MaxFlowRouting) for multiple different random graphs (including Erdos-Renyi, Barábasi-Albert, and Watts-Strogatz) and also for the topologies of some of the most important Internet backbones of the U.S.A., Europe, Brazil, and Japan: Internet2, Geant, RNP, and Wide. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_10528 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast Reroute with Highly Connected Routes Based on Maximum Flow Evaluation Okida, Leon Schuze-Rosa, Maverson E. Duarte Jr, Elias P. Networking and Internet Architecture Discrete Mathematics Fault-tolerant routing allows the selection of alternative routes to the destination after the route being used fails. Fast Reroute (FRR) is a proactive strategy through which the protocol pre-configures backup routes that are activated when needed. In this work, we propose the MaxFlowRouting algorithm that employs maximum flow evaluation as well as the route size to select routes that are highly connected. The main advantage of the proposed algorithm is that if any component of such a route fails, there are more alternative paths to the destination in comparison with the route computed with Dijkstra's shortest path algorithm. Simulation results are presented in which we compare the two algorithms (Dijkstra's and MaxFlowRouting) for multiple different random graphs (including Erdos-Renyi, Barábasi-Albert, and Watts-Strogatz) and also for the topologies of some of the most important Internet backbones of the U.S.A., Europe, Brazil, and Japan: Internet2, Geant, RNP, and Wide. |
| title | Fast Reroute with Highly Connected Routes Based on Maximum Flow Evaluation |
| topic | Networking and Internet Architecture Discrete Mathematics |
| url | https://arxiv.org/abs/2410.10528 |