[dpdk-dev] Why DPDK is not using compressed TRIE for LPM6?

[Atul Shree]

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 at cse.iitd.ac.in
>> Cc: dev at dpdk.org; Dumitrescu, Cristian <cristian.dumitrescu at intel.com>
>> 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