Project

General

Profile

Actions

Task #1271

closed

RIB stores as a trie

Added by Syed Amin about 10 years ago. Updated almost 10 years ago.

Status:
Closed
Priority:
Normal
Assignee:
Category:
RIB
Target version:
Start date:
Due date:
% Done:

100%

Estimated time:

Description

Develop a trie to store the RIB, in order to support route inheritance flags.


Related issues 1 (0 open1 closed)

Blocks NFD - Task #1326: Delete expired RIB entriesClosedSyed Amin

Actions
Actions #1

Updated by Syed Amin about 10 years ago

  • Due date set to 03/06/2014
  • Status changed from New to In Progress
  • Priority changed from Normal to High
  • Start date changed from 02/18/2014 to 03/04/2014
  • % Done changed from 0 to 30
Actions #2

Updated by Alex Afanasyev almost 10 years ago

  • Project changed from 14 to NFD
  • Category set to RIB
  • Target version set to v0.2
Actions #3

Updated by Junxiao Shi almost 10 years ago

  • Subject changed from Creation of Trie to store prefixes and related information to RIB stores as a trie
  • Description updated (diff)
  • % Done changed from 100 to 30
Actions #4

Updated by Lan Wang almost 10 years ago

  • Assignee changed from Syed Amin to Vince Lehman
Actions #5

Updated by Junxiao Shi almost 10 years ago

20140512 research meeting with Tian Song decides that Tian will provide advice on how to implement the trie for RIB.
One possibility is to implement RIB on top of NameTree, if class NameTree can provide sufficient algorithms for RIB usage. NameTree entry will need a generic type to support either FIB/PIT/Measurements/StrategyChoice or RIB.

Actions #6

Updated by Lan Wang almost 10 years ago

Anyone can share a copy of the design document for NameTree? I don't know enough about it to make a comment on its applicability in RIB at this moment.

Actions #7

Updated by Haowei Yuan almost 10 years ago

Please find the data structure design of the NameTree on Slide 11 of this document (https://dl.dropboxusercontent.com/u/2661516/14_02_14_Table_Design_updated.pdf), which was used when we discussed the NameTree design. I have updated the slides with the implemented APIs.

A more general description of NameTree and its functions (prepared by Junxiao and Alex?) is available at http://redmine.named-data.net/issues/1187.

Lan Wang wrote:

Anyone can share a copy of the design document for NameTree? I don't know enough about it to make a comment on its applicability in RIB at this moment.

Actions #8

Updated by Lan Wang almost 10 years ago

Is the current NameTree implementation generic enough for us to store RIB in it? Alex told me that it is not right now.

Actions #9

Updated by Junxiao Shi almost 10 years ago

NameTree entry needs to be extended / generalized to support RIB.
NameTree algorithms should be sufficient.

There is a long term benefit to have RIB and NFD tables both use NameTree, rather than creating a separate structure, because any improvement to the NameTree can benefit both.

Actions #10

Updated by Lan Wang almost 10 years ago

I wonder if Vince is able to modify the implementation of NameTree to support generic entries and make it implement an interface (which can be implemented by other data structures, e.g., trie).

Actions #11

Updated by Vince Lehman almost 10 years ago

  • % Done changed from 30 to 70
Actions #12

Updated by Vince Lehman almost 10 years ago

  • % Done changed from 70 to 80
Actions #13

Updated by Vince Lehman almost 10 years ago

  • % Done changed from 80 to 90
Actions #14

Updated by Vince Lehman almost 10 years ago

  • Status changed from In Progress to Code review
  • % Done changed from 90 to 100
Actions #15

Updated by Syed Amin almost 10 years ago

  • Blocks Task #1326: Delete expired RIB entries added
Actions #16

Updated by Vince Lehman almost 10 years ago

  • Status changed from Code review to Closed
  • % Done changed from 90 to 100
Actions

Also available in: Atom PDF