[dpdk-dev] [PATCH v8 0/6] Elastic Flow Distributor

[Thomas Monjalon]

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