> -----Original Message----- > From: dev [mailto:dev-boun...@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.gua...@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.macio...@intel.com>
