[Ndn-interest] efficient lookup method

Haowei Yuan hyuan at wustl.edu
Sat Jul 4 22:02:40 PDT 2015

Hi Aliaar,

Since you mentioned hashing, beside these papers, there are also several
hash-based name prefix lookup methods that you might be interested, such as

Reliably Scalable Name Prefix Lookup, ANCS 2015
Caesar: a content router for high-speed forwarding on content names, ANCS
Fast Name Lookup for Named Data Networking, IWQoS 2014
Named data networking on a router: fast and dos-resistant forwarding with
hash tables, ANCS 2013

Hope this helps.


On Sat, Jul 4, 2015 at 9:51 AM, 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.lists.cs.ucla.edu/pipermail/ndn-interest/attachments/20150705/57e81f7c/attachment.html>

More information about the Ndn-interest mailing list