Bug #1966
open
Interest unsatisfied due to Interest aggregation combined with duplicate Nonce suppression
0%
Description
Topology:
B---A---C
\ |
--D---E
Every link has 10ms delay.
Consumers are at node B,E.
Producer is at node C.
Broadcast strategy is used on all nodes.
FIB entries are:
- on node A: nexthops=C
- on node D: nexthops=A
- on node E: nexthops=D
- on node B: nexthops=A,D
Steps to reproduce:
- time=0: Interest with nonceB is expressed on node B, and is forwarded to node A and node D
- time=10: Interest with nonceB arrives node A on B-A link, and is forwarded to node C
- time=10: Interest with nonceB arrives node D on B-D link, and is forwarded to node A
- time=15: similar Interest with nonceE is expressed on node E, and is forwarded to node D
- time=20: Interest with nonceB arrives node A on D-A link, and is dropped because it has a duplicate Nonce
- time=25: Interest with nonceE arrives node D on E-D link, and is aggregated to the existing PIT entry because it's similar
- time=30: Interest with nonceB arrives node C on A-C link, and is answered
- time=40: Data arrives node A, and is returned to node B, but not to node D
- time=50: Data arrives node B, and is not forwarded
- Data never arrives node E
Expected: Interest from node E is satisfied
Actual: Interest from node E is unsatisfied
This problem is caused by the combination effect of Interest aggregation and duplicate Nonce suppression.
Files
Updated by Junxiao Shi over 9 years ago
- Description updated (diff)
This problem hasn't surfaced in operations yet. @Beichuan pointed out this problem through theoretical analysis.
Updated by Junxiao Shi over 9 years ago
- Description updated (diff)
Let's consider whether this problem can be solved by NACK.
When node A sees nonceB from D, this duplicate Nonce is considered loop or multi-path arrival, and these two reasons are distinguishable, because nonceB has been sent to C.
- If node A sends a reasonless NACK to D (send back the Interest), node D doesn't know it's due to duplicate Nonce, so it won't think about resending the Interest to A with nonceE.
- If node A sends a NACK-DUPLICATE to D, node D knows what's happening, so it can resend the Interest with nonceE.
Updated by Junxiao Shi over 9 years ago
@Lan provided two other solutions without using NACK.
http://www.lists.cs.ucla.edu/pipermail/nfd-dev/2014-September/000443.html
multi-consumer flag¶
When D receives nonceE, D can resend the Interest to A. This Interest packet carries a multi-consumer flag.
Upon receiving an Interest with multi-consumer flag, node A should always return Data.
A node should send Interest with multi-consumer flag only once when the second Interest arrives.
If a third Interest arrives, it's unnecessary to send multi-consumer flag again because upstream won't suppress Data.
freshly generated Nonce¶
When D receives nonceE, D can resend the Interest to A. This Interest packet carries a freshly generated nonceD (different from nonceB and nonceE).
Upon receiving an Interest with nonceD, node A would return Data to D.
A node should send Interest with freshly generated Nonce only once when the second Interest arrives.
If a third Interest arrives, it's unnecessary to send Interest again because upstream won't suppress Data.
Updated by Junxiao Shi about 9 years ago
Van gave the following idea on 20150319 meeting:
- When a router wants to probe, it should send to all nexthops at same time. In case paths converge at some point, Interest arriving on shortest path wins.
- If a router needs to retry after some time, it should wait for PIT entry timeout (#2551) on all upstreams before sending the same Nonce.
- If a router needs to retry immediately, it should generate a new Nonce.
Beichuan says in 20150320 conference call that "wait for PIT entry timeout" is difficult, because a router never knows where the converge point may be, and thus cannot know the what duration it should wait for.
Updated by Junxiao Shi about 9 years ago
- Subject changed from Interest unsatisfied due to similar Interest suppression combined with loop detection to Interest unsatisfied due to Interest aggregation combined with duplicate Nonce suppression
- Description updated (diff)
Updated by
Updated by Junxiao Shi over 7 years ago
- File Nack-duplicate_20161027.docx Nack-duplicate_20161027.docx added
- Target version changed from v0.5 to v0.6
Updated by
Updated by Junxiao Shi almost 4 years ago
- Related to Feature #5046: Multicast strategy should send an Interest on Duplicate NACK w/ a different Nonce added
Updated by Junxiao Shi over 3 years ago
20210108 NFD call discussed this problem regarding the use of Nack~Duplicate.
Recommended Procedure from 20161027¶
In the procedure given in Nack-duplicate_20161027.docx (#1966-7) Recommendation of Nack-Duplicate processing section (implemented in NDN-DPDK as of end of 2020), this problem is solved as follows:
- time=0: Interest with nonceB is expressed on node B, and is forwarded to node A and node D
- time=10: Interest with nonceB arrives node A on B-A link, and is forwarded to node C
- time=10: Interest with nonceB arrives node D on B-D link, and is forwarded to node A
- time=15: similar Interest with nonceE is expressed on node E, and is forwarded to node D
- time=20: Interest with nonceB arrives node C on A-C link, and is answered
- time=20: Interest with nonceB arrives node A on D-A link, and is dropped because it has a duplicate Nonce; A returns a Nack~Duplicate to D
- time=25: Interest with nonceE arrives node D on E-D link, and is aggregated to the existing PIT entry because it's similar
- time=30: Data arrives node A, and is returned to node B, but not to node D
- time=30: Nack~Duplicate with nonceB arrives node D on A-D link; D sends Interest with nonceE to node A
- time=40: Data arrives node B on A-B link, and is not forwarded
- time=40: Interest with nonceE arrives node A on D-A link, and is answered with cached Data
- time=50: Data arrives node D on A-D link, and is returned to node E
- time=60: Data arrives node E on D-E link, and is not forwarded
NFD 0.7.1 Behavior¶
There have been recurring complaints against Nack~Duplicate in NFD, especially in the context of multicast strategy and data synchronization protocols.
The main reason is that, NFD is not implementing the 20161027 recommendation.
Instead, in step 6 node A returns the Nack~Duplicate to D, but in step 9 node D does not resend the Interest with nonceE to node A.
It's worth noting that merely deleting the Nack packet would not solve the original problem, as mentioned in the issue description.
Return Data to Every Downstream¶
This is one of the alternatives considered at 20210108 NFD call.
It would behave as follows:
- time=0: Interest with nonceB is expressed on node B, and is forwarded to node A and node D
- time=10: Interest with nonceB arrives node A on B-A link, and is forwarded to node C
- time=10: Interest with nonceB arrives node D on B-D link, and is forwarded to node A
- time=15: similar Interest with nonceE is expressed on node E, and is forwarded to node D
- time=20: Interest with nonceB arrives node C on A-C link, and is answered
- time=20: Interest with nonceB arrives node A on D-A link, and is aggregated to the existing PIT entry because it's similar
- time=25: Interest with nonceE arrives node D on E-D link, and is aggregated to the existing PIT entry because it's similar
- time=30: Data arrives node A, and is returned to node B and node D
- time=40: Data arrives node B on A-B link, and is not forwarded
- time=40: Data arrives node D on A-D link, and is returned to node E
- time=50: Data arrives node E on D-E link, and is not forwarded
In this approach, the Nonce field is unnecessary and can be eliminated.
The above steps still contain the Nonce field for identifying the packet, but it does not participate in the algorithm.
No Interest Aggregation¶
This is one of the alternatives considered at 20210108 NFD call.
It would behave as follows:
- time=0: Interest with nonceB is expressed on node B, and is forwarded to node A and node D
- time=10: Interest with nonceB (from step 1) arrives node A on B-A link, and is forwarded to node C
- time=10: Interest with nonceB (from step 1) arrives node D on B-D link, and is forwarded to node A
- time=15: similar Interest with nonceE is expressed on node E, and is forwarded to node D
- time=20: Interest with nonceB (from step 2) arrives node C on A-C link, and is answered
- time=20: Interest with nonceB (from step 3) arrives node A on D-A link, and is forwarded again to node C
- time=25: Interest with nonceE (from step 4) arrives node D on E-D link, and is forwarded again to node A
- time=30: Data (from step 5) arrives node A, and is returned to node B and node D
- time=30: Interest with nonceB (from step 6) arrives node C on A-C link, and is answered
- time=35: Interest with nonceE (from step 7) arrives node A on D-A link, and is answered with cached Data
- time=40: Data (from step 8) arrives node B on A-B link, and is not forwarded
- time=40: Data (from step 8) arrives node D on A-D link, and is returned to node E 13: time=40: Data (from step 9) arrives node A on C-A link, and is dropped because there's no PIT entry
- time=45: Data (from step 10) arrives node D on A-D link, and is dropped because there's no PIT entry
- time=50: Data (from step 12) arrives node E on D-E link, and is not forwarded