[Ndn-interest] Loop Detection Issue

Wed Aug 3 09:33:26 PDT 2016

> On Aug 3, 2016, at 9:03 AM, marxer at claudio.li wrote:
> 
> 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.

The nonce in the NACk from Z to C2 is C2’s nonce.  It must be the nonce C2 sent to Z because NFD section 4.4.1 says “and the last outgoing Nonce was the same as the Nonce carried in the NACK.”  So, if Z were to return the C1 nonce, C2 would ignore that NACK.  Section 4.4.2 says one must use the in-record (and nonce) in the NACK’s generation.

So, C2 cannot determine whose Interest looped.  Receiving the “duplicate NACK” only means _some_ loop happened that prevented C2’s interest from being satisfied. I couldn’t find anything in NFD about what the NACk type is on these relayed duplicate NACKs.  I assume they are all the same type.

> 
>> 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