IEEE Communications Magazine - June 2017 - page 214

IEEE Communications Magazine • June 2017
0163-6804/17/$25.00 © 2017 IEEE
In modern switches, a packet can go through
a number of processing steps to determine, for
example, if the packet has to be discarded due
to security policies, if it needs to be marked for
quality of service or to determine the next hop
for the packet. Most of those steps can be mod-
eled as a matching of some of the packet fields
with a set of rules that are stored in the switch.
This has been generalized with the adoption of
Software Defined Networks, using for example,
the Openflow protocol, on which the processing
steps are programmable as table matching oper-
ations and defined dynamically by a controller.
Implementing this flexible packet matching in
a switch is challenging, as we need to support
multiple matching tables, each having different
key size, and the size of the tables should also
be programmable. The main options to support
multiple tables are to use different memories for
each table or to have several tables share the
same memories. In the first approach, each table
would have to match the size and width of the
memories to achieve an efficient memory usage.
This is a severe limitation when flexible table size
and entry width need to be supported. In the
second approach, all the tables can dynamically
share the memories, providing better flexibility.
The problem is that the width of the memories
needs to be dimensioned to support the larg-
est entry size. This leads to significant memory
waste for smaller entries. Hash based techniques
like cuckoo hashing can be used to efficient-
ly implement exact matching using standard
SRAM memories, and are widely used in mod-
ern switches. However, current implementations
only support entries of one size. This article pres-
ents the Single Double cuckoo hash, which can
support elements of two sizes. Its main benefit
is to improve memory utilization when multiple
tables with entries of different sizes share the
same memories. This is achieved at the cost of a
small increase in circuit complexity.
Over the last decades switches and routers have
evolved from being fairly simple packet forward-
ing devices to become extremely complex pack-
et processing systems [1]. At the same time port
density and speed have also increased exponen-
tially, making high speed switches one of the
hardest network elements to implement. Packet
processing on a switch includes, for example, Eth-
ernet and IP forwarding, security related functions
like access control lists and firewalls, encapsula-
tion and de-encapsulation, marking for quality
of service, and many more. For most of them,
some fields of the incoming packet have to be
checked against a set of stored rules or routes to
make a decision. Those functions can be modeled
in a generic way as table matching operations.
That is the approach taken in Software Defined
Networks (SDN), which aim to make packet for-
warding flexible and programmable [2]. In SDN,
protocols like Openflow are used to program the
tables and actions that a switch or router uses for
packet processing. A modern switch must there-
fore provide flexible table matching operations.
This flexibility includes the number of tables, their
sizes and the width of the entries.
It would seem that software running on one or
more general purpose processors or specialized
network processors can provide the flexibility to
implement programmable table matching oper-
ations. That is true, but the problem is that the
speed that can be achieved in processing packets
does not meet the speed needed in today’s high
speed switches [3, 4]. Modern high speed switch-
es typically have 32/64 ports running at 50/100
Gb/s, which makes a purely software implemen-
tation of packet processing not viable. Instead,
application specific integrated circuits (ASICs) are
used [3, 4]. However, making hardware imple-
mentations that are flexible but yet operate at
high speed is challenging [5].
Exact table matching operations can be imple-
mented in hardware using content addressable
memories (CAMs). CAMs use specialized circuit-
ry to compare the incoming value with all those
stored in the memory in parallel [6]. This means
that they perform the table matching operation
in one memory access cycle. The main draw-
back of CAMs is their high cost in terms of cir-
cuit area and power compared to standard SRAM
memories. Exact table matching can also be effi-
ciently implemented in SRAM memories using
hash tables [7]. In particular, cuckoo hashing is
an attractive option as it provides a constant and
small worst case number of hash lookups for
an exact table match operation [8]. This means
that table matching can also be done in a single
memory access cycle by using a small number
of SRAM memories operating in parallel, each
performing a hash lookup [9]. The use of SRAM
memories reduces the cost compared to CAMs,
Flexible Packet Matching with
Single Double Cuckoo Hash
Gil Levy, Salvatore Pontarelli, and Pedro Reviriego
The authors present the
Single Double Cuckoo
hash that can support
elements of two sizes.
Its main benefit is to
improve the memory
utilization when multiple
tables with entries of
different sizes share the
same memories. This is
achieved at the cost of a
small increase in circuit
Gil Levy is with Mellanox; Salvatore Pontarelli is with University of Rome Tor Vergata; and Pedro Reviriego is with Universidad Antonio de Nebrija.
Digital Object Identifier:
1...,204,205,206,207,208,209,210,211,212,213 215,216,217,218,219,220,221,222,223,224,...228
Powered by FlippingBook