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

[Stephen Hemminger]

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.
        * LPM lookup table can be lock free reader safe using RCU.

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.