[Ndn-interest] NDN data structures for FIB, PIT, CS

Junxiao Shi shijunxiao at email.arizona.edu
Fri Apr 13 13:52:10 PDT 2018

Hi Cesar

I was curious about the default data structures used by NDN tables. I was
> wandering if there is any RFC that states the structure to be used in ICN.

Choice of data structure is an implementation choice. An NDN node can use
any data structure as long as it can fulfill the requirements of NDN
protocol (see http://hdl.handle.net/10150/625652 chapter 3).
RFCs should describe the protocol requirements. RFCs should not constrain
data structure choice.

According to my findings in the NDN code, the structure used are Red-Black
> Trees for Content Stores[0] and Hashing Tables[1,2] for FIB[3] and PIT[4].
> [1] Hashtable m_ht;: nano daemon/table/name-tree.hpp
> [2] Hashtable: daemon/tree/name-tree-hashtables.hpp
> [3] Fib: NameTree daemon/table/fib.hpp
> [4]: NameTree daemon/table/pit.hpp
> [5] typedef std::set<EntryImpl> Table; daemon/table/cs.hpp

These are NFD's choices, but not necessarily the best choices.
It's possible to use hash tables for all three tables, as described in Named
data networking on a router: Fast and DoS-resistant forwarding with hash
tables <https://ieeexplore.ieee.org/document/6665203/>.
It's also possible to use a single tree for all three tables, as done in ccnd
0.7.2 <https://redmine.named-data.net/projects/nfd/wiki/CcndKnowledge>.

Yours, Junxiao
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.lists.cs.ucla.edu/pipermail/ndn-interest/attachments/20180413/fad6f1cf/attachment.html>

More information about the Ndn-interest mailing list