Project

General

Profile

Actions

Task #2863

closed

NamePrefixTableEntries should store RoutingTableEntries using a pointer

Added by Vince Lehman over 9 years ago. Updated about 8 years ago.

Status:
Closed
Priority:
High
Target version:
Start date:
06/09/2015
Due date:
% Done:

100%

Estimated time:

Description

NamePrefixTableEntries can store a pointer to destination RoutingTableEntries instead of making a copy for each RoutingTableEntry.

Currently, even if multiple NamePrefixTableEntries share the same destination router, they will each individually keep a copy of the associated RoutingTableEntry.


Files

nptdoc.pdf (99.9 KB) nptdoc.pdf Long-form document explaining design choices, and a brief discussion about changes. Nicholas Gordon, 08/10/2016 01:59 PM

Related issues 2 (0 open2 closed)

Blocked by NLSR - Task #2862: Create flowchart for interaction between RoutingTable, NamePrefixTable, and FIBClosedMuktadir Chowdhury06/09/2015

Actions
Blocks NLSR - Task #2864: A RoutingTable calculation should only update NamePrefixTableEntries with an affected RoutingTableEntryClosedNicholas Gordon

Actions
Actions #1

Updated by Vince Lehman over 9 years ago

  • Blocked by Task #2862: Create flowchart for interaction between RoutingTable, NamePrefixTable, and FIB added
Actions #2

Updated by Vince Lehman over 9 years ago

  • Target version set to v0.3.0
Actions #3

Updated by Nicholas Gordon over 8 years ago

  • Status changed from New to In Progress
  • Assignee set to Nicholas Gordon
  • Priority changed from Normal to High
  • Target version deleted (v0.3.0)
Actions #4

Updated by Nicholas Gordon over 8 years ago

  • Target version set to v0.3.0
Actions #5

Updated by Nicholas Gordon over 8 years ago

I have developed a plan for implementation: I intend to give the NPT a storage pool of routing table entries in the form of a hash map. I have not yet decided whether to store the RTEs in the hash set as pointers or as whole objects, but I am not sure that this distinction is very important.

Keeping an array of pointers would be more space efficient, since each pointer is only 8 bytes, but because hash maps have very fast lookup time and also this approach solves the entry duplication problem, I think it is worth the slight loss of space efficiency.

I intend to use the names associated with the router to hash the RTE pool entry, which contains the next hop list, count of NPT entries using it, and all the other things a RTE would have, to map the values. Again, I think the ease of use easily trumps the small costs.

Actions #6

Updated by Nicholas Gordon over 8 years ago

  • Status changed from In Progress to Code review
  • % Done changed from 0 to 100

The implemented solution passes all of the unit tests. It is currently on gerrit for code review. More unit tests were written to test the internal functionality of the new data structure.

Actions #7

Updated by Nicholas Gordon about 8 years ago

  • Target version changed from v0.3.0 to v0.3.1
Actions #8

Updated by Nicholas Gordon about 8 years ago

Actions #9

Updated by Nicholas Gordon about 8 years ago

  • Blocks Task #2864: A RoutingTable calculation should only update NamePrefixTableEntries with an affected RoutingTableEntry added
Actions #10

Updated by Nicholas Gordon about 8 years ago

After some time I was able to iron out kinks with the convergence experiment I'd developed. A reduced testbed topology of 30 nodes was used. The working directory was made on a ramdisk, and before each experiment iteration the whole ramdisk was emptied, stale mini-net furniture was destroyed, and any lingering NFD processes were killed. The results were:

Master NLSR. 30-node topology, on Fri Aug 26 14:02:35 EDT 2016: average time over 10 runs: 28.73963184357 seconds.
NPT-patched NLSR. 30-node topology, on Fri Aug 26 14:15:51 EDT 2016: average time over 10 runs: 28.52513318061 seconds.
Difference: ~0.214s.

With a difference this small it is not possible to tell if this is statistical noise or a significant result. The size and/or complexity of the topology could be increased, or more iterations could be done to smooth out possible statistical variations.

Actions #11

Updated by Nicholas Gordon about 8 years ago

  • Status changed from Code review to Closed
Actions

Also available in: Atom PDF