From: "Maciocco, Christian" <christian.maciocco@intel.com>
To: "De Lara Guarch, Pablo" <pablo.de.lara.guarch@intel.com>,
"dev@dpdk.org" <dev@dpdk.org>
Cc: "De Lara Guarch, Pablo" <pablo.de.lara.guarch@intel.com>
Subject: Re: [dpdk-dev] [PATCH v2 0/5] Elastic Flow Distributor
Date: Mon, 9 Jan 2017 18:19:20 +0000 [thread overview]
Message-ID: <F15AFC7D20A92244A577550D05A7A984B2512DED@ORSMSX103.amr.corp.intel.com> (raw)
In-Reply-To: <1483751166-32423-1-git-send-email-pablo.de.lara.guarch@intel.com>
> -----Original Message-----
> From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Pablo de Lara
> Sent: Friday, January 06, 2017 5:06 PM
> To: dev@dpdk.org
> Cc: De Lara Guarch, Pablo <pablo.de.lara.guarch@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@intel.com>
next prev parent reply other threads:[~2017-01-09 18:19 UTC|newest]
Thread overview: 63+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-12-02 14:52 [dpdk-dev] [PATCH 0/2] " Pablo de Lara
2016-12-02 14:52 ` [dpdk-dev] [PATCH 1/2] efd: new Elastic Flow Distributor library Pablo de Lara
2016-12-02 14:52 ` [dpdk-dev] [PATCH 2/2] examples/flow_distributor: sample app to demonstrate EFD usage Pablo de Lara
2017-01-07 1:06 ` [dpdk-dev] [PATCH v2 0/5] Elastic Flow Distributor Pablo de Lara
2017-01-07 1:06 ` [dpdk-dev] [PATCH v2 1/5] efd: new Elastic Flow Distributor library Pablo de Lara
2017-01-07 1:06 ` [dpdk-dev] [PATCH v2 2/5] app/test: add EFD functional and perf tests Pablo de Lara
2017-01-07 1:06 ` [dpdk-dev] [PATCH v2 3/5] examples/flow_distributor: sample app to demonstrate EFD usage Pablo de Lara
2017-01-07 1:06 ` [dpdk-dev] [PATCH v2 4/5] doc: add EFD library section in Programmers guide Pablo de Lara
2017-01-07 1:06 ` [dpdk-dev] [PATCH v2 5/5] doc: add flow distributor guide Pablo de Lara
2017-01-09 18:19 ` Maciocco, Christian [this message]
2017-01-12 22:15 ` [dpdk-dev] [PATCH v3 0/5] Elastic Flow Distributor Pablo de Lara
2017-01-12 22:15 ` [dpdk-dev] [PATCH v3 1/5] efd: new Elastic Flow Distributor library Pablo de Lara
2017-01-12 22:15 ` [dpdk-dev] [PATCH v3 2/5] app/test: add EFD functional and perf tests Pablo de Lara
2017-01-12 22:15 ` [dpdk-dev] [PATCH v3 3/5] examples/flow_distributor: sample app to demonstrate EFD usage Pablo de Lara
2017-01-12 22:15 ` [dpdk-dev] [PATCH v3 4/5] doc: add EFD library section in Programmers guide Pablo de Lara
2017-01-12 22:16 ` [dpdk-dev] [PATCH v3 5/5] doc: add flow distributor guide Pablo de Lara
2017-01-15 12:04 ` [dpdk-dev] [PATCH v4 0/5] Elastic Flow Distributor Pablo de Lara
2017-01-15 12:04 ` [dpdk-dev] [PATCH v4 1/5] efd: new Elastic Flow Distributor library Pablo de Lara
2017-01-16 4:25 ` Jerin Jacob
2017-01-16 15:34 ` De Lara Guarch, Pablo
2017-01-15 12:04 ` [dpdk-dev] [PATCH v4 2/5] app/test: add EFD functional and perf tests Pablo de Lara
2017-01-15 12:04 ` [dpdk-dev] [PATCH v4 3/5] examples/flow_distributor: sample app to demonstrate EFD usage Pablo de Lara
2017-01-15 12:04 ` [dpdk-dev] [PATCH v4 4/5] doc: add EFD library section in Programmers guide Pablo de Lara
2017-01-16 4:15 ` Jerin Jacob
2017-01-16 15:33 ` De Lara Guarch, Pablo
2017-01-15 12:04 ` [dpdk-dev] [PATCH v4 5/5] doc: add flow distributor guide Pablo de Lara
2017-01-16 9:43 ` [dpdk-dev] [PATCH v5 0/5] Elastic Flow Distributor Pablo de Lara
2017-01-16 9:43 ` [dpdk-dev] [PATCH v5 1/5] efd: new Elastic Flow Distributor library Pablo de Lara
2017-01-16 9:43 ` [dpdk-dev] [PATCH v5 2/5] app/test: add EFD functional and perf tests Pablo de Lara
2017-01-16 9:43 ` [dpdk-dev] [PATCH v5 3/5] examples/flow_distributor: sample app to demonstrate EFD usage Pablo de Lara
2017-01-16 9:43 ` [dpdk-dev] [PATCH v5 4/5] doc: add EFD library section in Programmers guide Pablo de Lara
2017-01-16 9:43 ` [dpdk-dev] [PATCH v5 5/5] doc: add flow distributor guide Pablo de Lara
2017-01-16 15:08 ` [dpdk-dev] [PATCH v5 0/5] Elastic Flow Distributor Thomas Monjalon
2017-01-17 8:34 ` De Lara Guarch, Pablo
2017-01-16 19:21 ` [dpdk-dev] [PATCH v6 " Pablo de Lara
2017-01-16 19:21 ` [dpdk-dev] [PATCH v6 1/5] efd: new Elastic Flow Distributor library Pablo de Lara
2017-01-17 20:32 ` Thomas Monjalon
2017-01-17 21:11 ` Thomas Monjalon
2017-01-16 19:21 ` [dpdk-dev] [PATCH v6 2/5] app/test: add EFD functional and perf tests Pablo de Lara
2017-01-16 19:21 ` [dpdk-dev] [PATCH v6 3/5] examples/flow_distributor: sample app to demonstrate EFD usage Pablo de Lara
2017-01-16 19:21 ` [dpdk-dev] [PATCH v6 4/5] doc: add EFD library section in Programmers guide Pablo de Lara
2017-01-16 19:21 ` [dpdk-dev] [PATCH v6 5/5] doc: add flow distributor guide Pablo de Lara
2017-01-17 20:35 ` Thomas Monjalon
2017-01-17 20:29 ` [dpdk-dev] [PATCH v6 0/5] Elastic Flow Distributor Thomas Monjalon
2017-01-17 22:10 ` [dpdk-dev] [PATCH v7 0/6] " Pablo de Lara
2017-01-17 22:10 ` [dpdk-dev] [PATCH v7 1/6] efd: new Elastic Flow Distributor library Pablo de Lara
2017-01-17 22:10 ` [dpdk-dev] [PATCH v7 2/6] efd: add AVX2 vect lookup function Pablo de Lara
2017-01-17 22:10 ` [dpdk-dev] [PATCH v7 3/6] app/test: add EFD functional and perf tests Pablo de Lara
2017-01-17 22:10 ` [dpdk-dev] [PATCH v7 4/6] examples/flow_distributor: sample app to demonstrate EFD usage Pablo de Lara
2017-01-17 22:10 ` [dpdk-dev] [PATCH v7 5/6] doc: add EFD library section in Programmers guide Pablo de Lara
2017-01-17 22:10 ` [dpdk-dev] [PATCH v7 6/6] doc: add flow distributor guide Pablo de Lara
2017-01-17 22:18 ` [dpdk-dev] [PATCH v7 0/6] Elastic Flow Distributor De Lara Guarch, Pablo
2017-01-17 22:23 ` [dpdk-dev] [PATCH v8 " Pablo de Lara
2017-01-17 22:23 ` [dpdk-dev] [PATCH v8 1/6] efd: new Elastic Flow Distributor library Pablo de Lara
2017-01-18 18:56 ` Thomas Monjalon
2017-01-18 19:27 ` De Lara Guarch, Pablo
2017-01-18 19:44 ` Thomas Monjalon
2017-01-17 22:23 ` [dpdk-dev] [PATCH v8 2/6] efd: add AVX2 vect lookup function Pablo de Lara
2017-01-17 22:23 ` [dpdk-dev] [PATCH v8 3/6] app/test: add EFD functional and perf tests Pablo de Lara
2017-01-17 22:23 ` [dpdk-dev] [PATCH v8 4/6] examples/flow_distributor: sample app to demonstrate EFD usage Pablo de Lara
2017-01-17 22:23 ` [dpdk-dev] [PATCH v8 5/6] doc: add EFD library section in Programmers guide Pablo de Lara
2017-01-17 22:23 ` [dpdk-dev] [PATCH v8 6/6] doc: add flow distributor guide Pablo de Lara
2017-01-18 19:57 ` [dpdk-dev] [PATCH v8 0/6] Elastic Flow Distributor Thomas Monjalon
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=F15AFC7D20A92244A577550D05A7A984B2512DED@ORSMSX103.amr.corp.intel.com \
--to=christian.maciocco@intel.com \
--cc=dev@dpdk.org \
--cc=pablo.de.lara.guarch@intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).