[ovs-discuss] Flow eviction based on LRU

Joe Stringer joe at ovn.org
Thu Jan 26 21:48:55 UTC 2017

On 25 January 2017 at 23:32, Avi Cohen (A) <avi.cohen at huawei.com> wrote:
>> -----Original Message-----
>> From: ovs-discuss-bounces at openvswitch.org [mailto:ovs-discuss-
>> bounces at openvswitch.org] On Behalf Of Joe Stringer
>> Sent: Wednesday, 25 January, 2017 8:47 PM
>> To: Avi Cohen (A)
>> Cc: ovs-discuss at openvswitch.org
>> Subject: Re: [ovs-discuss] Flow eviction based on LRU
>> On 24 January 2017 at 23:55, Avi Cohen (A) <avi.cohen at huawei.com> wrote:
>> > Thanks Joe,
>> > 1.  so the only flows-eviction process  (from datapath cache)  is
>> implemented in udpif_revalidator thread ?  deleting flows that exceed  10s
>> idle time ?
>> Yes. Alternatively if flow dump duration is long (takes ~1s to dump all flows),
>> then additional heuristics will kick in to delete low-throughput flows, see
>> should_revalidate(). Furthermore, if any configuration or OpenFlow changes
>> then that thread will delete related datapath flows.
>> > 2.  Where is the implementation of http://openvswitch.org/ovs-
>> vswitchd.conf.db.5.pdf  ?
>> > This intends to be  a LRU approximation
>> Can you be more specific where in the 58-page document you're referring
>> to? It's possible the documentation is a little out of sync with the current
>> implementation.
> [Avi Cohen (A)]
> Joe - look at page 36 -  pasted below: - specially look at the pseudo LRU eviction algorithm 3 steps
> overflow_policy: optional string, either refuse or evict
> Controls the switch’s behavior when an OpenFlow flow table modification request would add
> flows in excess of flow_limit. The supported values are:
> refuse Refuse to add the flow or flows. This is also the default policy when overflow_policy is
> unset.
> evict Delete the flow that will expire soonest. See groups for details.
> groups: set of strings
> When overflow_policy is evict, this controls how flows are chosen for eviction when the flow table
> would otherwise exceed flow_limit flows. Its value is a set of NXM fields or sub-fields, each
> of which takes one of the forms field[] or field[start..end], e.g. NXM_OF_IN_PORT[]. Please
> see nicira−ext.h for a complete list of NXM field names.
> When a flow must be evicted due to overflow, the flow to evict is chosen through an approximation
> of the following algorithm:
> 1. Divide the flows in the table into groups based on the values of the specified fields or sub-
> fields, so that all of the flows in a given group have the same values for those fields. If a flow
> does not specify a given field, that field’s value is treated as 0.
> 2. Consider the flows in the largest group, that is, the group that contains the greatest number of
> flows. If two or more groups all have the same largest number of flows, consider the flows in
> all of those groups.
> 3. Among the flows under consideration, choose the flow that expires soonest for eviction.
> The eviction process only considers flows that have an idle timeout or a hard timeout. That is,
> eviction never deletes permanent flows. (Permanent flows do count against flow_limit.)
> Open vSwitch ignores any inv alid or unknown field specifications.
> When overflow_policy is not evict, this column has no effect.

OK, this is talking about something different from what I was referring to.

This is about OpenFlow flow table rule eviction, which
ofproto_configure_table() will provide more details. This has nothing
to do with the datapath flow cache and revalidator threads.

More information about the discuss mailing list