Feature #3888
closed
Loop detection: duplicate Nonce from same incoming face is not loop
100%
Description
Currently, incoming Interest pipeline drops an Interest whenever its Nonce duplicates a previously seen Nonce, even if the new Interest comes from the same face as the previous Nonce.
One drawback of this procedure is: when an application retransmits an Interest, it must generate a new Nonce.
We should not treat duplicate Nonce from same incoming face as loop.
Updated by Junxiao Shi almost 8 years ago
- Estimated time changed from 3.00 h to 6.00 h
This idea was proposed by Beichuan.
There is no danger of persistent looping, because:
- Forwarder itself does not make up an Interest. Every Interest comes from a consumer.
- If an Interest loops back to the same forwarder, the looping Interest must come from a different face than the original consumer, and it would be dropped.
An implication of this idea is that a forwarder may have less choices in trying a different path.
/--D--\
C---A B---P
\--E--/
In this topology, suppose the first Interest expressed by an application on C is forwarded via C-A-D-B-P path, but link A-D has failed before the Data is returned.
If C re-expresses the Interest without changing the Nonce, forwarding the Interest via C-A-E-B-P path would not work because B would detect a duplicate Nonce from E, which is a different face than D from which the previous Nonce is seen, and drop the Interest as looping.
If C re-expresses the Interest with a new Nonce, the Interest can be forwarded normal via C-A-E-B-P path.
Updated by Anonymous almost 8 years ago
Another implication is that you now have to remember the incoming face associated with each nonce. However, the current "dead nonce list" does not store this information.
Thus, we already found two cases in which the consumer would have to create a new nonce anyway (you mentioned the other one).
I propose the following fix: Whenever a duplicate nonce comes from the same application face the local forwarder changes the nonce before forwarding the interest. This allows the consumer app to use the same nonce, but avoids the two problems mentioned above.
Updated by Anonymous almost 8 years ago
As discussed in today's NFD call, another option is to not even give the application the option to set a nonce. The forwarder that receives this nonce-less Interest then adds a random nonce.
We wonder if there is any problem with that design?
Updated by Junxiao Shi almost 8 years ago
Correction of note-3:
The idea on 20161213 NFD call is to not require application to set a Nonce; application MAY still set a Nonce.
Any forwarder that receives a Nonce-less Interest adds a random Nonce prior to processing.
This is implemented in CCNx 0.7.2.
Updated by Junxiao Shi over 7 years ago
- Status changed from New to In Progress
This design is approved on 20170223 meeting. I'll start forwarding pipelines changes.
Updated by Junxiao Shi over 7 years ago
- Status changed from In Progress to Code review
- % Done changed from 0 to 100
Updated by Davide Pesavento over 7 years ago
Junxiao Shi wrote:
- If an Interest loops back to the same forwarder, the looping Interest must come from a different face than the original consumer [...]
Isn't this assumption false on multi-access links?
Updated by Junxiao Shi over 7 years ago
Isn't this assumption false on multi-access links?
20170302 meeting confirms this assumption is false on ad hoc links.
If we treat a duplicate Nonce on the same incoming face as retransmission, persistent loop can occur:
/--B--\
G---A C
| |
F D
\--E--/
- G expresses an Interest.
- A relays the Interest through its ad hoc wireless interface. B receives the Interest, but F does not receive the Interest due to interference.
- B, C, D, E, F relay the Interest through their ad hoc wireless interfaces.
- When the Interest gets back to A, A would be receiving a duplicate Nonce on its ad hoc wireless interface.
- If A does not treat this Interest as looping, it would relay the Interest again. B, C, D, E, F also relays this Interest, causing a persistent loop.
The solution is to treat a duplicate Nonce as legitimate retransmission only if it's received from the same face and same remote endpoint. In the above example, when the Interest loops back to A, A would see the remote endpoint is F instead of G, and thus detect it as a loop.
We did not see any problem with regular multi-access links.
Since ad hoc link type is not yet implemented, we do not need to implement "same face and same remote endpoint" as this moment. To prevent problems when we add ad hoc link type, I'll update the current implementation to apply "legit retransmission" rule only to point-to-point links.
Updated by Junxiao Shi over 7 years ago
- Status changed from Code review to In Progress
Code is merged. I'll update NFD devguide.
Updated by Junxiao Shi over 7 years ago
- Status changed from In Progress to Resolved
nfd-docs:commit:bc2a286d0e4ddacd1fae69f3234a5b5cb5394ab9