[Ndn-interest] Loop Detection Issue

Wed Aug 3 09:03:27 PDT 2016

On 08/03/16 17:16, Marc.Mosko at parc.com wrote:
> My understanding is that X should send a “duplicate NACK” to Z.  As 
> long as the NACK is not lost, C2 will get the NACK and re-try its 
> Interest with a difference nonce (if using BestRoute v2 strategy).  If 
> the NACK is lost, then you still have the described problematic 
> behavior.  Note that the BestRoute v2 strategy will not re-transmit the 
> C2 Interest at Z with a different nonce, it will propagate the NACK to 
> C2.

Right, the point is missed is that the interest of C2 (green) dangles at 
Z *but* the "duplicate NACK" caused by C1s looping interest (red) still 
reaches C2.  Then the obvious solutions is - as you say - that C2 
(instead of Z, as I first thought)  re-tries with a new nonce. This new 
interest will not dangle at Z since Z meanwhile cleaned its PIT due to 
the NACK.

"By-insight": Receiving a "duplicate NACK" does not necessarily mean 
that the own interest looped but also refer to an interest which carries 
the same name as the own interest but is generated by someone else.

> 
> I also think that the duplicate NACK would be propagated along the 
> whole reverse route to Y and then back to X, if using BestRoute v2.
> 
> Another thing to consider is that NFD uses an aggregation hold-down 
> timer.  The Interest from C2 would only be aggregated at Z if it 
> arrived within 250 msec of the Interest from Y.  If it arrived after 
> that, it would not be aggregated. This is strategy dependent.  I think 
> there’s also current work on using an exponential back off rather than 
> a fixed 250 msec.
> 
> Yet another another thing to consider is that there are two ways X can 
> detect a duplicate nonce.  First is what we’ve talked about, it has a 
> pending PIT entry.  The second case is if the duplicate Interest from Z 
> arrives after the content from S has cleared the PIT entry at X, but 
> there is still a “dead nonce list” entry at X.  If you read section 
> 4.2.1 (Incoming Interest Pipeline) of version 6 (I believe current) NFD 
> guide, step 2 is to check the Dead Nonce List.  In this case, even 
> though X may have a content store entry, the Interest from Z is given 
> to the “Interest loop pipeline”.  It explicitly does not create an 
> in-record for the Interest from Z.  Section 4.2.2 (Interest loop 
> pipeline) will generate a NACK and drop the Interest.  At this point Z 
> would forward the NACK to C2 (via BestRoute) and C2 would re-try.
> 
> Finally, one should also note that a duplicate NACK is only generated 
> on a point-to-point face.  If the incoming face is multiple access, no 
> NACK is generated.  C2 would need to timeout in that case.

Thank you for all the additional information.

> 
> Marc

Claudio

> 
> 
>> On Aug 3, 2016, at 6:43 AM, marxer at claudio.li wrote:
>> 
>> 
>> On 08/03/16 14:28, Lan Wang (lanwang) wrote:
>>> They have different nonces but if the PIT entry created by C1 has not 
>>> been removed, then C2 may be suppressed.   This is the dangling PIT 
>>> entries problem.The solutions (already implemented in NFD) are the 
>>> following:
>> 
>> Yes, this is what we meant in the example.
>> 
>>> 1. some strategies, e.g., recent versions of BestRoute) allow 
>>> interest retransmission: when an interest is forwarded, a suppression 
>>> timer is set on the PIT.  When the timer expires, it  may forward any 
>>> new Interest matching the PIT (and then set the suppression timer 
>>> again).
>>> 2. when X detects an Interest with a duplicate nonce, it sends a 
>>> duplicate NACK  which may be further forwarded to clear the dangling 
>>> PIT entries at the nodes that sent the interest.  When the PIT entry 
>>> is cleared, new interest with the same name can be forwarded.  Right 
>>> now some strategies (not all) in NFD handle the NACKs correctly.
>> 
>> Yes, this works. A question regarding the implementation: According to 
>> the NFD developer guide, the PIT does not hold nonce values. Thus Z 
>> can not fully reconstruct the interest from C2. Does Z generate a new 
>> nonce? If yes: Not sure but intuitively I think that loop partially 
>> detection might be broken if the green interest was also part of a 
>> loop (because Z changes its nonce).
>> 
>>> Lan
>> 
>> Thanks to all of you for the explanations,
>> Claudio
>> 
>>>> On Aug 3, 2016, at 4:54 AM, Lixia Zhang <lixia at cs.ucla.edu> wrote:
>>>> I have a few other questions to the specifics of the scenario.
>>>> for a short answer quick: interests form C1 and C2 carry different 
>>>> nonces, so your concern on the last slide should not happen as I 
>>>> see.
>>>>> On Aug 3, 2016, at 1:15 AM, marxer at claudio.li wrote:
>>>>> Hi all,
>>>>> Urs and I constructed a situation in which we think the network 
>>>>> does not behave as expected (attached PDF). Can this happen in the 
>>>>> wild or did we oversee something?
>>>>> Thanks,
>>>>> Urs and Claudio
>>>>> <interest-looping.pdf>_______________________________________________
>>>>> Ndn-interest mailing list
>>>>> Ndn-interest at lists.cs.ucla.edu
>>>>> http://www.lists.cs.ucla.edu/mailman/listinfo/ndn-interest
>>>> _______________________________________________
>>>> Ndn-interest mailing list
>>>> Ndn-interest at lists.cs.ucla.edu
>>>> http://www.lists.cs.ucla.edu/mailman/listinfo/ndn-interest
>> _______________________________________________
>> Ndn-interest mailing list
>> Ndn-interest at lists.cs.ucla.edu
>> http://www.lists.cs.ucla.edu/mailman/listinfo/ndn-interest
> 