To access the full text documents, please follow this link:

A lightweight algorithm for traffic filtering over sliding windows
Sanjuàs Cuxart, Josep; Barlet Ros, Pere; Solé Pareta, Josep; Andriuzzi, Gabriella
Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors; Universitat Politècnica de Catalunya. CBA - Sistemes de Comunicacions de Banda Ampla
The problem of testing whether a packet belongs to a set of filtered addresses has been traditionally addressed using Bloom filters. They have a small memory footprint and require few memory accesses per query and insertion, while presenting a small probability of false positive. The problem of automatic eviction of filtered addresses after a pre-configured time window is more challenging, since it requires tracking insertion times for later removal. This has been achieved in the literature by replacing the Bloom filter's vector of bits for a vector of timestamps. This approach precisely expires old items from the filter, but has a large memory footprint. We present a novel Bloom filter based data structure that features approximate information expiration. This small extra source of error allows for a more compact filter representation, thus becoming more suitable to fit in more expensive, faster memory. Additionally, our data structure is more flexible in that it allows for balancing the trade-off between filtering and expiration accuracy. Our experiments show that this method can obtain up to orders of magnitude higher overall accuracy than the time-stamp approach using the same amount of memory.
Peer Reviewed
Àrees temàtiques de la UPC::Enginyeria de la telecomunicació::Telemàtica i xarxes d'ordinadors::Xarxes de banda ampla
Computer networks -- Management
Broadband communication systems
Data structures
Maintenance engineering
Memory management
Radiation detectors
Time measurement
Xarxes de comunicacions -- Gestió
Telecomunicació de banda ampla, Sistemes de
Attribution-NonCommercial-NoDerivs 3.0 Spain

Show full item record

Related documents

Other documents of the same author

Mikians, Jakub; Barlet Ros, Pere; Sanjuàs Cuxart, Josep; Solé Pareta, Josep
Barlet Ros, Pere; Sanjuàs Cuxart, Josep; Solé Pareta, Josep; Gandía, Maria Isabel; Malagón, Chelo
Sanjuàs Cuxart, Josep; Barlet Ros, Pere; Duffield, Nick; Kompella, Ramana
Sanjuàs Cuxart, Josep; Barlet Ros, Pere; Duffield, Nick; Kompella, Ramana
Paredes Oliva, Ignasi; Barlet Ros, Pere; Solé Pareta, Josep