From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qt0-f181.google.com (mail-qt0-f181.google.com [209.85.216.181]) by dpdk.org (Postfix) with ESMTP id F08727CB9 for ; Tue, 15 Aug 2017 12:49:29 +0200 (CEST) Received: by mail-qt0-f181.google.com with SMTP id p3so2412775qtg.2 for ; Tue, 15 Aug 2017 03:49:29 -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=CT4opv3JjdFBTuvt2F9C2HwEw84aoplmvDDpAwkQs64=; b=ctr1rOCt+O7SD0MZejPah/UblkiKGQNmjPgDNN7n2dWm3ep+LeR1xNke+GjwMSNw6y lVMemQNgyZQM+l6HERyl624PCPvkMPeC++qDjtpjA4zgsWDdBTR18fI6YCAfSoM4H9GZ OpIhAAuM6vMksA4OUw2zWiZBYeNS/bMnZMJhH/bhYPxUap1VtUO2Lm2+hvNJyujqIK6S 6T015+daVPaHhTmqii5evG+iLEaHwX5vyMDHipH7Z5gMy5cr21h8motjpTB5WHRx9o/v 7BClutz9jJCF9JYd2OTxyYDnS1BBllTanvrktfEHjw9B14q+kZ6MlIKtfUG1oyoDNKaL gEsw== 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=CT4opv3JjdFBTuvt2F9C2HwEw84aoplmvDDpAwkQs64=; b=JizHdzum+mCr6X2Ligk995dHGyYgtn/pLVFACbbheT5hoZPMmRpdm8fSeMvOySxaYY NNmTHwm4kA1MfAn3KfvOZPB6P12YIpRSe+iadZmSAi7P+ycsig0Kz5AVBBIXJJQ570X8 09Zumfs/xI8fg47Z7zkW/wOy73eUxIZpVI8KQ6ZNFrd0Tf6oWj8tZtF/vxkk9Cfph0Yi GRa6KS+wchllzPgNabtOm724b6RCTM6H1vcj/4xKB8z85RogbGbZ1hiuOF/lU42Imi7Z 1gVU2jsd//+pACqxQXCwqOnb9pkHpJtcCdAnsIcM+MDoteCUXvPvIpDDvigPOW+HUS1N a12Q== X-Gm-Message-State: AHYfb5jqCSGNot+ykqjwz7jL1tpzxfk/r8vBIFbyZDIUKieRoJOh6hhA gMCfXqyK1BoiKxKCgWmEHR6gbr4NFQ== X-Received: by 10.200.49.85 with SMTP id h21mr35311180qtb.324.1502794169005; Tue, 15 Aug 2017 03:49:29 -0700 (PDT) MIME-Version: 1.0 Received: by 10.200.49.137 with HTTP; Tue, 15 Aug 2017 03:49:28 -0700 (PDT) In-Reply-To: <20170815082322.GA568@bricha3-MOBL3.ger.corp.intel.com> References: <1499801585-10031-1-git-send-email-medvedkinv@gmail.com> <20170814105156.GA8112@bricha3-MOBL3.ger.corp.intel.com> <20170815082322.GA568@bricha3-MOBL3.ger.corp.intel.com> From: Vladimir Medvedkin Date: Tue, 15 Aug 2017 13:49:28 +0300 Message-ID: To: Bruce Richardson Cc: "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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 15 Aug 2017 10:49:30 -0000 The advantage is in increasing control plane operations speed. I tested with my fullview + internal routes. It had 650030 prefixes(shuffled) with 1000 specific (longer /24) prefixes within 73 /24 networks. Every prefix had unique next hop. In this test the speed of inserting new routes was increased 70 times against current LPM. This was achieved due to 1. keeping routes in a trie structure instead of array (no need to get free room for rule) 2. avoid unnecessary reads in tbl24 (checking for .depth). Thanks to rte_rib_v4_get_next_child() (that is reverse order traversal without recursion) you can get all more specific prefixes inside your target prefix (you want to add/del), so you can get all ranges between that more specifics and write next hop unconditionally to tbl24 and tbl8. 2017-08-15 11:23 GMT+03:00 Bruce Richardson : > On Tue, Aug 15, 2017 at 01:28:26AM +0300, Vladimir Medvedkin wrote: > > 2017-08-14 13:51 GMT+03:00 Bruce Richardson >: > > > > > 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). > > > > > What is the advantage of using the rte_rib for control plane access over > the existing rules table structure. Are not the basic operations needed > for adding/removing/looking-up rules supported by both? > > /Bruce > -- Regards, Vladimir