DPDK patches and discussions
 help / color / mirror / Atom feed
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 v8 0/6] Elastic Flow Distributor
Date: Wed, 18 Jan 2017 20:57:07 +0100	[thread overview]
Message-ID: <14708124.1KBzAnKM0v@xps13> (raw)
In-Reply-To: <1484691836-193472-1-git-send-email-pablo.de.lara.guarch@intel.com>

2017-01-17 22:23, 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.

Applied, thanks

      parent reply	other threads:[~2017-01-18 19:57 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           ` [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               ` Thomas Monjalon [this message]

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=14708124.1KBzAnKM0v@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).