NFD

Junxiao Shi wrote:

It is dependent upon a NDN protocol change that allows a Data to satisfy only one Interests.

One option for such protocol change is #3333. However, I'm not yet claiming #3333 as a blocking issue. A different protocol change that fulfills "one Data satisfies one Interest" condition is also acceptable.

How about the following design? (copied from the email I sent you)

When a Data packet arrives:

1. Create a duplicate for each Interest it satisfies.
2. Then let each strategy handle its copy of the data packet as it wants.

Reply to note-5:

In C-D-E topology, suppose E receives a Data /A/B from local app that satisfies pending Interest /A and /A/B. E would duplicate the Data as two copies to be processed by the effective strategy for each PIT entry. Normally, the strategy would send the Data to D. D would receive two copies of the Data.
When D receives the first copy of the Data, following the same rules, it would duplicate the Data again for each pending Interest and send two copies to C. When the second copy arrives at D, D would drop it as unsolicited. As a result, D could not make use of any congestion mark or lack thereof attached to the second Data copy from E.

The essence of #3333 is to explicit associate a Data copy with a pending Interest through a packet header named "Interest digest". Merely duplicating the Data for each PIT entry would not help.

Okay, that makes sense.

I think we can go ahead and implement this feature for Data that satisfies only one Interest, as you described in note-1.

In NFD, each pending Interest could be handled by a separate forwarding strategy.

How common is this scenario?

Davide Pesavento wrote:

In NFD, each pending Interest could be handled by a separate forwarding strategy.

How common is this scenario?

Probably about as rare as a Data packet satisfying more than one pending Interest.

I'm fine with just ignoring that case, and implementing the new pipelines for the case of one Interest-one Data. Should work fine in >99% of all cases.

But the problem here is really caused by having multiple strategies with "authority" over the same Data packet, not by the fact that one Data packet can satisfy multiple Interests. So why don't we ignore the case of multiple strategies, instead of that of satisfying multiple Interests?

That should also work and includes a couple more cases.

So the logic would be:

if (satisfiesMultipleInterests && usesSeparateStrategies) {
  // old design: strategy can't manipulate Data
}
else {
  // new design: strategy *can* manipulate Data
}

But the problem here is really caused by having multiple strategies with "authority" over the same Data packet, not by the fact that one Data packet can satisfy multiple Interests.

Correct.

So why don't we ignore the case of multiple strategies, instead of that of satisfying multiple Interests?

Incoming Data pipeline triggers strategy for each PIT entry. It would be more complicated to compare whether all PIT entries use the same strategy.

this issue is already implementable for an incoming Data that happen to satisfy only one Interest

I'm currently running some ndnSIM experiments, and found that only supporting this case (Data satisfying one Interest) is not good enough.

Example use case: I tried to send two simultaneous probing packets (same name, different nonce) which can get aggregated in one PIT entry. At the aggregating router, the returning Data should be updated differently for both outgoing data packets, based on the congestion level of each link's outgoing queue.

This requires that the strategy is given authority at least in the case when Data only satisfies one PIT entry (rather than just one Interest).

Junxiao Shi wrote:

So why don't we ignore the case of multiple strategies, instead of that of satisfying multiple Interests?

Incoming Data pipeline triggers strategy for each PIT entry. It would be more complicated to compare whether all PIT entries use the same strategy.

So how about we ignore the case of Data satisfying multiple PIT entries?

this issue is already implementable for an incoming Data that happen to satisfy only one Interest

This requires that the strategy is given authority at least in the case when Data only satisfies one PIT entry (rather than just one Interest).

Yes, "one Interest" meant "one PIT entry", regardless of how many downstreams it has.

So how about we ignore the case of Data satisfying multiple PIT entries?

Yes. Once incoming Data pipeline finds multiple PIT matches, the strategy cannot control Data forwarding, but can observe Data arrival as the case today.

Okay, that design sounds good to me.

Junxiao Shi wrote:

Yes. Once incoming Data pipeline finds multiple PIT matches, the strategy cannot control Data forwarding, but can observe Data arrival as the case today.

How does the current code prevent fw manipulating Data?

How does the current code prevent fw manipulating Data?

“Prevent” is the wrong word. Current API never allowed strategy to manipulate Data. Any attempt to manipulate Data results in undefined behavior (i.e. not guaranteed/tested to work).

According to the discussions, people seem to aggree with adding an API to manipulate Data when only one pit entry is matched. How about the following logic:

for (pitEntry : pitMatches) {

  if (pitMatches.size() == 1) {
     dispatchToStrategy(strategy.canManipulateDataBeforeSatisfyInterest);
  }

  dispatchToStrategy(strategy.beforeSatisfyInterest);
}

But within the method Forwarder::onIncomingData(Face& inFace, const Data& data), data cannot be manipulated (such as adding a prefix announcement tag). How to support it with minimum changes to exiting code?

if (pitMatches.size() == 1) {
dispatchToStrategy(strategy.canManipulateDataBeforeSatisfyInterest);
}

This is insufficient. The strategy should be given full control over the Data, including dropping or delaying the Data. Thus, forwarding should pass the Data to the strategy via a trigger and stop further processing. The strategy can modify/delay Data as it wants, and then invoke actions (methods on Strategy base class) to send the Data out.

Junxiao Shi wrote:

This is insufficient. The strategy should be given full control over the Data, including dropping or delaying the Data. Thus, forwarding should pass the Data to the strategy via a trigger and stop further processing. The strategy can modify/delay Data as it wants, and then invoke actions (methods on Strategy base class) to send the Data out.

For self-learning, it only needs to attach a prefix announcement tag to Data. What well happen if self-learning does it in the beforeSatisfyInterest method.

Stop saying "for self-learning". This is a generic feature asked by many on nfd-dev and ndnSIM community. The API needs to be general.

Junxiao Shi wrote:

Stop saying "for self-learning". This is a generic feature asked by many on nfd-dev and ndnSIM community. The API needs to be general.

What will happen if forwarding strategy attaches a tag to Data in the beforeSatisfyInterest method?

What will happen if forwarding strategy attaches a tag to Data in the beforeSatisfyInterest method?

It triggers undefined behavior. beforeSatisfyInterest API does not allow modifying Data in any way, including changing tags.

How do people like strategy-data-trigger_20170209.pptx?

I like it. It supports more features and is less confusing.

I am not convinced to implement the feature of "extend PIT entry lifetime".

The design eliminates the global "straggler timer" that is a major source of confusion in strategy API. Strategies that need this feature would have to invoke "extend PIT entry lifetime" action to retain the PIT entry.
NCC and best-route do not depend on this. I'm unsure about ASF. Self learning needs it to learn non fastest paths as backups.

A compatability question is how to seamlessly change the APIs in all forwarding strategy

1. Add new APIs. Mark old APIs as deprecated.
2. Report a bug for each strategy that invokes old API. Assign them to author of the strategy.
3. Reject all new or updated strategies that invokes API in code reviews.
4. Delete old APIs and also the straggler timer when step2 bugs are closed.

to submit the changes in all strategy along with this feature?

Don't try this. It'll produce a unusually large commit and you'll have trouble to find people to review it.

How about making two separate submits, the first one to simplify the APIs about the PIT entry lifetime, and the second one to change the APIs related Data pipelines?

Junxiao, in your slides:

Unsatisfy timer expiration invokes "before remove pending Interest" trigger.
* The intention was for strategy to clean up states, but all existing strategies use ScopedEventId or similar for cleanups and do not use this trigger.

Do you suggest that remove this trigger? Since the unsatify and stragger timers point to different triggers, merging them may end with an API that has complicated parameters. If the trigger for unsatify timer is removed, it needs a different design.

How about making two separate submits, the first one to simplify the APIs about the PIT entry lifetime, and the second one to change the APIs related Data pipelines?

If you need to ask about commit arrangement, be very specific about what each commit contains.

Since the unsatify and stragger timers point to different triggers, merging them may end with an API that has complicated parameters. If the trigger for unsatify timer is removed, it needs a different design.

Both unsatisfy timer (last in-record expiration time) and straggler timer (100ms after last out-record is rejected or strategy rejects Interest) are gone.
The new expiration timer differs from both old timers. See page11-13 of strategy-data-trigger_20170209.pptx for its exact semantics.

Junxiao Shi wrote:

How about making two separate submits, the first one to simplify the APIs about the PIT entry lifetime, and the second one to change the APIs related Data pipelines?

If you need to ask about commit arrangement, be very specific about what each commit contains.

Since the unsatify and stragger timers point to different triggers, merging them may end with an API that has complicated parameters. If the trigger for unsatify timer is removed, it needs a different design.

Both unsatisfy timer (last in-record expiration time) and straggler timer (100ms after last out-record is rejected or strategy rejects Interest) are gone.
The new expiration timer differs from both old timers. See page11-13 of strategy-data-trigger_20170209.pptx for its exact semantics.

I agree with most of your design, but I have a different implementation plan that includes two commits:

1. changes that do not break any strategies, including simplifying PIT entry timers (but not to change the semantics of straggler timer), and removing unused trigger (reject interest trigger is used by 6 strategies, so not included).

2. the rest changes mentioned in strategy-data-trigger_20170209.pptx, including add triggers to handle Data pipelines, removing Interest rejection trigger, and changing timer settings, need a broader discussion before being implemented, because this commit breaks existing strategies.

Teng Liang wrote:

the rest changes mentioned in strategy-data-trigger_20170209.pptx, including add triggers to handle Data pipelines, removing Interest rejection trigger, and changing timer settings, need a broader discussion before being implemented, because this commit breaks existing strategies.

You cannot break existing strategies.

Davide Pesavento wrote:

Teng Liang wrote:

the rest changes mentioned in strategy-data-trigger_20170209.pptx, including add triggers to handle Data pipelines, removing Interest rejection trigger, and changing timer settings, need a broader discussion before being implemented, because this commit breaks existing strategies.

You cannot break existing strategies.

That's what I wanted to avoid. These changes need to be discussed first. Even after we agree to implement them, we have make sure they are backward compatible.

Teng Liang wrote:

Even after we agree to implement them, we have make sure they are backward compatible.

They don't need to be backward compatible. You can change things in a backward incompatible manner, as long as you update all existing strategies so that they still work after your changes.

Teng Liang wrote:

The uncertain part to me is that whether the new timer would break any forwarding strategy.

I tried the new expiration timer settings for PIT entry in different pipeline stages (https://gerrit.named-data.net/#/c/4556/5..6/daemon/fw/forwarder.cpp), and it passed all daemon test cases. I assume it works.

https://gerrit.named-data.net/4556 patchset8 is trying to do two things together:

1. Eliminate "before expire pending Interest" strategy trigger.
2. Merge "unsatisfy timer" and "straggler timer" into one field without changing its semantics.

The first change makes sense, because "before expire pending Interest" strategy trigger is too limited and it has not been used.
The second change, however, does not show clear benefit, but increases confusion and uncertainty on correctness.
I suggest reverting the second change and only keeping the first change.

Also, to modify anything in forwarding pipelines, please provide an update to forwarding-pipelines_*.pptx file. You can find this file in https://gitlab.com/named-data/TR-NDN-0021-NFD-dev-guide repository under slides directory. You may upload updated version of this file, renamed as the current date, to this Redmine issue. After uploading a version, never delete it, but upload additional versions with new filenames (you may append a letter after the date in case there are multiple versions on the same day). Once the changes are agreed upon, you can commit the last file into the repository replacing the old one, and modify the text and figures in devguide itself.

Junxiao Shi wrote:

https://gerrit.named-data.net/4556 patchset8 is trying to do two things together:

1. Eliminate "before expire pending Interest" strategy trigger.
2. Merge "unsatisfy timer" and "straggler timer" into one field without changing its semantics.

The first change makes sense, because "before expire pending Interest" strategy trigger is too limited and it has not been used.
The second change, however, does not show clear benefit, but increases confusion and uncertainty on correctness.
I suggest reverting the second change and only keeping the first change.

I agree to change the semantics for the new timer (not keeping the old timer semantics), and I think the first change is part of the second change. So these changes can go together, but I also agree to separate them, if people think it is necessary.

Also, to modify anything in forwarding pipelines, please provide an update to forwarding-pipelines_*.pptx file. You can find this file in https://gitlab.com/named-data/TR-NDN-0021-NFD-dev-guide repository under slides directory. You may upload updated version of this file, renamed as the current date, to this Redmine issue. After uploading a version, never delete it, but upload additional versions with new filenames (you may append a letter after the date in case there are multiple versions on the same day). Once the changes are agreed upon, you can commit the last file into the repository replacing the old one, and modify the text and figures in devguide itself.

Thanks. Do you mean that to keep a local repo until the final commit?

Thanks. Do you mean that to keep a local repo until the final commit?

No, you don't need a local repository. You just need to update the slides, which is a single file. Updated slides should be uploaded to Redmine only, and uploaded versions should never be deleted.

Junxiao Shi wrote:

https://gerrit.named-data.net/4556 patchset8 is trying to do two things together:

1. Eliminate "before expire pending Interest" strategy trigger.
2. Merge "unsatisfy timer" and "straggler timer" into one field without changing its semantics.

The first change makes sense, because "before expire pending Interest" strategy trigger is too limited and it has not been used.
The second change, however, does not show clear benefit, but increases confusion and uncertainty on correctness.
I suggest reverting the second change and only keeping the first change.

Actually pathset8 uses the new timer semantics described in strategy-data-trigger_20170209.pptx. With the new timer semantics, do you agree that these two changes go into one commit?

With the new timer semantics, do you agree that these two changes go into one commit?

They need to be separate as these are independent changes.

Actually pathset8 uses the new timer semantics described in strategy-data-trigger_20170209.pptx.

As I already said, “extend PIT entry lifetime” strategy action is necessary. A strategy action must appear as a protected method on Strategy base class, because a strategy does not have access to Forwarder instance.

Teng Liang wrote:

do you agree that these two changes go into one commit?

No, don't ever do that, unless the changes are really trivial and self-contained.

Junxiao Shi wrote:

With the new timer semantics, do you agree that these two changes go into one commit?

They need to be separate as these are independent changes.

Well, unsatisfy timer points to onInterestUnsatisfied, so they are somewhat dependent. However, I agree to make two commits.

forwarding-pipelines_20180226.pptx has the following errors or inconsistencies with the design given in strategy-data-trigger_20170209. Note that not all errors are caused by this updated, but it is required to fix all errors before proceeding.

• ContentStore hit pipeline did not specify the duration of PIT expiry timer. The duration should be zero. Unless the strategy extends PIT entry lifetime, the PIT entry would be finalized as soon as the strategy trigger returns.
• In ContentStore hit pipeline "dispatch matched Data in CS to strategy" step, it is incorrect to specify "which strategy should process this Data". Effective strategy solely depends on Interest. It is the Interest that determines which strategy would be triggered.
• ContentStore miss pipeline did not specify the duration of PIT expiry timer. The PIT expiry timer should expire when the last PIT in-record expires. Unless the strategy extends or shortens PIT entry lifetime, the PIT entry would be finalized when the last PIT in-record expires, i.e. when no downstream is still expecting a response.
• There shouldn't be an Interest reject pipeline. To reject an Interest, the strategy should invoke change PIT entry lifetime strategy action and set the PIT entry lifetime to be zero. Consequently, the PIT entry would be finalized as soon as the strategy trigger returns. Note that although Interest reject pipeline and reject pending Interest strategy action no longer exist, you may still retain Strategy::rejectPendingInterest as a helper function that invokes change PIT entry lifetime strategy action.
• incoming Data pipeline did not specify the duration of PIT expiry timer. The duration should be zero. Unless the strategy extends PIT entry lifetime, the PIT entry would be finalized as soon as the after receive Data strategy trigger returns.
• A send Data strategy action is needed for use in after receive Data. Its parameters are similar to send Nack strategy action. A helper function Strategy::sendAllData may be provided similar to Strategy::sendNacks.
• In several pages, strategy trigger is being inconsistently referred to as "After CS hit", "invoke incoming Interest callback", etc. They should use the form "trigger strategy: after CS hit", "trigger strategy: incoming Interest", etc, and color-coded in "strategy" category (hint: use PowerPoint "quick style" for color coding; don't edit colors directly).
• incoming Interest pipeline and outgoing Nack pipeline determine whether to send Nack with "is multi-access face" condition, but incoming Nack pipeline determine whether to accept Nack with "is point-to-point face" condition. They should use the same condition.

As a reminder, when you update forwarding-pipelines_*.pptx, never delete an older version. This is to ensure comments like this can be interpreted against a certain version. If you mistakenly delete an older version, you'll be asked to re-upload it before any further review would be given.

Junxiao Shi wrote:

• A send Data strategy action is needed for use in after receive Data. Its parameters are similar to send Nack strategy action. A helper function Strategy::sendAllData may be provided similar to Strategy::sendNacks.

The meaning of sendAllData is unclear/misleading. sendDataToAll would be much more intuitive. You may consider renaming the existing sendNacks to sendNackToAll for consistency.

Eliminate "before expire pending Interest" strategy trigger.

The first change makes sense, because "before expire pending Interest" strategy trigger is too limited and it has not been used.

A bit late since this has already been merged, but:

• How do you know this features hasn't been used be researchers? There's a lot more strategies used in published research than the ones shipping with NFD.

• Why is it "too limited"? How do you plan to avoid these limitations?

Eliminate "before expire pending Interest" strategy trigger.

"before expire pending Interest" strategy trigger is too limited and it has not been used.

• How do you know this features hasn't been used be researchers? There's a lot more strategies used in published research than the ones shipping with NFD.

NFD never guarantees backwards compatibility. Third parties either stay with old version, or switch to new API.

• Why is it "too limited"? How do you plan to avoid these limitations?

Strategy does not usually care about when the PIT entry disappears, but sometimes needs a timed trigger earlier than that (e.g. RTO).
For the former, strategy can know when PIT entry disappears by adding a StrategyInfo on the PIT entry and waiting for its destructor invocation. “before expire pending Interest” trigger was designed for cleaning up StrategyInfo but it’s obviously better to use the destructor.
For the latter, strategy can use the scheduler.

• ContentStore miss pipeline did not specify the duration of PIT expiry timer. The PIT expiry timer should expire when the last PIT in-record expires. Unless the strategy extends or shortens PIT entry lifetime, the PIT entry would be finalized when the last PIT in-record expires, i.e. when no downstream is still expecting a response.

The last PIT in-record is the record for the incoming Interest. Why not directly use the Interest lifetime + now as the expiry timer?

The last PIT in-record to expire is not necessarily the last incoming Interest. Consider the following:

1. At time 0, an Interest arrives from downstream 1001 with lifetime 4000. Downstream 1001’s in-record is to expire at time 4000. PIT entry’s expiry timer shall expire at time 4000.
2. At time 1000, an Interest arrives from downstream 1002 with lifetime 1500. Downstream 1002’s in-record is to expire at time 2500. PIT entry’s expiry timer shall expire at time 4000, not 2500.
3. At time 2000, an Interest arrives from downstream 1001 with lifetime 200. Downstream 1001’s in-record is to expire at time 2200, shortened from the previous 4000. PIT entry’s expiry timer shall expire at time 2500.

Teng: If you have completed forwarding updates, please remember to write NFD devguide. I will not approve any strategy code changes until NFD devguide updates are uploaded.

forwarding-pipelines_20180403.pptx does not render correctly.

• Ensure all text (except "Y" "N" on the arrow) are embedded in a shape instead of in a separate textbox. To embed text in a shape, select the shape then type over it. If text exceeds shape boundary, you may uncheck "Format Shape - Shape Options - Text Box - Wrap text in shape" option, and insert line breaks manually.
• Ensure both ends of each arrow is anchored to a shape.
• Width and height of most shapes should be multiple of 0.3in.

Junxiao Shi wrote:

forwarding-pipelines_20180403.pptx does not render correctly.

Which software and platform are you using? It works perfect on Mac using Microsoft PowerPoint and Ubuntu using LibreOffice Impress.

• Ensure all text (except "Y" "N" on the arrow) are embedded in a shape instead of in a separate textbox. To embed text in a shape, select the shape then type over it. If text exceeds shape boundary, you may uncheck "Format Shape - Shape Options - Text Box - Wrap text in shape" option, and insert line breaks manually.

You cannot type over a line on Mac's PowerPoint, and I see no problem of using a textbox and group it with the line.

• Ensure both ends of each arrow is anchored to a shape.

Although it does not really affect understanding, I changed the the arrow type in the latest update.

• Width and height of most shapes should be multiple of 0.3in.

Obviously, this will bad and not fit in a page. The current shape looks better to me.

My office uses Microsoft Office 365 in Windows 10. You can find the same in University Libraries.
Please fix all problems, or I won't review.

To solve the render problem on different platforms, we should use .pdf in future.

It's insufficient. How can you guarantee the next editor would be able to have a correctly rendered PPTX before she updates the pipeline design?

You cannot type over a line on Mac's PowerPoint, and I see no problem of using a textbox and group it with the line.

The pipelines document shall be updated on Windows only.

• Ensure both ends of each arrow is anchored to a shape.

Although it does not really affect understanding, I changed the the arrow type in the latest update.

It ensures the arrows stay in place when moving other elements.

• Width and height of most shapes should be multiple of 0.3in.

Obviously, this will bad and not fit in a page. The current shape looks better to me.

This requirement forces you to rethink the organization of each diagram and ensures it is understandable. If a diagram becomes too large, split it into multiple diagrams.

Junxiao Shi wrote:

You cannot type over a line on Mac's PowerPoint, and I see no problem of using a textbox and group it with the line.

The pipelines document shall be updated on Windows only.

Junxiao, you cannot force people to use Windows for a task since it's not free.

you cannot force people to use Windows for a task since it's not free.

See note-64 first line second sentence.

Apply the same logic: you cannot force people to support Odroid and macOS because I cannot afford these.

Junxiao Shi wrote:

you cannot force people to use Windows for a task since it's not free.

See note-64 first line second sentence.

Apply the same logic: you cannot force people to support Odroid and macOS because I cannot afford these.

It is not the same logic. The NDN project provides hardware to run CI on those platforms, you don't have to own those machines yourself.

Also, this is completely off-topic.

Junxiao Shi wrote:

• Width and height of most shapes should be multiple of 0.3in.

Obviously, this will bad and not fit in a page. The current shape looks better to me.

This requirement forces you to rethink the organization of each diagram and ensures it is understandable. If a diagram becomes too large, split it into multiple diagrams.

I re-organized it as Teng's slide.png. Can you understand the content?

One change is that I made some shapes smaller and put the text under the shapes, in order to make it clearer. Is it clearer than your previous slides? Why are we wasting time on how to make slides style satisfied upon your standards?

The NFD developer guide is updated accordingly (see commit 99302934a57448be268def81abf4b8619462d1f3). Please take a look. Thanks.

Davide Pesavento wrote:

Is this issue complete apart from documentation?

Yes, I think so. It is better if Junxiao confirms it.