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.