Feature #3888: Loop detection: duplicate Nonce from same incoming face is not loop - NFD - NDN project issue tracking system

Feature #3888

closed

Loop detection: duplicate Nonce from same incoming face is not loop

Added by Junxiao Shi almost 8 years ago. Updated over 7 years ago.

Status:

Closed

Priority:

Normal

Assignee:

Junxiao Shi

Category:

Forwarding

Target version:

v0.6

Start date:

Due date:

% Done:

100%

Estimated time:

6.00 h

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.

History
Notes
Property changes

Actions

Copy link

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.

Actions

Copy link

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.

Actions

Copy link

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?

Actions

Copy link

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.

Actions

Copy link

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.

Actions

Copy link

Updated by Junxiao Shi over 7 years ago

Status changed from In Progress to Code review
% Done changed from 0 to 100

https://gerrit.named-data.net/3732

Actions

Copy link

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?

Actions

Copy link

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.

Actions

Copy link