[Ndn-interest] efficient lookup method

Arunkumar Dhananjayan arunkd13 at gmail.com
Sun Jul 5 01:27:48 PDT 2015


Hi Aliaar,

I think you are tackling the right problem and I believe your research has
good scope in improving the state of the art. You should surely read the
papers you have mentioned and the ones suggested by Haowei.

I see two directions in which you can proceed with your research:

1. Tackle the fundamental problem of efficient name lookup especially
longest prefix matching on which NDN is based on, by coming up with a novel
data structure or algorithm

or

2. Take some of the existing proposed solutions and do a comparison study
of them with data using a real life application

I think more research is needed in both areas.

wishing you the best,
arun

On Sat, Jul 4, 2015 at 8:21 PM, mana alliar <alrrrr.mmmm at gmail.com> wrote:

> Hello,
> My name is Mana Aliaar and I'm a student at shahid beheshti university of
> Tehran, Iran.
> i would appreciate it if you could help me.
> I'm currently working on "proposing an efficient routing in NDN" as my
> master thesis subject.
> following are some of the papers that i've read so far.
> Scalable Name Lookup in NDN Using Effective Name Component Encoding
> <http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6258041>
> Wire Speed Name Lookup: A GPU-based Approach
> <http://dl.acm.org/citation.cfm?id=2482647>
> NameFilter: Achieving fast name lookup with low memory cost via applying
> two-stage Bloom filters
> <http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=6566742&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel7%2F6556116%2F6566708%2F06566742.pdf%3Farnumber%3D6566742>
>
> and the main challenges that these papers express are:
> 1)Complex name structure:i)names consists of digits and characters; ii)
> names have variable length ;   iii) the upper bound length of names are
> unknown.
> 2) and the size of the routing tables(PIT and FIB) which in NDN are 2 or 3
> times larger than IP.
>
> __________________________________________________________________________________________________________________________
> NOW, based on above papers that see lookup speed and forwarding table size
> as major challenges in routing in NDN. I've come to a lookup method:
>
> first for ENTERING THE NAMES IN TABLES: first each name is divided into
> multiple parts. an efficient hash function must be used for each name part.
> and the hash digest must be stored in a table.
> I was thinking of using some kind of indexing method here. like the hash
> result of first part of names must be stored in first level hash tables and
> the hash result of the second part of the name must be stored in second
> level hash tables. and so on.
>
> each entry in table has a pointer to a linked list which the complete
> names are stored there. and the rest of the name prefixes are sotored in
> linked lists.
>
> and for LOOKING UP THE NAME: first the hash result of first part is
> computed and found in first level hash table. then the second part is found
> and... the the rest of the name is found from the linked lists.
>
>
> __________________________________________________________________________________________________________________________
> I have the following questions:
> 1) first of all i would like to know your idea about above papers: am i
> working on the right subject? i mean are these papers seeing the problem in
> NDN in the right way? are their work authentic?
> 2) second, about the proposed method:  what is your idea about the above
> method?
> 3) if i'm on the wrong subject, can you please guide me to the right
> direction? can you suggest some similar works that has done on routing in
> NDN?
> It would be great to know your idea about these questions.
>
> __________________________________________________________________________________________________________________________
> I will be eternally grateful for any help you can provide.
> Thank you.
> Aliaar
>
>
> _______________________________________________
> Ndn-interest mailing list
> Ndn-interest at lists.cs.ucla.edu
> http://www.lists.cs.ucla.edu/mailman/listinfo/ndn-interest
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.lists.cs.ucla.edu/pipermail/ndn-interest/attachments/20150705/78ebf9f6/attachment.html>


More information about the Ndn-interest mailing list