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

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

[ankit bhardwaj]

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.

Here are my questions:
Q1: Why DPDK is not doing the compression?
Q2. In the worst case the table will behave like an uncompressed TRIE and
in other cases, there is a scope of improvement. Is it worth doing?

 --
Ankit Bhardwaj

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

[Atul Shree]

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.

Here are my questions:
Q1: Why DPDK is not doing the compression?
Q2. In the worst case the table will behave like an uncompressed TRIE 
and
in other cases, there is a scope of improvement. Is it worth doing?

Thank you!

Atul Shree

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

[Bruce Richardson]

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.

> Here are my questions:
> Q1: Why DPDK is not doing the compression?

It's probably not a deliberate omission, more likely that nobody has
done it.

> Q2. In the worst case the table will behave like an uncompressed TRIE and
> in other cases, there is a scope of improvement. Is it worth doing?
> 

If there is improvement in the normal case, with the worst-case perf
being no worse, it sounds like it may be worth doing. Feel free to
submit patches for evaluation on the list.

Regards,
/Bruce

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

[Vladimir Medvedkin]

Hi all,

Currently I'm working on compressed trie implementation for LPM4 lib. I
think it could be adapted for LPM6.

2017-05-29 12:30 GMT+03:00 Bruce Richardson <bruce.richardson@intel.com>:

> 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.
>
> > Here are my questions:
> > Q1: Why DPDK is not doing the compression?
>
> It's probably not a deliberate omission, more likely that nobody has
> done it.
>
> > Q2. In the worst case the table will behave like an uncompressed TRIE and
> > in other cases, there is a scope of improvement. Is it worth doing?
> >
>
> If there is improvement in the normal case, with the worst-case perf
> being no worse, it sounds like it may be worth doing. Feel free to
> submit patches for evaluation on the list.
>
> Regards,
> /Bruce
>
>


-- 
Regards,
Vladimir

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

[Dumitrescu, Cristian]

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

Re: [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@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.
>> >
>> 
> 
> 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