From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga07.intel.com (mga07.intel.com [134.134.136.100]) by dpdk.org (Postfix) with ESMTP id 3B16A5A29 for ; Thu, 12 Jan 2017 23:15:23 +0100 (CET) Received: from orsmga005.jf.intel.com ([10.7.209.41]) by orsmga105.jf.intel.com with ESMTP; 12 Jan 2017 14:14:20 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.33,220,1477983600"; d="scan'208";a="52377447" Received: from silpixa00381631.ir.intel.com (HELO silpixa00381631.ger.corp.intel.com) ([10.237.222.122]) by orsmga005.jf.intel.com with ESMTP; 12 Jan 2017 14:14:19 -0800 From: Pablo de Lara To: dev@dpdk.org Cc: Pablo de Lara Date: Thu, 12 Jan 2017 22:15:55 +0000 Message-Id: <1484259360-198276-1-git-send-email-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1483751166-32423-1-git-send-email-pablo.de.lara.guarch@intel.com> References: <1483751166-32423-1-git-send-email-pablo.de.lara.guarch@intel.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Subject: [dpdk-dev] [PATCH v3 0/5] Elastic Flow Distributor X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 12 Jan 2017 22:15:23 -0000 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 Changes in v3: - Fixed SVG files - Fixed copyright dates - Reformatted parts of documentation 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 | 5 +- 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 | 428 +++++++ doc/guides/prog_guide/img/efd_i1.svg | 130 ++ doc/guides/prog_guide/img/efd_i10.svg | 384 ++++++ doc/guides/prog_guide/img/efd_i11.svg | 319 +++++ doc/guides/prog_guide/img/efd_i12.svg | 1008 +++++++++++++++ doc/guides/prog_guide/img/efd_i2.svg | 280 +++++ doc/guides/prog_guide/img/efd_i3.svg | 634 ++++++++++ doc/guides/prog_guide/img/efd_i4.svg | 203 +++ doc/guides/prog_guide/img/efd_i5.svg | 183 +++ doc/guides/prog_guide/img/efd_i6.svg | 1254 +++++++++++++++++++ doc/guides/prog_guide/img/efd_i7.svg | 790 ++++++++++++ doc/guides/prog_guide/img/efd_i8.svg | 182 +++ doc/guides/prog_guide/img/efd_i9.svg | 390 ++++++ doc/guides/prog_guide/index.rst | 23 + doc/guides/rel_notes/release_17_02.rst | 15 + doc/guides/sample_app_ug/flow_distributor.rst | 494 ++++++++ doc/guides/sample_app_ug/img/flow_distributor.svg | 1254 +++++++++++++++++++ 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 | 3 +- lib/librte_eal/common/include/rte_log.h | 3 +- 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 | 3 +- 44 files changed, 12334 insertions(+), 5 deletions(-) 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_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_i7.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