From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp3.iitd.ac.in (smtp3.iitd.ac.in [103.27.11.44]) by dpdk.org (Postfix) with ESMTP id 0DAC92B86 for ; Wed, 31 May 2017 08:10:27 +0200 (CEST) Received: from smtp3.iitd.ac.in (localhost [127.0.0.1]) by smtp3.iitd.ac.in (Postfix) with ESMTP id 64F5E4084E; Wed, 31 May 2017 11:40:26 +0530 (IST) Received: from localhost (localhost [127.0.0.1]) by smtp3.iitd.ac.in (Postfix) with ESMTP id 47BCA405C6; Wed, 31 May 2017 11:40:26 +0530 (IST) Authentication-Results: smtp3.iitd.ac.in (amavisd-new); dkim=pass (1024-bit key) reason="pass (just generated, assumed good)" header.d=cse.iitd.ac.in DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cse.iitd.ac.in; h=user-agent:message-id:references:in-reply-to:reply-to:subject :subject:from:from:date:date:content-transfer-encoding :content-type:content-type:mime-version:received:received :received; s=iitd; t=1496211022; x=1498025423; bh=8sjWptE+0dNCmz M0m1stg0gvcvvz8jhnKCm1ZyAadd0=; b=WBK+XWJxu0OVLz1rjtg/lBfN57sk4o nO2JUefH9hyY0Ugtlw+7hMsFDUFYwfGr16o92359VlfBqu1+RC794sQrNwGM5y6h HRb+15z6dY21hsQvxiAgaja3bQmJjcakhMWx2LdqJ9qcAyUUa8kX+FsABUgr+F1h xyg3D8OK7DJQI= X-Virus-Scanned: Debian amavisd-new at smtp2.iitd.ernet.in Received: from smtp3.iitd.ac.in ([127.0.0.1]) by localhost (smtp3.iitd.ac.in [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id GldKlOkny7Nd; Wed, 31 May 2017 11:40:22 +0530 (IST) Received: from webmail.iitd.ernet.in (webmail.iitd.ac.in [10.7.172.189]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) (Authenticated sender: cs5120282) by smtp3.iitd.ac.in (Postfix) with ESMTPSA id E03C040848; Wed, 31 May 2017 11:40:19 +0530 (IST) Received: from [10.237.23.192] by webmail.iitd.ernet.in with HTTP (HTTP/1.1 POST); Wed, 31 May 2017 11:40:19 +0530 MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII; format=flowed Content-Transfer-Encoding: 7bit Date: Wed, 31 May 2017 11:40:19 +0530 From: Atul Shree To: "Dumitrescu, Cristian" Cc: "Richardson, Bruce" , cs5120282@cse.iitd.ac.in, dev@dpdk.org Mail-Reply-To: cs5120282@cse.iitd.ac.in In-Reply-To: <3EB4FA525960D640B5BDFFD6A3D891267BA60339@IRSMSX108.ger.corp.intel.com> References: <20170529093008.GB32120@bricha3-MOBL3.ger.corp.intel.com> <3EB4FA525960D640B5BDFFD6A3D891267BA60339@IRSMSX108.ger.corp.intel.com> Message-ID: X-Sender: Atul.Shree.cs512@cse.iitd.ac.in User-Agent: Roundcube Webmail/1.2.2 X-BSPAM: CLEAN 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 Reply-To: cs5120282@cse.iitd.ac.in List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 31 May 2017 06:10:28 -0000 Hi Cristian, We thought of using compressed trie because in worst case it will become the simple trie but in general cases if will avoid very costly memory operation of accessing a new node. On 29-05-2017 18:12, Dumitrescu, Cristian wrote: >> -----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? >> >> 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. >> > >> > > Hi Atul, > > As far as I can recall, we already implemented a sort of tree > compression in 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 into 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 algorithm. Our algorithm is well explained in this link. http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Text/trie02.html as well as on Wikipedia https://en.wikipedia.org/wiki/Radix_tree. > 2. Can you summarize the key improvement for LPM6 as result of using > this algorithm. Is this a performance improvement, how/why is it > achieved, it is a general improvement benefiting all use-cases or just > a specific subset? We have used the prefixes from the link https://github.com/efficient/gopt/blob/ipv6/data_dump/ipv6/uniq_ipv6_rib_201409. But this is just to demonstrate. Our idea have nothing to do with this dataset. We were getting more than 50% throughput improvement on this dataset. Our compressed trie was able to save around 0.5 lookups per prefix on average. There is always some some trade off involved with one or other data structure. This will give very high throughput on average. Haven't tested on worst case scenarios. Implementing this algorithm in DPDK will boils down to two choices i) Intel wants to perform better in worst case or ii) much better in average case. > Thanks, > Cristian Thank you Atul