Optimal In/Out TCAM Encodings of Ranges

Authors:

Abstract
Hardware-based packet classification has become an essential component in many networking devices. It often relies on ternary content-addressable memories (TCAMs), which compare the packet header against a set of rules. TCAMs are not well suited to encode range rules. Range rules are often encoded by multiple TCAM entries, and little is known about the smallest number of entries that one needs for a specific range. In this paper, we introduce the In/Out TCAM, a new architecture that combines a regular TCAM together with a modified TCAM. This custom architecture enables independent encoding of each rule in a set of rules. We provide the following theoretical results for the new architecture: 1) We give an upper bound on the worst-case expansion of range rules in one and two dimensions. 2) For extremal ranges, which are 89% of the ranges that occur in practice, we provide an efficient algorithm that computes an optimal encoding. 3) We present a closed-form formula for the average expansion of an extremal range.
Funding Information
  • Israel Science Foundation (822/10, 1241/12)
  • United States-Israel Binational Science Foundation (2012344)
  • German-Israeli Foundation for Scientific Research and Development (GIF) (1161/2011)
  • Israeli Centers of Research Excellence (I-CORE) (4/11)
  • Gordon Fund for Systems Engineering
  • Neptune Magnet Consortium
  • Israel Ministry of Science and Technology
  • Intel ICRI-CI Center
  • Hasso Plattner Institute Research School
  • Technion Funds for Security Research
  • Erteschik and Greenberg Research Funds

This publication has 28 references indexed in Scilit: