A lightweight algorithm for traffic filtering over sliding windows

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.