[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