Recently great attention has been given to point-of-failure swap rerouting, an efficient technique for routing in the presence of transient failures. According to this technique, a message follows the normal routing table information unless the next hop has failed; in this case, it is redirected towards a precomputed link, called swap; once this link has been crossed, normal routing is resumed. The choice of the swap edge is done according to some optimization criteria on the resulting new route. The amount of precomputed information required in addition to the routing table is rather small: a single link per each destination. Several efficient serial algorithms have been presented to compute this information for several optimization criteria (Fdist, Fsum, Fincr, Fmax). Only the algorithm corresponding to Fdist has been efficiently implemented in a distributed environment, while for the other optimization criteria no distributed solution has been devised yet. In this paper we present protocols, based on a new strategy, that allow the efficient distributed computation of all the optimal swap edges under Fsum, Fincr, Fmax. Although considerably more difficult than Fdist, these problems can be solved with the same cost. In systems allowing long messages, we develop solution protocols based on the same strategy that use only O (n) messages without increasing the total amount of transmitted data items.

Computing All The Best Swap Edges Distributively

PAGLI, LINDA;PRENCIPE, GIUSEPPE;
2008

Abstract

Recently great attention has been given to point-of-failure swap rerouting, an efficient technique for routing in the presence of transient failures. According to this technique, a message follows the normal routing table information unless the next hop has failed; in this case, it is redirected towards a precomputed link, called swap; once this link has been crossed, normal routing is resumed. The choice of the swap edge is done according to some optimization criteria on the resulting new route. The amount of precomputed information required in addition to the routing table is rather small: a single link per each destination. Several efficient serial algorithms have been presented to compute this information for several optimization criteria (Fdist, Fsum, Fincr, Fmax). Only the algorithm corresponding to Fdist has been efficiently implemented in a distributed environment, while for the other optimization criteria no distributed solution has been devised yet. In this paper we present protocols, based on a new strategy, that allow the efficient distributed computation of all the optimal swap edges under Fsum, Fincr, Fmax. Although considerably more difficult than Fdist, these problems can be solved with the same cost. In systems allowing long messages, we develop solution protocols based on the same strategy that use only O (n) messages without increasing the total amount of transmitted data items.
Flocchini, Paola; Pagli, Linda; Prencipe, Giuseppe; Santoro, Nicola; Widmayer, Peter
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/11568/196840
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 9
social impact