From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from out1-smtp.messagingengine.com (out1-smtp.messagingengine.com [66.111.4.25]) by dpdk.org (Postfix) with ESMTP id 3AF832C2E for ; Tue, 16 Jan 2018 01:41:59 +0100 (CET) Received: from compute1.internal (compute1.nyi.internal [10.202.2.41]) by mailout.nyi.internal (Postfix) with ESMTP id BEF4E20D39; Mon, 15 Jan 2018 19:41:58 -0500 (EST) Received: from frontend2 ([10.202.2.161]) by compute1.internal (MEProxy); Mon, 15 Jan 2018 19:41:58 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=monjalon.net; h= cc:content-transfer-encoding:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-sender :x-me-sender:x-sasl-enc; s=mesmtp; bh=kU1NPKiaKbGgJTCuIwLp8Yvvny Wy+90rrkms+q5NpfQ=; b=Jac3VyVjOLXih4Ssy5JPjQYnhK7PGGEe9fMfh1C0ED TCpBZ219AC62+AQxRXYUZgR1uIaDld6DmESphc8jNXlr/ElEHy2bxchaRPJJQheQ VXKr6U5cnp1ly8xgqZ8bfYYkmmwRBk96KasMeHc66yM6zAM34YuQ44ykbYu2TnCJ A= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-sender:x-me-sender:x-sasl-enc; s=fm1; bh=kU1NPK iaKbGgJTCuIwLp8YvvnyWy+90rrkms+q5NpfQ=; b=VVGqC20LEIK6zcsK/VVX2f kxSo61WfrihhjDUfI9q56OjqFCudjJrkK+SU+L3yeMk7CU+cBjdlAU+3jka22obi 2ZBxpgrryJYOGcqxHOtoGl691HPyBK4V7QgJown4EXcWjeVYJ6rOKpwhso0L9Ml9 goDSgqrVvNz7jBT3KikFGpXrPeiYDzVKZ9KqiKRcyo2kRgg6I+woYfS4XlG9aB3I 6JYWbmNdDl2lOc4qgHupQik5JNmfSdfX5OBwASXW9NWMLYJVx7waSdrJV65YlU3I cdmXpgRO63Pzv2guEmp6BI+0HOucz0XDZEkmybGa8A8m+UF8Ah2HJx2DZwiRGE5g == X-ME-Sender: Received: from xps.localnet (184.203.134.77.rev.sfr.net [77.134.203.184]) by mail.messagingengine.com (Postfix) with ESMTPA id 6CD8A24235; Mon, 15 Jan 2018 19:41:58 -0500 (EST) From: Thomas Monjalon To: Vladimir Medvedkin , Bruce Richardson Cc: dev@dpdk.org Date: Tue, 16 Jan 2018 01:41:26 +0100 Message-ID: <2566554.Dzhr3r4fI6@xps> In-Reply-To: References: <1499801585-10031-1-git-send-email-medvedkinv@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: 7Bit Content-Type: text/plain; charset="us-ascii" 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, 16 Jan 2018 00:41:59 -0000 Bruce, Vladimir, There was no progress since August. Is there a plan to benefit from Vladimir's work? 15/08/2017 13:01, Vladimir Medvedkin: > Moreover rte_rib_v4_node could contain app specific extension (.ext field). > For example you can implement PIC (prefix independent convergence) by > linking rte_rib_v4_node with similar next hop together and precalculate > feasible next hop for each. Something like: > struct rte_rib_pic_nh { > struct *rte_rib_v4_node; > uint64_t nh; > uint64_t feasible_nh; > } > and keep that linked list's head in next hop structure. > When next hop fails you just jump from rte_rib_v4_node rte_rib_v4_node and > change next hop very fast. > > 2017-08-15 13:49 GMT+03:00 Vladimir Medvedkin : > > > 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 > > > > > >