From patchwork Tue Aug 22 00:19:53 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: "Wang, Yipeng1" X-Patchwork-Id: 27709 Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [IPv6:::1]) by dpdk.org (Postfix) with ESMTP id D5AED7D6E; Tue, 22 Aug 2017 02:21:13 +0200 (CEST) Received: from mga02.intel.com (mga02.intel.com [134.134.136.20]) by dpdk.org (Postfix) with ESMTP id 2B9CC7D4F for ; Tue, 22 Aug 2017 02:21:11 +0200 (CEST) Received: from fmsmga004.fm.intel.com ([10.253.24.48]) by orsmga101.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 21 Aug 2017 17:21:10 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.41,410,1498546800"; d="scan'208";a="302858660" Received: from bdw-yipeng.jf.intel.com ([10.54.81.30]) by fmsmga004.fm.intel.com with ESMTP; 21 Aug 2017 17:21:09 -0700 From: Yipeng Wang To: vincent.jardin@6wind.com, stephen@networkplumber.org, bruce.richardson@intel.com, konstantin.ananyev@intel.com, thomas@monjalon.net Cc: dev@dpdk.org, yipeng1.wang@intel.com, charlie.tai@intel.com, sameh.gobriel@intel.com, ren.wang@intel.com Date: Mon, 21 Aug 2017 17:19:53 -0700 Message-Id: <1503361193-36699-8-git-send-email-yipeng1.wang@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1503361193-36699-1-git-send-email-yipeng1.wang@intel.com> References: <1503361193-36699-1-git-send-email-yipeng1.wang@intel.com> MIME-Version: 1.0 Subject: [dpdk-dev] [PATCH 7/7] doc: add membership documentation 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: , Errors-To: dev-bounces@dpdk.org Sender: "dev" This patch adds the documentation for membership library. Signed-off-by: Yipeng Wang --- doc/api/doxy-api-index.md | 3 +- doc/api/doxy-api.conf | 1 + doc/guides/prog_guide/img/member_i1.svg | 1613 +++++++++++++++++++++++++++++++ doc/guides/prog_guide/img/member_i2.svg | 36 + doc/guides/prog_guide/img/member_i3.svg | 148 +++ doc/guides/prog_guide/img/member_i4.svg | 450 +++++++++ doc/guides/prog_guide/img/member_i5.svg | 163 ++++ doc/guides/prog_guide/img/member_i6.svg | 332 +++++++ doc/guides/prog_guide/img/member_i7.svg | 399 ++++++++ doc/guides/prog_guide/index.rst | 14 + doc/guides/prog_guide/member_lib.rst | 432 +++++++++ doc/guides/rel_notes/release_17_11.rst | 17 + 12 files changed, 3607 insertions(+), 1 deletion(-) create mode 100644 doc/guides/prog_guide/img/member_i1.svg create mode 100644 doc/guides/prog_guide/img/member_i2.svg create mode 100644 doc/guides/prog_guide/img/member_i3.svg create mode 100644 doc/guides/prog_guide/img/member_i4.svg create mode 100644 doc/guides/prog_guide/img/member_i5.svg create mode 100644 doc/guides/prog_guide/img/member_i6.svg create mode 100644 doc/guides/prog_guide/img/member_i7.svg create mode 100644 doc/guides/prog_guide/member_lib.rst diff --git a/doc/api/doxy-api-index.md b/doc/api/doxy-api-index.md index 19e0d4f..fe87e09 100644 --- a/doc/api/doxy-api-index.md +++ b/doc/api/doxy-api-index.md @@ -105,7 +105,8 @@ The public API headers are grouped by topics: [LPM IPv4 route] (@ref rte_lpm.h), [LPM IPv6 route] (@ref rte_lpm6.h), [ACL] (@ref rte_acl.h), - [EFD] (@ref rte_efd.h) + [EFD] (@ref rte_efd.h), + [member] (@ref rte_member.h) - **QoS**: [metering] (@ref rte_meter.h), diff --git a/doc/api/doxy-api.conf b/doc/api/doxy-api.conf index 823554f..b792d6d 100644 --- a/doc/api/doxy-api.conf +++ b/doc/api/doxy-api.conf @@ -58,6 +58,7 @@ INPUT = doc/api/doxy-api-index.md \ lib/librte_mempool \ lib/librte_meter \ lib/librte_metrics \ + lib/librte_member \ lib/librte_net \ lib/librte_pdump \ lib/librte_pipeline \ diff --git a/doc/guides/prog_guide/img/member_i1.svg b/doc/guides/prog_guide/img/member_i1.svg new file mode 100644 index 0000000..fc5f56a --- /dev/null +++ b/doc/guides/prog_guide/img/member_i1.svg @@ -0,0 +1,1613 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Page-1 + + + + Sheet.165 + + Sheet.1 + + Circle + List 1 matching Criteria 1 + + + + + + + + + List 1 matching Criteria 1 + + List 1 matching Criteria 1 + + Circle.23 + List 2 + + + + + + + + + List 2 + + List 2 + + Circle.24 + List 1 matching Criteria 1 + + + + + + + + + List 1 matching Criteria 1 + + List 1 matching Criteria 1 + + Sheet.5 + + Triangle + + + + + + + + + + Sheet.7 + setsum + + + + setsum + + + Circle.29 + List 2 matching Criteria 2 + + + + + + + + + List 2 matching Criteria 2 + + List 2 matching Criteria 2 + + + Sheet.9 + + Sheet.10 + + Triangle + + + + + + + + + + Sheet.12 + Set Summary + + + + Set Summary + + + Sheet.13 + + + + + + + Sheet.14 + Flow Key + + + + Flow Key + + Sheet.15 + + + + + + + Sheet.16 + + + + + + + Sheet.17 + + + + + + + Sheet.18 + + + + + + + Sheet.19 + New Flow => New Assignment + + + + New Flow => New Assignment + + Sheet.20 + + + + + + + Sheet.21 + Old Flow => forward to specific thread + + + + Old Flow => forward to specific thread + + Sheet.22 + + + + + + + Sheet.23 + + + + + + + Sheet.24 + + + + + + + + Sheet.25 + + Circle + + + + + + + + + + Circle.156 + + + + + + + + + + Circle.157 + + + + + + + + + + Circle.158 + + + + + + + + + + Circle.159 + + + + + + + + + + Sheet.31 + + + + + + + Sheet.32 + + + + + + + Sheet.33 + + + + + + + Sheet.34 + + + + + + + Sheet.35 + + + + + + + Rectangle.167 + SUM + + + + + + + + + + SUM + + Rectangle.168 + Packet + + + + + + + + + + + Packet + + Rectangle.169 + SUM + + + + + + + + + + SUM + + Rectangle.170 + Packet + + + + + + + + + + + Packet + + Sheet.40 + + + + Sheet.41 + + + + + + + Sheet.42 + Encode ID + + + + Encode ID + + + Sheet.43 + + + + + + User + + Sheet.45 + + + + + + + + + + + + + + + + + + + Sheet.46 + + + + + + + Sheet.47 + + + + + + + Sheet.48 + + + + + + + + + + + + User.7 + + Sheet.50 + + + + + + + + + + + + + + + + + + + Sheet.51 + + + + + + + Sheet.52 + + + + + + + Sheet.53 + + + + + + + + + + + + User.12 + + Sheet.55 + + + + + + + + + + + + + + + + + + + Sheet.56 + + + + + + + Sheet.57 + + + + + + + Sheet.58 + + + + + + + + + + + + Data Center + + Sheet.60 + + + + + + + Sheet.61 + + + + + + + Sheet.62 + + + + + + + Sheet.63 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Load balancer + + Sheet.65 + + + + + + + + + + + Sheet.66 + + + + + + + + + + + + Directory server + + Sheet.68 + + + + + + + Sheet.69 + + + + Sheet.70 + + + + Sheet.71 + + + + Sheet.72 + + + + Sheet.73 + + + + Sheet.74 + + + + Sheet.75 + + + + Sheet.76 + + + + Sheet.77 + + + + Sheet.78 + + + + Sheet.79 + + + + Sheet.80 + + + + Sheet.81 + + + + Sheet.82 + + + + Sheet.83 + + + + Sheet.84 + + + + Sheet.85 + + + + + Sheet.86 + + + + + Sheet.87 + + + + + Sheet.88 + + + + + Sheet.89 + + + + + Sheet.90 + + + + Sheet.91 + + + + Sheet.92 + + + + Sheet.93 + + + + Sheet.94 + + + + Sheet.95 + + + + Sheet.96 + + + + Sheet.97 + + + + Sheet.98 + + + + Sheet.99 + + + + Sheet.100 + + + + Sheet.101 + + + + Sheet.102 + + + + Sheet.103 + + + + + + + + Sheet.104 + + + + Sheet.105 + + + + + + Sheet.106 + + + + + + + + + Directory server.104 + + Sheet.108 + + + + + + + Sheet.109 + + + + Sheet.110 + + + + Sheet.111 + + + + Sheet.112 + + + + Sheet.113 + + + + Sheet.114 + + + + Sheet.115 + + + + Sheet.116 + + + + Sheet.117 + + + + Sheet.118 + + + + Sheet.119 + + + + Sheet.120 + + + + Sheet.121 + + + + Sheet.122 + + + + Sheet.123 + + + + Sheet.124 + + + + Sheet.125 + + + + + Sheet.126 + + + + + Sheet.127 + + + + + Sheet.128 + + + + + Sheet.129 + + + + + Sheet.130 + + + + Sheet.131 + + + + Sheet.132 + + + + Sheet.133 + + + + Sheet.134 + + + + Sheet.135 + + + + Sheet.136 + + + + Sheet.137 + + + + Sheet.138 + + + + Sheet.139 + + + + Sheet.140 + + + + Sheet.141 + + + + Sheet.142 + + + + Sheet.143 + + + + + + + + Sheet.144 + + + + Sheet.145 + + + + + + Sheet.146 + + + + + Cloud + + + + + + + + + + + + + + Triangle + setsum + + + + + + + + + + setsum + + Sheet.149 + + + + + + + Sheet.150 + + + + + + + Sheet.151 + + + + + + + Sheet.152 + Clients + + + + Clients + + Sheet.153 + Distributed Cache + + + + Distributed Cache + + Sheet.154 + Web Servers + + + + Web Servers + + Simple Arrow + + + + + + + + + + + Simple Arrow.153 + + + + + + + + + + + + Rectangle + + + + + + + + + + Rectangle.158 + + + + + + + + + + Rectangle.159 + + + + + + + + + + Rectangle.160 + + + + + + + + + + Sheet.161 + (a) Distributed Web Cache + + + + + + + (a) Distributed Web Cache + + Sheet.162 + (b) Detecting Routing Loops + + + + + + + (b) Detecting Routing Loops + + Sheet.163 + (c) In-order Workload Scheduler + + + + + + + (c) In-order Workload Scheduler + + Sheet.164 + (d) Database Semi-join Operations + + + + + + + (d) Database Semi-join Operations + + + diff --git a/doc/guides/prog_guide/img/member_i2.svg b/doc/guides/prog_guide/img/member_i2.svg new file mode 100644 index 0000000..759c654 --- /dev/null +++ b/doc/guides/prog_guide/img/member_i2.svg @@ -0,0 +1,36 @@ + + + + + + + + + + Page-1 + + + Sheet.3 + False Positive Probability = (1-(1-1/m)kn)k ≃ (1-ekn/m)k + + + + False Positive Probability = (1-(1-1/m)kn)k ≃ (1-ekn/m)k + + diff --git a/doc/guides/prog_guide/img/member_i3.svg b/doc/guides/prog_guide/img/member_i3.svg new file mode 100644 index 0000000..41e92cb --- /dev/null +++ b/doc/guides/prog_guide/img/member_i3.svg @@ -0,0 +1,148 @@ + + + + + + + + + + + + + + + + + + + + + + + + Page-1 + + Sheet.174 + + Circle + + + + + + + Circle.156 + + + + + + + Circle.157 + + + + + + + Circle.158 + + + + + + + Circle.159 + + + + + + + Sheet.160 + + + + Sheet.161 + + + + Sheet.162 + + + + Sheet.163 + + + + Sheet.164 + + + + Rectangle.167 + BF of IDs + + + + + BF of IDs + + Rectangle.168 + Packet + + + + + Packet + + Rectangle.169 + BF of IDs + + + + + BF of IDs + + Rectangle.170 + Packet + + + + + Packet + + Sheet.171 + + + + Sheet.172 + + + + Sheet.173 + Encode ID + + Encode ID + + + diff --git a/doc/guides/prog_guide/img/member_i4.svg b/doc/guides/prog_guide/img/member_i4.svg new file mode 100644 index 0000000..a2b6f2f --- /dev/null +++ b/doc/guides/prog_guide/img/member_i4.svg @@ -0,0 +1,450 @@ + + + + + + + + + + + + + + + + + + + + + Page-1 + + + Sheet.47 + + Sheet.1 + Element + + + + Element + + Sheet.2 + + + + + + + Rectangle.54 + + + + + + + + + + Rectangle.55 + + + + + + + + + + Rectangle.56 + + + + + + + + + + Rectangle.57 + + + + + + + + + + Rectangle.58 + + + + + + + + + + Rectangle.59 + + + + + + + + + + Sheet.9 + BF-1 + + + + BF-1 + + Rectangle.74 + + + + + + + + + + Rectangle.75 + + + + + + + + + + Rectangle.76 + + + + + + + + + + Rectangle.77 + + + + + + + + + + Rectangle.78 + + + + + + + + + + Rectangle.79 + + + + + + + + + + Rectangle.81 + + + + + + + + + + Rectangle.82 + + + + + + + + + + Rectangle.83 + + + + + + + + + + Rectangle.84 + + + + + + + + + + Rectangle.85 + + + + + + + + + + Rectangle.86 + + + + + + + + + + Rectangle.88 + + + + + + + + + + Rectangle.89 + + + + + + + + + + Rectangle.90 + + + + + + + + + + Rectangle.91 + + + + + + + + + + Rectangle.92 + + + + + + + + + + Rectangle.93 + + + + + + + + + + Sheet.28 + + + + + + + Sheet.29 + + + + + + + Sheet.31 + + Block Arrow + + + + + + + + + + Sheet.33 + h1, h2 .. hk + + + + h1, h2 .. hk + + + Sheet.34 + + + + + + + Sheet.35 + + + + + + + Sheet.36 + + + + + + + Sheet.37 + + + + + + + Sheet.38 + BF-2 + + + + BF-2 + + Sheet.39 + BF-X + + + + BF-X + + Sheet.40 + BF-L + + + + BF-L + + Sheet.41 + Hashing for lookup/Insertion into a vector of BFs happens once + + + + Hashing for lookup/Insertion into a vector of BFs happens once + + Sheet.44 + + + + + + + Sheet.45 + Lookup/Insertion is done in the series of BFs, one by one or ... + + + + Lookup/Insertion is done in the series of BFs, one by one or can be optimized to do in parallel. + + Sheet.46 + + + + + + + + diff --git a/doc/guides/prog_guide/img/member_i5.svg b/doc/guides/prog_guide/img/member_i5.svg new file mode 100644 index 0000000..c1728cf --- /dev/null +++ b/doc/guides/prog_guide/img/member_i5.svg @@ -0,0 +1,163 @@ + + + + + + + + + + + + + + + + + + + + + Page-1 + + + Sheet.1 + + Triangle + + + + + + + + + + Sheet.3 + vBF + + + + vBF + + + Sheet.4 + + + + + + + Sheet.5 + Flow Key + + + + Flow Key + + Sheet.6 + + + + + + + Sheet.7 + + + + + + + Sheet.8 + + + + + + + Sheet.9 + + + + + + + Sheet.10 + New Flow => New Assignment + + + + New Flow => New Assignment + + Sheet.11 + + + + + + + Sheet.12 + Old Flow => forward to specific thread + + + + Old Flow => forward to specific thread + + Sheet.13 + + + + + + + Sheet.14 + + + + + + + Sheet.15 + + + + + + + Sheet.17 + + + + Sheet.18 + A BF corresponding to each worker thread + + + + A BF corresponding to each worker thread + + diff --git a/doc/guides/prog_guide/img/member_i6.svg b/doc/guides/prog_guide/img/member_i6.svg new file mode 100644 index 0000000..265179f --- /dev/null +++ b/doc/guides/prog_guide/img/member_i6.svg @@ -0,0 +1,332 @@ + + + + + + + + + + + + + + + + + + Page-1 + + + Sheet.121 + + Rectangle.2 + + + + + + + + + + Rectangle.4 + + + + + + + + + + Rectangle.10 + Signatures for target 1 + + + + + + + + + + Signatures fortarget 1 + + Sheet.53 + + + + + + + Sheet.54 + Match 1 + + + + Match 1 + + Sheet.55 + Packet Payload + + + + Packet Payload + + Sheet.56 + + + + + + + Sheet.96 + Attack Signature Length 1 + + + + Attack Signature Length 1 + + Sheet.114 + + Sheet.106 + + Rectangle.100 + + + + + + + + + + Rectangle.101 + + + + + + + + + + Rectangle.102 + + + + + + + + + + Rectangle.103 + + + + + + + + + + Rectangle.104 + + + + + + + + + + Rectangle.105 + + + + + + + + + + + Sheet.107 + + Rectangle.100 + + + + + + + + + + Rectangle.101 + + + + + + + + + + Rectangle.102 + + + + + + + + + + Rectangle.103 + + + + + + + + + + + Rectangle.104 + + + + + + + + + + Rectangle.105 + + + + + + + + + + + + + Sheet.89 + + + + + + + Rectangle.115 + Signatures for target 2 + + + + + + + + + + Signatures fortarget 2 + + Sheet.116 + Attack Signature Length 2 + + + + Attack Signature Length 2 + + Sheet.118 + Attack Signature Length L + + + + Attack Signature Length L + + Sheet.119 + + + + + + + Sheet.120 + Match 2 + + + + Match 2 + + Sheet.85 + + + + + + + Sheet.117 + Attack Signature Length X + + + + Attack Signature Length X + + + Sheet.122 + HTSS + + + + HTSS + + diff --git a/doc/guides/prog_guide/img/member_i7.svg b/doc/guides/prog_guide/img/member_i7.svg new file mode 100644 index 0000000..e23ae26 --- /dev/null +++ b/doc/guides/prog_guide/img/member_i7.svg @@ -0,0 +1,399 @@ + + + + + + + + + + + + + + + + + + + + + + + + Page-1 + + + Sheet.121 + + Rectangle.2 + + + + + + + + + + Rectangle.4 + + + + + + + + + + Rectangle.10 + Flow Keys Matching Mask 1 + + + + + + + + + + Flow Keys Matching Mask 1 + + Sheet.53 + + + + + + + Sheet.54 + Match + + + + Match + + Sheet.55 + Flow ID1 + + + + Flow ID1 + + Sheet.96 + Flow Mask 1 + + + + Flow Mask 1 + + Sheet.114 + + Sheet.106 + + Rectangle.100 + + + + + + + + + + Rectangle.101 + + + + + + + + + + Rectangle.102 + + + + + + + + + + Rectangle.103 + + + + + + + + + + Rectangle.104 + + + + + + + + + + Rectangle.105 + + + + + + + + + + + Sheet.107 + + Rectangle.100 + + + + + + + + + + Rectangle.101 + + + + + + + + + + Rectangle.102 + + + + + + + + + + + Rectangle.103 + + + + + + + + + + + Rectangle.104 + + + + + + + + + + Rectangle.105 + + + + + + + + + + + + + Sheet.89 + + + + + + + Rectangle.115 + Flow Keys Matching Mask 2 + + + + + + + + + + Flow Keys Matching Mask 2 + + Sheet.85 + + + + + + + Sheet.56 + + + + + Sheet.122 + HTSS with False Negative (Cache) + + + + HTSS with False Negative (Cache) + + Sheet.123 + Active + + + + Active + + Sheet.124 + Target for Flow ID 1 + + + + Target for Flow ID 1 + + Sheet.125 + Flow ID2 + + + + + + + Flow ID2 + + Sheet.126 + New/Inactive + + + + New/Inactive + + Sheet.127 + + + + + + + Sheet.128 + Miss + + + + Miss + + Sheet.129 + Flow Mask 2 + + + + Flow Mask 2 + + Sheet.130 + + + + + + + Sheet.131 + + + + + + + Sheet.132 + + + + + + + Sheet.133 + Flow Mask X + + + + Flow Mask X + + Sheet.134 + Flow Mask L + + + + Flow Mask L + + diff --git a/doc/guides/prog_guide/index.rst b/doc/guides/prog_guide/index.rst index 40f04a1..7ff5144 100644 --- a/doc/guides/prog_guide/index.rst +++ b/doc/guides/prog_guide/index.rst @@ -50,6 +50,7 @@ Programmer's Guide timer_lib hash_lib efd_lib + member_lib lpm_lib lpm6_lib packet_distrib_lib @@ -191,6 +192,19 @@ Programmer's Guide :numref:`figure_efd11` :ref:`figure_efd11` +:numref:`figure_membership1` :ref:`figure_membership1` + +:numref:`figure_membership2` :ref:`figure_membership2` + +:numref:`figure_membership3` :ref:`figure_membership3` + +:numref:`figure_membership4` :ref:`figure_membership4` + +:numref:`figure_membership5` :ref:`figure_membership5` + +:numref:`figure_membership6` :ref:`figure_membership6` + +:numref:`figure_membership7` :ref:`figure_membership7` **Tables** diff --git a/doc/guides/prog_guide/member_lib.rst b/doc/guides/prog_guide/member_lib.rst new file mode 100644 index 0000000..48946d6 --- /dev/null +++ b/doc/guides/prog_guide/member_lib.rst @@ -0,0 +1,432 @@ +.. BSD LICENSE + Copyright(c) 2017 Intel Corporation. All rights reserved. + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in + the documentation and/or other materials provided with the + distribution. + * Neither the name of Intel Corporation nor the names of its + contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + + +.. _Member_Library: + +Membership Library +======================= + +Introduction +------------ +The DPDK Membership Library provides an API for DPDK applications to insert a +new member, delete an existing member, or query the existence of a member in a +given set, or a group of sets. For the case of a group of sets the library +will return not only whether the element has been inserted before in one of +the sets but also which set it belongs to. The Membership Library is an +extension and generalization of a traditional filter structure (for example +Bloom Filter [Member-bloom]) that has multiple usages in a wide variety of +workloads and applications. In general, the Membership Library is a data +structure that provides a “set-summary” on whether a member belongs to a set, +and as discussed in details later, there are two advantages of using such a +set-summary rather than operating on a “full-blown” complete list of elements: +first, it has a much smaller storage requirement than storing the whole list of +elements themselves, and secondly checking an element membership (or other +operations) in this set-summary is much faster than checking it for the +original full-blown complete list of elements. + +We use the term “Set-Summary” in this guide to refer to the space-efficient, +probabilistic membership data structure that is provided by the library. A +membership test for an element will return the set this element belongs to or +null (meaning not found) with very high probability of accuracy. Set-summary +is a fundamental data aggregation component that can be used in many network +(and other) applications. It is a crucial structure to address performance and +scalability issues of diverse network applications including overlay networks, +data-centric networks, flow table summaries, network statistics and +traffic monitoring. A set-summary is useful for applications who need to +include a list of elements while a complete list requires too much space +and/or too much processing cost. In these situations, the set-summary works as +a lossy hash-based representation of a set of members. It can dramatically +reduce space requirement and significantly improve the performance of set +membership queries at the cost of introducing a very small membership test error +probability. + +.. _figure_membership1: +.. figure:: img/member_i1.* + + Example Usages of Membership Library + +We believe that there are various usages for a Membership Library in a very +large set of applications and workloads. Interested readers can refer to +[Member-survey] for a survey of possible networking usages. The above figure +provide a small set of examples of using the Membership Library. Sub-figure(a) +depicts a distributed web cache architecture where a collection of proxies +attempt to share their web caches (cached from a set of backend web servers) to +provide faster responses to clients, and the proxies uses the Membership +Library to share summaries of what web pages they are caching. With the +Membership Library, a proxy receiving an \http request will inquire the +set-summary to find its location and quickly determine whether to retrieve the +requested web page from a nearby proxy or from a backend web server. +Sub-figure(b) depicts another example for using the Membership Library to +prevent routing loops which is typically done using slow TTL countdown and +dropping packets when TTL expires. As shown in Sub-figure(b), an embedded +set-summary in the packet header itself can be used to summarize the set of +nodes a packet has gone through, and each node upon receiving a packet can check +whether its id is a member of the set of visited nodes, and if it is then a +routing loop is detected. Sub-Figure(c) presents another usage of Membership +Library to load balance flows to worker threads with in-order guarantee where a +set-summary is used to query if a packet belongs to an existing flow or a new +flow. Packets belonging to a new flow are forwarded to the current least loaded +worker thread, while those belonging to an existing flow are forwarded to the +pre-assigned thread to guarantee in-order processing. Sub-figure(d) highlights +yet another usage example in the database domain where a set-summary is used to +determine joins between sets instead of creating a join by comparing each +element of a set against the other elements in a different set, a join is done +on the summaries since they can efficiently encode members of a given set. + +We are including a configurable Membership Library in DPDK to cover set +membership functionality for both a single set and multi-set scenarios. The +library is optimized to support the customer network applications which require +membership checking functionality. In this guide, we will cover two set-summary +schemes including vector of Bloom Filters and Hash-Table based +set-summary schemes with and without false negative probability, followed by +a brief discussion of the Membership Library API. + +Vector of Bloom Filters +-------------------------- + +Bloom Filter (BF) [Member-bloom] is a well-known space-efficient +probabilistic data structure that answers set membership queries (test whether +an element is a member of a set) with some probability of false positives and +zero false negatives; a query for an element returns either it is "possibly in +a set" (with very high probability) or "definitely not in a set". + +The BF is a method for representing a set of n elements (for example flow keys +in network applications domain) to support membership queries. The idea of BF is +to allocate a bit-vector v with m bits, which are initially all set to 0. Then +it chooses k independent hash functions h1, h2, … hk with hash values range from +1 to m to perform hashing calculations on each element. Every time when an +element X being inserted into the set, the bits at positions h1(X), h2(X), … +hk(X) in v are set to 1 (any particular bit might be set to 1 multiple times +for multiple different inserted elements). Given a query for any element Y, the +bits at positions h1(Y), h2(Y), ... hk(Y) are checked. If any of them is 0, +then Y is definitely not in the set. Otherwise there is a high probability that +Y is a member of the set with certain false positive probability. As shown in +the next equation, the false positive probability can be made arbitrarily small +by changing the number of hash functions (k) and the vector length (m). + +.. _figure_membership2: +.. figure:: img/member_i2.* + + Bloom Filter False Positive Probability + +Without BF, an accurate membership testing could involve a costly hash table +lookup and full element comparison. The advantage of using a BF is to simplify +the membership test into a series of hash calculations and memory accesses for a +small bit-vector, which can be easily optimized. Hence the lookup throughput +(set membership test) can be significantly faster than a normal hash table +lookup with element comparison. + +.. _figure_membership3: +.. figure:: img/member_i3.* + + Detecting Routing Loops Using BF + +BF is used for applications that need only one set, and the +membership of elements is checked against the BF. The example discussed +in the above figure is one example of potential applications that uses only one +set to capture the node IDs that have been visited so far by the packet. Each +node will then check this embedded BF in the packet header for its own id, and +if the BF indicates that the current node is definitely not in the set then a +loop-free route is guaranteed. + + +.. _figure_membership4: +.. figure:: img/member_i4.* + + Vector Bloom Filter (vBF) Overview + +To support membership test for both multiple sets and single set, +the library implements Vector Bloom Filter (vBF) scheme. +vBF basically composes of multiple bloom filters as a vector of bloom filers. +The membership test is conducted on all of the +bloom filters concurrently to determine which set(s) it belongs to or none of +them. The basic idea of vBF is shown in the above figure where an element is +used to address multiple bloom filters concurrently and the bloom filter +index(es) with a hit is returned. + +.. _figure_membership5: +.. figure:: img/member_i5.* + + vBF for Flow Scheduling to Worker Thread + +As previously mentioned, there are many usages of such structure. vBF is used +for applications that needs to check membership against multiple sets +simultaneously. The example discussed in the above figure uses a set to capture +all flows being assigned for processing at a given worker thread. Upon receiving +a packet the vBF is used to quickly figure out if this packet belongs to a new flow +so as to be forwarded to the current least loaded worker thread, or otherwise it +should be queued for an existing thread to guarantee in-order processing (i.e. +the property of vBF to indicate right away that a given flow is a new one or +not is critical to minimize response time latency). + +It should be noted that vBF can be implemented using a set of single bloom +filters with sequential lookup of each BF. However, being able to concurrently +search all set-summaries is a big throughput advantage. In the library, certain +parallelism is realized by the implementation of checking all bloom filters +together. + + +Hash-Table based Set-Summaries +--------------------------------- + +Hash-table based set-summary (HTSS) is another scheme in the membership library. +Cuckoo filter [Member-cfilter] is an example of hash-table based set summary. +HTSS can be easily extended to support multi-set membership testing like what +vBF does. Meanwhile, HTSS can easily outperform vBF when the number of sets is +large, since HTSS uses a single hash table for membership testing while vBF +requires testing a series of Bloom Filters each corresponding to one set. + +.. _figure_membership6: +.. figure:: img/member_i6.* + + Using HTSS for Attack Signature Matching + +As shown in the above figure, attack signature matching where each set +represents a certain signature length (for correctness of this example, an +attack signature should not be a subset of another one) in the payload is a good +example for using HTSS with 0% false negative (i.e., when an element returns not +found, it has a 100% certainty that it is not a member of any set). The packet +inspection application benefits from knowing right away that the current payload +does not match any attack signatures in the database to establish its +legitimacy, otherwise a deep inspection of the packet is needed. + +HTSS employs a similar but simpler data structure to a traditional hash table, +and the major difference is that HTSS stores only the signatures but not the +full keys/elements which can significantly reduce the footprint of the table. +Along with the signature, HTSS also stores a value to indicate the target set. +When looking up for an element, the element is hashed and the HTSS is addressed +to retrieve the signature stored. If the signature matches then the value is +retrieved corresponding to the index of the target set which the element belongs +to. Because signatures can collide, HTSS can still has false positive +probability similar to vBF. Furthermore, if elements are allowed to be +overwritten or evicted when the hash table becomes full, it will also have a +false negative probability. We discuss this case in the next section. + +Set-Summaries with False Negative Probability +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +As previously discussed, traditional set-summaries (e.g. Bloom Filters ) do not +have a false negative probability, i.e., it is 100% certain when an element +returns “not to be present” for a given set. However, the Membership Library +also supports a set-summary probabilistic data structure based on HTSS which +allows for false negative probability. + + +In HTSS, when the hash table becomes full, keys/elements will fail to be added +into the table and the hash table has to be resized to accommodate for these new +elements, which can be expensive. However, if we allow new elements to overwrite +or evict existing elements (as a cache typically does), then the resulting +set-summary will begin to have false negative probability. This is because the +element that was evicted from the set-summary may still be present in the target +set. For subsequent inquiries the set-summary will falsely report the element +not being in the set, hence having a false negative probability. + +The major usage of HTSS with false negative is to use it as a cache for +distributing elements to different target sets. By allowing HTSS to evict old +elements, the set-summary can keep track of the most recent elements +(i.e. active) as a cache typically does. Old inactive elements (infrequently +used elements) will automatically and eventually get evicted from the +set-summary. It worth noting that the set-summary still has false positive +probability, which means the application either can tolerate certain false positive +or it has fall-back path when false positive happens. + +.. _figure_membership7: +.. figure:: img/member_i7.* + + Using HTSS with False Negatives for Wild Card Classification + +HTSS with false negative (i.e. a cache) also has its wide set of applications. +For example wild card flow classification (e.g. ACL rules) highlighted in the +above figure is an example of such application. In that case each target set +represents a sub-table with rules defined by a certain flow mask. The flow masks +are non-overlapping, and for flows matching more than one rule only the highest +priority one is inserted in the corresponding sub-table (interested readers can +refer to the Open vSwitch (OvS) design of Mega Flow Cache (MFC) [Member-OvS] +for further details). Typically the rules will have a large number of distinct +unique masks and hence, a large number of target sets each corresponding to one +mask. Because the active set of flows varies widely based on the network +traffic, HTSS with false negative will act as a cache for pair for the current active set of flows. When a miss occurs (as +shown in red in the above figure) the sub-tables will be searched sequentially +one by one for a possible match, and when found the flow key and target +sub-table will be inserted into the set-summary (i.e. cache insertion) so +subsequent packets from the same flow don’t incur the overhead of the +sequential search of sub-tables. + +Library API Overview +-------------------- +The design goal of the Membership Library API is to be as generic as possible to +support all the different types of set-summaries we discussed in previous +sections and beyond. Fundamentally, the APIs need to include creation, +insertion, deletion, and lookup. + +.. Set-summary Type Query +.. ~~~~~~~~~~~~~~~~~~~~~~~~ + +.. *void rte\_ms\_type\_query(enum rte\_ms\_setsum\_type\*\* types)* + +.. This function intends to serve as a convenient tool to query which set-summary +.. types are supported in the current version of DPDK. Since the implementations of +.. the set-summaries can vary, initial versions of the Membership Library may only +.. support a subset of the set-summaries we discussed previously. Programmers could +.. use this API to decide which type is available to use in the current version of DPDK. + +Set-summary Create +~~~~~~~~~~~~~~~~~~~~~ + +*rte\_member\_create* function is used to create a set-summary structure, the input parameter +is a struct to pass in parameters that needed to initialize the set-summary, while the function returns the +pointer to the created set-summary or NULL if the creation failed. + +The general input arguments used when creating the set-summary should include *name* +which is the name of the created set-summary, *type* which is one of the types +supported by the library (e.g. RTE\_MEMBER\_TYPE\_HT for HTSS or RTE\_MEMBER\_TYPE\_VBF for vBF), and *key\_len* +which is the length of the element/key. There are other parameters +are only used for certain type of set-summary, or means slightly different for different types of set-summary. +For example, *num\_keys* parameter means the total number of entries for Hash table based set-summary. +However, for bloom filter, this value means the expected number of keys that could be +inserted into the bloom filter(s). The value is used to calculate the size of each +bloom filter. +We also pass two seeds: *prim\_hash\_seed* and +*sec\_hash\_seed* for the primary and secondary hash functions to calculate two independent hash values. +*socket\_id* parameter is the NUMA socket ID for the memory used to create the +set-summary. For HTSS, another parameter *iscache* is used to indicate +if this set-summary is a cache (i.e. with false negative probability) or not. +For vBF, extra parameters are needed. For example, *num\_set* is the number of +sets needed to initialize the vector bloom filters. This number is equal to the +number of bloom filters will be created. +*false\_pos\_rate* is the false positive rate. num\_keys and false\_pos\_rate will be used to determine +the number of hash functions and the bloom filter size. + + +Set-summary Element Insertion +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +.. *rte\_membership\_add(const void *setsum, const void *key, MEMBERSHIP\_TARGET\_TYPE target\_id)* + +*rte\_member\_add* is the function to insert an element/key in a set-summary structure, if it fails an +error is returned. For success the returned value is deferent based on the +set-summary mode to provide extra information for the users. For vBF +mode, a return value of 0 means a successful insert. For HTSS mode without false negative, the insert +could fail with -ENOSPC if the table is full. With false negative (i.e. cache mode), +for insert that does not cause any eviction (i.e. no overwriting happens to an +existing entry) the return value is 0. For insertion that causes eviction, the return +value is 1 to indicate such situation, but it is not an error. + +The input arguments for the function should include the *key* which is a pointer to the element/key that needs to +be added to the set-summary, and *set\_id* which is the set id associated +with the key that needs to be added. + + +Set-summary Element Lookup +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + +.. *rte\_membership\_lookup(const void \*setsum, const void \*key, MEMBERSHIP\_TARGET\_TYPE \*target\_id)* + +*rte\_member\_lookup* looks up a single key/element in the set-summary structure. It +returns as soon as the first match is found. The return value is 1 if a +match is found and 0 otherwise. The arguments for the function include *key* which is a pointer to the +element/key that needs to be looked up, and *set\_id* which is used to return the +first target set id where the key has matched, if any. + +.. *rte\_membership\_lookup\_bulk(const void \*setsum, const void \*\*keys, uint32\_t num\_keys, MEMBERSHIP\_TARGET\_TYPE \*target\_ids)* + +*rte\_member\_lookup\_bulk* is the function to look up a bulk of keys/elements in the +set-summary structure for their first match. Each key lookup returns as soon as the first match is found. The +return value is the number of keys that find a match. The arguments of the +function include *keys* which is a pointer to a bulk of keys that are to be looked up, +*num\_keys* is the number +of keys that will be looked up, and *set\_ids* are the return target set +ids for the first match found for each of the input keys. *set\_ids* is an array +needs to be sized according to the *num\_keys*. If there is no match, the set id +for that key will be set to RTE_MEMBER_NO_MATCH. + +.. *rte\_membership\_lookup\_multi(const void \*setsum, const void \*key, MEMBERSHIP\_TARGET\_TYPE \*target\_id)* + +*rte\_member\_lookup\_multi* function looks up a single key/element in the +set-summary structure for multiple matches. It +returns ALL the matches (possibly more than one) found for this key when it +is matched against all target sets (it worth noting that for cache mode HTSS, +the current implementation matches at most one target set). The return value is +the number of matches +that was found for this key (for cache mode HTSS the return value +should be at most 1). The arguments for the function include *key* which is a pointer to the +element/key that needs to be looked up, *match\_per\_key* which is to indicate maximum number of matches +the user expect to find for each key, and *set\_id* which is used to return all +target set ids where the key has matched, if any. The *set\_id* array should be sized +according to *match\_per\_key*. For vBF, maximum number of matches per key is equal +to the number of sets. For HTSS, maximum number of matches per key is equal to two times +entry count per bucket. *match\_per\_key* should be equal or smaller than maximum number of +possible matches. + +.. *rte\_membership\_lookup\_multi\_bulk(const void \*setsum, const void \*\*keys, uint32\_t num\_keys, uint32\_t max\_match\_per\_key, uint32\_t \*match\_count, MEMBERSHIP\_TARGET\_TYPE \*target\_ids)* + +*rte\_membership\_lookup\_multi\_bulk* function looks up a bulk of keys/elements elements in the +set-summary structure for multiple matches, each key lookup returns ALL the matches (possibly more +than one) found for this key when it is matched against all target sets (cache mode HTSS +matches at most one target set). The +return value is the number of keys that find one or more matches in the +set-summary structure. The arguments of the +function include *keys* which is +a pointer to a bulk of keys that are to be looked up, *num\_keys* is the number +of keys that will be looked up, *match\_per\_key* is the possible +max number of matches for each key, *match\_count* which is the returned number +of matches for each key, and *set\_ids* are the returned target set +ids for all matches found for each keys. *set\_ids* is 2-D array +that for each key, a 1-D array should be sized according to *match\_per\_key*. +*match\_per\_key* should be equal or smaller than maximum number of +possible matches, similar to *rte\_member\_lookup\_multi*. + + +Set-summary Element Delete +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +.. *rte\_membership\_delete(void \*setsum, const void \*key, MEMBERSHIP\_TARGET\_TYPE target\_id)* + +*rte\_membership\_delete* function deletes an element/key from a set-summary structure, if it fails +an error is returned. The input arguments should include *key* which is a pointer to the +element/key that needs to be deleted from the set-summary, and *set\_id* +which is the set id associated with the key to delete. It worth noting that current +implementation of vBF does not support deletion [1]_. An error code -EINVAL will be returned. + +.. [1] Traditional bloom filter does not support proactive deletion. Supporting proactive deletion require additional implementation and performance overhead. + +References +----------- + +[Member-bloom] B H Bloom, "Space/Time Trade-offs in Hash Coding with Allowable Errors," Communications of the ACM, 1970. + +[Member-survey] A Broder and M Mitzenmacher, "Network Applications of Bloom Filters: A Survey," in Internet Mathematics, 2005. + +[Member-cfilter] B Fan, D G Andersen and M Kaminsky, "Cuckoo Filter: Practically Better Than Bloom," in Conference on emerging Networking Experiments and Technologies, 2014. + +[Member-OvS] B Pfaff, "The Design and Implementation of Open vSwitch," in NSDI, 2015. \ No newline at end of file diff --git a/doc/guides/rel_notes/release_17_11.rst b/doc/guides/rel_notes/release_17_11.rst index 170f4f9..4002df3 100644 --- a/doc/guides/rel_notes/release_17_11.rst +++ b/doc/guides/rel_notes/release_17_11.rst @@ -41,6 +41,23 @@ New Features Also, make sure to start the actual text at the margin. ========================================================= +* **Added Membership library (rte_member).** + + Added membership library. It provides an API for DPDK applications to insert a + new member, delete an existing member, or query the existence of a member in a + given set, or a group of sets. For the case of a group of sets the library + will return not only whether the element has been inserted before in one of + the sets but also which set it belongs to. + + The Membership Library is an extension and generalization of a traditional + filter (for example Bloom Filter) structure that has multiple usages in a wide + variety of workloads and applications. In general, the Membership Library is a + data structure that provides a “set-summary” and responds to set-membership + queries whether a certain member belongs to a set(s). + + See the :ref:`Membership Library ` documentation in + the Programmers Guide document, for more information. + Resolved Issues ---------------