From: Thomas Monjalon <thomas.monjalon@6wind.com>
To: Pablo de Lara <pablo.de.lara.guarch@intel.com>
Cc: dev@dpdk.org
Subject: Re: [dpdk-dev] [PATCH v6 0/5] Elastic Flow Distributor
Date: Tue, 17 Jan 2017 21:29:44 +0100 [thread overview]
Message-ID: <2025228.QPsT3Dr00a@xps13> (raw)
In-Reply-To: <1484594519-227376-1-git-send-email-pablo.de.lara.guarch@intel.com>
2017-01-16 19:21, Pablo de Lara:
> 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
>
> Changes in v6:
>
> - Separated x86 SIMD code in different file
It would have been nice to make a separate patch for x86.
> - Fixed shared library compilation
> - Fixed figure reference in documentation
> - Added missing parameter documentation
Unfortunately, there is another compilation error on ARM:
lib/librte_efd/rte_efd.c:39:23: fatal error:
immintrin.h: No such file or directory
next prev parent reply other threads:[~2017-01-17 20:29 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 ` [dpdk-dev] [PATCH v2 0/5] Elastic Flow Distributor Maciocco, Christian
2017-01-12 22:15 ` [dpdk-dev] [PATCH v3 " 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 ` Thomas Monjalon [this message]
2017-01-17 22:10 ` [dpdk-dev] [PATCH v7 0/6] Elastic Flow Distributor 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=2025228.QPsT3Dr00a@xps13 \
--to=thomas.monjalon@6wind.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).