[ovs-dev] [PATCH] classifier: Speed up classification when reg0 partitions the flow table.

Ben Pfaff blp at nicira.com
Mon Jan 14 20:02:37 UTC 2013

On Mon, Jan 14, 2013 at 09:12:34AM +0200, Jarno Rajahalme wrote:
> On Jan 12, 2013, at 2:24 , ext Ben Pfaff wrote:
> > We have a controller that puts many rules with different reg0 values into
> > the flow table, where reg0 is used (by "resubmit"s) to distinguish stages
> > in a pipeline.  Thus, any given flow only needs to be hashed into
> > classifier "cls_table"s that contain a match for the flow's reg0 value.
> > This commit optimizes the classifier lookup by (probabilistically) skipping
> > the "cls_table"s that can't possibly match.
> It would seem more natural to change the controller in question to
> use multiple tables (one for each stage of the pipeline) and
> possibly goto table instructions instead of resubmits. In addition
> to avoiding unnecessary conceptual complexity within OVS, that would
> also avoid the overhead of manipulating and matching the reg0, so
> that should be even more efficient.

The description I gave is a simplified one.  In fact, there are many
more than 255 possible "stages", the identifiers for the stages have
structured values composed of bitmasks, and the identifiers are
transmitted "across the wire" using tunnel keys with encoding and
decoding at each end.  Using multiple tables would not be sufficient.

> > This speeds up flow setup performance with the controller in question by
> > about 19%.
> I assume that the performance penalty for other types of controllers
> is rather small.

I doubt there is any measurable penalty.

> > + *
> > + * Partitioning
> > + * ============
> > + *
> > + * Suppose that a given classifier is being used to handle multiple stages in a
> > + * pipeline using "resubmit", with reg0 distinguishing between the different
> > + * stages.  For example, reg0 value 1 might identify ingress rules, reg0 value
> > + * 2 might identify ACLs, and reg0 value 3 might identify egress rules.  Such a
> > + * classifier is essentially partitioned into multiple sub-classifiers on the
> > + * basis of the reg0 value.
> > + *
> > + * The classifier has a special optimization to speed up matching in this
> > + * scenario:
> If use of multiple tables is out of the question for some reason,
> the 2nd best option would be to use the Openflow metadata instead of
> reg0 for this optimization. That would allow also strictly
> OF-compliant controllers to benefit from the partitioning
> optimization.

I could make the field used for partitioning configurable, or try to
come up with an algorithm to infer a good field for partitioning.  I
doubt the controller team would be excited about changing something
that's worked well for them for years.

More information about the dev mailing list