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

["Dumitrescu, Cristian" <cristian.dumitrescu@intel.com>]

> -----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 <cristian.dumitrescu@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.
> >
> 
> 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.
> 

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.
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?

Thanks,
Cristian