Approximate caches for packet classification

Many network devices such as routers and firewalls employ caches to take advantage of temporal locality of packet headers in order to speed up packet processing decisions. Traditionally, cache designs trade off time and space with the goal of balancing the overall cost and performance of the device. We examine another axis of the design space that has not been previously considered: accuracy. In particular, we quantify the benefits of relaxing the accuracy of the cache on the cost and performance of packet classification caches. Our cache design is based on the popular Bloom filter data structure. This paper provides a model for optimizing Bloom filters for this purpose, as well as extensions to the data structure to support graceful aging, bounded misclassification rates, and multiple binary predicates. Given this, we show that such caches can provide nearly an order of magnitude cost savings at the expense of misclassifying one billionth of packets for IPv6-based caches.