[ovs-dev] [PATCH RFC] dpif-netdev: ACL+dpcls for Wildcard matching.

Jan Scheurich jan.scheurich at web.de
Fri May 20 09:04:21 UTC 2016


> >> What we do see, however is that there is often a strong correlation
> >> between the ingress port and the subset of masks/subtables that have
> >> hits. The entire megaflow cache typically decomposes nicely into
> >> partitions that are hit only by packets entering from equivalent
> >> ports (e.g. traffic from Phy -> VM and VM -> Phy)
> >>
> >> Since megaflows are by nature non-overlapping, the search can stop at
> >> the first match. Keeping a separate list of subtables per ingress
> >> port, sorted by frequency of hits, should reduce the average number
> >> of subtables lookups to a minimum, even if the total number of
> >> subtables gets large.
> >>
> >> Has such an idea been considered?
> >
> > [Antonio F] This approach sounds interesting.
> >
> 
> I had thought of sorting the subtables periodically, but never got to do
> anything about it. Actually, I'd like to see how that performs compared to the
> ACL proposal before deciding what to do.
> 
> dpcls already uses struct pvector to store the subtables. It would be rather
> easy to use the pvector API to assign a 'priority' corresponding to the hit
> count and then sort the subtables accordingly and publish the newly ordered
> pvector for the pmd thread to use for lookups. The only extra fast path cost
> would be the incrementing of subtable hit counts.
> 
> Would the fact that each pmd thread has it's own dpcls take care of the
> separation per ingress port? I.e., if performance matters then maybe each
> port has its own pad thread?
> 
>   Jarno

The true value of sorting subtables will only materialize when having one 
sorted list per ingress port. Due to RSS and vhost-user multi-queue I am 
afraid that, when performance really matters, each port will be split over
more than one PMD and every PMD will serve many ports. There is no reason
why the assignment of port rx queues to PMD threads should in any way 
correlate to the decomposition of the megaflow cache.

So we would have to add a sorted list of subtables per ingress port to the 
PMD. One way would be to periodically sort this list based on subtable
hit counters. Another, simpler approach might be to always insert the last hit
subtable at the front of the list (a most recently used list), but that
has slightly higher cost per packet.

/Jan



More information about the dev mailing list