[dpdk-dev] [PATCH v2 0/5] Elastic Flow Distributor

Maciocco, Christian christian.maciocco at intel.com
Mon Jan 9 19:19:20 CET 2017



> -----Original Message-----
> From: dev [mailto:dev-bounces at dpdk.org] On Behalf Of Pablo de Lara
> Sent: Friday, January 06, 2017 5:06 PM
> To: dev at dpdk.org
> Cc: De Lara Guarch, Pablo <pablo.de.lara.guarch at intel.com>
> Subject: [dpdk-dev] [PATCH v2 0/5] Elastic Flow Distributor
> 
> EFD is a distributor library that uses perfect hashing to determine a target/value
> for a given incoming flow key. It has the following advantages:
> first, because it uses perfect hashing it does not store the key itself and hence
> lookup performance is not dependent on the key size. Second, the target/value
> can be any arbitrary value hence the system designer and/or operator can better
> optimize service rates and inter-cluster network traffic locating.  Third, since the
> storage requirement is much smaller than a hash-based flow table (i.e. better fit
> for CPU cache), EFD can scale to millions of flow keys. Finally, with current
> optimized library implementation performance is fully scalable with number of
> CPU cores.
> 
> The basic idea of EFD is when a given key is to be inserted, a family of hash
> functions is searched until the correct hash function that maps the input key to
> the correct value is found. However, rather than explicitly storing all keys and
> their associated values, EFD stores only indices of hash functions that map keys
> to values, and thereby consumes much less space than conventional  flow-based
> tables. The lookup operation is very simple, similar to computational-based
> scheme, given an input key the lookup operation is reduced to hashing that key
> with the correct hash function.
> 
> Intuitively, finding a hash function that maps each of a large number (millions) of
> input keys to the correct output value is effectively impossible, as a result EFD,
> breaks the problem into smaller pieces (divide and conquer). EFD divides the
> entire input key set into many small groups. Each group consists of
> approximately 20-28 keys (a configurable parameter for the library), then, for
> each small group, a brute force search to find a hash function that produces the
> correct outputs for each key in the group.
> It should be mentioned that since in the online lookup table for EFD doesn’t
> store the key itself, the size of the EFD table is independent of the key size and
> hence EFD lookup performance which is almost constant irrespective of the
> length of the key which is a highly desirable feature especially for longer keys.
> 
> Library code is included in the patch, plus an sample application that shows how
> the library can be used.
> 
> RFC for this library was already sent:
> http://dpdk.org/ml/archives/dev/2016-October/049238.html
> 
> For more information on the library, check out the following document:
> https://github.com/pablodelara/perfect_hash_flow_distributor/blob/master/EF
> D_description.pdf
> 
> Changes in v2:
> 
> - Added documentation for library and sample app
> - Fixed checkpatch errors/warnings
> - Added functional and performance tests
> - Made key size variable at runtime
> - Made code multi-architecture compatible at runtime
> 
> 
> Pablo de Lara (5):
>   efd: new Elastic Flow Distributor library
>   app/test: add EFD functional and perf tests
>   examples/flow_distributor: sample app to demonstrate EFD usage
>   doc: add EFD library section in Programmers guide
>   doc: add flow distributor guide
> 
>  MAINTAINERS                                       |    9 +
>  app/test/Makefile                                 |    3 +
>  app/test/test_efd.c                               |  494 ++++++++
>  app/test/test_efd_perf.c                          |  407 ++++++
>  config/common_base                                |    5 +
>  doc/api/doxy-api-index.md                         |    3 +-
>  doc/api/doxy-api.conf                             |    1 +
>  doc/api/examples.dox                              |    4 +
>  doc/guides/prog_guide/efd_lib.rst                 |  413 ++++++
>  doc/guides/prog_guide/img/efd_i1.svg              |   78 ++
>  doc/guides/prog_guide/img/efd_i10.svg             | 1272 +++++++++++++++++++
>  doc/guides/prog_guide/img/efd_i11.svg             |  413 ++++++
>  doc/guides/prog_guide/img/efd_i12.svg             |  590 +++++++++
>  doc/guides/prog_guide/img/efd_i13.svg             | 1407
> +++++++++++++++++++++
>  doc/guides/prog_guide/img/efd_i2.svg              |  209 +++
>  doc/guides/prog_guide/img/efd_i3.svg              |  420 ++++++
>  doc/guides/prog_guide/img/efd_i4.svg              |  364 ++++++
>  doc/guides/prog_guide/img/efd_i5.svg              |  578 +++++++++
>  doc/guides/prog_guide/img/efd_i6.svg              |  413 ++++++
>  doc/guides/prog_guide/img/efd_i8.svg              |  776 ++++++++++++
>  doc/guides/prog_guide/img/efd_i9.svg              |  271 ++++
>  doc/guides/prog_guide/index.rst                   |    1 +
>  doc/guides/rel_notes/release_17_02.rst            |   15 +
>  doc/guides/sample_app_ug/flow_distributor.rst     |  492 +++++++
>  doc/guides/sample_app_ug/img/flow_distributor.svg |  417 ++++++
>  doc/guides/sample_app_ug/index.rst                |    1 +
>  examples/Makefile                                 |    1 +
>  examples/flow_distributor/Makefile                |   44 +
>  examples/flow_distributor/distributor/Makefile    |   57 +
>  examples/flow_distributor/distributor/args.c      |  200 +++
>  examples/flow_distributor/distributor/args.h      |   39 +
>  examples/flow_distributor/distributor/init.c      |  371 ++++++
>  examples/flow_distributor/distributor/init.h      |   76 ++
>  examples/flow_distributor/distributor/main.c      |  362 ++++++
>  examples/flow_distributor/node/Makefile           |   48 +
>  examples/flow_distributor/node/node.c             |  417 ++++++
>  examples/flow_distributor/shared/common.h         |   99 ++
>  lib/Makefile                                      |    1 +
>  lib/librte_eal/common/include/rte_log.h           |    1 +
>  lib/librte_efd/Makefile                           |   56 +
>  lib/librte_efd/rte_efd.c                          | 1354 ++++++++++++++++++++
>  lib/librte_efd/rte_efd.h                          |  294 +++++
>  lib/librte_efd/rte_efd_version.map                |   12 +
>  mk/rte.app.mk                                     |    1 +
>  44 files changed, 12488 insertions(+), 1 deletion(-)  create mode 100644
> app/test/test_efd.c  create mode 100644 app/test/test_efd_perf.c  create
> mode 100644 doc/guides/prog_guide/efd_lib.rst  create mode 100644
> doc/guides/prog_guide/img/efd_i1.svg
>  create mode 100644 doc/guides/prog_guide/img/efd_i10.svg
>  create mode 100644 doc/guides/prog_guide/img/efd_i11.svg
>  create mode 100644 doc/guides/prog_guide/img/efd_i12.svg
>  create mode 100644 doc/guides/prog_guide/img/efd_i13.svg
>  create mode 100644 doc/guides/prog_guide/img/efd_i2.svg
>  create mode 100644 doc/guides/prog_guide/img/efd_i3.svg
>  create mode 100644 doc/guides/prog_guide/img/efd_i4.svg
>  create mode 100644 doc/guides/prog_guide/img/efd_i5.svg
>  create mode 100644 doc/guides/prog_guide/img/efd_i6.svg
>  create mode 100644 doc/guides/prog_guide/img/efd_i8.svg
>  create mode 100644 doc/guides/prog_guide/img/efd_i9.svg
>  create mode 100644 doc/guides/sample_app_ug/flow_distributor.rst
>  create mode 100644 doc/guides/sample_app_ug/img/flow_distributor.svg
>  create mode 100644 examples/flow_distributor/Makefile
>  create mode 100644 examples/flow_distributor/distributor/Makefile
>  create mode 100644 examples/flow_distributor/distributor/args.c
>  create mode 100644 examples/flow_distributor/distributor/args.h
>  create mode 100644 examples/flow_distributor/distributor/init.c
>  create mode 100644 examples/flow_distributor/distributor/init.h
>  create mode 100644 examples/flow_distributor/distributor/main.c
>  create mode 100644 examples/flow_distributor/node/Makefile
>  create mode 100644 examples/flow_distributor/node/node.c
>  create mode 100644 examples/flow_distributor/shared/common.h
>  create mode 100644 lib/librte_efd/Makefile  create mode 100644
> lib/librte_efd/rte_efd.c  create mode 100644 lib/librte_efd/rte_efd.h  create
> mode 100644 lib/librte_efd/rte_efd_version.map
> 
> --
> 2.7.4

Series-acked-by: Christian Maciocco <christian.maciocco at intel.com>


More information about the dev mailing list