Papers
Network Applications of Bloom Filters: A Survey
Andrei Broder, Michael Mitzenmacher · Internet Mathematics, Vol. 1, No. 4, pp. 485-509 (2004), 2004
The problem and the principle of the Bloom filter
The paper is a survey: it brings together, in a unified way, how Bloom filters have been used and modified in networking problems. A Bloom filter is a space-efficient randomized data structure that represents a set to answer membership queries. The price is accepting false positives, but the authors note that the space savings often outweigh this when the error probability is controlled. The structure is a vector of m bits, initially all 0, plus k independent hash functions that map each item to positions in the vector. To insert an element, you compute the k positions and set those bits to 1. To query, you compute the item's k positions: if any bit is 0, the item is certainly not in the set; if all are 1, it is assumed to be there, although it could be a false positive. Therefore there are no false negatives. The theme that unites the applications is that the filter offers a succinct way to represent a list or set that, in full, would take up too much space in the network. The authors sum this up in the so-called Bloom filter principle: wherever a list or set is used and space is precious, consider a Bloom filter if the effect of false positives can be mitigated. The paper groups the applications into four categories, which the authors themselves admit are loose and not exhaustive: collaboration in overlay and peer-to-peer networks, resource routing, packet routing, and measurement.
The math: false positive rate, optimal k, and lower bound
After inserting the n elements, the probability that a specific bit is still 0 is approximately e raised to the power of minus kn/m. The false positive rate is then approximately (1 minus that quantity) raised to the power of k. There are two opposing forces: more hash functions give more chances of finding a 0 bit for an item outside the set, but leave fewer bits at 0 in the vector. Given m and n, the number of functions that minimizes the rate is k equal to ln 2 times m/n; at that point, half of the bits are 0 and the rate is (1/2) raised to the power of k, about (0.6185) raised to the power of m/n. In practice k must be an integer, and a slightly smaller k may be preferred because it requires computing fewer hashes. The paper gives as an example that, with m equal to 8n, the false positive rate is just above 0.02. The authors also derive a lower bound: any representation that allows false positives for a fraction of at most ε of the universe, with no false negatives, needs essentially n log2(1/ε) bits, when n is small relative to the size of the universe (the practical case). By comparison, the optimal Bloom filter needs a factor of log2 e, about 1.44, more than this asymptotic bound. Schemes with fewer bits exist, such as those based on perfect hashing, but the paper describes them as more complicated and less flexible; with perfect hashing, any change to the set would require recomputing the function.
Variations: union, counters and compressed filters
The simple structure allows cheap tricks. If two filters represent different sets, have the same number of bits and use the same hash functions, the bitwise OR of the vectors represents the union. If the size is a power of 2, the filter can be halved by ORing the first half with the second and masking the most significant bit in queries. Another problem is removal: zeroing the bits of a removed item can erase bits shared with other items. The solution, attributed in the paper to Fan et al., is the counting Bloom filter, which replaces each bit with a small counter, incremented on insertion and decremented on removal. The analysis cited in the paper indicates that 4 bits per counter are enough for most applications, and that, with k at most (ln 2)m/n, the probability that any counter reaches 16 is below 1.37 × 10^-15 times m. If a counter overflows, one approach is to leave it at its maximum value. There is also the compressed filter, proposed by Mitzenmacher: when the filter will be transmitted, it may be worth using a larger, sparser vector with fewer hash functions and compressing it. In the paper's table example, with at most 16 bits transmitted per element, going from 16 bits per element and 11 hashes (rate 0.000459) to a vector of 48 bits per element and 3 hashes, which compresses to under 16 bits per element with high probability, cuts the rate by about half.
Collaborative and resource-routing applications
The paper's detailed example is the Summary Cache, by Fan et al., for sharing among web caches. Instead of exchanging lists of URLs, each proxy periodically broadcasts a Bloom filter of its cache contents. On a false positive, the proxy requests a page from another proxy that does not have it, causing extra delay; even so, the text states that the traffic gain outweighs this cost. Since the cache changes frequently, it suggests keeping a counting Bloom filter locally and broadcasting the plain version of 0s and 1s; the alternative would be to rebuild the filter from scratch on each update sent, and the counting Bloom filter reduces and amortizes this cost. The paper says the technique is used in the Squid proxy, where the filters are called Cache Digests. In moderately sized peer-to-peer networks (hundreds of nodes), storing a filter for each of the other nodes may be feasible when storing each node's list of objects is not, as in the PlanetP prototype. To reconcile sets, one peer sends its filter to the other, which then sends only what appears to be missing; because of false positives, not everything is sent, but most of it is. In resource routing, a tree-based framework keeps unified lists per node, and the OR union makes them easy to build. A false positive can send the request down a wrong path, requiring backtracking or a slower, safe mechanism. Rhea and Kubiatowicz use the attenuated Bloom filter, an array of filters per edge, one per hop distance.
Packet routing, measurement and limits
For packet routing, the paper describes three uses. In Icarus, each packet carries in its header a small Bloom filter of the nodes it has visited; if the OR of a node's mask does not change the filter, there may be a loop. In Stochastic Fair Blue, a counting Bloom filter detects aggressive flows or flows that do not respond to congestion marking. Each counter has a marking probability that rises when many packets are queued on that counter and falls when there are none, and the packet is marked with the smallest of the k probabilities; a well-behaved flow that lands on the same counters suffers a false positive, and one suggested mitigation is to periodically swap the hash functions. For multicast, Grönvall proposes keeping, per interface, a filter of addresses, avoiding storing the addresses in the router. For measurement, Estan and Varghese hash each packet k times into byte counters and flag a flow as heavy if the smallest counter exceeds a threshold; conservative update, which only raises the counters to the maximum the flow could have accumulated, greatly reduces false positives on real data, since several light flows that land on the same counter are less likely to push it above the threshold. In SPIE, routers keep filters of the packets they have seen to trace the origin of malicious packets; a false positive creates extra branches in the reconstructed path. The paper closes by recalling the cost: false positives must be evaluated in each application, and it cites later extensions such as count-min sketch, spectral and Bloomier filters.
See the ideas at work
Practice the designs that use this paper in the System Design school.