TCAM Representations of Intervals of Integers Encoded by Binary Trees

Wojciech Fraczak1, Wojciech Rytter2,3, Mohammadreza Yazdani4
1Dépt d’informatique, Université du Québec en Outaouais Gatineau PQ, Canada
2Inst. of Informatics, Warsaw University Warsaw, Poland
3Department of Mathematics and Informatics Copernicus University, Torun, Poland
4Systems and Computer Engineering, Carleton University Ottawa ON, Canada

Abstract

We investigate the problem of efficient representations of intervals of positive integers in TCAM (Ternary Content Addressable Memory). The integers are encoded by binary strings of the same length \( n \) and a TCAM of width \( n \) is a string-oriented representation of arbitrary sets of \( n \)-bit strings in terms of a collection of simple sets, called rules. Each rule is a concatenation (of length \( m \)) of singleton sets (i.e., single digits \( 0 \) and \( 1 \)) or the set \(\{0,1\}\) denoted by \( * \). We consider a family of \( n \)-bit encodings for integers, called dense-tree encodings, which includes the lexicographic encoding (i.e., standard unsigned binary encoding) and the binary reflected Gray encoding. We provide exact bounds (with respect to \( n \)) on the minimal sizes of TCAMs representing a subset of \( n \)-bit strings corresponding to an interval. Some other issues related to the minimal sizes and number of essential rules of TCAMs are also investigated.