From: Yipeng Wang <yipeng1.wang@intel.com>
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
Subject: [dpdk-dev] [PATCH 0/7] Add Membership Library
Date: Mon, 21 Aug 2017 17:19:46 -0700 [thread overview]
Message-ID: <1503361193-36699-1-git-send-email-yipeng1.wang@intel.com> (raw)
DPDP Membership Library provides an API that can be used by many DPDK
applications to conduct one or more set-membership tests (we mention some
possible use cases below, but interested readers can refer to
[1] for a wider survey of use cases).
The basic functionalities of the Membership Library include
inserting a new member, deleting an existing member, and querying the existence
of a member. The query result would indicate with high accuracy which specific
set this member belongs to among a group of sets.
The Membership Library is an extension and generalization of traditional filter
data structures [2,3], which maintain a space-efficient “set-summary”.
There are two advantages of using such a set-summary rather than operating on a
“full-blown” complete list of elements: firstly it has a much smaller storage
requirement than storing the whole list of elements, and secondly set membership
tests (or other operations) is much more efficient than searching through the
complete list of elements.
A membership test for an element will return the set this element belongs to if
found (or return "not-found") with high accuracy. If needed, the accuracy of the
membership tests could be further increased with larger storage space.
Set-summary is a fundamental data aggregation component that can be used in many
network applications. It is a crucial structure to address performance and
scalability issues of diverse applications including overlay networks, wild card
flow classification, web-caches, load balancing, connection tracking,
data-centric networks, flow table summaries, network statistics and traffic
monitoring. Our Proof of Concept (PoC) using set-summary to optimize flow lookup
in Open vSwitch (OvS) shows a speedup of about 2-3X.
This patch set implements two types of set-summaries, i.e., hash-table based
set-summary (HTSS) and Vector Bloom Filter (vBF). HTSS supports both the
non-cache and cache modes. The non-cache mode can incur a small chance of
false-positives which is the case when the set-summary indicates a key belongs
to a given set while actually it is not. The cache mode can also have
false-negatives in addition to false-positives. False-negatives means the case
when the set-summary indicates a key does not belong to a given set while
actually it does. This happens because cache mode allows new key to evict
existing keys. vBF only has false-positives similar to the non-cache HTSS.
However, one can set the false-positive rate arbitrarily. HTSS's
false-positive rate is determined by the hash-table size and the signature size.
We sent out RFC previously:
http://dpdk.org/ml/archives/dev/2017-May/066599.html
[1] A Broder and M Mitzenmacher, “Network Applications of Bloom Filters: A
Survey,” in Internet Mathematics, 2005.
[2] B H Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors,”
Communications of the ACM, 1970.
[3] B Fan, D G Andersen and M Kaminsky, “Cuckoo Filter: Practically Better Than
Bloom,” in Conference on emerging Networking Experiments and Technologies, 2014.
Yipeng Wang (7):
member: implement main API
member: implement HT mode
member: implement vBF mode
member: add AVX for HT mode
member: enable the library
test/member: add functional and perf tests
doc: add membership documentation
MAINTAINERS | 7 +
config/common_base | 5 +
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 +
lib/Makefile | 2 +
lib/librte_eal/common/eal_common_log.c | 1 +
lib/librte_eal/common/include/rte_log.h | 1 +
lib/librte_member/Makefile | 50 +
lib/librte_member/rte_member.c | 357 +++++++
lib/librte_member/rte_member.h | 518 ++++++++++
lib/librte_member/rte_member_ht.c | 567 +++++++++++
lib/librte_member/rte_member_ht.h | 115 +++
lib/librte_member/rte_member_vbf.c | 309 ++++++
lib/librte_member/rte_member_vbf.h | 85 ++
lib/librte_member/rte_member_version.map | 15 +
lib/librte_member/rte_member_x86.h | 111 ++
mk/rte.app.mk | 2 +
test/test/Makefile | 3 +
test/test/test_member.c | 550 ++++++++++
test/test/test_member_perf.c | 643 ++++++++++++
30 files changed, 6948 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
create mode 100644 lib/librte_member/Makefile
create mode 100644 lib/librte_member/rte_member.c
create mode 100644 lib/librte_member/rte_member.h
create mode 100644 lib/librte_member/rte_member_ht.c
create mode 100644 lib/librte_member/rte_member_ht.h
create mode 100644 lib/librte_member/rte_member_vbf.c
create mode 100644 lib/librte_member/rte_member_vbf.h
create mode 100644 lib/librte_member/rte_member_version.map
create mode 100644 lib/librte_member/rte_member_x86.h
create mode 100644 test/test/test_member.c
create mode 100644 test/test/test_member_perf.c
--
2.7.4
next reply other threads:[~2017-08-22 0:20 UTC|newest]
Thread overview: 81+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-08-22 0:19 Yipeng Wang [this message]
2017-08-22 0:19 ` [dpdk-dev] [PATCH 1/7] member: implement main API Yipeng Wang
2017-08-22 3:59 ` Stephen Hemminger
2017-08-22 10:02 ` Luca Boccassi
2017-08-24 9:35 ` Ferruh Yigit
2017-08-24 9:55 ` Luca Boccassi
2017-08-24 10:32 ` Ferruh Yigit
2017-09-02 12:55 ` Luca Boccassi
2017-09-02 23:49 ` Luca Boccassi
2017-08-24 18:38 ` Wang, Yipeng1
2017-09-02 12:54 ` Luca Boccassi
2017-08-22 0:19 ` [dpdk-dev] [PATCH 2/7] member: implement HT mode Yipeng Wang
2017-08-22 0:19 ` [dpdk-dev] [PATCH 3/7] member: implement vBF mode Yipeng Wang
2017-08-22 0:19 ` [dpdk-dev] [PATCH 4/7] member: add AVX for HT mode Yipeng Wang
2017-08-22 0:19 ` [dpdk-dev] [PATCH 5/7] member: enable the library Yipeng Wang
2017-08-22 0:19 ` [dpdk-dev] [PATCH 6/7] test/member: add functional and perf tests Yipeng Wang
2017-08-22 0:19 ` [dpdk-dev] [PATCH 7/7] doc: add membership documentation Yipeng Wang
2017-08-22 4:01 ` [dpdk-dev] [PATCH 0/7] Add Membership Library Stephen Hemminger
2017-08-23 2:58 ` Wang, Yipeng1
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 " Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 1/7] member: implement main API Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 2/7] member: implement HT mode Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 3/7] member: implement vBF mode Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 4/7] member: add AVX for HT mode Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 5/7] member: enable the library Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 6/7] test/member: add functional and perf tests Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 7/7] doc: add membership documentation Yipeng Wang
2017-09-04 13:19 ` Mcnamara, John
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 0/7] Add Membership Library Yipeng Wang
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 1/7] member: implement main API Yipeng Wang
2017-09-22 10:47 ` Thomas Monjalon
2017-09-25 14:15 ` De Lara Guarch, Pablo
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 2/7] member: implement HT mode Yipeng Wang
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 3/7] member: implement vBF mode Yipeng Wang
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 4/7] member: add AVX for HT mode Yipeng Wang
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 5/7] member: enable the library Yipeng Wang
2017-09-22 10:48 ` Thomas Monjalon
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 6/7] test/member: add functional and perf tests Yipeng Wang
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 7/7] doc: add membership documentation Yipeng Wang
2017-09-18 18:42 ` Mcnamara, John
2017-09-25 12:30 ` De Lara Guarch, Pablo
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 0/7] Add Membership Library Yipeng Wang
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 1/7] member: implement main API Yipeng Wang
2017-10-02 10:04 ` De Lara Guarch, Pablo
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 2/7] member: implement HT mode Yipeng Wang
2017-10-02 13:30 ` De Lara Guarch, Pablo
2017-10-03 1:18 ` Wang, Yipeng1
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 3/7] member: implement vBF mode Yipeng Wang
2017-10-02 15:44 ` De Lara Guarch, Pablo
2017-10-03 1:24 ` Wang, Yipeng1
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 4/7] member: add AVX for HT mode Yipeng Wang
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 5/7] member: enable the library Yipeng Wang
2017-10-02 15:47 ` De Lara Guarch, Pablo
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 6/7] test/member: add functional and perf tests Yipeng Wang
2017-10-02 16:20 ` De Lara Guarch, Pablo
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 7/7] doc: add membership documentation Yipeng Wang
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 0/7] Add Membership Library Yipeng Wang
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 1/7] member: implement main API Yipeng Wang
2017-10-03 8:42 ` De Lara Guarch, Pablo
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 2/7] member: implement HT mode Yipeng Wang
2017-10-03 8:47 ` De Lara Guarch, Pablo
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 3/7] member: implement vBF mode Yipeng Wang
2017-10-03 8:50 ` De Lara Guarch, Pablo
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 4/7] member: add AVX for HT mode Yipeng Wang
2017-10-03 9:01 ` De Lara Guarch, Pablo
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 5/7] member: enable the library Yipeng Wang
2017-10-03 9:04 ` De Lara Guarch, Pablo
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 6/7] test/member: add functional and perf tests Yipeng Wang
2017-10-03 9:07 ` De Lara Guarch, Pablo
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 7/7] doc: add membership documentation Yipeng Wang
2017-10-03 9:08 ` De Lara Guarch, Pablo
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 0/7] Add Membership Library Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 1/7] member: implement main API Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 2/7] member: implement HT mode Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 3/7] member: implement vBF mode Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 4/7] member: add AVX for HT mode Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 5/7] member: enable the library Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 6/7] test/member: add functional and perf tests Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 7/7] doc: add membership documentation Yipeng Wang
2017-10-04 13:44 ` Mcnamara, John
2017-10-08 22:14 ` [dpdk-dev] [PATCH v6 0/7] Add Membership Library Thomas Monjalon
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1503361193-36699-1-git-send-email-yipeng1.wang@intel.com \
--to=yipeng1.wang@intel.com \
--cc=bruce.richardson@intel.com \
--cc=charlie.tai@intel.com \
--cc=dev@dpdk.org \
--cc=konstantin.ananyev@intel.com \
--cc=ren.wang@intel.com \
--cc=sameh.gobriel@intel.com \
--cc=stephen@networkplumber.org \
--cc=thomas@monjalon.net \
--cc=vincent.jardin@6wind.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).