Encoding Short Ranges in TCAM Without Expansion: Efficient Algorithm and Applications

Anat Bremler-Barr, David Hay, Yotam Harchol, Yacov Hel-Or
Conferences & Workshops
Deep Packet Inspection (DPI)


We present RENE ́ — a novel encoding scheme for short ranges on Ternary content addressable memory (TCAM), which, unlike previous solutions, does not impose row expansion, and uses bits proportionally to the maximal range length. We provide theoretical analysis to show that our encoding is the closest to the lower bound of number of bits used. In addition, we show several applications of our technique in the field of packet classification, and also, how the same technique could be used to efficiently solve other hard problems such as the nearest-neighbor search problem and its variants. We show that using TCAM, one could solve such problems in much higher rates than previously suggested solutions, and outperform known lower bounds in traditional memory models. We show by experiments that the translation process of RENE ́ on switch hardware induces only a negligible 2.5% latency overhead. Our nearest neighbor implementation on a TCAM device provides search rates that are up to four orders of magnitude higher than previous best prior-art solutions.

Supplemental Material

Technical Report

@inproceedings{10.1145/2935764.2935769, author = {Bremler-Barr, Anat and Harchol, Yotam and Hay, David and Hel-Or, Yacov}, title = {Encoding Short Ranges in TCAM Without Expansion: Efficient Algorithm and Applications}, year = {2016}, isbn = {9781450342100}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/2935764.2935769}, doi = {10.1145/2935764.2935769},booktitle = {Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures}, pages = {35–46}, numpages = {12}, keywords = {range encoding, TCAM, nearest neighbor}, location = {Pacific Grove, California, USA}, series = {SPAA ’16} }