<div dir="ltr">Hi Cesar<div><br><div><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">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.<br></div></blockquote><div><br></div><div>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 <a href="http://hdl.handle.net/10150/625652">http://hdl.handle.net/10150/625652</a> chapter 3).</div><div>RFCs should describe the protocol requirements. RFCs should not constrain data structure choice.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">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].<div><br></div><div><div>[1] Hashtable m_ht;: nano daemon/table/name-tree.hpp<br>[2] Hashtable: daemon/tree/name-tree-<wbr>hashtables.hpp<br>[3] Fib: NameTree daemon/table/fib.hpp<br>[4]: NameTree daemon/table/pit.hpp</div></div><div>[5] <span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">typedef std::set<EntryImpl> Table; <span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">daemon/table/cs.hpp</span></span></div></div>
</blockquote></div><div class="gmail_extra"><br></div>These are NFD's choices, but not necessarily the best choices.</div></div></div><div class="gmail_extra">It's possible to use hash tables for all three tables, as described in <a href="https://ieeexplore.ieee.org/document/6665203/">Named data networking on a router: Fast and DoS-resistant forwarding with hash tables</a>.</div><div class="gmail_extra">It's also possible to use a single tree for all three tables, as done in <a href="https://redmine.named-data.net/projects/nfd/wiki/CcndKnowledge">ccnd 0.7.2</a>.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Yours, Junxiao</div></div>