Bloom filters are used in many computing and networking applications where they provide a simple method to test if an element is present in a set. In some of those systems, reliability is a major concern and therefore the Bloom filters should be protected to ensure that errors do not affect the system behavior. One of the most common type of errors in electronic implementations of Bloom filters are radiation induced soft errors. Soft errors can corrupt the contents of a Bloom filter causing false positives and false negatives. Error Correction Codes (ECCs) can be used to protect the Bloom filter so that for example single bit errors are detected and corrected. However, the use of ECCs impacts the implementation area, power and delay. In this paper, a method to efficiently protect the contents of a Bloom filter is presented. The scheme exploits the different effects at the system level of false positives and false negatives to achieve effective error protection at lower cost than that of a traditional ECC. To illustrate the benefits of the proposed method, a case study is presented where the proposed implementation is compared with the use of a traditional Hamming ECC.

Reviriego, P., Pontarelli, S., Maestro, J., & Ottavi, M. (2015). A method to protect Bloom filters from soft errors. In IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems (DFTS), 2015 (pp.80-84). IEEE [10.1109/DFT.2015.7315140].

A method to protect Bloom filters from soft errors

PONTARELLI, SALVATORE;OTTAVI, MARCO
2015

Abstract

Bloom filters are used in many computing and networking applications where they provide a simple method to test if an element is present in a set. In some of those systems, reliability is a major concern and therefore the Bloom filters should be protected to ensure that errors do not affect the system behavior. One of the most common type of errors in electronic implementations of Bloom filters are radiation induced soft errors. Soft errors can corrupt the contents of a Bloom filter causing false positives and false negatives. Error Correction Codes (ECCs) can be used to protect the Bloom filter so that for example single bit errors are detected and corrected. However, the use of ECCs impacts the implementation area, power and delay. In this paper, a method to efficiently protect the contents of a Bloom filter is presented. The scheme exploits the different effects at the system level of false positives and false negatives to achieve effective error protection at lower cost than that of a traditional ECC. To illustrate the benefits of the proposed method, a case study is presented where the proposed implementation is compared with the use of a traditional Hamming ECC.
28th IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems, DFTS 2015
University of Massachusetts, usa
2015
Rilevanza internazionale
Settore ING-INF/01 - Elettronica
eng
Bloom filters; Error correction; Soft errors;
Intervento a convegno
Reviriego, P., Pontarelli, S., Maestro, J., & Ottavi, M. (2015). A method to protect Bloom filters from soft errors. In IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems (DFTS), 2015 (pp.80-84). IEEE [10.1109/DFT.2015.7315140].
Reviriego, P; Pontarelli, S; Maestro, J; Ottavi, M
File in questo prodotto:
File Dimensione Formato  
07315140.pdf

non disponibili

Licenza: Copyright dell'editore
Dimensione 189.45 kB
Formato Adobe PDF
189.45 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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: http://hdl.handle.net/2108/132016
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
social impact