NFD

For step2 - enumeration:

Not sure if using the naming convention to distinguish async-strategy is good design.

By having the strategy name in the prefix, once a fib entry is inserted into the NameTree,

• if the prefix of the fib entry contains strategy name, we check if the NameTree entry has any children with PIT entry, then decide whether to send the Interest or not.
• otherwise, we do nothing.

I am not sure if we've reached a consensus on 06/19/2019 NFD call.

• Lixia and Beichuan want to make it a standalone strategy;
• Junxiao (and this issue) suggests we are going to make a building block.

According to the last NFD call, it seems Beichuan concluded that we want to build a single strategy and Junxiao had no objection. If that's the case, should we modify the issue description to build a single strategy?

There's no conflict: you need a building block, and a single strategy that references said building block.

While I am looking for an efficient way to enumerate a portion of PIT entries, I have a question: according to NFD developer guide, the FIB is expected to be relatively stable, meaning there won't be many FIB entry nexthop update, so there won't be too frequent PIT entry enumeration.

So is it safe to say the overall overhead of PIT entries enumeration after new nexthops is not too significant?

Ju Pan wrote:

While I am looking for an efficient way to enumerate a portion of PIT entries, I have a question: according to NFD developer guide, the FIB is expected to be relatively stable, meaning there won't be many FIB entry nexthop update, so there won't be too frequent PIT entry enumeration.

So is it safe to say the overall overhead of PIT entries enumeration after new nexthops is not too significant?

Any comments?

Here is an idea to reduce the partial enumeration overhead, which requires modifying the NameTreeEntry class.

We add a bool field - subTreeHasDiffSc - for NameTreeEntry class to tell if the current NTE's subtree has a different strategy choice than the current one.

Init: subTreeHasDiffSc is set to false by default,
If: 1. a new entry is inserted into the NameTree or 2. the existing's entry's strategy choice is changed,
Then: we check the current entry's parent to see if they have a different strategy choice, if yes: we set parent's subTreeHasDiffSc to true. Then we keep checking the parent's parent and do the same checking, all the way to the root node.

This will apply an extra O(logn) time complexity to each NameTree insertion and StrategyChoice entry update operation.

With the help of subTreeHasDiffSc field, in the partial enumeration step, we only need to check the entry's subTreeHasDiffSc to see if we need to visit the subtree, instead of going through all the node in the subtree to check if there is a different strategy choice than the current entry's.

Any comments?

Question: According to the developer guide, a FIB entry contains a name prefix and a non-empty collection of NextHop records. But the issue is "Transmit pending Interests upon FIB nexthop creation". If there is already a nexthop in the FIB entry, shouldn't we forward the Interest directly to that nexthop instead of retaining it? So based on my understanding, the issue should be "Transmit pending Interests upon FIB entry insertion". That is, we retain the PIT entry only when there is no FIB entry matching.

Please let me know if I got anything wrong here. Thanks.

"FIB next-hop creation" is correct. Even if a FIB entry exists and was used upon Interest arrival, the creation of a new next-hop presents a new opportunity to reach the content via this next-hop.

Junxiao Shi wrote:

"FIB next-hop creation" is correct. Even if a FIB entry exists and was used upon Interest arrival, the creation of a new next-hop presents a new opportunity to reach the content via this next-hop.

But I feel like the FIB next-hop creation should not trigger PIT entry partial enumeration, only the FIB entry insertion should.
If a FIB entry exists, it means the corresponding PIT entry doesn't need to be retained, we just forward them according to the existing forwarding strategy.
The only case we want to retain the PIT entry is when there is no corresponding FIB entry.

For the best-route-strategy2's parameter format, can we simplly do this:

// doesn't support async
/localhost/nfd/strategy/best-route/%FD%05 

// support async
/localhost/nfd/strategy/best-route/%FD%05/async  

Proposing a NameTreeEntry modification to solve the partial enumeration overhead:
Adding an integer field numOfSubtreeSupportAsync for NameTreeEntry class to indicate how many subtrees (root from current node’s children) support async-strategy behavior.

Yes, this is correct. It is a classical data structure design problem.
The "async" terminology needs to be changed to "supportsNewNextHop" to remove ambiguity. "supportsNewNextHop" indicates whether a strategy wants to receive "afterNewNextHop" trigger.

// support async
/localhost/nfd/strategy/best-route/%FD%05/async  

Mostly correct.
You must increment version number in the strategy name each time the strategy has a behavior change, see NFD devguide for details.

Ju Pan wrote:

// support async
/localhost/nfd/strategy/best-route/%FD%05/async  

I suggest finding a better name for this feature. "async" doesn't give any indication on what it's really about.

Davide Pesavento wrote:

Ju Pan wrote:

// support async
/localhost/nfd/strategy/best-route/%FD%05/async  

I suggest finding a better name for this feature. "async" doesn't give any indication on what it's really about.

What about:

/localhost/nfd/strategy/best-route/%FD%06/retain-pit-entry
/localhost/nfd/strategy/best-route/%FD%06/pit-entry-wait
/localhost/nfd/strategy/best-route/%FD%06/suport-new-nexthop

any other suggestions?

[Updated]

Here is the summary of the discussion from NFD Call on 07/22/2019.

1. We need to build a generic mechanism to notify the NFD when the new nexthops are created. Any logic after NFD knowing the nexhop creation is supposed to be handled by the forwarding strategies themselves. In this issue, we will deal with sending out all "unforwarded" pending Interests to the new nexthop. Anything more complicated than that is out of scope.

2. Async behavior consists of the following steps:

   • Interests arrive at NFD;
   • NFD doesn't have any nexthop for the corresponding name prefixes;
   • NFD retains these Interests in PIT:
     • To prevent congestion, there is a per downstream limit for the number of retained Interests: for a downstream, if the Interests retained by NFD exceeds the limit, the rest will get NACKed (no route Interest response)
     • The per downstream limit is configurable through the strategy parameter. Considering the initial congestion window size is 1, intuitively we set the per downstream limit to be 5.
   • Once there is a new nexthop created, NFD checks against its PIT, if there are matching pending Interests, send them out.

Ju Pan wrote:

/localhost/nfd/strategy/best-route/%FD%06/retain-pit-entry
/localhost/nfd/strategy/best-route/%FD%06/pit-entry-wait

Neither of these is a good name. You're putting the accent on the PIT entry, which is little more than an implementation detail. The feature is about being notified of new nexthops, so something like "new-nexthop-trigger" or "notify-new-nexthop".

/localhost/nfd/strategy/best-route/%FD%06/suport-new-nexthop

This is better. But I'd drop "support" because whether the feature is supported or not is a property of the code, it cannot be turned on or off, what you can enable or disable at runtime is the reaction to the nexthop insertion.

Btw, it could be argued that this new behavior should be enabled by default. In that case the parameter name should be something like "disable-new-nexthop-trigger" or "no-notify-new-nexthop".

Ju Pan wrote:

Any logic after NFD knowing the nexhop creation is supposed to be handled by the forwarding
strategies themselves,

Correct.

it's out of the scope of this issue.

No. The basic reaction of sending out all "unforwarded" pending Interests to the new nexthop should be done in this issue. Anything more complicated than that is out of scope.

• Once NFD is notified a new nexthop creation

This is confusing. It sounds like there's some external process that notifies NFD about new nexthops, which is not true.

In 5642,4, Strategy::afterNewNextHop trigger is declared as:

  /** \brief trigger after new FIB nexthop creation
   *
   *  In the base class, this method checks NameTree to see if there are any pending Interets
   *  under the new FIB nexthop prefix. If so, send them to the new nexthop.
   */
  virtual void
  afterNewNextHop(const Name& prefix, const fib::NextHop& nextHop);

This declaration is wrong, because strategy triggers operate at the granularity of PIT entry, and does not have access to the NameTree.
The reason of prohibiting direct access to the NameTree is to prevent a strategy from accessing namespace under another strategy's control, as that would cause conflicts.
The correct declaration is:

  virtual void
  afterNewNextHop(const Name& prefix, const fib::NextHop& nextHop, const shared_ptr<pit::Entry>& pitEntry);

Forwarding pipelines must perform the enumeration on behalf of the strategy, and invoke the trigger for each affected PIT entry.

HI Junxiao, thanks for point this out. I also noticed this problem, that's why I tried to add a signal in fib-entry and a triggerAfterNewNextHop() in forwarder, then connect them. I actually made comments about this just before your comments on Gerrit, could you comment on them? Basically, the issues are:

1. as Davide pointed out, the overhead of one signal per fib entry may be unacceptable,
2. how can I connect signal in fib-entry to the method in the forwarder.

Thanks.

The overhead of per-FIB-entry signals must be proven by benchmark. However, per-FIB-entry signals aren't necessary: you only need a signal on the FIB itself, and then all nexthop updates must be done through Fib::addNextHop(entry, nh) and Fib::removeNextHop(entry, nh) methods, while the nexthop update functions on fib::Entry type are marked private after making Fib type a friend.

From https://gerrit.named-data.net/c/NFD/+/5642/6/daemon/fw/forwarder.cpp#519

I think there is a potential problem that will trigger multiple notifications for the same PIT entries and some false notifications. Here is the case:

/a and /a/b FIB entries with child inherit: if new route registered for /a/b, the same new face will be added to /a as well. With the current logic, this will trigger update of pit entries related to /a/b and children + separate trigger for update of pit entries related to /a and children

FIB and RIB operate independently. From FIB point of view, this would be two events:

1. Add nexthop to /a/b: this triggers strategies for PIT entries under /a/b that are not covered by another FIB entry.
2. Add nexthop to /a: this triggers strategies for PIT entries under /a that are not covered by another FIB entry, i.e. PIT entries under /a/b would be excluded.

/a/b and /a/b/c with capture flag

FIB does not see RIB's capture flag. FIB entry takes effect on PIT entries under its name prefix, excluding any PIT entries covered by other FIB entries. Therefore, capture flag or not, the enumeration procedure will do the right thing.

Summary of the 2019-08-12 NFD Call:

We want to divide this task into 4 commits:

Commit 1: Add a signal in the Fib class and moving addOrUpdateNextHop function to Fib class

• Add a afterNewNextHop signal in Fib class
• Adding addOrUpdateNextHop() function for Fib class. Change everything that updates the nexthop to go through Fib's addOrUpdateNextHop().
• Mark addOrUpdateNextHop() and removeNexHop() functions as private (for code consistency issues)
• Change the unit tests for fib-entry class (probably others)

Commit 2: Add the per downstream counters to avoid exceeding the retained Interests limit.
Commit 3: Add strategy trigger and enumeration part. In forwarder's constructor, connect the enumeration to Fib's afterNewNextHop signal.
Commit 4: Implement something to react to the trigger.

Patch 3 uploaded:
fw: add processing for afterNewNextHop signal
https://gerrit.named-data.net/c/NFD/+/5720

This patch modifies forwarding pipelines. It must be accompanied by an update to the forwarding pipelines slides in NFD devguide.

Junxiao Shi wrote:

This patch modifies forwarding pipelines. It must be accompanied by an update to the forwarding pipelines slides in NFD devguide.

So I should request access to the project on GitLab, modify the slide, and push the change directly. Correct?

You updated the slides but didn't update the date in the file name.

Davide Pesavento wrote:

You updated the slides but didn't update the date in the file name.

Done now.

Davide Pesavento wrote:

Davide Pesavento wrote:

You updated the slides but didn't update the date in the file name.

Done now.

Thanks!

Right now, we have a counter per face.

I should increase this counter when the Interest is buffered due to no next hop (don't increase the counter if the Interest is aggregated). So for unsatisfied pitEntry, only the first inrecord's counter will be increased by 1.

I decrease the counter when the Interest is sent due to new next hop and only decrease by 1 for the first inrecord of pitEntry.

Question:

1. But what if the Interest is never sent and gets expired? How should we decrease the counter? Do you have any suggestions?
2. I am using a const_cast to increase/decrease the counter which is argued to be bad, any suggestion on this?

For the first question, about how to decrease counter when Interest expires. Can we simply decrease the counter (if it's not zero) for the first in-record when the pitEntry expires?

But there could be: the pitEntry doesn't enable new-next-hop, the counter should not be decreased in this case.