[ovs-dev] [PATCH v4 6/6] Classifier: Track address prefixes.

Jarno Rajahalme jrajahalme at nicira.com
Tue Dec 3 23:53:27 UTC 2013


On Dec 3, 2013, at 9:11 AM, Ben Pfaff <blp at nicira.com> wrote:

> On Tue, Nov 26, 2013 at 11:24:52AM -0800, Jarno Rajahalme wrote:
>> Add a prefix tree (trie) structure for tracking the used address
>> space, enabling skipping classifier tables containing longer masks
>> than necessary for an address field value in a flow being classified.
>> This enables less unwildcarding for datapath flows in parts of the
>> address space without host routes.
>> 
>> Trie lookup is interwoven to the staged lookup, so that a trie is
>> searched only when the configured trie field field becomes relevant
>> for the lookup.  The trie lookup results are retained so that each
>> trie is checked at most once for each classifier lookup.
>> 
>> This implementation tracks the number of rules at each address prefix
>> for the whole classifier.  More aggressive table skipping would be
>> possible by maintaining lists of tables that have prefixes at the
>> lengths encountered on tree traversal, or by maintaining separate
>> tries for subsets of rules separated by metadata fields.
>> 
>> Prefix tracking is configured via OVSDB.  A new column "fieldspec" is
>> added to the database table "Flow_Table".  "fieldspec" is a string map
>> with only the "prefix" key defined so far (other keys can be added in
>> future):
>> 
>> "prefix"   A comma separated list of field names for which prefix
>>           lookup should be used.
>> 
>> As of now, the fields for which prefix lookup can be enabled are:
>> - tun_id, tun_src, tun_dst
>> - metadata
>> - nw_src, nw_dst (or aliases ip_src and ip_dst)
>> - ipv6_src, ipv6_dst
>> 
>> There is a maximum number of fields that can be enabled for any one
>> flow table.  Currently this limit is 3.
>> 
>> Examples:
>> 
>> ovs-vsctl set Bridge br0 flow_tables:0=@N1 -- \
>> --id=@N1 create Flow_Table name=table0
>> ovs-vsctl set Bridge br0 flow_tables:1=@N1 -- \
>> --id=@N1 create Flow_Table name=table1
>> 
>> ovs-vsctl set Flow_Table table0 fieldspec:prefix=tun_id
>> ovs-vsctl set Flow_Table table1 fieldspec:prefix=ip_dst,ip_src
>> 
>> ovs-vsctl remove Flow_Table table1 fieldspec prefix
>> 
>> Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
> 
> Thank you!
> 
> I reviewed the schema and documentation first.  Here are some comments.
> I will look at the code next.
> 
> Thanks,
> 
> Ben.
> 
> 
> Schema
> ======
> 
> I think that there is a lot to think about in the schema.  The name
> "fieldspec" for the column implies that it makes sense to group
> everything related to fields together, but there is already one
> exception (the "groups" column already names fields, or actually
> subfields).
> 
> Making the new column a string map implies that later we might add more
> field-related configuration, but do we intend to do that (do you have
> any ideas already)?

I think Ethan had plans for more on this… nothing fully baked yet, though.

>  If we don't have any solid ideas, then I'd be
> inclined to make this an "optional string" or "set of strings" column
> instead of a "map" column.
> 
> The existing "groups" column sets two precedents here.  They might not
> be relevant.  I'll explain.
> 
> The first precedent is for naming fields by their NXM or OXM names.  I
> seem to recall that I did it that way because those names are already
> standardized (in the ONF documents, for OXM) or semi-standardized (in
> nicira-ext.h) and because there was an existing syntax for subfields.
> However, that may not be a good precedent to follow here, since the
> short names are more or less carved in stone too due to long use and
> because we don't care about subfields (yet? If you think subfield
> prefixes will make sense someday, speak up), so your judgment is
> important on this.

I do not see a need for prefix tracking for subfields, it really makes sense
for full addresses only (skipping the beginning of a prefix would make the
visible address space overlapping, and not using the full address would
lose the ability to handle host routes). Even for IPv6 you’d NOT need to
limit the processing to the first 64-bits; if the flow table contains only
proper prefixes (no host routes) the tree depth will automatically be limited
to the depth of the longest prefix in the flow table.

> 
> The second precedent is that "groups" is a set of field names rather
> than a comma-separated list.  That is a little cleaner, in my opinion.
> However, it might not apply here because I think we need an ordered list
> of prefixes and a set is not ordered.
> 

The ordering is not important, so a set would be fine as well.

> Documentation
> =============
> 
> I would mention this in NEWS.
> 

Will do.

> I think that this is strictly an optimization, that is, it is impossible
> for an observer to tell whether address prefix tracking is enabled, or
> on which fields, by looking at treatment of packets alone, but the
> documentation does not make this clear.
> 
> The documentation doesn't explain why one would want to specify a
> particular set of fields, or the effect of the order of the fields.
> 

I clarified these points, thanks.

> The documentation XML elements are slightly off: a multi-paragraph term
> definition should be <dd><p>...</p><p>...</p></dd>, not
> <dd>...</dd><dd>...</dd>.  (It's possible that this gets formatted the
> very same way, but still...)

Noted and fixed.

  Jarno

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openvswitch.org/pipermail/ovs-dev/attachments/20131203/96611a8b/attachment-0003.html>


More information about the dev mailing list