Hash, don't cache: Fast packet forwarding for enterprise edge routers

As forwarding tables and link speeds continue to grow, fast packet forwarding becomes increasingly challenging for enterprise edge routers. Simply building routers with ever larger amounts of ever faster memory is not appealing, since high-speed memory is both expensive and power hungry. Instead, we believe future enterprise routers should leverage a hierarchical memory architecture consisting of a small, fast memory and a large, slow memory. However, the conventional approach of caching popular forwarding-table entries in the fast memory does not perform well in practice, especially under worst-case workloads with a wide range of destination IP addresses. Instead, the small memory could be used to store one Bloom filter of the address blocks associated with each outgoing link. In this paper, we present techniques to make the use of Bloom filters practical for enterprise edge routers, including optimizing the sizes of Bloom filters with limited fast memory, handling routing changes and dynamically tuning Bloom filter sizes using counting Bloom filters in slow memory, and handling the small number of false positives. Our evaluation shows that our scheme works well with less than 1 MB of fast memory.