On Wed, Jul 27, 2011 at 08:40:47AM +0900, Simon Horman wrote:
> On Tue, Jul 26, 2011 at 10:55:00AM -0700, Ben Pfaff wrote:
> > Memory consumption is of course one motivation for limiting the number
> > of kernel flows. Another, which may be more important, is that some of
> > ovs-vswitchd's algorithms are O(n) in the number of kernel flows.
>
> As you may have guessed from my recent posts relating to large(ish)
> number of flows, I am interesting in scaling to rather more than 1,000
> flows. And O(n) portions are something that I would be rather happy
> to see weeded out, somehow.
Let me describe the major reasons that O(n) behavior arises. Maybe a
fresh set of eyes can help.
1. To determine what flows should be retained in the kernel, and
what flows should be discarded, based on the number of packets
that have recently passed through for that flow. We also need to
do this to maintain accurate OpenFlow flow statistics.
Currently this is implemented by periodically dumping stats for
every kernel flow, clearly O(n). I don't know a better way.
2. When the OpenFlow flow table changes, we have to run all of the
existing kernel flows through the new version of the flow table
("revalidate" them), to see whether their actions should change.
It would be nice to avoid this work for flows whose actions will
not in fact change, but I do not know a general way to do that.
If you have any ideas, please do pass them along.
3. When the MAC learning table changes, either adding or removing or
changing a MAC learning entry, we have to find all of the flows
that relied on the previous value of that entry and revalidate
them. OVS uses a Bloom filter to reduce the required amount of
work to a small constant factor of the number of kernel flows in
the common case, but it's still technically O(n).
> > In the long run, my goal is to devise heuristics to figure out whether a
> > given kernel flow is likely to be worthwhile. One friend of mine
> > suggests that a "naive Bayesian classifier" would be an approach worth
> > pursuing. That's more of a research project than a plan, so until then,
> > I agree that your idea of making it tunable is a good one.
>
> My current test is rather abusive - I'm using the kernel packet generator
> to send packets for many flows at roughly the same per-flow packet rate.
> In that scenario all flows are equal, so I think that classification would
> probably break down. Indeed, it plays havoc with the current eviction
> algorithm.
> However, I do agree that some kind of prioritisation algorithm could work
> well with less abusive (and more common?) workloads.
What does your flow table look like?
_______________________________________________
dev mailing list
[email protected]
http://openvswitch.org/mailman/listinfo/dev
