netdev - Re: Poptrie in Linux kernel

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Message-ID: <CAFgPn1CWTg3Yx4vdXhsqOnzGV4ifWva9PkL51QnUmDaGMWesMQ@mail.gmail.com>
Date:   Wed, 5 Sep 2018 18:30:10 -0400
From:   "Md. Islam" <mislam4@...t.edu>
To:     Yasuhiro Ohara <yasuhiro.ohara@....com>,
        Netdev <netdev@...r.kernel.org>
Cc:     "panda@...go.wide.ad.jp" <panda@...go.wide.ad.jp>,
        Hayakawa Yutaro <yhayakawa3720subscribe@...il.com>
Subject: Re: Poptrie in Linux kernel

Hi Yasuhiro

I would like to point out that the lookup process, Trie construction
and even the Trie itself is not same as the patent [1]. The idea of
splitting prefix into multiple level  is not new. SAIL [2] does it as
well. In fact, I started by implementing SAIL in Linux kernel. Then
came across the idea of representing chunk IDs with bitmap in Poptrie
[3] and in this book [4]. Although my work was inspired by your paper
[3] and SAIL [2] and this book [4] (I was not aware of the patent[1]),
actual trie, trie lookup and trie construction process is very
different from the paper/patent. The only thing that's same is the
name, POPTRIE :-) As that was a ACM SIGCOMM paper, I thought using the
same name will be helpful for others to understand and review my work.

Looking forward to your suggestions.

1. http://www.conceptsengine.com/patent/grant/0005960863
2. Yang, Tong, et al. "Guarantee IP lookup performance with FIB
explosion." ACM SIGCOMM  2014.
3. Asai, Hirochika, and Yasuhiro Ohara. "Poptrie: A compressed trie
with population count for fast and scalable software IP routing table
lookup." ACM SIGCOMM, 2015.
4. Warren, Henry S. Hacker's delight. Pearson Education, 2013.

Many thannks
Tamim

On Wed, Sep 5, 2018 at 7:48 AM, Yasuhiro Ohara <yasuhiro.ohara@....com> wrote:
>
> Dear Islam,
>
> Thank you for being interested in and implementing the Poptrie.
>
> Yes, NTT Communications (my company) has filed the patent for the Poptrie.
>
> To my best knowledge, the patent issue is totally different
> from the copyright issue (of the source code), and so even
> the copyright issue were cleared/solved, it does not mean
> the patent issue was gone.
>
> I am requesting to my company what is our company's action
> to your Poptrie implementation.
>
> Would you please wait for a while until NTT Communications
> decide its response. We will inform you as soon as it is decided.
>
> Best regards,
> Yasu
>
>> -----Original Message-----
>> From: Md. Islam [mailto:mislam4@...t.edu]
>> Sent: Wednesday, September 05, 2018 2:55 PM
>> To: panda@...go.wide.ad.jp
>> Cc: Hayakawa Yutaro; Yasuhiro Ohara（小原泰弘）
>> Subject: Poptrie in Linux kernel
>>
>> Hi Hirochika
>>
>> I am a PhD student of Kent State University, Ohio, USA. I came across your
>> Poptrie paper and found it fascinating. I implemented it in Linux kernel.
>> However the trie construction and lookup process is somewhat different from
>> the original paper. For instance, in my case, the node looks like as
>> following.
>>
>> struct poptrie_node {
>>     u64 vector;
>>     u64 leafvec;
>>     //Not needed in SIGCOMM paper
>>     u64 nodevec;
>>     struct poptrie_node *child_nodes;
>>     u8 *leaves;
>>     //Not needed in SIGCOMM paper
>>     u8 *prefixes;
>>     //Not needed in SIGCOMM paper
>>     struct rcu_head        rcu;
>> };
>>
>> Note that here I used some extra variables than the SIGCOMM paper.
>> This is because trie is construction/lookup process is different than the
>> original paper. This will be more evident if you look more at my patch.
>>
>> My implementation is also not based on the original implementation
>> (https://github.com/pixos/poptrie). However as the implementation is
>> copyrighted by you, I would like to ask your permission if I can submit
>> my implementation to upstream kernel.
>>
>> Hayakawa also pointed that NTT communications have patented this. I was
>> not aware of this. Could you please advise if I can submit the patch as
>> Poptrie to upstream Linux kernel? I have cited your paper in the patch.
>> I don't have any problem acknowledgeing your and NTT's contribution. You
>> guys know you deserve it :-) I have attached the patch and my draft paper
>> regarding my implementation. Could you please take a look at the paper and
>> patch to see if there is any legal problem in getting this patch into upstream
>> Linux kernel.
>>
>> Please let me know any question.
>>
>> Many thanks
>> Tamim
>> PhD Candidate,
>> Kent State University
>> http://web.cs.kent.edu/~mislam4/