[Ndn-interest] Loop Detection Issue

[marxer at claudio.li]

On 08/04/16 16:25, Lan Wang (lanwang) wrote:
> Marc,
> 
>> On Aug 3, 2016, at 10:16 AM, 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.
> 
> The NACK will not be propagated from Z to C2 because the NACKed nonce 
> is difference from the nonce in C2’s interest.

Since the interests from C1 and C2 are aggregated by Z, both clients are 
affected. Wouldn't it make sense that Z separates the NACK and also 
informs C2? For example by exchanging the nonce in the NACK or with 
something like a "dangling-entry-NACK" generated by Z. At the point C2 
receives such a "dangling-entry-NACK", the PIT entries of the looping 
interest are removed because of the "duplicate NACK". Thus C2 could 
succesfully re-try.

>> 
>> 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.
> 
> This is correct.
>> 
>> 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 sec.
> 
> Yes.
>> 
>> 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.
> 
> Yes.
> 
>>  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.
>> 
> I don’t think the NACK will be forwarded to C2.
> 
>> 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.
> 
> Right now NACK is only generated on a point-to-point face in NFD, 
> because we don’t have a final NACK design for multi-access links yet.  
> But NACK is still applicable to multi-access links in general.
> 
> Lan
>> 
>> Marc
>> 
>> 
>>> 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
>> 
>