lib/classifier: Use a prefix tree to optimize ports wildcarding.
authorJarno Rajahalme <jrajahalme@nicira.com>
Wed, 30 Apr 2014 21:09:08 +0000 (14:09 -0700)
committerJarno Rajahalme <jrajahalme@nicira.com>
Wed, 30 Apr 2014 21:09:08 +0000 (14:09 -0700)
commit69d6040e861a6a001e65be85c0ed2aa8e60ac83e
treeacd4739d4628e6a6f793ff146d0eb600958eebb1
parentb53d5c33bc91bdd2e46c67aec3af04a4dc020e26
lib/classifier: Use a prefix tree to optimize ports wildcarding.

Using a prefix tree (aka 'trie') for transport ports matching produces
less specific (more wildcarded) datapath megaflows.

Each subtable that matches on transport ports has it's own ports trie.
This trie is consulted only after a failing lookup to determine the
number of bits that need to be unwildcarded to guarantee that any
packet that should match on any of the other rules will not match this
megaflow.

Signed-off-by: Jarno Rajahalme <jrajahalme@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>
NEWS
lib/classifier.c
tests/classifier.at