Project

General

Profile

Feature #4931

Transmit pending Interests upon FIB nexthop creation

Added by Junxiao Shi about 1 year ago. Updated 7 months ago.

Status:
In Progress
Priority:
Normal
Assignee:
Category:
Forwarding
Target version:
-
Start date:
Due date:
% Done:

80%

Estimated time:
9.00 h

Description

Currently, every strategy rejects an Interest if no FIB nexthop exists: when an Interest arrives but there's no matching FIB nexthop, the strategy drops the Interest, erases the PIT entry, and optionally sends a Nack.
This causes difficulty in repo insertion and other use cases.

This issue is to develop an async strategy building block. With this strategy activated on a namespace:

  1. When an Interest arrives but there's no matching FIB nexthop, the PIT entry is still retained.
  2. When a new FIB nexthop is inserted, forwarding plane enumerates a portion of the PIT covered by the FIB entry and triggers the strategy. This requires forwarding plane changes.
  3. The strategy may forward the Interest to the new FIB nexthop.

Careful consideration must be given to reduce overhead:

  • PIT enumeration should only cover a namespace subset where this type of strategy is active and FIB nexthop list has changed.
  • Number of enumerated entries should be bounded, or the enumeration should be performed asynchronously, to prevent freezing the forwarding thread.
  • Outgoing Interests should be paced/bounded to prevent congestion.

Files

async-strategy.cpp (3.77 KB) async-strategy.cpp meeting log Ju Pan, 06/25/2019 02:06 PM
async_strategy_0.pdf (99.2 KB) async_strategy_0.pdf async-strategy intro (incomplete) Ju Pan, 07/09/2019 03:22 PM
#1

Updated by Ju Pan about 1 year ago

  • Status changed from New to In Progress
  • Assignee set to Ju Pan
#2

Updated by Ju Pan about 1 year ago

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.
#3

Updated by Ju Pan about 1 year ago

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?

#4

Updated by Junxiao Shi about 1 year ago

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

#5

Updated by Ju Pan about 1 year ago

Here is the summary of the discussion between Junxiao and me:

1). We want to modify the existing strategies (BestRouteStrategy2, AsfStrategy, and MulticastStrategy) to support holding PIT entry instead of making a new strategy or using building block. The reasons are:

  • "building block" in a separate class doesn't make sense, there is no logic other than "retain PIT entry"
  • Creating a separate class doesn't make sense either, because after FIB nexthop is in place, forwarding logic is almost the same as forwarding a new Interest and that differs per strategy. Duplicating an existing strategy complicates the code complexity and the maintainability.

2). We also discussed the implementation detail for each step.

Step 1: When an Interest arrives but there's no matching FIB nexthop, the PIT entry is still retained.

  • In Fib class, we add an afterNewNextHop signal
  • Create new triggers in Strategy base class: supportsNewNextHop() and afterNewNextHop()
  • Enable user to decide whether to activate "retaining PIT entry' feature by using strategy parameter (#3868)
  • Add new block in BestRouteStrategy2::afterReceiveInterest to check if support "retaining PIT", if so, set the PIT entry expiry timer to Interest lifetime.

Step 2: When a new FIB nexthop is inserted, forwarding plane enumerates a portion of the PIT covered by the FIB entry and triggers the strategy. This requires forwarding plane changes.

  • In forwarding, we add a triggerStrategyAfterNewNextHop() function. It handles the partial enumeration of the affected NameTree entries. triggerStrategyAfterNewNexthop() is connected to afterNewNexthop signal.
  • For each affected NameTree entry, we lookup StrategyChoice table to determine the effective strategy for nte.getName(), then trigger strategy on PIT entry.

Step 3: The strategy may forward the Interest to the new FIB nexthop.

  • In afterNewNextHop() trigger, we forward the Interest to nexthops.

3). Thoughts on reducing overhead:

  • PIT enumeration should only cover a namespace subset where this type of strategy is active and FIB nexthop list has changed.
  • We should skip this subtree if no strategy within this subtree supports NewNextHop trigger.
  • We can easily know the effective strategy for the current nte: either nte has Strategy Choice, or nte's ancestor has it.
  • But, how to know if there are any other Strategy Choices within the subtree? The naive way is to go through every node in the subtree, but this will cause too much overhead. We are still looking for a more efficient way.
  • Number of enumerated entries should be bounded, or the enumeration should be performed asynchronously, to prevent freezing the forwarding thread.
  • TBD
  • Outgoing Interests should be paced/bounded to prevent congestion.
  • TBD
#6

Updated by Ju Pan about 1 year ago

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?

#7

Updated by Ju Pan about 1 year ago

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?

#8

Updated by Ju Pan about 1 year ago

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?

#9

Updated by Ju Pan about 1 year ago

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.

#10

Updated by Junxiao Shi about 1 year ago

"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.

#11

Updated by Ju Pan about 1 year ago

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.

#12

Updated by Ju Pan about 1 year ago

  • File async_strategy.pdf added

Ju Pan wrote:

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?


Updates:

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.

Init: the numOfSubtreeSupportAsync is set to 0 by default.
numOfSubtreeSupportAsync is greater than 0 means there are nodes in the subtrees that support async-strategy behavior. So in PIT entry partial enumeration, we might want to visit the subtree.

Case 1: when a new entry is inserted into the NameTree

  • If the strategy choice supports async-strategy:
    1. Increase its parent’s numOfSubtreeSupportAsync by 1.
    2. If the parent numOfSubtreeSupportAsync is set from 0 to 1 (meaning this subtree starts to support async-strategy), we go to parent’s parent and repeat the algorithm all the way to the root entry if necessary. Otherwise, stop here.
  • If the strategy choice doesn’t support async-strategy, we do nothing.

Case 2: when an existing entry's strategy choice is changed

  • SC is changed from supporting async-strategy to not supporting async-strategy:
    1. If numOfSubtreeSupportAsync is 0, then go to its parent and decrease numOfSubtreeSupportAsync by 1
    2. If the parent’s numOfSubtreeSupportAsync becomes 0 and it doesn’t support async-strategy, go to the parent’s parent and repeat the algorithm.
  • SC is changed from not supporting async-strategy to supporting async-strategy:
    1. If its numOfSubtreeSupportAsync is 0, repeat the first bullet point in case 1;
    2. Otherwise, do nothing.

Then in the PIT entry partial enumeration, we only need to check the numOfSubtreeSupportAsync of the current node:

  • If numOfSubtreeSupportAsync == 0
    • no need to visit the subtree
  • If numOfSubtreeSupportAsync > 0
    • may visit the subtree
#13

Updated by Ju Pan about 1 year ago

  • File deleted (async_strategy.pdf)
#15

Updated by Ju Pan about 1 year ago

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  
#16

Updated by Junxiao Shi about 1 year ago

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.

#17

Updated by Davide Pesavento about 1 year ago

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.

#18

Updated by Ju Pan about 1 year ago

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?

#19

Updated by Ju Pan 12 months ago

[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.
#20

Updated by Davide Pesavento 12 months ago

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".

#21

Updated by Davide Pesavento 12 months ago

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.

#22

Updated by Junxiao Shi 11 months ago

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.

#23

Updated by Ju Pan 11 months ago

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.

#24

Updated by Junxiao Shi 11 months ago

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.

#25

Updated by Junxiao Shi 11 months ago

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.

#26

Updated by Ju Pan 11 months ago

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.

#27

Updated by Ju Pan 10 months ago

  • % Done changed from 0 to 20

patch 1 merged:

table: add Fib::afterNewNextHop signal
https://gerrit.named-data.net/c/NFD/+/5642

#28

Updated by Ju Pan 10 months ago

  • % Done changed from 20 to 70

Patch 2 merged:
face: add a per face counter for Interests kept by the forwarder
https://gerrit.named-data.net/c/NFD/+/5678

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

#29

Updated by Junxiao Shi 10 months ago

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.

#30

Updated by Ju Pan 10 months ago

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?

#31

Updated by Davide Pesavento 10 months ago

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

#32

Updated by Davide Pesavento 10 months ago

Davide Pesavento wrote:

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

Done now.

#33

Updated by Ju Pan 9 months ago

Davide Pesavento wrote:

Davide Pesavento wrote:

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

Done now.

Thanks!

#34

Updated by Davide Pesavento 8 months ago

  • % Done changed from 70 to 80
#35

Updated by Ju Pan 7 months ago

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?
#36

Updated by Ju Pan 7 months ago

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.

Also available in: Atom PDF