IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 26, NO.

2, APRIL 2018 835

Encoding Short Ranges in TCAM Without

Expansion: Efficient Algorithm and Applications
Anat Bremler-Barr, Member, IEEE, Yotam Harchol , Member, IEEE,
David Hay, Member, IEEE, and Yacov Hel-Or, Member, IEEE
Abstract— We present range encoding with no expansion
(RENÉ)— a novel encoding scheme for short ranges on Ternary
content addressable memory (TCAM), which, unlike previous solu-
tions, 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 Fig. 1. Diagram of the TCAM lookup process. The query is compared to
and its variants. We show that using TCAM, one could solve all entries in parallel and the index of the first matching entry is used to find
such problems in much higher rates than previously suggested the result.
solutions, and outperform known lower bounds in traditional
memory models. We show by experiments that the translation
process of RENÉ on switch hardware induces only a negligible
Multi-field packet classification is becoming more and more
2.5% latency overhead. Our nearest neighbor implementation on important in modern network architectures, such as SDN
a TCAM device provides search rates that are up to four orders and network function virtualization (NFV) [8]. Specifically,
of magnitude higher than previous best prior-art solutions. recently suggested SDN frameworks perform more network
Index Terms— Computer networks, switching systems, infor- functionalities on switches, such as load balancing [9], DDoS
mation retrieval, search methods, nearest neighbor search. prevention [10], and quality of service (QoS) [11]. The initia-
I. I NTRODUCTION tive for NFV suggests to implement higher level tasks such
as deep packet inspection and caching as virtual software
T ERNARY content addressable memories (TCAMs) have
become highly popular in networking equipment and
network processing units. TCAMs are used for high-
services, and make traffic flow through them using smart
classification rules. All such frameworks heavily rely on multi-
speed IP lookup and packet classification in switches and field packet classification. Many of these fields are better
routers [1], [2]. Software defined networking (SDN) schemes expressed as ranges.
such as OpenFlow [3] rely on TCAM as the main hardware While TCAMs become more and more popular, it is still
for their data path. TCAM was also suggested to be used a hard problem to efficiently represent range rules on such
for other computationally intensive tasks such as pattern memories. Over the last decade there has been an intense line
matching [4], [5], heavy-hitters detection [6], and similarity of research on range encoding on TCAM [12]–[24]. Aside
search in databases [7]. from propositions to rearchitect TCAM devices to natively
TCAM is an associative memory module. It is composed support range rules [13], these solutions can roughly be clas-
of an array of ternary words, each consisting of ternary digits, sified as either database-independent or database-dependent
namely: 0, 1, or *. The ‘*’ digits serve as ‘wild cards’ that can encoding schemes. Database-independent schemes encode all
be matched with either ‘0’ or ‘1’. Given a query word, TCAM possible ranges using the same technique, thus allowing fast
returns the first location in the memory array that matches the hot updates [12], [14], [15]. However, these schemes use
query. This process is illustrated in Figure 1. exponential TCAM row expansion, where a row is expanded
into several rows, exponentially to the number of range fields
Manuscript received June 14, 2017; revised September 26, 2017; accepted in it.
January 19, 2018; approved by IEEE/ACM T RANSACTIONS ON N ETWORK -
ING Editor Y. Ganjali. Date of publication February 5, 2018; date of
Database-dependent schemes trades the hot updates flexi-
current version April 16, 2018. This work was supported in part by the bility for more compact codes [17], [20], but usually performs
European Research Council under the European Union’s Seventh Framework well only when the number of encoded ranges is small, as the
Programme FP7/2007-2013/ERC under Grant 259085 and in part by the
Israeli Centers of Research Excellence Program under Center 4/11. Partial produced code is proportional to the number of ranges in
and preliminary versions of this paper appeared in ACM DaMoN 2015 and database. Database-dependent schemes do not scale for large
ACM SPAA 2016. (Corresponding author: Yotam Harchol.) number of ranges, as we show in Section IV-A. Therefore, this
A. Bremler-Barr and Y. Hel-Or are with the Interdisciplinary Center
Herzliya, School of Computer Science, Herzliya 46150, Israel.
paper focuses on a database-independent approach.
Y. Harchol is with the Electrical Engineering and Computer Science In this paper we present a database-independent range
Department, University of California at Berkeley, Berkeley, CA 94720 USA encoding scheme, called RENÉ - Range Encoding with No
(e-mail: yotam@[Link]). Expansion - that eliminates row expansion completely when
D. Hay is with the School of Computer Science and Engineering, The
Hebrew University of Jerusalem, Jerusalem 91904, Israel. ranges are short enough. The code produced by RENÉ is
Digital Object Identifier 10.1109/TNET.2018.2797690 proportional to the maximal range length, not to the number
1063-6692 © 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See [Link] for more information.
836 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 26, NO. 2, APRIL 2018

Fig. 2. Toy example: A binary-reflected Gray code (BRGC) encoding tree and the encoding of ranges [5 − 8] and [7, 10] using our scheme. In this example,
maximal range length is 4. Ranges are divided into layers of non-overlapping ranges. Two layers contain only ranges that can be encoded using Gray code
and therefore are not shown. Containing range [4, 11] is encoded based on the BRGC values, which forms the first left four bits. Extra bits correspond to
layers: Fifth bit to layer L1 and sixth bit to layer L3 . If a range belongs to a layer, then the value of the bit corresponding to that layer is the binary value
of the range for this layer. Otherwise, that bit is set to ‘*’. The total number of bits is proportional to the maximal encoded length and is independent of the
number of encoded ranges.

of ranges, as in database-dependent schemes. In many cases, thousands or higher) and the dimensionality is high (in the
as we show in this paper, ranges are limited in length. For order of tens or hundreds), the exact solutions break down and
example, it was shown in [15] that in real-life packet classifi- produce exponential time complexity1 [33], [34]. This problem
cation tables more than 60% of the TCP port ranges are short. is widely known as the curse of dimensionality.
Moreover, packet classification also uses other range fields, To overcome the curse of dimensionality, approximated
where all ranges are short (such as IP ToS or TTL). On some nearest neighbor (ANN) solutions are commonly used. In par-
fields one may apply quantization and categorization to reduce ticular, a c-ANN is a solution where the distance of the
the length of ranges without hurting classification accuracy retrieved point from q is at most c times the true dis-
(e.g. packet length). Nonetheless, RENÉ can be combined with tance from the nearest point. For the ANN problem, prob-
other approaches to represent a wider spectrum of ranges if abilistic dimensionality reduction such as locality sensitive
necessary. hashing (LSH) [33] was proven to be useful, with query time
In addition to packet-classification, where TCAM has sub-linear in n but linear in d. For very-high dimensional space
already been selected as de-facto industry standard, we pro- this may still pose a problem [35]. Note also that the solution
pose in this paper using a TCAM as a co-processor to CPU in provided by LSH is correct only with high probability.
order to solve hard problems from other domains in computer To our knowledge, we are the first to present a database-
science. Specifically, we show how an encoding scheme such independent encoding scheme for short ranges on TCAM with
as RENÉ, which requires no row expansion, can be used to no row expansion. In a nutshell, RENÉ divides all ranges
practically and efficiently solve the nearest neighbor search of some length hmax into hmax layers of disjoint ranges.
problem and its variants, removing the infamous curse of Using the binary-reflected Gray code (BRGC) [36], which
dimensionality from them. was shown to be more expressive for ranges than binary
Multidimensional nearest neighbor search (NN) lies at representation [15], it focuses on a specific area where the
the core of many computer science applications. Given a encoded range is. Using additional bits, it exactly points to
database of objects and a query, we wish to find the object the encoded range inside the area in focus, where a single
in the database most similar to the query object. Commonly, additional bit represents the location of the range inside the
the objects are mapped to points in high-dimensional metric layer it belongs to. A toy example is shown in Figure 2.
space. In this context, given a query point q ∈ Rd and a Using a general conjunction operator we present next,
set of points S = {pi }ni=1 , pi ∈ Rd , the goal is to find a we are able to encode all ranges with length up to hmax . The
point p ∈ S most similar to the query point q under some total length of RENÉ’s code for a w-bits field, when encoding
distance metric. In addition to the exact NN, many variants of ranges of up to length hmax , is w − log2 (hmax ) + hmax − 1.
this problem exist, including k-nearest neighbor, approximate This means that RENÉ is feasible on contemporary TCAMs
nearest neighbor, fixed-radius near neighbors, and more. The for ranges up to length of 512, depending on the available
NN and its variants are utilized in a wide range of applications, space on TCAM and number of range fields. We also present
such as spatial search, object recognition, image matching, a theoretical analysis and show that at least max(hmax −1, w)
image segmentation, classification and detection, to name a bits are required to encode short ranges of up to length hmax
few [25]–[29]. in a w-bits field. RENÉ is closer to this lower bound than any
When the dimensionality of the points is small, many solu- previously-suggested technique.
tions were proven to be very effective. These include mainly
space partitioning techniques [30]–[32]. However, when the 1 Exact brute-force search works in time that is linear to n and d, but is very
number of the data points is large (in the order of tens of slow for high n and d. Space partitioning techniques are exponential in d.
BREMLER-BARR et al.: ENCODING SHORT RANGES IN TCAM WITHOUT EXPANSION 837

We show several applications for RENÉ in the area of it only reduces the worst case of row expansion to 2w − 4.
packet classification, along with an implementation of such an DIRPE [14] suggests a tradeoff between row expansion and
application on a powerful OpenFlow switch. We also show by the number of bits required to code the range. For encoding
experiments that the penalty in latency for translating values without expansion, it demands the unfeasible number of 2w −1
using RENÉ is negligible. bits.
We evaluate and experiment our nearest-neighbor algo- The database-dependent range encoding techniques design
rithms on a real TCAM device and achieve search rates the encoding to efficiently encode the ranges that specifically
up to four orders of magnitude higher than previous best appear in the database. These techniques [16]–[20] use extra
prior-art solutions [7], [33], [37]. bits, in addition to the w bits of the range field. The basic
idea [18] is to use the extra bits as a bit map: a single extra
II. BACKGROUND bit is assigned to each selected range in order to avoid the
A. Ternary Content Addressable Memory (TCAM) need to represent it by prefix expansion.
Several works [16]–[20] deal with the scalability problem
Contemporary TCAM devices operate at very high rates,
of this basic technique, which requires one bit per range.
between hundreds of millions to more than one billion
However, all these solutions still require either very long rows,
queries per second [38], [39]. These devices have about 20-40
proportionally to the number of encoded ranges, or they trade
megabits of memory that can be configured to accommodate
that for row expansion. Moreover, some of these solutions
entries of up to about 640-bits wide (the wider the entry,
demand extra logic or extra memory that makes them useless
the fewer entries can be stored on the chip).
in our case, where the number of ranges is high.
The downsides of TCAM are that it is power hungry,
In [42] and [43] it was suggested to use negation rules on
tends to generate high heat (thus requiring extra cooling),
TCAM instead of row expansion, when applicable, such that
and relatively expensive, compared to a standard DRAM chip.
rules may specify the opposite of a range and a corresponding
A high-density TCAM consumes 12 to 15 W per chip when
opposite action (e.g. ‘deny’ instead of ‘accept’ in ACL).
the entire memory is used [2]. However, compared to com-
This reduces worst-case expansion factor to w but does not
pute units and coprocessors such as CPU or GPU, TCAMs’
eliminate it, and is only applicable in certain scenarios.
power requirement, heating and price are actually lower, and
In [44] and [45] it was suggested to use the independence
become similar only when connecting multiple TCAMs in
of order between entries [44], or the independence between
parallel, as usually done in high end networking equipment.
ingress and egress linecards [45], in order to reduce the
For example, Intel’s E7-4870 CPU consumes 130 W [40],
number of bits used to represent multi-field forwarding tables.
and Nvidia’s Tesla K80 GPU consumes up to 300 W [41].
Specifically, this reduces the width of TCAM entries and
Another downside could be that currently, a TCAM cannot be
compacts longer ranges to shorter ranges. It is possible to
easily deployed on a standard PC, as they are manufactured
use our proposed encoding scheme can be used on top of
for networking equipment.
the result tables provided by these works. In such a case, this
However, due to their impressive adoption for network-
will allow our scheme to represent longer ranges efficiently.
ing devices, TCAMs are becoming larger, faster, less power
However, our scheme is database independent and using such
hungry and less expensive. We speculate that this trend will
techniques will force it to be database-dependent.
continue. Inspired by the adoption of Graphics Processing
Other works [21]–[24], [46], [47] improve the overall
Units (GPUs) for general purpose parallel computing in recent
TCAM memory requirements for classification rules, or split
years, in Section V we also suggest that TCAMs may be useful
the rules into multiple TCAM chips [48], [49]. However, these
for other tasks outside the networking field.
works do not focus specifically on range encoding, and can be
used on top of most of the range encoding techniques including
B. Range Encoding on TCAM the one proposed in this paper.
The problem of range encoding on TCAM has received Other works use TCAM for similarity search in databases.
considerable attention in the context of packet classification. Shinde et al. [7] encode probabilistic hash functions on TCAM
The traditional technique for range representation [12] is to implement locality-sensitive hashing [33]. Afek et al. [50]
prefix expansion, where a range is represented by a set of use TCAM to implement priority queues with a constant time
prefixes, each of which can be stored by a single TCAM lookup operation and as a by-product, to provide a TCAM-
entry. The worst-case expansion ratio when using prefix expan- based sorting algorithm with O(n) time.
sion for a w-bit field is 2w − 2 and for an entry with d The limitation of all the methods has inspired a suggestion
ranges it is (2w − 2)d . Lakshminarayanan et al. [14], and to change the TCAM hardware [13], to implement range
Bremler-Barr and Hendler [15] suggest encoding schemes matching directly in hardware. However this solution changes
other than binary: In [14], Lakshminarayanan et al. propose TCAM architecture dramatically, and it does not seem feasible
DIRPE, a hierarchical version of fence encoding. Bremler- in the near future, since TCAM is a popular memory chip
Barr and Hendler [15] propose SRGE - an encoding based on that exists in tens of millions of routers and switches today.
binary reflected Gray code [36]. However, these works do not Moreover, the solution harms the flexibility of TCAM imple-
reduce the range expansion to one, or, in the case of [14], mentation, where every entry is simply encoded as a string of
it requires an infeasible exponential memory size to do that. ternary bits, regardless of the fields type and borders.
SRGE [15] points out that more ranges can be expressed by Gray code [36] was originally designed for error correction
using Gray code than when using binary representation, but purposes in communication networks. However, as shown
838 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 26, NO. 2, APRIL 2018

in [15], the reflectivity of this encoding can be used in TCAMs, dimension of the search space (d) is low (e.g., around 10
along with the ternary representation provided by this device, or 20) [33]. An experimental study [34] has in fact shown
to represent intervals. As ternary gray code cannot be used that such approaches scale poorly with the number of dimen-
to represent all possible intervals, it was suggested in [20] to sions d, and even when d > 10, they may perform worse than
divide intervals into layers, and use binary encoding of those a brute-force scan.
layers to represent all intervals. In this work we rely on both Locality sensitive hashing (LSH) [51] is another tech-
ideas. nique for solving instances of the N EAR N EIGHBOR R EPORT
P ROBLEM; its goal is to be more useful in higher dimensions.
The idea of this technique is to find a family of hash functions
C. Nearest-Neighbor Search that map neighboring points to the same hash bucket with
The nearest neighbor search problem is formally defined high probability, so that if two points are in the same bucket,
by the following definition for points in a discrete space of they are likely to be close-enough neighbors. One could create
dimension d: different LSH solvers for different N EAR N EIGHBOR R EPORT
Definition 1: Given a set of data points S = {pi }ni=1 , P ROBLEM instances and thus provide an approximated solu-
pi ∈ Zd and a query point q ∈ Zd , T HE N EAREST-N EIGHBOR tion for the nearest-neighbor problem. The size of the hash
P ROBLEM is to find the point s∗ = arg mins∈S D(s, q), where function family depends on the size of the data set, rather
D(s, q) is a distance between s and q. than on the space dimension. LSH was further investigated
As discussed above, in order to overcome the curse of and later works provided better approximation and running
dimensionality, the accuracy of the solution is sometimes times [33], [54]. Building on the LSH idea, Lv et al. [55]
compromised. The c–A PPROXIMATE N EAREST-N EIGHBOR proposed reducing the number of hash functions by multiple
P ROBLEM (c-ANN) searches for a point p ∈ S such that probing of hash buckets that are likely to contain query
D(p, q) < c · D(s∗ , q), where s∗ is the nearest point to q. results. Another LSH-based approach is locality sensitive B-
One important generalization of the nearest neighbor prob- trees (LSB-Trees) [56], which improves the running time and
lem that can be solved with minor adaptations of our frame- quality of results. In Section V-E we show, however, that
work is the T HE k–N EAREST-N EIGHBOR P ROBLEM, which for high-quality results, the computation time of LSH can
finds a set S  ⊆ S of k points such that for each p ∈ S  and be relatively long, and incomparable to the computation time
p ∈ S \ S  , D(p , q) ≤ D(p, q). We show these adaptations in required by our solution.
Section V-B. A different approach to tackle the curse of dimensionality
A simpler problem that we will use as a building block in is to use parallel hardware. For example, graphics processing
our algorithms only searches for a neighbor close enough to units (GPUs), which are currently fully programmable using
the query point, or discovers that there is no such neighbor at CUDA and OpenCL, have hundreds of computing cores,
all: and can help reduce the effect of higher dimensions. Two
Definition 2: Given a set of points S = {pi }ni=1 , pi ∈ Zd , fast nearest neighbor search implementations were presented
and a query point q ∈ Zd , let d∗ = mins∈S D(s, q). The in [37], [57], and [58]. These implementations, both written in
r–N EAR -N EIGHBOR R EPORT P ROBLEM is to find the point CUDA, basically perform a multithreaded brute-force scan of
s ∈ S such that D(s , q) ≤ r if d∗ ≤ r, and to return false if the data set using a GPU. A GPU was also used to implement
d∗ > r. a parallel version of the LSH algorithm [59]. While these
Note that under ∞ , a solution for the r–N EAR -N EIGHBOR approaches leverage the parallelism of GPUs and provide
R EPORT P ROBLEM is a data point within the d-dimensional much faster solutions than previous approaches, we show in
cube of edge length 2r that is centered in the query point. Section V-E how TCAM can provide an even more time-
Thus, our framework for solving c-ANN can be viewed as efficient solution to the nearest-neighbor problem.
solving (either in parallel or sequentially) a series of r–N EAR - To the best of our knowledge, using TCAM for near-
N EIGHBOR R EPORT P ROBLEM instances for increasing values est neighbor search has been considered only once, by
of r. As pointed out in [51], this solves the c-A PPROXIMATE Shinde et al. [7] who proposed the TLSH scheme, where a
N EAREST N EIGHBOR P ROBLEM, where the approximation TCAM device is utilized to implement LSH with a series of
ratio is determined by the maximum ratio between consecutive TCAM lookup cycles. In this scheme, each database point is
values of r. mapped to a ternary code, where each ternary digit is generated
One method for solving the N EAR N EIGHBOR R EPORT using a random projection and dividing the projected line into
P ROBLEM is bucketing [51]. The idea behind it is to divide m bins whose assignments alternate between ternary digits
the d-dimensional space into a grid of d-dimensional cells. [0, ∗, 1, ∗, 0, ∗, 1, · · · ]. As the ‘*’ digit can match both ‘0’ and
Given a point q located in some cell, we look for its nearest ‘1’, this assignment blurs the boundaries between the 0 and
neighbor, p, in the cell. Then, we search for other points p 1 bins such that the ternary hashed representation of nearby
in adjacent cells such that D(p , q) < D(p, q). If such a point points matches with high probability. Our algorithms, however,
p exists, we update p to be p . We then continue looking for are deterministic and take a completely different approach,
such points in adjacent cells until the distance of the cell’s as we will highlight in the rest of the paper.
boundary from q is larger than D(p, q). Other, more advanced
space-partitioning techniques to solve the N EAR N EIGHBOR III. E NCODING S CHEME FOR S HORT R ANGES
R EPORT P ROBLEM are kd-Trees [52] and Random Projection Our goal is to encode a range up to a certain length hmax
Trees [53]. However, all these methods are only useful if the using a single TCAM entry of as few bits as possible. Such
BREMLER-BARR et al.: ENCODING SHORT RANGES IN TCAM WITHOUT EXPANSION 839

Fig. 3. Encoding trees for Binary Reflected Gray Codes of length 1, 2, and 3 bits.

code will allow encoding classification rules with multiple For example, BRGC(4, 8) = 1 · BRGC(3, 4) =
ranges without row expansion at all. 11 · BRGC(0, 2) = 110 · BRGC(0, 1) = 110. An example
for values in [0, 16) is shown in Figure 2.
A. Basic Definitions Figure 3 shows the recursive process of constructing BRGC
for n = log w = 3 bits. We begin with n = 1, where 0 is
We begin with some basic definitions that will be used
encoded as 0 and 1 is encoded as 1. To construct the code for
throughout the rest of this section. First, we define a ternary
n = 2, the code is duplicated and reflected, and an additional
bit-wise comparison:
leading 0-bit (1-bit) is added to the first (second) part. The
Definition 3: Let a = a0 , . . . , am and b = b0 , . . . , bm be
result is can be viewed as a tree with two levels, where
two ternary words (ai , bi ∈ {0, 1, *}). a matches b, denoted
the encoding of a number (a leaf) is the sequence of binary
a ≈ b, if and only if for every i ∈ {0, . . . , m}, either ai =
digits (transitions) that lead to it. This process can continue
bi , or ai is *, or bi is *.
recursively for any number of bits. The BRGC codeword can
RENÉ encodes ranges in discrete spaces. We begin by
also be computed directly using a simple formula
defining an encoding function tcode for values and ranges.
By wildcarding some of the bits of a BRGC codeword
Let U = [0, 2w ) ⊂ N0 be a range on the natural line. RENÉ’s
we can create a ternary range representation. For example,
encoding function tcode encodes either a value v ∈ U, or a
as can be seen in Figure 2, the ternary word *1** matches
range R ⊆ U. It is important to note that RENÉ treats U as
all values in the range [4, 11]. In fact, when looking at this
a cyclic ‘wrap-around’ space and thus throughout this paper,
tree representation of the BRGC encoding, we observe that all
any range [x, y) refers in fact to [x, y mod 2w ).
ranges that exactly contain a full sub-tree, or two adjacent full
The result of the encoding function is either a binary word
sub-trees, can be represented using a single ternary BRGC
(for exact values) or a ternary word (for ranges), and we expect
codeword (namely, a BRGC codeword where some of the
that a ternary match tcode(v) ≈ tcode(R) will imply that
0-1 bits were replaced by ‘*’ symbols).
the value v is inside the range R. This is formally defined as
Before formulating and proving this observation we define
follows:
the following terms that will be used in the proof:
Definition 4: An encoding function tcode is admissible
if for every value v ∈ U and every range R ⊆ U, tcode(v) ≈ • k-prefix is a ternary word in which the k least significant
tcode(R) if and only if v ∈ R. Furthermore, for any point bits are ‘*’ and the rest are either 0 or 1.
v ∈ U, tcode(v) does not contain ‘*’ symbols. • k-semi-prefix is a ternary word in which the k least
significant bits are ‘*’, one additional bit is also ‘*’, and
B. Binary-Reflected Gray Code for TCAM the rest are either 0 or 1.
The binary-reflected Gray code (BRGC) [36] is a binary We now formulate and prove the following theorem:
encoding of integers in a contiguous range such that the codes Theorem 1: If all values are BRGC-encoded, then a single
of any two consecutive numbers differ by a single bit. A b-bits ternary BRGC codeword suffices to admissibly encode a range
BRGC is constructed recursively by reflecting a (b − 1)-bits R = [x, y mod 2w ) if and only if there exist non-negative
BRGC.2 integers i, k, for which x = i · 2k and y = (i + 2) · 2k .
Definition 5: The BRGC encoding function Specifically, one of the following cases holds:
BRGC(v, 2w ) encodes a point p (where 0  p < 2w ) 1) If i is even, the (k + 1) least significant bits of the
with w bits. It is defined recursively as follows: codeword are *, and the rest are either 0 or 1. Thus,
the ternary codeword is (k + 1)-prefix.
BRGC (0, 1) = ε
 2) If i is odd, the k least significant bits of the codeword
0 · BRGC (p, 2w/2 ) if p < 2w/2 are *, one additional bit is *, and the rest are either
BRGC (p, 2w ) =
1 · BRGC (2w −p−1, 2w/2) otherwise 0 or 1. Thus, the ternary codeword is k-semi-prefix.
where ε is the empty word and ‘·’ denotes concatenation. Proof: The proof follows by induction on k: For k = 0,
2 The ranges are [i, i + 2). These ranges are simply two adjacent
BRGC of a value x can be directly calculated using the following
formula: x ⊕ (x  1), where ⊕ and  are the bitwise operations of XOR leaves in the BRGC tree representation, and, by definition of
and Right Shift, respectively. Gray code, they differ in a single bit only.
840 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 26, NO. 2, APRIL 2018

Fig. 4. BRGC encoding tree for points in range [0, 16), and ternary representations of intervals of lengths 4, 8 that can be represented using this encoding.

If i is even, then there is an even number of leaves before

these two, and thus these two leaves are siblings and have
a common direct ancestor x with height k + 1 = 1. Thus,
the (k + 1)-prefix that is the concatenation of the log(w) − 1 Fig. 5. Encoding structure for a value or range of length h.
bits that represent the path to x with one *, represents the
range [i, i + 2) (case 1 in Theorem 1).
If i is odd, then the two leaves do not have a common direct Figure 4 illustrates the BRGC encoding tree for all points
ancestor. However, they do have some common ancestor up in the range [0, 15], and the ternary encoding for all intervals
in the higher levels of the tree, let it be at height h. Thus, of lengths 4, 8 that satisfy the condition above.
their representation differ in the hth bit. Since the codewords Theorem 1 implies that when encoding ranges of length h,
of i and i + 1 differ only in one bit, there are no additional the log2 (h) − 1 least significant bits are always ‘*’ thus one
bits where they differ. Therefore, the k-semi-prefix in which can save TCAM space by omitting these uninformative bits.
the hth bit is * and the rest of the bits are as in i and i + 1
BRGC codewords, represents the range [i, i + 2) (case 2 in C. An Encoding Function for Ranges
Theorem 1).
We assume that the lemma is correct for some k, and show We call those ranges that can be encoded using a single
that it is correct also for k + 1: Let R = [i ·2k+1 , (i + 2)·2k+1) ternary BRGC codeword trivial ranges, and all other ranges
be a range of length 2k+2 , for some positive integer i. Let nontrivial ranges. In this section, we extend the BRGC encod-
j1 = 2i, j2 = 2i + 2, and let R1 = [j1 · 2k , (j1 + 2) · 2k ), R2 = ing scheme so that it can encode in a single ternary word
[j2 · 2k , (j2 + 2) · 2k ) be two ranges of length 2k+1 . Then, nontrivial ranges as well. We append extra bits to the end of
R = R1 ∪ R2 , and since j1 and j2 are even, R1 , R2 can be BRGC codewords, as depicted in Figure 5: w − log2 (h) + 1
represented using (k + 1)-prefixes (case 1 in Theorem 1). bits are used for the binary BRGC encoding of a value v ∈ U,
If i is even, then in the tree representation of the BRGC or for the ternary BRGC encoding of some trivial range R.
encoding there exists an even number of subtrees of height To encode nontrivial ranges of length h = 2k (k ∈ N0 ), at most
k + 1 before the subtree that represents R1 . Thus, the roots h − 2 bits are added as extra bits.
of the subtrees that represent R1 , R2 are siblings, and the The key idea of RENÉ is to divide all ranges of some length
first w − k − 2 bits of their ternary BRGC codewords are h = 2k (k ∈ N0 ) into h layers, such that a layer Lih is the set of
equal. Wildcarding the k + 2 least significant bit would all ranges [x, x + h) for which x mod h = i. Note that two of
k−1
yield a (k + 2)-prefix that represents their union and thus these layers contain only trivial ranges (L0h and L2h ). We are
represents R. left with h − 2 layers that contain nontrivial ranges. We assign
If i is odd, then the roots of the subtrees that represent an extra bit for each layer of nontrivial ranges. The value of
R1 , R2 are not siblings, but they do have some common ances- this bit alternates between adjacent ranges in the same layer,
tor. We denote the right bound of R1 as x = (2i + 2) · 2k − 1 such that for any pair of consecutive ranges in the same layer,
and the left bound of R2 as y = (2i + 2) · 2k . x and y are two the value of the bit corresponding to this layer is different.
consecutive integers and thus their BRGC representation differ Hence, for a value v ∈ U, tcode(v) is the 1 + w − log2 (h)
in one bit only. If we assume towards a contradiction that the most significant bits of BRGC(v), concatenated with h − 2
extra bits. The value th
difference is in one of the k + 1 least significant bits, then
i
 v−iof
 the i extra bit corresponds to layer
both BRGC codewords of these points share the same prefix Lh and is set to h mod 2.
of length that is greater than w − k − 1, so the two values can For nontrivial ranges we define their cover range as follows:
be represented using the same subtree of height k + 1, which Definition 6: For any nontrivial range of length h = 2k
is impossible as R1 = R2 . Thus, the difference between the (k ∈ N0 ), R = [x, x + h), let the cover range of R, denoted
two codewords is in one of the w − k − 1 most significant bits, by cover(R), be the range [ x/h · h, ( x/h + 2) · h).
and the (k + 1)-semi-prefix that has ‘*’s in this bit and in the We first notice the following property of cover ranges:
k + 1 least significant bits, represents the union of R1 and R2 Lemma 1: For any range R = [x, x + h) of length h = 2k
which is R. (k ∈ N0 ), cover(R) fully contains R.
BREMLER-BARR et al.: ENCODING SHORT RANGES IN TCAM WITHOUT EXPANSION 841

Fig. 6. Encoding for all sub-ranges of length 4 and values in range [0, 16). Left bits are the ternary BRGC encoding. Right bits are the extra bits for
nontrivial layers. The bits in gray can be removed as explained in Section III-B.

Proof: Assume by contradiction that R starts before To prove the other direction, assume that a value v ∈ / R
cover(R) starts or ends after cover(R) ends. If R starts has the same bit value as R. Let Rbefore = [x − h, x) be the
before cover(R), x < x/h · h. So x/h < x/h , which is range that precedes R in Lih and Rafter = [x + h, x + 2h) be
of course impossible. Also, if R ends before cover(R) ends, the range that succeeds R in Lih . The bit value of Rbefore and
x + h > ( x/h + 2) · h. This implies that x/h > x/h + 1 Rafter must be different than the bit value of R as they are
which is also impossible, and thus a contradiction. both adjacent to R. Since v ∈ cover(R) but not in R, and
Note that the existence of the cover range is a unique since the length of cover(R) is at most 2h, v must be either
property of the binary-reflected Gray code. The cover range in Rbefore or in Rafter , and thus it must have the opposite
cover(R) helps us distinguish R from other ranges in the bit value than R.
same layer. For range R = [x, x + h) ∈ Lih of length h = 2k We now turn to the main theorem.
(k ∈ N0 ), tcode(I) starts with the 1 + w − log2 (h) most Theorem 2: The function tcode is an admissible encoding
significant bits of the ternary BRGC representation of R, if R function for ranges of length h = 2k .
is trivial, or of cover(R), if R is nontrivial. Then, h−2 extra Proof: Assume that there exist a value v and a range R
bits are concatenated one after
 the other where the ith bit is for which v ∈ R but tcode(v) ≈ tcode(R). v is in R so
either * if I ∈ i x−i
/ Lh or h mod 2 otherwise (namely, all the the ternary BRGC of R (in case R is trivial) or of cover(R)
extra bits except one are *). (in case R is nontrivial) must match the BRGC encoding of
Our main result is that RENÉ’s encoding function, tcode , v ternary-wise. Thus, some extra bit does not match. Since
is an admissible encoding function for ranges of any length for trivial ranges all extra bits are *, R must be nontrivial.
h = 2k (k ∈ N0 ). The total length of the admissible encoding For nontrivial ranges, only one extra bit in tcode(R) is not
produced by tcode for a single value or range is hence w − a ‘*’. However, this bit must be equal to the corresponding
log(h) + h − 1. bit in tcode(v) by Lemma 3, which is a contradiction to the
Before proving this result (Theorem 2), we introduce the assumption that tcode(v) ≈ tcode(R).
following two technical lemmas: To prove the opposite direction, assume that there exist a
Lemma 2: If a range R is nontrivial, then no other range value v and a range R for which tcode(v) ≈ tcode(R)
from the same layer is fully contained in cover(R). but v ∈/ R. The BRGC encoding of v must match the ternary
Proof: Assume R = [x, x + h), where h = 2k , and that BRGC encoding of R (in case R is trivial) or cover(R)
there exists another range from the same layer, R , that is (if R is nontrivial). If R is trivial and there is a match then
also fully contained in cover(R). By the definition of the v ∈ R, as all extra bits in tcode(R) are ‘*’. Thus, R must
layers, R and R are both of length h and are not overlapping. be nontrivial, and v must be inside cover(R). However by
By Definition 6, cover(R) is of length 2k+1 , implying that Lemma 3, if v ∈ cover(R) and has the same bit value as R
the union of R and R is equal to cover(R), but since both for the layer R belongs to, then v must be in R.
ranges are fully contained in the cover, the union is exactly Figure 6 shows the encoding of all sub-ranges of length 4
the cover. This, in turn, implies that x mod h = x/h . in range [0, 16). Note that the first and third layers do not
Choosing i = 2 x/h yields that R = [i · 2k , (i + 2) · 2k ) require extra bits, so these are both set to * in their encoding.
and thus, by Theorem 1, R is a trivial range, in contrast to the In other layers, the corresponding extra bit alternates between
assumption. ranges in the same layer. For example, the range [1, 4], which
Based on this property of cover ranges, we can completely cannot be encoded solely using a ternary BRGC codeword,
distinguish between ranges in the same layer using the extra is encoded as 0***1*, where the fifth bit is the extra bit that
bits we added to the ternary BRGC encoding: corresponds to the second layer. Only points in [1, 4] match
Lemma 3: Let R = [x, x + h), where h = 2k , be a range this encoding.
in Lih . For every value v in cover(R), if v ∈ R, v has the
same bit value as R, and if v ∈ / R, then v has the opposite bit D. Encoding Multiple Range Lengths
value. Given RENÉ’s encoding function for ranges of some max-
Proof: Assume that a value v ∈ R, has a bit value that is imal length hmax we can encode, without using more bits,
different
 than the  value of R. v is in R so v − x  h, and
 x−ibit all ranges whose lengths are smaller than hmax as well.
thus v−i h = h , meaning that the bit value of v must be
We define a logical conjunction operation, denoted by ,
equal to the bit value of R. to encode the intersection of two ranges. The truth table
842 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 26, NO. 2, APRIL 2018

TABLE I Algorithm 1 Encoding Function for a Value v

T HE T RUTH TABLE OF A T ERNARY L OGICAL C ONJUNCTION ,
1: function tcode (v, hmax )
D ENOTED BY THE  O PERATOR
2:  v - value, hmax - maximal range length
3: word ← BRGC(p)  (log2 (hmax ) − 1)  Bitwise
shift
4: for i ← 0 to (hmax − 1) do
5: if layer is skipped then
6: continue  Optional - encode less layers
7: end if
of such a conjunction is given in Table I. ⊥ means an
8: if layer is nontrivial
 (i = 0 and i = hmax
2 ) then
undefined output, and we later make sure to never get such
an output when using this operation. For two ternary words, 9: b ← hmax mod 2
v−i

a = a0 , . . . , am and b = b0 , . . . , bm , the conjunction c = a b 10: word ← (word  1)|b  Bitwise OR

is the ternary word where ci = ai bi . If at least one of 11: end if
the symbols ci is ⊥, then c is also marked as ⊥ and is not 12: end for
defined. Note that the conjunction operation is independent of 13: return word
the specific encoding function. 14: end function
The essence of the conjunction operation is captured in the
following two lemmas:
Lemma 4: For any value v ∈ U and any two ranges [x, x + h) of length h < hmax (h is not necessarily a power
R1 , R2 ⊆ U, if tcode is an admissible encoding function of 2 anymore) can be written as the intersection of two ranges
for R1 and R2 , then tcode(v) ≈ tcode(R1 ) tcode(R2 ) of length hmax as follows:
if and only if v ∈ R1 ∩ R2 .
Proof: Assume tcode(v) ≈ tcode(R1 ) tcode(R2 ) [x, x + h) = [x + h − hmax , x + h) ∩ [x, x + hmax ).
and v ∈ / R1 ∩ R2 . Without loss of generality, assume v ∈ / R1 . Using the conjunction operator and Lemma 4 we can construct
Since v ∈ / R1 and tcode is an admissible encoding function, the code for ranges of any length h  hmax , with hmax − 2
there exists some i for which tcode(v)i = *, tcode(R1 )i = extra-bits:
*, and tcode(v)i = tcode(R1 )i . Without loss of gen-
erality, let tcode(v)i = 0, so tcode(R1 )i = 1 and tcode([x, x + h))
therefore tcode(R1 )i tcode(R2 )i is either 1 or ⊥. Thus, = tcode([x + h − hmax , x + h)) tcode([x, x + hmax )).
by definition, tcode(v)i ≈ tcode(R1 )i tcode(R2 )i
implying tcode(v) ≈ tcode(R1 ) tcode(R2 ), which is We also know from Lemma 5 that tcode([x, x + h)) is not
a contradiction. ⊥ as the intersection is never empty.
To prove the other direction, assume that v ∈ R1 ∩ R2 . The encoding function tcode(v) for some value v when
Since v ∈ R1 and v ∈ R2 and tcode is admissible, using any range lengths up to hmax is shown in Algorithm 1.
tcode(v)i ≈ tcode(R1 )i and tcode(v)i ≈ tcode(R2 )i , When encoding a range R of length h  hmax that is centered
for any i. The admissibility of tcode also implies that at some point v, Algorithm 2 is used to obtain tcode(R).
tcode(v)i is either 0 or 1. Assume without loss of generality The length of the resulting encoding of a value v ∈ U or a
that for some i it is 0. Then, tcode(R1 )i and tcode(R2 )i range R ⊆ U is therefore w − log2 (hmax ) + hmax − 1.
are either 0 or *. Hence, tcode(R1 )i tcode(R2 )i is
either 0 or *, and therefore, tcode(v)i ≈ tcode(R1 )i E. Running Time Analysis
tcode(R2 )i . Since this is true for any i, it implies that Computing tcode for either a value or a range is simple:
tcode(v) ≈ tcode(R1 ) tcode(R2 ), and the claim results only depend on the value or range themselves, and
follows. the maximal range length hmax . The running time of both
Lemma 5: If tcode is an admissible encoding function functions, for a value and a range, is linear with hmax , and
for R1 and R2 , and the result of tcode(R1 ) tcode(R2 ) does not depend in the number of encoded ranges: O(hmax )
is ⊥ then R1 ∩ R2 = ∅. when encoding a value and O(hmax + h) when encoding a
Proof: Assume tcode(R1 ) tcode(R2 ) = ⊥ and to range of length h  hmax .
the contrary, that R1 ∩ R2 = ∅. Then, there exists some i
for which, without loss of generality, tcode(R1 )i = 0 and
tcode(R2 )i = 1, and some value v ∈ R1 ∩ R2 . From the F. Lower Bound on the Number of Bits per Range
admissibility of tcode , if v ∈ R1 , then tcode(v) = 0, As previously recalled, Lakshminarayanan et al. [14] intro-
and thus v ∈ / R2 , and if v ∈ R2 , then tcode(v) = 1, and duced the worst-case necessary condition of 2w − 1 bits to
thus v ∈/ R1 , which is a contradiction. encode a w-bit range. We use this observation to introduce a
Note that the other direction of Lemma 5 is not necessarily lower bound for the number of bits required to encode ranges,
true: the conjunction of codes of two disjoint ranges may not when their lengths are limited by some upper bound hmax :
be ⊥. Theorem 3: In order to represent any ranges up to length
We assume that there is a value hmax = 2kmax , which is hmax without row expansion, in a field of width w bits, at least
the maximum length we should consider. Note that any range max(hmax − 1, w) bits are necessary.
BREMLER-BARR et al.: ENCODING SHORT RANGES IN TCAM WITHOUT EXPANSION 843

Algorithm 2 Encoding Function for a Range [s, t] also contained in each other (and thus are overlapping), and a
1: function tcode ([s, t], hmax )
single bit per range is necessary to distinguish between them.
When using a range field with more bits (i.e. larger w), we do
2:  [s, t] - range, hmax - maximal range length
not reduce the number of possibly overlapping range. Thus,
3: if t − s + 1 = hmax then
the number of required bits cannot be lower than hmax − 1
4:  Encode range as an intersection
(note that this lower bound is not necessarily tight).
5: R1 = [s, s + hmax − 1]
In any case, and specifically when w > hmax − 1, at
6: R2 = [t − hmax + 1, t]
least w bits are necessary to represent singular values (ranges
7: Γ ← {R1 , R2 }
of length 1).
8: else  Encode range directly
9: Γ ← {[s, t]}
10: end if IV. RENÉ FOR PACKET C LASSIFICATION
11: result ← 0 Range encoding on TCAM has been used for packet clas-
12: count ← 0 sification for long time. Row expansion significantly limited
13: for [x, y] ∈ Γ do its usage when multiple header fields are ranges, leading
14: mask ← 0 vendors and administrators to avoid such situations as much
15: for i ← x + 1 to y do as possible. However, next generation SDN applications, such
16: mask ← mask|(BRGC(i − 1) ⊕ BRGC(i)) as load balancers, security tools, and quality of service, rely
17:  bitwise OR and XOR on sophisticated packet classification that is performed on the
18: end for datapath itself (i.e. the switch) [9]–[11], [60]. Most of these
19: word ← BRGC(x)  (log2 (hmax ) − 1) solutions require range based matching on multiple header
20: mask ← mask  (log2 (hmax ) − 1) fields. We summarize several examples for such fields and
21: for i ← 0 to (hmax − 1) do metadata information that can benefit when using RENÉ:
22: if layer is skipped then • TCP/UDP Port Fields: In real-life datasets, short ranges
23: continue  Optional - encode less layers (up to length 64) sometimes consist more than 60% of the
24: end if unique ranges [15]. Thus, if a network administrator uses
25: if layer is nontrivial (i = 0 and i = hmax2 ) then mainly short ranges for TCP/UDP port fields, or even for
26: if x mod hmax = i then  Irrelevant layer only one of these fields, RENÉ may suit their needs.
27: mask ← (mask  1)|1  Put a ‘*’ • Network ToS (or DSCP): In both the deprecated ToS
28: word ← word  1 field and the new DSCP field the precedence is set
29: else  [x, y] is in this layer using an increasing value, and to specify one or more
30: mask ← mask  1 precedence classes, either an exact value or a short range
31: b ← hx−i max
mod 2 should be used.
32: word ← (word  1)|b • Packet Size: Packet size (e.g. IP total length field) can
33: end if be a useful piece of information for packet classification.
34: end if When classifying according to this property, a catego-
35: end for rization can be done in order to reduce range lengths.
36: if count > 0 then As usually one does not classify packets according to a
37: result ← result (word, mask) specific length, but rather according to categories (small,
38: else medium, large, etc.), short ranges can be used to represent
39: result ← (word, mask) multiple categories. For example, a recent attack named
40: end if Tsunami SYN Flood Attack can be identified based on the
41: count ← count + 1 size of packets (about 1000 bytes or more) [61].
• Timestamp and Counters: Recent works suggest adding
42: end for
43: return result packet’s metadata such as hit counters and timestamps
44: end function
(or time deltas) to classification data path, for example in
OpenFlow switches [60]. It is likely that classification on
such fields would be based on ranges and not on exact
values, and thus RENÉ may be used.
Proof: The maximal range length hmax is given as some • IP Spoofing Detection: In order to protect against IP
fixed value. We show that the theorem is correct for any w  spoofing and attacks that use this technique (e.g., DDoS),
log2 (hmax ), as a field with less bits than that cannot have it was suggested to inspect the IP TTL value and conclude
ranges of length hmax . For w = log2 (hmax ), the range field about possible spoofed packets [62], [63]. The detection
starts at 0 and ends at hmax −1 and is of size of exactly hmax . is based on the fact that the TTL value does not change
According to the condition in [14, Th. 1], to encode all ranges dramatically over short time for the same host or subnet,
in this field, the worst-case length of the ternary representation and these values can be found using ping and other
is at least 2w − 1 = hmax − 1 bits. tools. Thus, if a packet with IP from a known subnet
The proof of [14, Th. 1] stems from the fact that for a comes with a TTL value that is too far from the expected
range of size 2w there are 2w −1 contained sub-ranges that are value, it is classified as spoofed and dropped.
844 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 26, NO. 2, APRIL 2018

Since the TTL value is not compared to an exact value,

but rather to a short range, RENÉ can be used in
order to implement IP spoofing detection on classification
hardware with TCAM.
• AS Numbering: BGP routers and SDX [64] sometimes
make classification decisions based on autonomous sys-
tems (ASes) numbers. Large ISPs and content providers
usually hold multiple, consecutive AS numbers [65],
which form one or more short ranges. For example,
Comcast has multiple such short ranges 7015-7016,
33489-33491, 33650-33668 (in addition to five more
non-consecutive AS numbers). Grouping AS numbers
to ranges can reduce the total number of classification Fig. 7. Analysis of the number of TCAM bits required for a 16-bits range
rules, as long as no row expansion is induced. RENÉ fits field when representing all ranges of up to a given length.
this goal as the ranges are short and it induces no row
expansion. of max(hmax − 1, w) bits (see Theorem 3), as a black,
dotted line. Evidently, RENÉ (blue, solid line) is much closer
A. Evaluation and Experiments to the lower bound than all other techniques. Moreover,
the bit requirements for database-dependent techniques such
1) Experiment on an OpenFlow Switch: We implemented as LIC [20] are higher by an order of magnitude, when all
RENÉ and a sample SDN application that uses it for packet ranges up to a certain length should be encoded. The database-
classification over the Ryu SDN controller [66]. We use a independent technique DIRPE [14] always requires 2w −1 bits
NoviFlow NoviKit 250 hardware switch that supports Open- as it does not use the additional information on the maximal
Flow 1.3 [3] and has an internal TCAM. Our code is available range length.
at [Link]
Classification uses OpenFlow table pipeline in the following
way: First table, given a destination TCP port for a packet, V. RENÉ FOR N EAREST N EIGHBOR S EARCH
writes its translation into RENÉ’s encoding to the metadata TCAM is a powerful device with high parallelism that
field (using the OpenFlow’s Write-Metadata instruction). This can also be used for tasks outside of the networking fields.
table is precomputed on the controller and contains up to 64K Just as TCAM has broken the performance limits of packet
entries - an entry for each port number. Then, second table classification and IP lookup in networking, it can also be
matches the packet according to the metadata only (original used to break such computational limits in problems from
port information is not necessary at this stage), and forwards other fields, serving as a coprocessor for the CPU, similarly
it accordingly. to a GPU or FPGA. RENÉ can be used to implement on
On the same switch, when a packet is classified based on such TCAM applications that use the nearest-neighbor prob-
only its TCP port, without table pipeline, the total round- lem or its variants. We show several such variants in this
trip time to and from the switch, using a 1Gbps copper section, and by experiments and simulations we show that
link, is 157μs. Using our table pipeline, such round-trip takes RENÉ can improve their performance by orders of magni-
161μs. Thus, latency increases by only 2.5%, which is a tudes.
negligible factor. Multidimensional nearest neighbor search (NN) lies at the
2) Quantitative Evaluation: To evaluate the quality of core of many computer science applications. The formal
RENÉ’s encoding function tcode we compare it with best definition of the problem in the space of integers is provided
prior-art encoding techniques that can provide no row expan- in Section II-C.
sion: DIRPE [14], a database-independent encoding scheme The NN problem and its variants are utilized in a wide
and LIC [20], a database-dependent encoding scheme. We do range of applications, such as spatial search, object recogni-
not compare RENÉ to SRGE [15], for example, as it requires tion, image matching, image segmentation, classification and
row expansion. We evaluate the database dependent scheme detection, to name a few [26]–[28].
LIC both in its worst case, where all ranges are to be In this section we present super high-speed algorithms for
represented, and using a commercial classification dataset with the NN problem using TCAM as a coprocessor, and our
257 range rules. Since our goal is no expansion of TCAM encoding scheme RENÉ. The proposed algorithms solve the
entries, we compare the amount of TCAM bits required ANN problem with ∞ -normed distance using a single TCAM
for a single range field, such that no expansion is induced lookup and linear space.
whatsoever. Using the classification database, LIC performs The r–N EAR -N EIGHBOR R EPORT P ROBLEM is a simpler
worse than RENÉ on ranges up to length 32. When the dataset problem that we will use as a building block in our algorithms.
contains much higher number of ranges, LIC always performs It only searches for a neighbor close enough to the query
worse than RENÉ. point, or discovers that there is no such neighbor at all. It is
Figure 7 shows the bit requirement of each encoding tech- formally defined in Definition 2.
nique, given the maximal length of encoded ranges, assuming Using RENÉ’s encoding function tcode , a single ternary
a 16-bits range field. In addition, it shows the lower bound match can determine whether a given d-dimensional point is
BREMLER-BARR et al.: ENCODING SHORT RANGES IN TCAM WITHOUT EXPANSION 845

Fig. 8. Illustration of the two alternative algorithms for Nearest Neighbor Search using TCAM. Left: Encoding nested cubes around each point in the
database. A query is a point in this encoding, and the result is the smallest cube encompassing the query point. Right: Encoding cubes around the query points
and the data is encoded as points. A query is a sequence of nested cubes in increasing edge length. The result is the first data point that matches a cube.

Algorithm 3 Encoding Function for a d-Dimensional Point are sorted by the value of h: the smaller h is, the higher the
1: function TCODE (p[], d, hmax ) priority of the entry.
2: word ← ε Given a query point q ∈ [0, w)d , we use tcode to build
3: for i ← 1 to d do a d-dimensional point representation for maximal edge length
4: word ← word + tcode(p[i], hmax ) of hmax , and use a single TCAM lookup to find the smallest
5: end for cube that contains the point q. The TCAM returns the highest
priority entry that matches, which is the entry of the cube that
6: return word
is centered at some point p, has the shortest edge length, and
7: end function
contains q. An example is shown in Figure 8 (left). Note that
in general, p is not necessarily the exact nearest neighbor of q
Algorithm 4 Encoding Function for a d-Dimensional Cube (as there may be more than one such cube with the same edge
1: function TCODE (p[], d, h, hmax ) length h). However, the distance (under ∞ ) of q from its exact

2: word ← ε nearest neighbor is strictly more than 12 maxh ∈H {h < h} .
3: for i ← 1 to d do As we will show later, by carefully choosing the edge length
4: word ← word + tcode([p[i] − h/2 , p[i] + set, we can obtain a c = 1 + ε approximation factor, where
h/2 ], hmax ) the size of H is inversely proportional to ε.
5: end for In our memory-efficient method, the data points and query
6: return word points switch roles: we store in the TCAM a single entry for
7: end function
each data point. The order of the entries does not matter. Upon
a query q, we construct a sequence of |H| cubes centered in
p with edge lengths in H. Then, we perform TCAM lookups
with cubes of increasing edge length values until a match is
inside a given d-dimensional cube: To encode a d-dimensional found. As in the previous method, if a point was matched with
point, or a d-dimensional cube, each coordinate is encoded a query of edge length h, then it is a solution of the h/2-N EAR
using the tcode function, and the codewords of all d N EIGHBOR R EPORT P ROBLEM.
coordinates are concatenated into a single ternary word.
1) Analysis of Approximation: Let H = {h1 , h2 , . . . , hmax }
The encoding functions for a d-dimensional point and for a
such that hi < hj for each i < j. Matching a data point
d-dimensional cube are shown in Algorithm 3 and in
p corresponding
  to a cube with edge length hi implies that
Algorithm 4, respectively.
D(p, q) ≤ h2i (where D is defined under ∞ ). Sincehi is
the first edge length to be matched, D(s∗ , q) ≥ hi−1 2 +1
A. Approximate Nearest-Neighbor Search (s∗ is the exact nearest neighbor of q). This implies that under
Our A PPROXIMATE N EAREST-N EIGHBOR S EARCH algorit- ∞ , both methods solve the c-A PPROXIMATE -N EAREST-
hi /2
hms solve in fact multiple instances of the r-N EAR N EIGHBOR N EIGHBOR P ROBLEM for c = maxhi ∈H hi−1 /2+1 , where
R EPORT P ROBLEM for increasing values of r. In ∞ , the value th
h is the i smallest element in H and h = 1 ∈ H.3
i 1
of r defines a cube around each data point p such that for all In order to get the exact nearest neighbor in ∞ , one can
query points q inside that cube, p is a valid solution of the choose H to be the set of odd numbers. Reducing the size
r-N EAR N EIGHBOR R EPORT P ROBLEM with q, and for all of H reduces the number of required entries, but decreases
query points outside that cube p is not a valid solution. the quality of the results. For example, to get a c-approximate
Our time-efficient method solves the A PPROXIMATE solution, H can consist of all even values up to 2/(c−1), along
N EAREST-N EIGHBOR S EARCH in a single TCAM lookup. with the values of a geometric series starting at 2/(c−1), with
Given a set H of edge lengths, let hmax = maxh H. For each the parameter c.
point p ∈ S and h ∈ H we store a TCAM entry representing a
d-dimensional cube centered at p, with edge length h. Entries 3 To get a bounded approximation ratio, 1 must be added to H.
846 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 26, NO. 2, APRIL 2018

When distances are defined under p norms,√ for finite values Algorithm 5 Exact k-N EAREST N EIGHBORS S EARCH Algo-
of p ≥ 1, the approximation ratio is at most c· p d in p , where rithm in p
c is the approximation ratio in ∞ . 1: function FIND - EXACT- KNN (q, S, k)
2) Database Update: Our algorithms allow efficient hot 2: N =∅  Candidate neighbors set
updates in the lookup database (the set S). Deletion of 3: hlast = −1
data points is trivial (simply delete all corresponding entries 4: repeat
from the TCAM). When using the time-efficient method, 5: (s, h) ← T CAM L OOKUP (q, S)
efficient addition of new points is possible by keeping some  returns the datapoint and correponding edge length
empty TCAM entries between entries of different edge length, 6: if |N | < k or hlast = −1 or h = hlast then
by adding entries for the corresponding cubes in these empty
7: N ← N ∪ N (s, h)
slots. Also, one can track deletion for more empty slots.
8: hlast ← h
Nevertheless, this further increases space requirement.
9: end if
When using the memory-efficient method, the situation is
10: until |N |  k and h > hlast
simpler: since the order of entries is not important, point
11: R ← arg minks ∈N Dp (s , q)  k min-distance points
addition or deletion requires a single TCAM entry update.
12: return R
13: end function
B. Exact Nearest-Neighbor Search in p
√
Our algorithms achieve p d approximate solution under p
norm. We suggest the following extension to find (exactly) the norm in the dq -dimensional space. Namely, for a p-norm,
nearest neighbor under p : For each data point s ∈ S and for ⎛ ⎞1/p
each edge length h ∈ H, we precompute√the neighborhood
set N (s, h) = {s ∈ S | Dp (s, s ) ≤ h p d}, where Dp is D(a, b)|Dq = ⎝ |ai − bi |p ⎠ .
i∈Dq
the distance between the two points under the p-norm. The
neighborhood sets are stored in memory. Precomputing these This problem is useful when some features in the vector are
sets is possible since datasets are relatively static and the not important for a specific query or user, and in traditional
neighborhood sets do not depend on the query points. computing models it is known to be more difficult [67] than
√ Since for every two points, the distance in p is at most the nearest neighbor problem, where all relevant dimensions
p
d the distance in ∞ , we immediately conclude that if the are given a-priori. For example, LSH (and its extension to
algorithms described in Section V-A return a data point s for TCAMs, TLSH [7]) cannot be used to solve this problem.
query point q with some distance h ∈ H, then the exact nearest However, our solution for the NN problem can be used
neighbor in p of q is in N (s, h). instantly to solve the partial match problem.
While this method requires additional computations follow- Under the maximum norm ∞ , a PARTIAL M ATCH solution
ing the TCAM lookup, in most datasets the number of points is to replace, in the queries, all the bits corresponding to
in N (s, h) would be very small. In our experiments (see coordinates in irrelevant dimensions with * bits. We replace
Section V-E) N (s, h) contained only s itself for lower values coordinates in queries and not for data point, as the relevant
of h in most cases and was small even for higher values of dimensions are selected per query. This technique works both
h. Thus, the time required to find the exact nearest neighbor for our time-efficient and memory-efficient methods.
is still much shorter than that required for brute-force over all For p , our solution results in p dq approximation, where dq
points in the database. is the dimension of the specific query. The extensions
The precomputed neighborhood sets can also be used to find to EXACT NEAREST NEIGHBOR SEARCH and k– NEAREST
k-nearest neighbors instead of only one. However, the number NEIGHBORS SEARCH, as described in Section V-B, work also
of neighbors in these sets might be smaller than k, so one for this problem. The neighborhood sets are precomputed
TCAM lookup might not suffice. To find the set of k exact on the d-dimensional space, but queries and distance com-
nearest neighbors, the lookup process should continue until putations after queries are done on the specific dq dimen-
k or more neighbors are found, and also until no more sional space. The results are still correct as distances in
neighbors are found in cubes whose edge length is equal to the dq -dimensional space are bounded by distances in the
that of previous neighbors. This process is formally described d-dimensional space.
in Algorithm 5, assuming a multi-match technique such as the
one presented in [14] is used.
D. Geometric Clustering on TCAM
Another closely related problem that could benefit from
C. Algorithms for the Partial Match Problem using TCAM with RENÉ is high-dimensional geometric
The PARTIAL M ATCH P ROBLEM is defined as follows: clustering. The k- MEANS CLUSTERING problem, for exam-
Definition 7: Given a set of data points S = {pi }ni=1 , ple, is usually solved as a sequence of nearest-neighbor
pi ∈ Zd , a query point q ∈ Zd , and a subset of the dimensions search problems, each of these consists of a database with k
Dq ⊆ {1, . . . , d} of size dq < d, T HE PARTIAL M ATCH d-dimensional points [68].
P ROBLEM is to find the point s∗ = arg mins ∈S D(s , q)|Dq , Algorithm 6 shows how the traditional k- MEANS CLUS -
where D(a, b)|Dq is the distance between a and b under some TERING algorithm can be implemented on TCAM using our
BREMLER-BARR et al.: ENCODING SHORT RANGES IN TCAM WITHOUT EXPANSION 847

Algorithm 6 k-M EANS C LUSTERING Algorithm on TCAM

1: function FIND - K - MEANS (S, k)
2: changed ← f alse
3: t←1
4: Randomly select D ← {d1 , . . . , dk } ⊆ S (|D| = k)
5: for i ← 1 to k do
6: C0i ← ∅
7: C1i ← ∅
8: end for
9: repeat
10: Clear TCAM
11: for h ← 1 to H do
12: for i ← 1 to k do
13: Add tcode (di , h) to end of TCAM Fig. 9. Throughput comparison of the various algorithms for solving the
14: end for nearest neighbor problem, as a function of the size of the search database.
Throughput of TCAM-based algorithms is simulated based on 360 M Hz
15: end for TCAM throughput. We denote TLSH with one TCAM lookup per r-Near
16: for each s ∈ S do Neighbor Report Problem instance as time-efficient, and TLSH with log(1/ε)
17: di ← query TCAM with tcode (s) TCAM lookups per instance as space-efficient.
18: if s ∈ i
/ Ct−1 then TCAM is used for packet classification for OpenFlow 1.3.
19: changed ← true Using the OpenFlow interface to the switch, we mapped each
20: Cti ← Cti ∪ {s} entry produced by our algorithms to a set of header fields.
21: end if A commercial traffic generator injected manually crafted pack-
22: end for ets that contain the queries in their headers, where each query
23: if changed then is broken into header fields in the same way TCAM entries
24: for i ← 1 to k do are stored.
25: di ← center of Cti We verified correctness by counting the number of matches
26: i
Ct+1 ←∅ of each TCAM entry. Using one ingress port the switch
27: end for easily achieved a throughput of 1.5M queries per second,
28: t←t+1 which is the upper bound of the link between the traffic
29: changed ← f alse generator and the switch (but not of the TCAM). Using
30: end if 24 ingress ports we achieved throughput of 35.69M queries
31: until changed = f alse per second (almost 1.5M × 24). Hence, the bottleneck was not
32: return D = {d1 , . . . , dk } in the TCAM: If we had more ports we could have reached
33: end function much higher throughput, as contemporary TCAM devices are
capable of query throughput of 360M to 1.6 billion queries
per second [38], [39].
encoding function tcode , under ∞ norm. As k is usually 2) Simulation Results: We compared our results to the
much smaller than the number of points, this solution requires results of brute-force exact nearest neighbor (using MAT-
relatively low TCAM space. Still, a standard TCAM can LAB or on GPU [37]), locality sensitive hashing [33], [51]
support up to thousands of clusters using this algorithm. (using implementation from [71]), and TLSH [7]. LSH approx-
imated results in 2 were comparable to our approximated
results in 2 only when LSH used the most complex hash
E. Evaluation and Experimental Results functions, or when used very large bins. Both options mean
We evaluate our nearest-neighbor algorithms using an image longer computation time due to either more complex hash
similarity search application (using GIST [69] descriptors), computation or much more distance computations.
on a real-life image dataset [70]. We then compare the results Figure 9 presents a comparison of the throughput (queries
and performance with prior-art solutions. Our evaluation is per second) of CPU implementations of LSH [71], GPU imple-
based both on experiments with real-life TCAM devices and mentation [37], TLSH [7] simulation, and RENÉ simulation.
simulations. Each image in the dataset was encoded as a Each line in the figure presents the throughput of a single
GIST vector in R512 , downsampled to R40 and quantified algorithm/implementation, as a function of the number of data
to {0, . . . , 255}40 before performing search. Images were points in the dataset.4
randomly partitioned to a dataset of 21, 019 images a query For the TCAM simulations we used a software simulation
set of 1, 000 images. with unbounded memory limits for the TCAM, 360MHz
1) Experiment With a TCAM Device: Since there is no throughput, with 50 cycles latency per query.
evaluation board for such devices, we used a commodity
4 LSH implementations were ran on an Intel Core i7 2600 3.4GHz CPU.
network switch (Quanta T1048-LB9) that contains a TCAM
We used the same dataset and queries for our algorithms, LSH and TLSH.
for our experiment (similarly to [7]). This switch has 48 TCAM algorithms used 10 different cube sizes. GPU throughput is as reported
1 Gbps ports, each handling at most 1.5M packets per second. in [37] for the closest lower values of n and d.
848 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 26, NO. 2, APRIL 2018

The required TCAM space for our space efficient method R EFERENCES
is 8M bits and for our time efficient method with 10 different [1] W. Jiang, Q. Wang, and V. K. Prasanna, “Beyond TCAMs: An SRAM-
cube sizes is 80M bits, with 440 bits wide entries. These based parallel multi-pipeline architecture for terabit IP lookup,” in Proc.
requirements are available in most modern TCAM devices. INFOCOM, 2008, pp. 1786–1794.
[2] V. C. Ravikumar and R. Mahapatra, “TCAM architecture for IP lookup
TLSH requires much higher TCAM capacity and much wider using prefix properties,” IEEE Micro, vol. 24, no. 2, pp. 60–69,
TCAM entries. Mar./Apr. 2004.
3) Geometric Clustering Analysis: In this section we ana- [3] OpenFlow Switch Specification Version 1.3.2, Open Netw. Found.,
lyze the running time of Algorithm 6. We define i to be Menlo Park, CA, USA, Apr. 2013.
[4] A. Bremler-Barr, D. Hay, and Y. Koral, “CompactDFA: Scalable pattern
the number of iterations until convergence, Tc as the time matching using longest prefix match solutions,” IEEE/ACM Trans. Netw.,
for completing a single TCAM cycle, T as the number of vol. 22, no. 2, pp. 415–428, Apr. 2014.
cycles required for TCAM to complete a request,5 and Tclear [5] A. Goel and P. Gupta, “Small subset queries and bloom filters using
ternary associative memories, with applications,” in Proc. SIGMETRICS,
as the time to clear the whole TCAM. Given the set of points 2010, pp. 143–154.
S, the set of edge lengths H and the number of clusters k, [6] M. Moshref, M. Yu, R. Govindan, and A. Vahdat, “DREAM: Dynamic
the running time of the algorithm is: resource allocation for software-defined measurement,” in Proc.
SIGCOMM, 2014, pp. 419–430.
Θ(i · (Tc · (k|H| + T · (1 + |S|)) + Tclear )) [7] R. Shinde, A. Goel, P. Gupta, and D. Dutta, “Similarity search and
locality sensitive hashing using ternary content addressable memories,”
4) Comparison to TLSH: As recalled, Shinde et al. [7] in Proc. SIGMOD, 2010, pp. 375–386.
were the first to suggest using TCAM for nearest neighbor [8] ETSI. (Oct. 2012). Network Function Virtualization. [Online]. Available:
[Link]
search. They use a ternary variant of the Locality Sensitive [9] R. Wang, D. Butnariu, and J. Rexford, “OpenFlow-based server load
Hashing, called TLSH, to provide a probabilistic solution for balancing gone wild,” in Proc. Hot-ICE, 2011, p. 12.
the nearest neighbor problem. The main advantages of our [10] Radware. (2014). DefenseFlow—SDN Applications and DDoS Attack
Defense. [Online]. Available: [Link]
algorithms over TLSH are that our time-efficient algorithm DefenseFlow/
solves multiple instances of the r-N EAR -N EIGHBOR R EPORT [11] M. S. Seddiki et al., “FlowQoS: QoS for the rest of us,” in Proc.
P ROBLEM in a single TCAM lookup, while TLSH requires HotSDN, 2014, pp. 207–208.
|H| lookups (hence the factor of 10 difference in the results [12] V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, “Fast and
scalable layer four switching,” in Proc. SIGCOMM, 1998, pp. 191–202.
presented in Figure 9), and that the TCAM space requirements, [13] E. Spitznagel, D. Taylor, and J. Turner, “Packet classification using
and specifically and more importantly TCAM entry width extended TCAMs,” in Proc. ICNP, 2003, pp. 120–131.
requirement, are lower in at least one order of magnitude [14] K. Lakshminarayanan, A. Rangarajan, and S. Venkatachary, “Algo-
rithms for advanced packet classification with ternary CAMs,” in Proc.
than those of TLSH. Furthermore, our algorithms provide SIGCOMM, 2005, pp. 193–204.
deterministic results and are not subject to probabilistic errors, [15] A. Bremler-Barr and D. Hendler, “Space-efficient TCAM-based classi-
and they allow database hot updates. fication using Gray coding,” in Proc. INFOCOM, 2007, pp. 1388–1396.
[16] Y.-K. Chang and C.-C. Su, “Efficient TCAM encoding schemes for
packet classification using Gray code,” in Proc. GLOBECOM, 2007,
VI. C ONCLUSION pp. 1834–1839.
While the problem of range encoding on TCAM has been [17] H. Che, Z. Wang, K. Zheng, and B. Liu, “DRES: Dynamic range
encoding scheme for TCAM coprocessors,” IEEE Trans. Comput.,
deeply investigated over recent years, the proven theoretical vol. 57, no. 7, pp. 902–915, Jul. 2008.
limits on the number of bits one must use have diverted [18] H. Liu, “Efficient mapping of range classifier into ternary-CAM,” in
researchers to use row expansion. However, row expansion Proc. 10th Symp. High Perform. Interconnects, 2002, pp. 95–100.
causes exponential increment in the number of TCAM entries. [19] J. V. Lunteren and T. Engbersen, “Fast and scalable packet classifi-
cation,” IEEE J. Sel. Areas Commun., vol. 21, no. 4, pp. 560–571,
New applications such as SDN implementations for load May 2003.
balancing, security tools, and NFV frameworks use more than [20] A. Bremler-Barr, D. Hay, and D. Hendler, “Layered interval codes
a few range fields. Thus, row expansion makes solutions that for TCAM-based classification,” Comput. Netw., vol. 56, no. 13,
pp. 3023–3039, Sep. 2012.
use it impractical. [21] O. Rottenstreich, I. Keslassy, A. Hassidim, H. Kaplan, and E. Porat, “On
In this paper we introduce the sub-problem of short range finding an optimal TCAM encoding scheme for packet classification,”
encoding, and we show that the theoretical limits on the in Proc. INFOCOM, 2013, pp. 2049–2057.
[22] Q. Dong, S. Banerjee, J. Wang, D. Agrawal, and A. Shukla, “Packet
number of required bits can be lowered in this situation. classifiers in ternary CAMs can be smaller,” in Proc. SIGMETRICS,
We present RENÉ: An encoding scheme for short ranges, 2006, pp. 311–322.
and show that it is closer to the lower bound than any other [23] C. R. Meiners, A. X. Liu, and E. Torng, “TCAM Razor: A systematic
technique. We then present multiple applications that may approach towards minimizing packet classifiers in TCAMs,” in Proc.
ICNP, Oct. 2007, pp. 266–275.
benefit from such short range encoding, in the area of packet [24] C. R. Meiners, A. X. Liu, and E. Torng, “Topological transformation
classification. Furthermore, we propose to use TCAM as a co- approaches to optimizing TCAM-based packet classification systems,”
processor for solving problems outside of the networking field, in Proc. SIGMETRICS, 2009, pp. 73–84.
[25] J. S. Beis and D. G. Lowe, “Shape indexing using approximate nearest-
such as the nearest neighbor problem and its variants, which neighbour search in high-dimensional spaces,” in Proc. IEEE Comput.
so far has been known to take very long time to compute. Soc. Conf. Comput. Vis. Pattern Recognit., Jun. 1997, pp. 1000–1006.
We show that using TCAM, one could solve such problems [26] M. Brown and D. G. Lowe, “Recognising panoramas,” in Proc. ICCV,
vol. 3. 2003, p. 1218.
in much higher rates than previously suggested solutions, [27] L. Liang, C. Liu, Y.-Q. Xu, B. Guo, and H.-Y. Shum, “Real-time texture
and outperform known lower bounds in traditional memory synthesis by patch-based sampling,” ACM Trans. Graph., vol. 20, no. 3,
models. pp. 127–150, 2001.
[28] J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman, “Object
5 TCAM works in a pipeline, where a request is processed over multiple retrieval with large vocabularies and fast spatial matching,” in Proc.
cycles, but at each cycle a new request may begin. CVPR, 2007, pp. 1–8.
BREMLER-BARR et al.: ENCODING SHORT RANGES IN TCAM WITHOUT EXPANSION 849

[29] D. G. Lowe, “Object recognition from local scale-invariant features,” [57] V. Garcia, E. Debreuve, and M. Barlaud, “Fast k nearest neigh-
in Proc. 7th IEEE Int. Conf. Comput. Vis., vol. 2. Sep. 1999, bor search using GPU,” in Proc. IEEE CVPR, Jun. 2008, pp. 1–6,
pp. 1150–1157. doi: 10.1109/CVPRW.2008.4563100.
[30] H. Samet, Foundations of Multidimensional and Metric Data Structures. [58] S. Liang, C. Wang, Y. Liu, and L. Jian, “CUKNN: A parallel implemen-
San Mateo, CA, USA: Morgan Kaufmann, 2006. tation of K-nearest neighbor on CUDA-enabled GPU,” in Proc. YC-ICT,
[31] J. L. Bentley, “Multidimensional divide-and-conquer,” Commun. ACM, 2009, pp. 415–418.
vol. 23, no. 4, pp. 214–229, 1980. [59] J. Pan and D. Manocha, “Fast GPU-based locality sensitive hashing for
[32] N. Beckmann, H.-P. Krıegel, R. Schneider, and B. Seeger, K-nearest neighbor computation,” in Proc. GIS, 2011, pp. 211–220.
“The R*-tree: An efficient and robust access method for points [60] P. Bosshart et al., “P4: Programming protocol-independent packet
and rectangles,” in Proc. ACM Sigmod Rec., 1990, vol. 19. no. 2, processors,” Comput. Commun. Rev., vol. 44, no. 3, pp. 87–95, 2014.
pp. 322–331. [61] Radware. (Oct. 2014). Tsunami SYN Flood Attack—A New Trend in
[33] A. Andoni and P. Indyk, “Near-optimal hashing algorithms for approx- DDoS Attacks? [Online]. Available: [Link]
imate nearest neighbor in high dimensions,” Commun. ACM, vol. 51, 2014/10/tsunami-syn-flood-attack/
no. 1, pp. 117–122, Jan. 2008. [62] G. Pazi, A. Bremler-Bar, R. Rivlin, and D. Touitou, “Protecting against
[34] R. Weber, H.-J. Schek, and S. Blott, “A quantitative analysis and distributed denial of service attacks,” U.S. Patent 2003 0 110 274 A1.
performance study for similarity-search methods in high-dimensional Jun. 12, 2003. [Online]. Available: [Link]
spaces,” in Proc. VLDB, 1998, pp. 194–205. US20030110274
[63] C. Jin, H. Wang, and K. G. Shin, “Hop-count filtering: An effective
[35] M. Muja and D. G. Lowe, “Fast approximate nearest neighbors
with automatic algorithm configuration,” in Proc. VISAPP, 2009, defense against spoofed DDoS traffic,” in Proc. CCS, 2003, pp. 30–41.
pp. 331–340. [64] A. Gupta et al., “SDX: A software defined internet exchange,” in Proc.
SIGCOMM, 2014, pp. 551–562.
[36] F. Gray, “Pulse code communication,” U.S. Patent 2 632 058 A,
[65] AS Names—CIDR Report. Accessed: Jan. 29, 2018. [Online]. Available:
Mar. 17, 1953.
[Link]
[37] V. Garcia, É. Debreuve, F. Nielsen, and M. Barlaud, “K-nearest neigh- org/as2.0/[Link]
bor search: Fast GPU-based implementations and application to high- [66] (2014). Ryu SDN Controller. [Online]. Available: [Link]
dimensional feature matching,” in Proc. ICIP, 2010, pp. 3757–3760. io/ryu/
[38] Renesas Electronics America Inc. 20 Mbit QUAD-Search Content [67] A. Borodin, R. Ostrovsky, and Y. Rabani, “Lower bounds for high
Addressable Memory. Accessed: Jul. 11, 2016. [Online]. Available: dimensional nearest neighbor search and related problems,” in Proc.
[Link] STOC, 1999, pp. 312–321.
[39] C. Inc. (2014). NEURON Search Processors. [Online]. Available: [68] S. P. Lloyd, “Least squares quantization in PCM,” IEEE Trans. Inf.
[Link] Theory, vol. IT-28, no. 2, pp. 129–137, Mar. 1982.
[40] I. Corp. (2011). Intel Xeon Processor E7-4870. [Online]. Available: [69] A. Oliva and A. Torralba, “Modeling the shape of the scene: A holistic
[Link] representation of the spatial envelope,” Int. J. Comput. Vis., vol. 42,
[41] Nvidia. (Nov. 2014). Tesla K80 GPU Accelerator. [Online]. no. 3, pp. 145–175, 2001.
Available: [Link] [70] B. C. Russell, A. Torralba, K. P. Murphy, and W. T. Freeman, “LabelMe:
07317-001_v04.pdf A database and Web-based tool for image annotation,” Int. J. Comput.
[42] O. Rottenstreich and I. Keslassy, “Worst-case TCAM rule expansion,” Vis., vol. 77, nos. 1–3, pp. 157–173, 2008.
in Proc. INFOCOM, 2010, pp. 1–5. [71] M. Aly, M. Munich, and P. Perona, “Indexing in large scale image
[43] O. Rottenstreich and I. Keslassy, “On the code length of TCAM coding collections: Scaling properties and benchmark,” in Proc. WACV, 2011,
schemes,” in Proc. ISIT, 2010, pp. 1908–1912. pp. 418–425.
[44] K. Kogan, S. I. Nikolenko, O. Rottenstreich, W. Culhane, and P. Eugster,
“Exploiting order independence for scalable and expressive packet
classification,” IEEE/ACM Trans. Netw., vol. 24, no. 2, pp. 1251–1264,
Apr. 2016. Anat Bremler-Barr received the Ph.D. degree
[45] K. Kogan, S. I. Nikolenko, P. Eugster, A. Shalimov, and O. Rottenstreich, (Hons.) in computer science from Tel Aviv Uni-
“Efficient FIB representations on distributed platforms,” IEEE/ACM versity, Tel Aviv, Israel. In 2001, she co-founded
Trans. Netw., vol. 25, no. 6, pp. 3309–3322, Dec. 2017. and was the Chief Scientist of Riverhead Networks,
[46] K. Kogan, S. Nikolenko, O. Rottenstreich, W. Culhane, and P. Eugster, Inc. (acquired by Cisco Systems in 2004), which
“SAX-PAC (scalable and expressive packet classification),” in Proc. provided systems to protect from denial-of-service
SIGCOMM, 2014, pp. 15–26. attacks. She then joined the Interdisciplinary Cen-
[47] C. R. Meiners, A. X. Liu, and E. Torng, “Bit Weaving: A non-prefix ter Herzliya, Herzliya, Israel, in 2004, where she
approach to compressing packet classifiers in TCAMs,” in Proc. ICNP, co-founded (with Prof. D. Hay) the DEEPNESS
2009, pp. 93–102. Laboratory (funded by an ERC starting grant) that
[48] K. Zheng, H. Che, Z. Wang, B. Liu, and X. Zhang, “DPPC-RE: TCAM- focuses on designing deep packet inspection for
based distributed parallel packet classification with range encoding,” next-generation network devices. She is currently an Associate Professor
IEEE Trans. Comput., vol. 55, no. 8, pp. 947–961, Aug. 2006. with the School of Computer Science, Interdisciplinary Center Herzliya. Her
[49] C. R. Meiners, A. X. Liu, E. Torng, and J. Patel, “Split: Optimizing research interests include computer networks and network security.
space, power, and throughput for TCAM-based classification,” in Proc.
ANCS, 2011, pp. 200–210.
[50] Y. Afek, A. Bremler-Barr, and L. Schiff, “Recursive design of hardware
priority queues,” in Proc. SPAA, 2013, pp. 23–32.
[51] P. Indyk and R. Motwani, “Approximate nearest neighbors: Towards
removing the curse of dimensionality,” in Proc. STOC, 1998, Yotam Harchol received the Ph.D. degree from the
pp. 604–613. Hebrew University of Jerusalem, Israel, in 2017.
[52] J. L. Bentley, “Multidimensional binary search trees used for associative Before joining the University of California at
searching,” Commun. ACM, vol. 18, no. 9, pp. 509–517, 1975. Berkeley (UC Berkeley), Berkeley, CA, USA, he
[53] S. Dasgupta and Y. Freund, “Random projection trees and low dimen- was a Post-Doctoral Researcher with VMware
sional manifolds,” in Proc. STOC, 2008, pp. 537–546. Research. He is currently a Post-Doctoral Scholar
[54] A. Gionis, P. Indyk, and R. Motwani, “Similarity search in high (with Prof. S. Shenker) with the Department of
dimensions via hashing,” in Proc. VLDB, 1999, pp. 518–529. Electrical Engineering and Computer Science, UC
[55] Q. Lv, W. Josephson, Z. Wang, M. Charikar, and K. Li, “Multi-probe Berkeley. His research interests include software-
LSH: Efficient indexing for high-dimensional similarity search,” in Proc. defined networking, network security, and high-
VLDB, 2007, pp. 950–961. performance algorithms for network middleboxes.
[56] Y. Tao, K. Yi, C. Sheng, and P. Kalnis, “Quality and efficiency in He was the recipient of the Intel Award for Graduate Students in 2010,
high dimensional nearest neighbor search,” in Proc. SIGMOD, 2009, the Hammer Fellowship for Master Students in 2009, and the Chais Scholar-
pp. 563–576. ship for Social Leadership in 2007.
850 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 26, NO. 2, APRIL 2018

David Hay received the B.A. degree (summa cum Yacov Hel-Or received the Ph.D. degree in com-
laude) and the Ph.D. degree in computer science puter science from the The Hebrew University of
from the Technion Israel Institute of Technology, Jerusalem. He was a Visiting Scientist with Google
Haifa, Israel, in 2001 and 2007, respectively. In addi- Inc. and a Research Scientist with Amazon from
tion, he was with: the IBM Haifa Research Laborato- 2016 to 2018. Prior to this, he held post-doctoral
ries, Haifa; Cisco Systems, San Jose, CA, USA; the positions with the Weizmann Institute of Science
Electronic Department, Politecnico di Torino, Turin, and the NASA Ames Research Center, California.
Italy; and the Electrical Engineering Department He is currently a Faculty Member with the School
with Columbia University, New York, NY, USA. of Computer Science, Interdisciplinary Center Her-
In 2010, he co-founded (with Prof. A. Brembler- zliya, Israel. His main research interests include
Barr) the DEEPNESS laboratory, focusing on deep computer vision, image processing, and computer
packet inspection in next-generation network devices. He is currently an graphics.
Associate Professor with The Rachel and Selim Benin School of Computer
Science and Engineering, The Hebrew University of Jerusalem, Jerusalem,
Israel. His research interests include computer networks in particular, network
algorithmics, packet classification, deep packet inspection, network survivabil-
ity, and software-defined networking.