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.oh...@ntt.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:misl...@kent.edu] >> Sent: Wednesday, September 05, 2018 2:55 PM >> To: pa...@hongo.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/
