[ovs-dev] [PATCH v2 1/3] ofproto: Use OF1.4+ "importance" as part of eviction criteria.
Jarno Rajahalme
jrajahalme at nicira.com
Fri Jul 3 10:49:51 UTC 2015
Acked-by: Jarno Rajahalme <jrajahalme at nicira.com>
> On Jul 2, 2015, at 8:41 PM, Ben Pfaff <blp at nicira.com> wrote:
>
> The "importance" field is considered before flow timeout because I figure
> that if you set the importance, you think it's important.
>
> Signed-off-by: Ben Pfaff <blp at nicira.com>
> Co-authored-by: Saloni Jain <saloni.jain at tcs.com>
> Signed-off-by: Saloni Jain <saloni.jain at tcs.com>
> ---
> v1->v2: Fixed doubled semicolon, no other changes.
>
> NEWS | 1 +
> ofproto/ofproto.c | 42 ++++++++++++++++------------
> tests/ofproto.at | 79 ++++++++++++++++++++++++++++++++++++++++++++++++++++
> vswitchd/vswitch.xml | 19 ++++++++++---
> 4 files changed, 119 insertions(+), 22 deletions(-)
>
> diff --git a/NEWS b/NEWS
> index d6db7d0..3da7cfd 100644
> --- a/NEWS
> +++ b/NEWS
> @@ -6,6 +6,7 @@ Post-v2.4.0
> - OpenFlow:
> * Group chaining (where one OpenFlow group triggers another) is
> now supported.
> + * OpenFlow 1.4+ "importance" is now considered for flow eviction.
> - Support for matching and generating options with Geneve tunnels.
> - Support Multicast Listener Discovery (MLDv1 and MLDv2).
>
> diff --git a/ofproto/ofproto.c b/ofproto/ofproto.c
> index c6fbf9f..4aa844e 100644
> --- a/ofproto/ofproto.c
> +++ b/ofproto/ofproto.c
> @@ -115,8 +115,8 @@ struct eviction_group {
>
> static bool choose_rule_to_evict(struct oftable *table, struct rule **rulep)
> OVS_REQUIRES(ofproto_mutex);
> -static uint32_t rule_eviction_priority(struct ofproto *ofproto, struct rule *)
> - OVS_REQUIRES(ofproto_mutex);;
> +static uint64_t rule_eviction_priority(struct ofproto *ofproto, struct rule *)
> + OVS_REQUIRES(ofproto_mutex);
> static void eviction_group_add_rule(struct rule *)
> OVS_REQUIRES(ofproto_mutex);
> static void eviction_group_remove_rule(struct rule *)
> @@ -7384,23 +7384,21 @@ eviction_group_find(struct oftable *table, uint32_t id)
> }
>
> /* Returns an eviction priority for 'rule'. The return value should be
> - * interpreted so that higher priorities make a rule more attractive candidates
> - * for eviction.
> - * Called only if have a timeout. */
> -static uint32_t
> + * interpreted so that higher priorities make a rule a more attractive
> + * candidate for eviction. */
> +static uint64_t
> rule_eviction_priority(struct ofproto *ofproto, struct rule *rule)
> OVS_REQUIRES(ofproto_mutex)
> {
> + /* Calculate absolute time when this flow will expire. If it will never
> + * expire, then return 0 to make it unevictable. */
> long long int expiration = LLONG_MAX;
> - long long int modified;
> - uint32_t expiration_offset;
> -
> - /* 'modified' needs protection even when we hold 'ofproto_mutex'. */
> - ovs_mutex_lock(&rule->mutex);
> - modified = rule->modified;
> - ovs_mutex_unlock(&rule->mutex);
> -
> if (rule->hard_timeout) {
> + /* 'modified' needs protection even when we hold 'ofproto_mutex'. */
> + ovs_mutex_lock(&rule->mutex);
> + long long int modified = rule->modified;
> + ovs_mutex_unlock(&rule->mutex);
> +
> expiration = modified + rule->hard_timeout * 1000;
> }
> if (rule->idle_timeout) {
> @@ -7412,7 +7410,6 @@ rule_eviction_priority(struct ofproto *ofproto, struct rule *rule)
> idle_expiration = used + rule->idle_timeout * 1000;
> expiration = MIN(expiration, idle_expiration);
> }
> -
> if (expiration == LLONG_MAX) {
> return 0;
> }
> @@ -7422,10 +7419,19 @@ rule_eviction_priority(struct ofproto *ofproto, struct rule *rule)
> *
> * This should work OK for program runs that last UINT32_MAX seconds or
> * less. Therefore, please restart OVS at least once every 136 years. */
> - expiration_offset = (expiration >> 10) - (time_boot_msec() >> 10);
> + uint32_t expiration_ofs = (expiration >> 10) - (time_boot_msec() >> 10);
>
> - /* Invert the expiration offset because we're using a max-heap. */
> - return UINT32_MAX - expiration_offset;
> + /* Combine expiration time with OpenFlow "importance" to form a single
> + * priority value. We want flows with relatively low "importance" to be
> + * evicted before even considering expiration time, so put "importance" in
> + * the most significant bits and expiration time in the least significant
> + * bits.
> + *
> + * Small 'priority' should be evicted before those with large 'priority'.
> + * The caller expects the opposite convention (a large return value being
> + * more attractive for eviction) so we invert it before returning. */
> + uint64_t priority = ((uint64_t) rule->importance << 32) + expiration_ofs;
> + return UINT64_MAX - priority;
> }
>
> /* Adds 'rule' to an appropriate eviction group for its oftable's
> diff --git a/tests/ofproto.at b/tests/ofproto.at
> index a564c81..3bd625d 100644
> --- a/tests/ofproto.at
> +++ b/tests/ofproto.at
> @@ -1864,6 +1864,85 @@ OFPST_FLOW reply (OF1.2):
> OVS_VSWITCHD_STOP
> AT_CLEANUP
>
> +AT_SETUP([ofproto - eviction using importance upon table overflow (OpenFlow 1.4)])
> +OVS_VSWITCHD_START
> +# Configure a maximum of 4 flows.
> +AT_CHECK(
> + [ovs-vsctl \
> + -- --id=@t0 create Flow_Table name=evict flow-limit=4 overflow-policy=evict \
> + -- set bridge br0 flow_tables:0=@t0 \
> + | ${PERL} $srcdir/uuidfilt.pl],
> + [0], [<0>
> +])
> +# Add 4 flows.
> +for in_port in 4 3 2 1; do
> + ovs-ofctl -O Openflow14 add-flow br0 importance=$((in_port + 30)),priority=$((in_port + 5)),hard_timeout=$((in_port + 500)),actions=drop
> +done
> +AT_CHECK([ovs-ofctl -O Openflow14 dump-flows br0 | ofctl_strip | sort], [0], [dnl
> + hard_timeout=501, importance=31, priority=6 actions=drop
> + hard_timeout=502, importance=32, priority=7 actions=drop
> + hard_timeout=503, importance=33, priority=8 actions=drop
> + hard_timeout=504, importance=34, priority=9 actions=drop
> +OFPST_FLOW reply (OF1.4):
> +])
> +# Adding another flow will cause the one with lowest importance to be evicted.
> +AT_CHECK([ovs-ofctl -O Openflow14 add-flow br0 hard_timeout=505,importance=35,priority=10,in_port=2,actions=drop])
> +AT_CHECK([ovs-ofctl -O Openflow14 dump-flows br0 | ofctl_strip | sort], [0], [dnl
> + hard_timeout=502, importance=32, priority=7 actions=drop
> + hard_timeout=503, importance=33, priority=8 actions=drop
> + hard_timeout=504, importance=34, priority=9 actions=drop
> + hard_timeout=505, importance=35, priority=10,in_port=2 actions=drop
> +OFPST_FLOW reply (OF1.4):
> +])
> +# Disable the Eviction configuration.
> +AT_CHECK([ovs-vsctl set Flow_Table evict overflow-policy=refuse])
> +# Adding another flow will cause the system to give error for FULL TABLE.
> +AT_CHECK([ovs-ofctl -O Openflow14 add-flow br0 hard_timeout=506,importance=36,priority=11,actions=drop],[1], [], [stderr])
> +AT_CHECK([head -n 1 stderr | ofctl_strip], [0],
> + [OFPT_ERROR (OF1.4): OFPFMFC_TABLE_FULL
> +])
> +#Dump flows. It should show only the old values
> +AT_CHECK([ovs-ofctl -O Openflow14 dump-flows br0 | ofctl_strip | sort], [0], [dnl
> + hard_timeout=502, importance=32, priority=7 actions=drop
> + hard_timeout=503, importance=33, priority=8 actions=drop
> + hard_timeout=504, importance=34, priority=9 actions=drop
> + hard_timeout=505, importance=35, priority=10,in_port=2 actions=drop
> +OFPST_FLOW reply (OF1.4):
> +])
> +# mod-flow that would modify a flow will be done successfully.
> +AT_CHECK([ovs-ofctl -O Openflow14 mod-flows br0 in_port=2,actions=NORMAL])
> +AT_CHECK([ovs-ofctl -O Openflow14 dump-flows br0 | ofctl_strip | sort], [0], [dnl
> + hard_timeout=502, importance=32, priority=7 actions=drop
> + hard_timeout=503, importance=33, priority=8 actions=drop
> + hard_timeout=504, importance=34, priority=9 actions=drop
> + hard_timeout=505, importance=35, priority=10,in_port=2 actions=NORMAL
> +OFPST_FLOW reply (OF1.4):
> +])
> +# Also a mod-flow that would add a flow will be refused.
> +AT_CHECK([ovs-ofctl mod-flows br0 in_port=5,actions=drop], [1], [], [stderr])
> +AT_CHECK([head -n 1 stderr | ofctl_strip], [0],
> + [OFPT_ERROR: OFPFMFC_TABLE_FULL
> +])
> +# Now set the eviction on timeout basis.
> +AT_CHECK(
> + [ovs-vsctl \
> + -- --id=@t0 create Flow_Table flow-limit=4 overflow-policy=evict \
> + -- set bridge br0 flow_tables:0=@t0 \
> + | ${PERL} $srcdir/uuidfilt.pl],
> + [0], [<0>
> +])
> +#Now add a new flow
> +AT_CHECK([ovs-ofctl -O Openflow14 add-flow br0 importance=37,hard_timeout=507,priority=11,in_port=6,actions=drop])
> +AT_CHECK([ovs-ofctl -O Openflow14 dump-flows br0 | ofctl_strip | sort], [0], [dnl
> + hard_timeout=503, importance=33, priority=8 actions=drop
> + hard_timeout=504, importance=34, priority=9 actions=drop
> + hard_timeout=505, importance=35, priority=10,in_port=2 actions=NORMAL
> + hard_timeout=507, importance=37, priority=11,in_port=6 actions=drop
> +OFPST_FLOW reply (OF1.4):
> +])
> +OVS_VSWITCHD_STOP
> +AT_CLEANUP
> +
> AT_SETUP([ofproto - eviction upon table overflow, with fairness (OpenFlow 1.0)])
> OVS_VSWITCHD_START
> # Configure a maximum of 4 flows.
> diff --git a/vswitchd/vswitch.xml b/vswitchd/vswitch.xml
> index b1d30f6..9f108f0 100644
> --- a/vswitchd/vswitch.xml
> +++ b/vswitchd/vswitch.xml
> @@ -3082,15 +3082,18 @@
>
> <p>
> When a flow must be evicted due to overflow, the flow to evict is
> - chosen through an approximation of the following algorithm:
> + chosen through an approximation of the following algorithm. This
> + algorithm is used regardless of how eviction was enabled:
> </p>
>
> <ol>
> <li>
> Divide the flows in the table into groups based on the values of the
> - specified fields or subfields, 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.
> + fields or subfields specified in the <ref column="groups"/> column,
> + 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. If <ref column="groups"/> is empty, then all
> + of the flows in the flow table are treated as a single group.
> </li>
>
> <li>
> @@ -3101,6 +3104,14 @@
> </li>
>
> <li>
> + If the flows under consideration have different importance values,
> + eliminate from consideration any flows except those with the lowest
> + importance. (``Importance,'' a 16-bit integer value attached to each
> + flow, was introduced in OpenFlow 1.4. Flows inserted with older
> + versions of OpenFlow always have an importance of 0.)
> + </li>
> +
> + <li>
> Among the flows under consideration, choose the flow that expires
> soonest for eviction.
> </li>
> --
> 2.1.3
>
> _______________________________________________
> dev mailing list
> dev at openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev
More information about the dev
mailing list