A lightweight algorithm for traffic filtering over sliding windows

Abstract

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

Postprint (published version)