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 <b...@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. _______________________________________________ dev mailing list dev@openvswitch.org http://openvswitch.org/mailman/listinfo/dev
