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

[Junxiao Shi]

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>