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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 1st ACM Workshop on Research on Enterprise Networking, WREN '09, Co-located with the 2009 SIGCOMM Conference, SIGCOMM'09
Pages37-44
Number of pages8
DOIs
StatePublished - 2009
Event1st Workshop: Research on Enterprise Networking, WREN 2009, Co-located with the 2009 SIGCOMM Conference, SIGCOMM'09 - Barcelona, Spain
Duration: Aug 17 2009Aug 21 2009

Publication series

NameComputer Communication Review
ISSN (Print)0146-4833
ISSN (Electronic)0146-4833

Other

Other1st Workshop: Research on Enterprise Networking, WREN 2009, Co-located with the 2009 SIGCOMM Conference, SIGCOMM'09
CountrySpain
CityBarcelona
Period8/17/098/21/09

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications

Keywords

  • Bloom filter
  • Enterprise edge routers
  • Packet forwarding

Fingerprint Dive into the research topics of 'Hash, don't cache: Fast packet forwarding for enterprise edge routers'. Together they form a unique fingerprint.

  • Cite this

    Yu, M., & Rexford, J. L. (2009). Hash, don't cache: Fast packet forwarding for enterprise edge routers. In Proceedings of the 1st ACM Workshop on Research on Enterprise Networking, WREN '09, Co-located with the 2009 SIGCOMM Conference, SIGCOMM'09 (pp. 37-44). (Computer Communication Review). https://doi.org/10.1145/1592681.1592688