All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH 0/2] Elastic Flow Distributor
@ 2016-12-02 14:52 Pablo de Lara
  2016-12-02 14:52 ` [PATCH 1/2] efd: new Elastic Flow Distributor library Pablo de Lara
                   ` (2 more replies)
  0 siblings, 3 replies; 63+ messages in thread
From: Pablo de Lara @ 2016-12-02 14:52 UTC (permalink / raw)
  To: dev; +Cc: 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

For more information on the library, check out the following document: 
https://github.com/pablodelara/perfect_hash_flow_distributor/blob/master/EFD_description.pdf


Pablo de Lara (2):
  efd: new Elastic Flow Distributor library
  examples/flow_distributor: sample app to demonstrate EFD usage

 config/common_base                             |    5 +
 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                       | 1203 ++++++++++++++++++++++++
 lib/librte_efd/rte_efd.h                       |  312 ++++++
 lib/librte_efd/rte_efd_version.map             |   12 +
 mk/rte.app.mk                                  |    1 +
 19 files changed, 3305 insertions(+)
 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

^ permalink raw reply	[flat|nested] 63+ messages in thread

end of thread, other threads:[~2017-01-18 19:57 UTC | newest]

Thread overview: 63+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-12-02 14:52 [PATCH 0/2] Elastic Flow Distributor Pablo de Lara
2016-12-02 14:52 ` [PATCH 1/2] efd: new Elastic Flow Distributor library Pablo de Lara
2016-12-02 14:52 ` [PATCH 2/2] examples/flow_distributor: sample app to demonstrate EFD usage Pablo de Lara
2017-01-07  1:06 ` [PATCH v2 0/5] Elastic Flow Distributor Pablo de Lara
2017-01-07  1:06   ` [PATCH v2 1/5] efd: new Elastic Flow Distributor library Pablo de Lara
2017-01-07  1:06   ` [PATCH v2 2/5] app/test: add EFD functional and perf tests Pablo de Lara
2017-01-07  1:06   ` [PATCH v2 3/5] examples/flow_distributor: sample app to demonstrate EFD usage Pablo de Lara
2017-01-07  1:06   ` [PATCH v2 4/5] doc: add EFD library section in Programmers guide Pablo de Lara
2017-01-07  1:06   ` [PATCH v2 5/5] doc: add flow distributor guide Pablo de Lara
2017-01-09 18:19   ` [PATCH v2 0/5] Elastic Flow Distributor Maciocco, Christian
2017-01-12 22:15   ` [PATCH v3 " Pablo de Lara
2017-01-12 22:15     ` [PATCH v3 1/5] efd: new Elastic Flow Distributor library Pablo de Lara
2017-01-12 22:15     ` [PATCH v3 2/5] app/test: add EFD functional and perf tests Pablo de Lara
2017-01-12 22:15     ` [PATCH v3 3/5] examples/flow_distributor: sample app to demonstrate EFD usage Pablo de Lara
2017-01-12 22:15     ` [PATCH v3 4/5] doc: add EFD library section in Programmers guide Pablo de Lara
2017-01-12 22:16     ` [PATCH v3 5/5] doc: add flow distributor guide Pablo de Lara
2017-01-15 12:04     ` [PATCH v4 0/5] Elastic Flow Distributor Pablo de Lara
2017-01-15 12:04       ` [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       ` [PATCH v4 2/5] app/test: add EFD functional and perf tests Pablo de Lara
2017-01-15 12:04       ` [PATCH v4 3/5] examples/flow_distributor: sample app to demonstrate EFD usage Pablo de Lara
2017-01-15 12:04       ` [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       ` [PATCH v4 5/5] doc: add flow distributor guide Pablo de Lara
2017-01-16  9:43       ` [PATCH v5 0/5] Elastic Flow Distributor Pablo de Lara
2017-01-16  9:43         ` [PATCH v5 1/5] efd: new Elastic Flow Distributor library Pablo de Lara
2017-01-16  9:43         ` [PATCH v5 2/5] app/test: add EFD functional and perf tests Pablo de Lara
2017-01-16  9:43         ` [PATCH v5 3/5] examples/flow_distributor: sample app to demonstrate EFD usage Pablo de Lara
2017-01-16  9:43         ` [PATCH v5 4/5] doc: add EFD library section in Programmers guide Pablo de Lara
2017-01-16  9:43         ` [PATCH v5 5/5] doc: add flow distributor guide Pablo de Lara
2017-01-16 15:08         ` [PATCH v5 0/5] Elastic Flow Distributor Thomas Monjalon
2017-01-17  8:34           ` De Lara Guarch, Pablo
2017-01-16 19:21         ` [PATCH v6 " Pablo de Lara
2017-01-16 19:21           ` [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           ` [PATCH v6 2/5] app/test: add EFD functional and perf tests Pablo de Lara
2017-01-16 19:21           ` [PATCH v6 3/5] examples/flow_distributor: sample app to demonstrate EFD usage Pablo de Lara
2017-01-16 19:21           ` [PATCH v6 4/5] doc: add EFD library section in Programmers guide Pablo de Lara
2017-01-16 19:21           ` [PATCH v6 5/5] doc: add flow distributor guide Pablo de Lara
2017-01-17 20:35             ` Thomas Monjalon
2017-01-17 20:29           ` [PATCH v6 0/5] Elastic Flow Distributor Thomas Monjalon
2017-01-17 22:10           ` [PATCH v7 0/6] " Pablo de Lara
2017-01-17 22:10             ` [PATCH v7 1/6] efd: new Elastic Flow Distributor library Pablo de Lara
2017-01-17 22:10             ` [PATCH v7 2/6] efd: add AVX2 vect lookup function Pablo de Lara
2017-01-17 22:10             ` [PATCH v7 3/6] app/test: add EFD functional and perf tests Pablo de Lara
2017-01-17 22:10             ` [PATCH v7 4/6] examples/flow_distributor: sample app to demonstrate EFD usage Pablo de Lara
2017-01-17 22:10             ` [PATCH v7 5/6] doc: add EFD library section in Programmers guide Pablo de Lara
2017-01-17 22:10             ` [PATCH v7 6/6] doc: add flow distributor guide Pablo de Lara
2017-01-17 22:18             ` [PATCH v7 0/6] Elastic Flow Distributor De Lara Guarch, Pablo
2017-01-17 22:23             ` [PATCH v8 " Pablo de Lara
2017-01-17 22:23               ` [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               ` [PATCH v8 2/6] efd: add AVX2 vect lookup function Pablo de Lara
2017-01-17 22:23               ` [PATCH v8 3/6] app/test: add EFD functional and perf tests Pablo de Lara
2017-01-17 22:23               ` [PATCH v8 4/6] examples/flow_distributor: sample app to demonstrate EFD usage Pablo de Lara
2017-01-17 22:23               ` [PATCH v8 5/6] doc: add EFD library section in Programmers guide Pablo de Lara
2017-01-17 22:23               ` [PATCH v8 6/6] doc: add flow distributor guide Pablo de Lara
2017-01-18 19:57               ` [PATCH v8 0/6] Elastic Flow Distributor Thomas Monjalon

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.