Encoding Short Ranges in TCAM Without Expansion: Efficient Algorithm and Applications
Title | Encoding Short Ranges in TCAM Without Expansion: Efficient Algorithm and Applications |
Publication Type | Conference Paper |
Year of Publication | 2016 |
Authors | Bremler-Barr, Anat, Harchol, Yotam, Hay, David, Hel-Or, Yacov |
Conference Name | Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures |
Publisher | ACM |
Conference Location | New York, NY, USA |
ISBN Number | 978-1-4503-4210-0 |
Keywords | Metrics, nearest neighbor, nearest neighbor search, pubcrawl, range encoding, TCAM |
Abstract | 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. |
URL | http://doi.acm.org/10.1145/2935764.2935769 |
DOI | 10.1145/2935764.2935769 |
Citation Key | bremler-barr_encoding_2016 |