acl-plugin: tm: add tuplemerge algorithm for relaxing the hashtable masks 62/13162/8
authorAndrew Yourtchenko <ayourtch@gmail.com>
Wed, 20 Jun 2018 08:44:19 +0000 (10:44 +0200)
committerDave Barach <openvpp@barachs.net>
Wed, 27 Jun 2018 11:46:28 +0000 (11:46 +0000)
commit2e0798f90d9672b1c8dc702a2bdae485a6771ff8
treeaa49d107ea0525e4e0c55fb660cb054bb470d3e0
parentb26743d093141a2aef19bdf8a7fe06dcaa81329a
acl-plugin: tm: add tuplemerge algorithm for relaxing the hashtable masks

Slightly refactored from the initial implementation of the TupleMerge [1]
algorithm by Valerio Bruschi (valerio.bruschi@telecom-paristech.fr)

[1] James Daly, Eric Torng "TupleMerge: Building Online Packet Classifiers
by Omitting Bits", In Proc. IEEE ICCCN 2017, pp. 1-10

Also add startup parameters to turn on/off the algorithm ("use tuple merge 1/0"),
and a startup parameter to be able to tweak the split threshold
("tuple merge split threshold N"), the default value of the split threshold
is 39 as per paper, but some more tuning might be necessary to find the best
value.

This change, alongside with the optimizations which avoid extra lookups,
significantly reduces the slowdown on the ClassBench generated ACLs, which
are supposed to resemble realistic ACLs seen in use in the field.

Change-Id: I9713e4673970e9a62d4d9e9718365293375fab7b
Signed-off-by: Andrew Yourtchenko <ayourtch@gmail.com>
src/plugins/acl/acl.c
src/plugins/acl/acl.h
src/plugins/acl/hash_lookup.c