On Mon, Aug 08, 2011 at 11:04:06AM +0100, Mike Bursell wrote: > > The biggest question in my mind is not how to formulate range matches > > but how to efficiently integrate them into the classifier. Do you > > have thoughts on that? > > Could you give some more details, please? I'm not looked into this area > much yet.
Consider the case where you have a set of OpenFlow flows that match on every field, except that you have not yet determined whether they match on TCP source port. The problem is then, how do you efficiently determine which of those (if any) matches on TCP source port, and if more than one, the one with the highest priority? For this case, it boils down to the roughly the same problem as an interval tree (e.g. see the Wikipedia article of that title), except that the priority adds complication. The 2-d case (e.g. a range match on both source and destination port) needs a more sophisticated data structure (a k-d tree, an R-tree, something else?). _______________________________________________ discuss mailing list [email protected] http://openvswitch.org/mailman/listinfo/discuss
