[ovs-discuss] Port range matching
blp at nicira.com
Mon Aug 8 09:04:54 PDT 2011
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?).
More information about the discuss