From mboxrd@z Thu Jan  1 00:00:00 1970
From: Stephen Hemminger <stephen@networkplumber.org>
Subject: Re: [PATCH v4 0/4] lib/rib: Add Routing Information Base
 library
Date: Thu, 26 Apr 2018 15:24:48 -0700
Message-ID: <20180426152448.0c21dc13@xeon-e3>
References: <1524780214-23196-1-git-send-email-medvedkinv@gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Cc: dev@dpdk.org, bruce.richardson@intel.com, thomas@monjalon.net,
 cristian.dumitrescu@intel.com
To: Medvedkin Vladimir <medvedkinv@gmail.com>
Return-path: <dev-bounces@dpdk.org>
Received: from mail-pg0-f66.google.com (mail-pg0-f66.google.com [74.125.83.66])
 by dpdk.org (Postfix) with ESMTP id B638B7F2D
 for <dev@dpdk.org>; Fri, 27 Apr 2018 00:24:51 +0200 (CEST)
Received: by mail-pg0-f66.google.com with SMTP id i194so16992091pgd.0
 for <dev@dpdk.org>; Thu, 26 Apr 2018 15:24:51 -0700 (PDT)
In-Reply-To: <1524780214-23196-1-git-send-email-medvedkinv@gmail.com>
List-Id: DPDK patches and discussions <dev.dpdk.org>
List-Unsubscribe: <https://dpdk.org/ml/options/dev>,
 <mailto:dev-request@dpdk.org?subject=unsubscribe>
List-Archive: <http://dpdk.org/ml/archives/dev/>
List-Post: <mailto:dev@dpdk.org>
List-Help: <mailto:dev-request@dpdk.org?subject=help>
List-Subscribe: <https://dpdk.org/ml/listinfo/dev>,
 <mailto:dev-request@dpdk.org?subject=subscribe>
Errors-To: dev-bounces@dpdk.org
Sender: "dev" <dev-bounces@dpdk.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.
        * 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.