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
