DPDK patches and discussions
 help / color / Atom feed
From: Vladimir Medvedkin <medvedkinv@gmail.com>
To: Stephen Hemminger <stephen@networkplumber.org>
Cc: dev@dpdk.org, Bruce Richardson <bruce.richardson@intel.com>,
	thomas@monjalon.net, cristian.dumitrescu@intel.com
Subject: Re: [dpdk-dev] [PATCH v4 0/4] lib/rib: Add Routing Information Base library
Date: Fri, 27 Apr 2018 11:27:04 +0300
Message-ID: <CANDrEHnZ051D2+uca1uwjNVJYBTk_3FCDOBjsd=LgnzjE_e=gA@mail.gmail.com> (raw)
In-Reply-To: <20180426152448.0c21dc13@xeon-e3>

Hi Stephen,


2018-04-27 1:24 GMT+03:00 Stephen Hemminger <stephen@networkplumber.org>:

> On Fri, 27 Apr 2018 01:03:30 +0300
> Medvedkin Vladimir <medvedkinv@gmail.com> wrote:
>
> > This patch series introduces new library librte_rib which potentially
> could
> > replace librte_lpm.
> >
> > RIB is an alternative to current LPM library.
> > It solves the following problems
> >  - Increases the speed of control plane operations against lpm such as
> >    adding/deleting routes
> >  - Adds abstraction from dataplane algorithms, so it is possible to add
> >    different ip route lookup algorythms such as DXR/poptrie/lpc-trie/etc
> >    in addition to current dir24_8
> >  - It is possible to keep user defined application specific additional
> >    information in struct rte_rib_node which represents route entry.
> >    It can be next hop/set of next hops (i.e. active and feasible),
> >    pointers to link rte_rib_node based on some criteria (i.e. next_hop),
> >    plenty of additional control plane information.
> >
> > v4:
> >   fix various bugs
> >   make struct rte_rib opaque
> >   make inline functions instead of macro
> >   remove RTE_RIB_MALLOC node allocation type
> >   add new lookup functions
> >   remove rte_dir24_8_lookup()
> >   add rte_dir24_8_get_lookup()
> >   add meson support
> >   add fib configuration
> >
> >
> > Medvedkin Vladimir (4):
> >   Add RIB library
> >   Add dir24_8 implementation for rib library
> >   Add autotests for RIB library
>
> The existing DPDK LPM code does need more work it does trade space for
> time.
>
> It does have some advantages though:
>         * LPM lookup table is independent of number of routes.
>
To be honest it depends on number of prefixes longer 24. But despite this
my implementation is independent of number of routes too.

>         * LPM lookup table can be lock free reader safe using RCU.
>
As I see you are using rcu only for tbl8's growing. This feature was out of
scope and could be added if needed. But I'm afraid about license
constraints.

>
> The existing slowness of add and delete was fixed at Vyatta/Brocade by
> replacing list with red-black tree. Patches were submitted but never
> merged.
>
Could you please share lpm_perf_autotest results for your version?
Here my results for lpm_perf_autotest and rib_perf_autotest (sizeof key ==
sizeof(struct rte_lpm_tbl_entry) so memory footprint is the same)
LPM:
Unique added entries = 1037026
Used table 24 entries = 14680064 (87.5%)
64 byte Cache entries used = 458753 (29360192 bytes)
Average LPM Add: 306566 cycles
Average LPM Lookup: 29.7 cycles (fails = 0.0%)
BULK LPM Lookup: 29.4 cycles (fails = 0.0%)
LPM LookupX4: 27.1 cycles (fails = 0.0%)
Average LPM Delete: 201360 cycles
Test OK
RIB:
Unique added entries = 1076816
Average RIB Add: 3149.62 cycles
BULK RIB Lookup: 23.8 cycles (fails = 0.0%)
Average RIB Delete: 2949.62 cycles
Test OK

As you can see for 1M+ routes I have 100 times faster add and 70 times
faster delete. Lookup speed is faster too.
It was achieved due to:
1. routes are kept in compressed binary tree so rule insertion/deletion are
cheap comparing to flat array in LPM. And yes, rb_tree implementation fixes
that problem too.
2. routes are kept in compressed binary tree so you can get less specific
prefix (parent node) for a given prefix (you want add/del to) and compare
it's next hop to a given next hop. There is no need to touch fib table if
they are equal.
3. routes are kept in compressed binary tree so you can traverse on some
part of that tree to get subprefixes for a given prefix (you want add/del
to). Hence you can get gaps between retrieved more specific routes and
based on this gaps unconditionally rewrite part of fib table. Comparing to
LPM where every write to tbl24 or tbl8 is accompanied by a comparison of
depth. In addition there is no need to keep depth in fib anymore.
4. LPM tbl8_alloc is expensive due to memory scan through tbl8 to find a
free tbl8 group. More effective to keep free tbl8 indexes in bitmap.

-- 
Regards,
Vladimir

  parent reply index

Thread overview: 61+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-04-26 22:03 Medvedkin Vladimir
2018-04-26 22:03 ` [dpdk-dev] [PATCH v4 1/4] Add RIB library Medvedkin Vladimir
2018-04-26 22:17   ` Stephen Hemminger
2018-04-26 22:18   ` Stephen Hemminger
2018-04-26 22:19   ` Stephen Hemminger
2018-04-26 22:19   ` Stephen Hemminger
2018-04-26 22:20   ` Stephen Hemminger
2018-04-27  6:45     ` Vladimir Medvedkin
2018-06-29 13:54   ` Bruce Richardson
2018-06-29 14:02   ` Bruce Richardson
2018-04-26 22:03 ` [dpdk-dev] [PATCH v4 2/4] Add dir24_8 implementation for rib library Medvedkin Vladimir
2018-04-26 22:03 ` [dpdk-dev] [PATCH v4 3/4] Add autotests for RIB library Medvedkin Vladimir
2018-06-29 14:13   ` Bruce Richardson
2018-06-29 15:07   ` Bruce Richardson
2018-06-29 15:31   ` Bruce Richardson
2018-04-26 22:03 ` [dpdk-dev] [PATCH v4 4/4] Add support for lpm and rib bulk lookup Medvedkin Vladimir
2018-04-26 22:24 ` [dpdk-dev] [PATCH v4 0/4] lib/rib: Add Routing Information Base library Stephen Hemminger
2018-04-26 22:27   ` Thomas Monjalon
2018-04-26 22:42     ` Stephen Hemminger
2018-04-26 22:49     ` Stephen Hemminger
2018-04-27  8:27   ` Vladimir Medvedkin [this message]
2018-06-29 15:48 ` Bruce Richardson
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 00/12] lib: add RIB and FIB liraries Vladimir Medvedkin
2019-09-12  7:37   ` Morten Brørup
2019-09-12  9:47     ` Medvedkin, Vladimir
2019-09-12 12:00       ` Morten Brørup
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 " Vladimir Medvedkin
2019-11-05 23:14     ` Thomas Monjalon
2019-11-06  5:50       ` David Marchand
2019-11-06  7:50         ` Thomas Monjalon
2019-11-06 11:53           ` Medvedkin, Vladimir
2019-11-06 11:59             ` Thomas Monjalon
2019-11-06 14:37               ` Aaron Conole
2019-11-06 11:50         ` Medvedkin, Vladimir
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 01/12] rib: add RIB library Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 02/12] test/rib: add RIB library autotests Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 03/12] rib: add ipv6 support for RIB Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 04/12] test/rib: add ipv6 support for RIB autotests Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 05/12] fib: add FIB library Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 06/12] fib: add FIB ipv6 support Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 07/12] fib: add DIR24-8 dataplane algorithm Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 08/12] fib: add dataplane algorithm for ipv6 Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 09/12] test/fib: add FIB library autotests Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 10/12] test/fib: add ipv6 support for FIB autotests Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 11/12] test/fib: add FIB library performance autotests Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 12/12] test/fib: add FIB library ipv6 " Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 01/12] rib: add RIB library Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 02/12] test/rib: add RIB library autotests Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 03/12] rib: add ipv6 support for RIB Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 04/12] test/rib: add ipv6 support for RIB autotests Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 05/12] fib: add FIB library Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 06/12] fib: add FIB ipv6 support Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 07/12] fib: add DIR24-8 dataplane algorithm Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 08/12] fib: add dataplane algorithm for ipv6 Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 09/12] test/fib: add FIB library autotests Vladimir Medvedkin
2019-09-12 14:07   ` Aaron Conole
2019-10-01 17:12     ` Medvedkin, Vladimir
2019-10-24 15:55       ` Thomas Monjalon
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 10/12] test/fib: add ipv6 support for FIB autotests Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 11/12] test/fib: add FIB library performance autotests Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 12/12] test/fib: add FIB library ipv6 " Vladimir Medvedkin

Reply instructions:

You may reply publically 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='CANDrEHnZ051D2+uca1uwjNVJYBTk_3FCDOBjsd=LgnzjE_e=gA@mail.gmail.com' \
    --to=medvedkinv@gmail.com \
    --cc=bruce.richardson@intel.com \
    --cc=cristian.dumitrescu@intel.com \
    --cc=dev@dpdk.org \
    --cc=stephen@networkplumber.org \
    --cc=thomas@monjalon.net \
    /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

DPDK patches and discussions

Archives are clonable:
	git clone --mirror http://inbox.dpdk.org/dev/0 dev/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 dev dev/ http://inbox.dpdk.org/dev \
		dev@dpdk.org
	public-inbox-index dev


Newsgroup available over NNTP:
	nntp://inbox.dpdk.org/inbox.dpdk.dev


AGPL code for this site: git clone https://public-inbox.org/ public-inbox