From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wm0-f50.google.com (mail-wm0-f50.google.com [74.125.82.50]) by dpdk.org (Postfix) with ESMTP id CDFD8FAEE for ; Wed, 18 Jan 2017 20:57:09 +0100 (CET) Received: by mail-wm0-f50.google.com with SMTP id c206so42993373wme.0 for ; Wed, 18 Jan 2017 11:57:09 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=6wind-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:user-agent:in-reply-to :references:mime-version:content-transfer-encoding; bh=pG4NYqmhLFFPVuUu7bV1KJudCeKg40u21iybTLRqlBM=; b=ScHiTODIPgdaXMxf8gb7Pknci60h0zePLULt2KqJ6JRaocALi2bv8VppYb3ZkNcQ/T Q1GrQOeRkQXaEd/P6w0pPYLIHBM82nVpRj2mYDwV+adtl+05donoCAtKi1DKX1GU5/Zu eENfHHXkK0QwdmgrH0ZP7LlMNvMomacBb7RIG17uG89s/F5VgNzlgAFDgDonioNoOo7u OQQ+DSCQhIZd9EGYKZxbLzlipeCbOwueEDsK/hfn8+UhL2/ctsv9tSQ09T7MnhSAXLTC WvC0SF1HiOImd8rhts59pTCa1aMn4WO1jh1O8mf5mMXjwIEbdaw1OEbZqX45uP4FiQAU /9OA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:user-agent :in-reply-to:references:mime-version:content-transfer-encoding; bh=pG4NYqmhLFFPVuUu7bV1KJudCeKg40u21iybTLRqlBM=; b=FD6DcQT9v1RIzQQ4sls+XOct9/iIohys+rSIetQvhMGn3P7V3x5OERRkRxJJ8SlYck 5/vVO8rd4Sve17Z8BbHVDT3HEanlV+GThXn0RPRz7MsQgMsA630y91VvonWoRE3erSjn iy2K6dhO++o/pIyg+eYJWRvLyK9EAu53A4URCe3IpRqFfW///ve8alT+itEW3QVmR6Xp sPinQmgPqejBzhi2eqM8O6++JKKPAsUMaBXvlrYdh9XqjgRlA94f2W4+rvoysHIyA0mA ZHfQ/GOuIs6TJBQ/JInQuCLB5UUjhL0tJvFoj1deInZC+VbtIQ0tZFgOFYWv+QxYOxeR +ERw== X-Gm-Message-State: AIkVDXLX5dh2CchJcK0YlmK109mxHsSpZ11AFgpXHYcvwyqYF9mg1S+p7XpnRwchKGA7qhpS X-Received: by 10.28.46.74 with SMTP id u71mr3968380wmu.136.1484769429532; Wed, 18 Jan 2017 11:57:09 -0800 (PST) Received: from xps13.localnet (184.203.134.77.rev.sfr.net. [77.134.203.184]) by smtp.gmail.com with ESMTPSA id q1sm7126419wmd.6.2017.01.18.11.57.08 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 18 Jan 2017 11:57:08 -0800 (PST) From: Thomas Monjalon To: Pablo de Lara Cc: dev@dpdk.org Date: Wed, 18 Jan 2017 20:57:07 +0100 Message-ID: <14708124.1KBzAnKM0v@xps13> User-Agent: KMail/4.14.10 (Linux/4.5.4-1-ARCH; KDE/4.14.11; x86_64; ; ) In-Reply-To: <1484691836-193472-1-git-send-email-pablo.de.lara.guarch@intel.com> References: <1484691037-192026-1-git-send-email-pablo.de.lara.guarch@intel.com> <1484691836-193472-1-git-send-email-pablo.de.lara.guarch@intel.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Subject: Re: [dpdk-dev] [PATCH v8 0/6] 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: Wed, 18 Jan 2017 19:57:10 -0000 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 adva= ntages: > first, because it uses perfect hashing it does not store the key itse= lf and > hence lookup performance is not dependent on the key size. Second, th= e > 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. >=20 > 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 i= nput key to > the correct value is found. However, rather than explicitly storing a= ll keys and > their associated values, EFD stores only indices of hash functions th= at map keys > to values, and thereby consumes much less space than conventional fl= ow-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. >=20 > 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 p= roduces the > correct outputs for each key in the group. > It should be mentioned that since in the online lookup table for EFD = doesn=E2=80=99t > 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 irrespectiv= e of the > length of the key which is a highly desirable feature especially for = longer > keys. >=20 > Library code is included in the patch, plus an sample application tha= t shows > how the library can be used. Applied, thanks