[dpdk-dev] [PATCH v6 0/5] Elastic Flow Distributor

Thomas Monjalon thomas.monjalon at 6wind.com
Tue Jan 17 21:29:44 CET 2017


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



More information about the dev mailing list