From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga14.intel.com (mga14.intel.com [192.55.52.115]) by dpdk.org (Postfix) with ESMTP id 30EE17CE1 for ; Mon, 29 May 2017 14:43:01 +0200 (CEST) Received: from orsmga003.jf.intel.com ([10.7.209.27]) by fmsmga103.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 29 May 2017 05:43:01 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.38,414,1491289200"; d="scan'208";a="974297260" Received: from irsmsx109.ger.corp.intel.com ([163.33.3.23]) by orsmga003.jf.intel.com with ESMTP; 29 May 2017 05:42:59 -0700 Received: from irsmsx108.ger.corp.intel.com ([169.254.11.133]) by IRSMSX109.ger.corp.intel.com ([169.254.13.250]) with mapi id 14.03.0319.002; Mon, 29 May 2017 13:42:58 +0100 From: "Dumitrescu, Cristian" To: "Richardson, Bruce" , "cs5120282@cse.iitd.ac.in" CC: "dev@dpdk.org" Thread-Topic: [dpdk-dev] Why DPDK is not using compressed TRIE for LPM6? Thread-Index: AQHS1lMQXZs31jb6GECW/pFQXc3JpqIK/uqAgABECyA= Date: Mon, 29 May 2017 12:42:58 +0000 Message-ID: <3EB4FA525960D640B5BDFFD6A3D891267BA60339@IRSMSX108.ger.corp.intel.com> References: <20170529093008.GB32120@bricha3-MOBL3.ger.corp.intel.com> In-Reply-To: <20170529093008.GB32120@bricha3-MOBL3.ger.corp.intel.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-titus-metadata-40: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiZjA1ZTc3MzctZTNiYy00NzAwLWJlNzYtY2Q0NGQwZDU4NmYyIiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX0lDIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE2LjUuOS4zIiwiVHJ1c3RlZExhYmVsSGFzaCI6IlwvQ3M3VG1idjBhRU9ZSWxpVGp1VEJBaU5xVG1NbE54amVTcllGSm9rYVJjPSJ9 x-ctpclassification: CTP_IC dlp-product: dlpe-windows dlp-version: 10.0.102.7 dlp-reaction: no-action x-originating-ip: [163.33.239.181] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Subject: Re: [dpdk-dev] Why DPDK is not using compressed TRIE for LPM6? 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: Mon, 29 May 2017 12:43:02 -0000 > -----Original Message----- > From: Richardson, Bruce > Sent: Monday, May 29, 2017 10:30 AM > To: cs5120282@cse.iitd.ac.in > Cc: dev@dpdk.org; Dumitrescu, Cristian > Subject: Re: [dpdk-dev] Why DPDK is not using compressed TRIE for LPM6? >=20 > On Sat, May 27, 2017 at 12:34:57AM +0530, Atul Shree wrote: > > Hello All, > > > > I was doing some experiments related to LPM6 look up and I have added > 20K > > entries in the table. By looking at the rte_lpm6_lookup() code I found = an > > opportunity to compress the TRIE and there is a significant improvement > > after compression. > > >=20 > Although I'm maintainer for LPM library, I'm not the original author of > the LPM6 code. However, I'll give my thoughts here. Adding Cristian D. on > CC as he was involved in the original implementation, IIRC. >=20 Hi Atul, As far as I can recall, we already implemented a sort of tree compression i= n LPM for IPv6, but it might not be exactly what you have in mind, as there= are multiple ways to compress a tree. It's been a while since I looked int= o this, so please bear with me for the next few clarifying questions: 1. Can you please provide a link to a good paper/article describing your al= gorithm. 2. Can you summarize the key improvement for LPM6 as result of using this a= lgorithm. Is this a performance improvement, how/why is it achieved, it is = a general improvement benefiting all use-cases or just a specific subset? Thanks, Cristian