From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <medvedkinv@gmail.com>
Received: from mail-qt0-f179.google.com (mail-qt0-f179.google.com
 [209.85.216.179]) by dpdk.org (Postfix) with ESMTP id 15F789105
 for <dev@dpdk.org>; Tue, 15 Aug 2017 00:28:28 +0200 (CEST)
Received: by mail-qt0-f179.google.com with SMTP id t37so59298422qtg.5
 for <dev@dpdk.org>; Mon, 14 Aug 2017 15:28:28 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=mime-version:in-reply-to:references:from:date:message-id:subject:to
 :cc; bh=M8LVi5KBxAOpZFL78ZsvbWp6PGD+qHPGPPZYRzb7tYc=;
 b=iayrKvJAWKYvwy+V4aaw9vgpYqsXYGCnQa956e7NFMK6TvJaxTOVaGcVU05O6OBDjA
 Uj06pgm9gt4XRKg1F9TvxFfUFOe4kqBgj3MLetG/Oq5hNnDu210hIhKG4ffDDqC5cLNL
 kAnTc92+aajO7C+am+lzjEluY4QJvYHUVmlgjpQij4QmrF8Ip7v1fTXYKAQwGe77ab4I
 8yHpoC0xv8dijT8qOy7VApDO86b5bCMZqDnNoLBUzuRvW6lTcm+X8aVpg5Kv/yaHPBHr
 JRDvYglphOihYsqaS4CiKaRKml8yQDqwg8mCe5goROMRqtaPCQh6HKfiRE9SNU4EsXjp
 KH6g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:in-reply-to:references:from:date
 :message-id:subject:to:cc;
 bh=M8LVi5KBxAOpZFL78ZsvbWp6PGD+qHPGPPZYRzb7tYc=;
 b=TgoFxF2MywRU0wDgWa/HhmmUlQz3qJhkpywB3oNwQJj7iIsN7nWP1ZmaYmJIyY9+4e
 rDED2Q6qn4YNw2X2xPcdRKkCavnQXYUZiL9R0lVwHkjJW83vbxO4DNpSbl7nsJa56/Le
 FfEU/zZ8rSyqTnwkuCg+04Iv17H48saU0tTYww+hWKNy6K706Co/cdzd8gyAxOU5bjJP
 chk6F/6PmbN/23owqQz9Vmsf+tGl1S8BHc+YgpM8TkRY6QjxB7/yXZRWgFwONa6qZq0j
 2cSzK41k/jKpD0hqybNR/JwB0erawxSn0g4jHhIuWEjZHHbl2U4j9SzSL/Ut4iCf0EvR
 b1Pg==
X-Gm-Message-State: AHYfb5gR0cJt+jdmvUqzU1Peu8galx37GSgu11BoR1QG/ECKdB4b4cJb
 PczfXW34z4cXEZsEnSPHHuitIJtcDQ==
X-Received: by 10.200.52.235 with SMTP id x40mr33658065qtb.70.1502749707494;
 Mon, 14 Aug 2017 15:28:27 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.200.49.137 with HTTP; Mon, 14 Aug 2017 15:28:26 -0700 (PDT)
In-Reply-To: <20170814105156.GA8112@bricha3-MOBL3.ger.corp.intel.com>
References: <1499801585-10031-1-git-send-email-medvedkinv@gmail.com>
 <20170814105156.GA8112@bricha3-MOBL3.ger.corp.intel.com>
From: Vladimir Medvedkin <medvedkinv@gmail.com>
Date: Tue, 15 Aug 2017 01:28:26 +0300
Message-ID: <CANDrEHm-y0xKZhRDrbfZNazMp-72SmX-Pybtz-z5u4qYDp4Zdw@mail.gmail.com>
To: Bruce Richardson <bruce.richardson@intel.com>
Cc: "dev@dpdk.org" <dev@dpdk.org>
Content-Type: text/plain; charset="UTF-8"
X-Content-Filtered-By: Mailman/MimeDel 2.1.15
Subject: Re: [dpdk-dev] [RFC] Add RIB library
X-BeenThere: dev@dpdk.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: DPDK patches and discussions <dev.dpdk.org>
List-Unsubscribe: <http://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: <http://dpdk.org/ml/listinfo/dev>,
 <mailto:dev-request@dpdk.org?subject=subscribe>
X-List-Received-Date: Mon, 14 Aug 2017 22:28:28 -0000

2017-08-14 13:51 GMT+03:00 Bruce Richardson <bruce.richardson@intel.com>:

> On Tue, Jul 11, 2017 at 07:33:04PM +0000, Medvedkin Vladimir wrote:
> > Hi,
> >
> > I want to introduce new library for ip routing lookup that have some
> advantages
> > over current LPM library. In short:
> >      - Increases the speed of control plane operations against lpm such
> as
> >        adding/deleting routes
> >      - Adds abstraction from dataplane algorythms, 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_v4_node which represents route
> entry.
> >        It can be next hop/set of next hops (i.e. active and feasible),
> >        pointers to link rte_rib_v4_node based on some criteria (i.e.
> next_hop),
> >        plenty of additional control plane information.
> >      - For dir24_8 implementation it is possible to remove
> rte_lpm_tbl_entry.depth
> >        field that helps to save 6 bits.
> >      - Also new dir24_8 implementation supports different next_hop sizes
> >        (1/2/4/8 bytes per next hop)
> >
> > It would be nice to hear your opinion. The draft is below.
> >
> > Medvedkin Vladimir (1):
> >   lib/rib: Add Routing Information Base library
> >
>
> On reading this patch and then having discussion with you offline, it
> appears there are two major new elements in this patchset:
>
> 1. a re-implementation of LPM, with the major advantage of having a
> flexible data-size
> 2. a separate control plane structure that is designed to fit on top off
> possibly multiple lookup structures for the data plane
>
> Is this correct?
>
Correct

>
> For the first part, I don't think we should carry about two separate LPM
> implementations, but rather look to take the improvements in your
> version back into the existing lib. [Or else replace the existing one,
> but I prefer pulling the new stuff into it, so as to keep backward
> compatibility]
>

> For the second part, perhaps you could expand a bit more on the thought
> here, and explain what all different data plane implementations would
> fit under it. Would, for instance a hash-lookup work? In that case, what
> would the data plane APIs be, and the control plane ones.
>

 I'm not sure for _all_ data plane implementations, but from my point of
view compressed prefix trie (rte_rib structure) could be useful at least
for dir24_8, dxr, bitmap handling. Concerning to hash lookup, it depends on
algorithm (array of hash tables indexed by mask length, unrolling prefix to
number of /32).
Perhaps it is better to waive the abstraction and make LPM as primary
struct that keeps rte_rib inside (instead of rules_tbl[ ]).
In that case rte_rib becomes side structure and it's API only for working
with a trie. LPM's API remains the same (except next_hop size and LPM
creation).


> Thanks,
> /Bruce
>



-- 
Regards,
Vladimir