[ovs-dev] [PATCH] lib/classifier: Use a prefix tree to optimize ports wildcarding.

[Ethan Jackson]

Jarno doesn't have that data at the moment, so here's a summary which
you can put in the commit message if you'd like.

To test this we took real customer ACL tables, and systematically sent
every port from 1 to 65k through them to see how many megaflows are
generated.  If you do nothing, you end up with 65k megaflows.  We have
one customer who has a pretty typical firewall table, which ends up
with ~200 megaflows.  And another very extreme customer which ends up
with ~3000 megaflows.  There are techniques which are better in the
sense that they result in fewer megaflows.  But the decision tree has
the advantage of being O(1), and generating at most 16 mask patterns.

Ethan

On Tue, Mar 11, 2014 at 10:09 PM, Ben Pfaff <blp at nicira.com> wrote:
> On Mon, Mar 10, 2014 at 06:49:55PM -0700, Ethan Jackson wrote:
>> Yep this is the same thing.  I've successfully shown that this
>> algorithm is the best for our use case and was intending to implement
>> it myself.  However, for many rather complicated reasons it became
>> important to have a prototype implementation quickly, so Jarno
>> graciously offered to pound out the implementation.
>>
>> On the issue of the algorithm choice.  We tried a bunch of things, but
>> when we simulated it against some real firewall rule sets, we found
>> that the simplest is the best: a decision tree.
>
> Can we have some kind of quantitative explanation of the benefits in the
> commit message?  I know from our face-to-face discussions that you have
> measured how this reduces the number of megaflows required to cover the
> whole port space in various circumstances.