On the Price of Locality in Static Fast Rerouting

Klaus Tycho Foerster, Juho Hirvonen, Yvonne Anne Pignolet, Stefan Schmid, Gilles Tredan

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

2 Sitaatiot (Scopus)

Abstrakti

Modern communication networks feature fully decen-tralized flow rerouting mechanisms which allow them to quickly react to link failures. This paper revisits the fundamental algorithmic problem underlying such local fast rerouting mechanisms. Is it possible to achieve perfect resilience, i.e., to define local routing tables which preserve connectivity as long as the underlying network is still connected? Feigenbaum et al. [1] and Foerster et al. [2] showed that, unfortunately, it is impossible in general.This paper charts a more complete landscape of the feasibility of perfect resilience. We first show a perhaps surprisingly large price of locality in static fast rerouting mechanisms: even when source and destination remain connected by a linear number of link-disjoint paths after link failures, local rerouting algorithms cannot find any of them which leads to a disconnection on the routing level. This motivates us to study resilience in graphs which exclude certain dense minors, such as cliques or a complete bipartite graphs, and in particular, provide characterizations of the possibility of perfect resilience in different routing models. We provide further insights into the price of locality by showing impossibility results for few failures and investigate perfect resilience on Topology Zoo networks.

AlkuperäiskieliEnglanti
OtsikkoProceedings - 52nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2022
KustantajaIEEE
Sivut215-226
Sivumäärä12
ISBN (elektroninen)978-1-6654-1693-1
DOI - pysyväislinkit
TilaJulkaistu - 2022
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaAnnual IEEE/IFIP International Conference on Dependable Systems and Networks - Baltimore, Yhdysvallat
Kesto: 27 kesäk. 202230 kesäk. 2022
Konferenssinumero: 52

Julkaisusarja

NimiProceedings : International Conference on Dependable Systems and Networks
ISSN (painettu)1530-0889
ISSN (elektroninen)2158-3927

Conference

ConferenceAnnual IEEE/IFIP International Conference on Dependable Systems and Networks
LyhennettäDSN
Maa/AlueYhdysvallat
KaupunkiBaltimore
Ajanjakso27/06/202230/06/2022

Sormenjälki

Sukella tutkimusaiheisiin 'On the Price of Locality in Static Fast Rerouting'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä