From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id 7D87C1B611 for ; Wed, 4 Oct 2017 05:16:32 +0200 (CEST) Received: from fmsmga004.fm.intel.com ([10.253.24.48]) by orsmga102.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 03 Oct 2017 20:16:31 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.42,476,1500966000"; d="scan'208";a="319258151" Received: from bdw-yipeng.jf.intel.com ([10.54.81.30]) by fmsmga004.fm.intel.com with ESMTP; 03 Oct 2017 20:16:31 -0700 From: Yipeng Wang To: dev@dpdk.org Cc: thomas@monjalon.net, charlie.tai@intel.com, sameh.gobriel@intel.com, pablo.de.lara.guarch@intel.com, john.mcnamara@intel.com, Yipeng Wang Date: Tue, 3 Oct 2017 20:12:25 -0700 Message-Id: <1507086745-6674-8-git-send-email-yipeng1.wang@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1507086745-6674-1-git-send-email-yipeng1.wang@intel.com> References: <1507005102-43821-1-git-send-email-yipeng1.wang@intel.com> <1507086745-6674-1-git-send-email-yipeng1.wang@intel.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Subject: [dpdk-dev] [PATCH v6 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: , X-List-Received-Date: Wed, 04 Oct 2017 03:16:33 -0000 This patch adds the documentation for membership library. Signed-off-by: Yipeng Wang Reviewed-by: John McNamara Reviewed-by: Pablo de Lara --- MAINTAINERS | 1 + 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 | 420 ++++++++ doc/guides/rel_notes/release_17_11.rst | 17 + 13 files changed, 3596 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/MAINTAINERS b/MAINTAINERS index afd36cf..51ef958 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -734,6 +734,7 @@ M: Yipeng Wang M: Sameh Gobriel F: lib/librte_member/ F: test/test/test_member* +F: doc/guides/prog_guide/member_lib.rst Traffic metering M: Cristian Dumitrescu 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..caca8dc --- /dev/null +++ b/doc/guides/prog_guide/member_lib.rst @@ -0,0 +1,420 @@ +.. 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 detail 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 +that the element is "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 + +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 back-end web servers) to + provide faster responses to clients, and the proxies use the Membership + Library to share summaries of what web pages/objects 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 back-end 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 the 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. + +Membership Library is a configurable library that is optimized to cover set +membership functionality for both a single set and multi-set scenarios. Two set-summary +schemes are presented including (a) vector of Bloom Filters and (b) Hash-Table based +set-summary schemes with and without false negative probability. +This guide first briefly describes these different types of set-summaries, usage examples for each, +and then it highlights 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 +``0`` to ``m-1`` to perform hashing calculations on each element to be inserted. 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 a single set, +the library implements a Vector Bloom Filter (vBF) scheme. +vBF basically composes multiple bloom filters into 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 structures. vBF is used +for applications that need to check membership against multiple sets +simultaneously. The example shown 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 HTSS. +HTSS supports multi-set membership testing like +vBF does. However, while vBF is better for a small number of targets, HTSS is more suitable +and 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. +As a result, generally speaking vBF is more adequate for the case of a small limited number of sets +while HTSS should be used with a larger number of sets. + +.. _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 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. 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 mentioned, 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 is 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 Create +~~~~~~~~~~~~~~~~~~ + +The ``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 which have a slightly different meaning for different types of set-summary. +For example, ``num_keys`` parameter means the maximum 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 ``is_cache`` 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 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +The ``rte_member_add()`` function is used to insert an element/key into a set-summary structure. If it fails an +error is returned. For success the returned value is dependent 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 +~~~~~~~~~~~~~~~~~~~~~~~~~~ + +The ``rte_member_lookup()`` function 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. + +The ``rte_member_lookup_bulk()`` function is used 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. + +The ``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 is 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, ``max_match_per_key`` which is to indicate the maximum number of matches +the user expects 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 ``max_match_per_key``. For vBF, the maximum number of matches per key is equal +to the number of sets. For HTSS, the maximum number of matches per key is equal to two time +entry count per bucket. ``max_match_per_key`` should be equal or smaller than the maximum number of +possible matches. + +The ``rte_membership_lookup_multi_bulk()`` function looks up a bulk of keys/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, ``max_match_per_key`` is the possible +maximum 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 +containing a 1-D array for each key (the size of 1-D array per key should be set by the user according to ``max_match_per_key``). +``max_match_per_key`` should be equal or smaller than the maximum number of +possible matches, similar to ``rte_member_lookup_multi``. + + +Set-summary Element Delete +~~~~~~~~~~~~~~~~~~~~~~~~~~ + +The ``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 is 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. diff --git a/doc/guides/rel_notes/release_17_11.rst b/doc/guides/rel_notes/release_17_11.rst index 8bf91bd..ba068ec 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 --------------- -- 2.7.4