[dpdk-dev] [PATCH v4 0/4] lib/rib: Add Routing Information Base library

[Vladimir Medvedkin]

Hi Stephen,


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

> On Fri, 27 Apr 2018 01:03:30 +0300
> Medvedkin Vladimir <medvedkinv at 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