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

[César A. Bernardini]

Thanks a lot for your answer Junxiao, it was really precise!

However, I could not download your thesis. The download button always
return 0 bytes.

Cheers,

2018-04-13 22:52 GMT+02:00 Junxiao Shi <shijunxiao at email.arizona.edu>:

> 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/20180416/ede8097b/attachment.html>