The resiliency of a network is its ability to remain effectively functioning also when any of its nodes or links fails. However, to reduce operational and set-up costs, a network should be small in size, and this conflicts with the requirement of being resilient. In this paper we address this trade-off for the prominent case of the broadcasting routing scheme, and we build efficient (i.e., sparse and fast) fault-tolerant approximate shortest-path trees, for both the edge and vertex single-failure case. In particular, for an n-vertex non-negatively weighted graph, and for any constant ε > 0, we design two structures of size TeX which guarantee (1 + ε)-stretched paths from the selected source also in the presence of an edge/vertex failure. This favorably compares with the currently best known solutions, which are for the edge-failure case of size O(n) and stretch factor 3, and for the vertex-failure case of size O(n logn) and stretch factor 3. Moreover, we also focus on the unweighted case, and we prove that an ordinary (α,β)-spanner can be slightly augmented in order to build efficient fault-tolerant approximate breadth-first-search trees.

Fault-tolerant approximate shortest-path trees / Bilò, Davide; Guala, L; Leucci, S; Proietti, G.. - 8738:(2014), pp. 137-148. (Intervento presentato al convegno European Symposium on Algorithms (ESA 2014) tenutosi a Wrocław, Poland nel 7-10 September 2014) [10.1007/978-3-662-44777-2_12].

Fault-tolerant approximate shortest-path trees

BILÒ, Davide;
2014-01-01

Abstract

The resiliency of a network is its ability to remain effectively functioning also when any of its nodes or links fails. However, to reduce operational and set-up costs, a network should be small in size, and this conflicts with the requirement of being resilient. In this paper we address this trade-off for the prominent case of the broadcasting routing scheme, and we build efficient (i.e., sparse and fast) fault-tolerant approximate shortest-path trees, for both the edge and vertex single-failure case. In particular, for an n-vertex non-negatively weighted graph, and for any constant ε > 0, we design two structures of size TeX which guarantee (1 + ε)-stretched paths from the selected source also in the presence of an edge/vertex failure. This favorably compares with the currently best known solutions, which are for the edge-failure case of size O(n) and stretch factor 3, and for the vertex-failure case of size O(n logn) and stretch factor 3. Moreover, we also focus on the unweighted case, and we prove that an ordinary (α,β)-spanner can be slightly augmented in order to build efficient fault-tolerant approximate breadth-first-search trees.
2014
978-3-662-44776-5
Fault-tolerant approximate shortest-path trees / Bilò, Davide; Guala, L; Leucci, S; Proietti, G.. - 8738:(2014), pp. 137-148. (Intervento presentato al convegno European Symposium on Algorithms (ESA 2014) tenutosi a Wrocław, Poland nel 7-10 September 2014) [10.1007/978-3-662-44777-2_12].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11388/50459
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 8
social impact