[ovs-git] [openvswitch/ovs] 6a0b0d: userspace datapath: Add OVS_HASH_L4_SYMMETRIC dp_h...

GitHub noreply at github.com
Fri May 25 22:10:02 UTC 2018


  Branch: refs/heads/master
  Home:   https://github.com/openvswitch/ovs
  Commit: 6a0b0d3be8573c42d750eb22e3445a3c759c8e8f
      https://github.com/openvswitch/ovs/commit/6a0b0d3be8573c42d750eb22e3445a3c759c8e8f
  Author: Jan Scheurich <jan.scheurich at ericsson.com>
  Date:   2018-05-25 (Fri, 25 May 2018)

  Changed paths:
    M datapath/linux/compat/include/linux/openvswitch.h
    M lib/flow.c
    M lib/flow.h
    M lib/odp-execute.c
    M ofproto/ofproto-dpif-xlate.c
    M ofproto/ofproto-dpif.c
    M ofproto/ofproto-dpif.h

  Log Message:
  -----------
  userspace datapath: Add OVS_HASH_L4_SYMMETRIC dp_hash algorithm

This commit implements a new dp_hash algorithm OVS_HASH_L4_SYMMETRIC in
the netdev datapath. It will be used as default hash algorithm for the
dp_hash-based select groups in a subsequent commit to maintain
compatibility with the symmetry property of the current default hash
selection method.

A new dpif_backer_support field 'max_hash_alg' is introduced to reflect
the highest hash algorithm a datapath supports in the dp_hash action.

Signed-off-by: Jan Scheurich <jan.scheurich at ericsson.com>
Signed-off-by: Nitin Katiyar <nitin.katiyar at ericsson.com>
Co-authored-by: Nitin Katiyar <nitin.katiyar at ericsson.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>


  Commit: 2e3fd24c7c440f87d7a24fbfce1474237de7e1cf
      https://github.com/openvswitch/ovs/commit/2e3fd24c7c440f87d7a24fbfce1474237de7e1cf
  Author: Jan Scheurich <jan.scheurich at ericsson.com>
  Date:   2018-05-25 (Fri, 25 May 2018)

  Changed paths:
    M lib/odp-util.c
    M ofproto/ofproto-dpif-xlate.c
    M ofproto/ofproto-dpif.c
    M ofproto/ofproto-dpif.h
    M tests/ofproto-dpif.at

  Log Message:
  -----------
  ofproto-dpif: Improve dp_hash selection method for select groups

The current implementation of the "dp_hash" selection method suffers
from two deficiences: 1. The hash mask and hence the number of dp_hash
values is just large enough to cover the number of group buckets, but
does not consider the case that buckets have different weights. 2. The
xlate-time selection of best bucket from the masked dp_hash value often
results in bucket load distributions that are quite different from the
bucket weights because the number of available masked dp_hash values
is too small (2-6 bits compared to 32 bits of a full hash in the default
hash selection method).

This commit provides a more accurate implementation of the dp_hash
select group by applying the well known Webster method for distributing
a small number of "seats" fairly over the weighted "parties"
(see https://en.wikipedia.org/wiki/Webster/Sainte-Lagu%C3%AB_method).
The dp_hash mask is autmatically chosen large enough to provide good
enough accuracy even with widely differing weights.

This distribution happens at group modification time and the resulting
table is stored with the group-dpif struct. At xlation time, we use the
masked dp_hash values as index to look up the assigned bucket.

If the bucket should not be live, we do a circular search over the
mapping table until we find the first live bucket. As the buckets in
the table are by construction in pseudo-random order with a frequency
according to their weight, this method maintains correct distribution
even if one or more buckets are non-live.

Xlation is further simplified by storing some derived select group state
at group construction in struct group-dpif in a form better suited for
xlation purposes.

Adapted the unit test case for dp_hash select group accordingly.

Signed-off-by: Jan Scheurich <jan.scheurich at ericsson.com>
Signed-off-by: Nitin Katiyar <nitin.katiyar at ericsson.com>
Co-authored-by: Nitin Katiyar <nitin.katiyar at ericsson.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>


  Commit: 06db81ccfe6d4c779de2ca73033abd7020db419b
      https://github.com/openvswitch/ovs/commit/06db81ccfe6d4c779de2ca73033abd7020db419b
  Author: Jan Scheurich <jan.scheurich at ericsson.com>
  Date:   2018-05-25 (Fri, 25 May 2018)

  Changed paths:
    M NEWS
    M lib/ofp-group.c
    M ofproto/ofproto-dpif.c
    M ofproto/ofproto-dpif.h
    M ofproto/ofproto-provider.h
    M tests/mpls-xlate.at
    M tests/ofproto-dpif.at
    M tests/ofproto-macros.at
    M utilities/ovs-ofctl.8.in

  Log Message:
  -----------
  ofproto-dpif: Use dp_hash as default selection method

The dp_hash selection method for select groups overcomes the scalability
problems of the current default selection method which, due to L2-L4
hashing during xlation and un-wildcarding of the hashed fields,
basically requires an upcall to the slow path to load-balance every
L4 connection. The consequence are an explosion of datapath flows
(megaflows degenerate to miniflows) and a limitation of connection
setup rate OVS can handle.

This commit changes the default selection method to dp_hash, provided the
bucket configuration is such that the dp_hash method can accurately
represent the bucket weights with up to 64 hash values. Otherwise we
stick to original default hash method.

We use the new dp_hash algorithm OVS_HASH_L4_SYMMETRIC to maintain the
symmetry property of the old default hash method.

A controller can explicitly request the old default hash selection method
by specifying selection method "hash" with an empty list of fields in the
Group properties of the OpenFlow 1.5 Group Mod message.

Update the documentation about selection method in the ovs-ovctl man page.

Revise and complete the ofproto-dpif unit tests cases for select groups.

Signed-off-by: Jan Scheurich <jan.scheurich at ericsson.com>
Signed-off-by: Nitin Katiyar <nitin.katiyar at ericsson.com>
Co-authored-by: Nitin Katiyar <nitin.katiyar at ericsson.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>


Compare: https://github.com/openvswitch/ovs/compare/dd8ff6ccf0d8...06db81ccfe6d
      **NOTE:** This service been marked for deprecation: https://developer.github.com/changes/2018-04-25-github-services-deprecation/

      Functionality will be removed from GitHub.com on January 31st, 2019.


More information about the git mailing list