On Tue, Jul 26, 2011 at 05:02:25PM -0700, Ben Pfaff wrote:
> 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.
Thanks, the list is very useful to me, though I don't have
any particularly insightful ideas at this stage.
>
> 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.
I guess this hurts a lot as that code's purpose
is to mitigate the effects of large numbers of flows.
Off the top of my head, I wonder if an approach that would
work would be to only ask the kernel for flows over a certain age.
Or otherwise push some of the logic into the kernel where
access to the data ought to be cheaper.
Or perhaps to have an algorithm that can deal with
a partial dump from the kernel - e.g. a dump of up to 10,000 flows.
> 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?
Does this answer the question?
sudo ovs-ofctl add-flow br3 "in_port=1 ip nw_dst=10.0.0.0/8 idle_timeout=0
action=output:3"
Where 3 is a dummy interface.
My test involves sending 128byte packets at 450,000 pps (~1/2Gigabit/s).
By tuning the eviction threshold and with the table resize fix
I sent a week or so back I can get up to 128k flows and still
a have a little of one CPU left over.
Empirically it seems that there is some hard limit of 128k flows
that I have hit.
_______________________________________________
dev mailing list
[email protected]
http://openvswitch.org/mailman/listinfo/dev
