[ovs-dev] [PATCH 2/3] Classifier: Track IP addresses for more wildcarding.

Ben Pfaff blp at nicira.com
Wed Nov 6 05:40:46 UTC 2013


On Fri, Nov 01, 2013 at 03:20:11PM -0700, Jarno Rajahalme wrote:
> Add a prefix tree (trie) structure for tracking the used
> IP address space, enabling skipping classifier tables
> containing longer masks than necessary for the given
> address.  This enables more wildcarding for megaflows in
> parts of the address space without host routes.
> In fact, the trie lookups results are only ever used when
> they could potentially reduce the number of bits that need
> to be un-wildcarded.
> 
> This implementation creates tries for IPv4 source and
> destiantion addresses in any classifier tables those
> fields are used.  The tries are computed before checking
> any other fields, so the same tree has nodes also for
> addresses from mutually exclusive rules, making this
> implementation sub-optimal in some cases.
> 
> It should be noted that this implementation does not
> require any constraining of rule priorities, meaning
> that this is not limited to longest-prefix match policy.
> 
> To mitigate overheads controllers could concentrate IP
> address matching into specific tables.
> 
> More aggressive table skipping would be possible by
> maintaining lists of tables that have prefixes at the
> lengths encountered on tree traversal.
> 
> Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>

Ethan, do you want to take a first look at this?



More information about the dev mailing list