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