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: cs5120...@cse.iitd.ac.in
Cc: dev@dpdk.org; Dumitrescu, Cristian <cristian.dumitre...@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
