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

Ben Pfaff blp at nicira.com
Wed Mar 12 05:09:24 UTC 2014


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.



More information about the dev mailing list