From: Yipeng Wang <yipeng1.wang@intel.com>
To: yipeng1.wang@intel.com
Cc: dev@dpdk.org, sameh.gobriel@intel.com, ren.wang@intel.com,
charlie.tai@intel.com
Subject: [dpdk-dev] [RFC] Add Membership Library
Date: Fri, 26 May 2017 18:34:47 -0700 [thread overview]
Message-ID: <1495848888-54621-1-git-send-email-yipeng1.wang@intel.com> (raw)
A proposal for a new DPDK library that is called “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). 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 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.
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,
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 membership library to optimize flow lookup for
Open vSwitch (OvS) shows a speed up of about 3X.
Signed-off-by: Yipeng Wang<Yipeng1.wang@intel.com>
Signed-off-by: Sameh Gobriel<sameh.gobriel@intel.com>
Signed-off-by: Charlie Tai<charlie.tai@intel.com>
Signed-off-by: Ren Wang<ren.wang@intel.com>
Yipeng Wang (1):
Add Membership Library
MAINTAINERS | 7 +
config/defconfig_x86_64-native-linuxapp-gcc | 3 +
doc/guides/prog_guide/img/memship_i1.svg | 1269 ++++++++++++++++++++++
doc/guides/prog_guide/img/memship_i2.svg | 36 +
doc/guides/prog_guide/img/memship_i3.svg | 148 +++
doc/guides/prog_guide/img/memship_i4.svg | 428 ++++++++
doc/guides/prog_guide/img/memship_i5.svg | 123 +++
doc/guides/prog_guide/img/memship_i6.svg | 233 ++++
doc/guides/prog_guide/img/memship_i7.svg | 277 +++++
doc/guides/prog_guide/index.rst | 14 +
doc/guides/prog_guide/membership_lib.rst | 421 +++++++
lib/Makefile | 3 +-
lib/librte_eal/common/eal_common_log.c | 1 +
lib/librte_eal/common/include/rte_log.h | 1 +
lib/librte_membership/Makefile | 48 +
lib/librte_membership/rte_membership.c | 378 +++++++
lib/librte_membership/rte_membership.h | 321 ++++++
lib/librte_membership/rte_membership_bf.c | 254 +++++
lib/librte_membership/rte_membership_bf.h | 99 ++
lib/librte_membership/rte_membership_cache.c | 345 ++++++
lib/librte_membership/rte_membership_cache.h | 95 ++
lib/librte_membership/rte_membership_ht.c | 471 ++++++++
lib/librte_membership/rte_membership_ht.h | 98 ++
lib/librte_membership/rte_membership_vbf.c | 391 +++++++
lib/librte_membership/rte_membership_vbf.h | 85 ++
lib/librte_membership/rte_membership_version.map | 15 +
mk/rte.app.mk | 1 +
test/test/Makefile | 2 +
test/test/test_membership.c | 459 ++++++++
29 files changed, 6025 insertions(+), 1 deletion(-)
create mode 100644 doc/guides/prog_guide/img/memship_i1.svg
create mode 100644 doc/guides/prog_guide/img/memship_i2.svg
create mode 100644 doc/guides/prog_guide/img/memship_i3.svg
create mode 100644 doc/guides/prog_guide/img/memship_i4.svg
create mode 100644 doc/guides/prog_guide/img/memship_i5.svg
create mode 100644 doc/guides/prog_guide/img/memship_i6.svg
create mode 100644 doc/guides/prog_guide/img/memship_i7.svg
create mode 100644 doc/guides/prog_guide/membership_lib.rst
create mode 100644 lib/librte_membership/Makefile
create mode 100644 lib/librte_membership/rte_membership.c
create mode 100644 lib/librte_membership/rte_membership.h
create mode 100644 lib/librte_membership/rte_membership_bf.c
create mode 100644 lib/librte_membership/rte_membership_bf.h
create mode 100644 lib/librte_membership/rte_membership_cache.c
create mode 100644 lib/librte_membership/rte_membership_cache.h
create mode 100644 lib/librte_membership/rte_membership_ht.c
create mode 100644 lib/librte_membership/rte_membership_ht.h
create mode 100644 lib/librte_membership/rte_membership_vbf.c
create mode 100644 lib/librte_membership/rte_membership_vbf.h
create mode 100644 lib/librte_membership/rte_membership_version.map
create mode 100644 test/test/test_membership.c
--
1.9.1
next reply other threads:[~2017-05-27 1:35 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-05-27 1:34 Yipeng Wang [this message]
2017-05-27 1:34 ` Yipeng Wang
2017-05-27 9:42 ` Vincent Jardin
2017-06-01 1:03 ` Wang, Yipeng1
2017-06-01 23:48 ` Vincent Jardin
2017-07-17 21:04 ` Vincent JARDIN
2017-06-02 20:51 ` Stephen Hemminger
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=1495848888-54621-1-git-send-email-yipeng1.wang@intel.com \
--to=yipeng1.wang@intel.com \
--cc=charlie.tai@intel.com \
--cc=dev@dpdk.org \
--cc=ren.wang@intel.com \
--cc=sameh.gobriel@intel.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).