[Ndn-interest] efficient lookup method

Muhammad Hosain Abdollahi Sabet M.AbdollahiSabet at mail.sbu.ac.ir
Sat Jul 4 13:25:46 PDT 2015

Hi Aliaar,

What do you mean by parts? You mean name components? Then, what is going to be the first part? How are you going to define that? I mean, is going to be something like putting first components' digest in a table and link each entry to another table, list or something?


-----Original Message-----
From: Ndn-interest on behalf of mana alliar
Sent: Sat 7/4/2015 7:21 PM
To: ndn-interest at lists.cs.ucla.edu
Subject: [Ndn-interest] efficient lookup method
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
Wire Speed Name Lookup: A GPU-based Approach
NameFilter: Achieving fast name lookup with low memory cost via applying
two-stage Bloom filters

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

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
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
It would be great to know your idea about these questions.

I will be eternally grateful for any help you can provide.
Thank you.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.lists.cs.ucla.edu/pipermail/ndn-interest/attachments/20150705/74ea803e/attachment.html>

More information about the Ndn-interest mailing list