Local Fast Rerouting with Low Congestion: A Randomized Approach
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913585550065664 |
|---|---|
| author | Bankhamer, Gregor Elsässer, Robert Schmid, Stefan |
| author_facet | Bankhamer, Gregor Elsässer, Robert Schmid, Stefan |
| contents | Most modern communication networks include fast rerouting mechanisms, implemented entirely in the data plane, to quickly recover connectivity after link failures. By relying on local failure information only, these data plane mechanisms provide very fast reaction times, but at the same time introduce an algorithmic challenge in case of multiple link failures: failover routes need to be robust to additional but locally unknown failures downstream. This paper presents local fast rerouting algorithms which not only provide a high degree of resilience against multiple link failures, but also ensure a low congestion on the resulting failover paths. We consider a randomized approach and focus on networks which are highly connected before the failures occur. Our main contribution are three simple algorithms which come with provable guarantees and provide interesting resilience-load tradeoffs, significantly outperforming any deterministic fast rerouting algorithm with high probability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2009_01497 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Local Fast Rerouting with Low Congestion: A Randomized Approach Bankhamer, Gregor Elsässer, Robert Schmid, Stefan Networking and Internet Architecture Distributed, Parallel, and Cluster Computing Most modern communication networks include fast rerouting mechanisms, implemented entirely in the data plane, to quickly recover connectivity after link failures. By relying on local failure information only, these data plane mechanisms provide very fast reaction times, but at the same time introduce an algorithmic challenge in case of multiple link failures: failover routes need to be robust to additional but locally unknown failures downstream. This paper presents local fast rerouting algorithms which not only provide a high degree of resilience against multiple link failures, but also ensure a low congestion on the resulting failover paths. We consider a randomized approach and focus on networks which are highly connected before the failures occur. Our main contribution are three simple algorithms which come with provable guarantees and provide interesting resilience-load tradeoffs, significantly outperforming any deterministic fast rerouting algorithm with high probability. |
| title | Local Fast Rerouting with Low Congestion: A Randomized Approach |
| topic | Networking and Internet Architecture Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2009.01497 |