[Nfd-dev] On the necessity of the STRAGGLER timer

[Klaus Schneider]

Some comments below.

On 11/17/2016 06:57 AM, Seweryn Dynerowicz wrote:
> Dear Marc,
>
> Thanks for this input, my replies are nested below.
>
> On 17 November 2016 at 11:56, <Marc.Mosko at parc.com
> <mailto:Marc.Mosko at parc.com>> wrote:
>
>     Two comments below
>>     On Nov 17, 2016, at 8:09 PM, Seweryn Dynerowicz
>>     <f80120 at ulusofona.pt <mailto:f80120 at ulusofona.pt>> wrote:
>>
>>     Dear Klaus,
>>
>>     On 16 November 2016 at 21:51, Klaus Schneider
>>     <klaus at cs.arizona.edu <mailto:klaus at cs.arizona.edu>> wrote:
>>
>>         I think Junxiao refers to Section 4.2.8
>>         Interest Finalize Pipeline: "The Dead Nonce List is a global
>>         data structure designed to detect looping Interests, and we
>>         want to insert as
>>         few Nonces as possible to keep its size down."
>>
>>
>>     The way I understand this specific point is that we do not want to
>>     insert the Nonce for every single Interest we ever receive. This
>>     is precisely
>>     what the next sentence states;
>>
>>     "Only outgoing Nonces (in out-records) need to be inserted,
>>     because an incoming Nonce that has never been sent out won't loop
>>     back.”
>
>     This is incorrect, or at best it’s a limited definition of loop.
>     You could have a first Interest with nonce A that would, if nothing
>     else happened, form a cycle and need to be dropped.  however, at
>     another node, that first Interest could be aggregated with a second
>     Interest with nonce B, and it is that second Interest that loops.
>     Then B might get aggregated with the node that sent A in the first
>     place, and neither loop is detected because there was no duplicate
>     nonces, only aggregations that will eventually timeout.  One could
>     ask, did a loop really happen in that case?  I think if you are
>     forming an equivalency class on Interests based on aggregation
>     similarity, then yes a loop did happen.
>
>
> I agree. From the perspective of the implementation, it seems that the
> source of the problem you're pointing out is that the Forwarder
> implements a loop detection scheme which makes assumptions on how the
> Strategy behave (to make it worse it makes assumptions on how other
> nodes Strategy behaves). The first case you describe occurs with a
> Strategy which, for a given Name, forwards EITHER all Interests it
> receives without changing their Nonce OR none. The second case
> (aggregation) occurs with a Strategy which decides to only forward some
> strict subset of the Interests it receives for a given Name. To
> guarantee that the implemented scheme detects all loops, all the nodes
> must be using the first Strategy. If any node uses the second Strategy,
> this introduces the possibility of a non-detectable Interest loop. A
> more strict scheme for Loop detection (i.e. keep track of traversed
> nodes) seems to be necessary.

A more strict loop detection scheme is to keep the PIT in-records around 
after the initial Interest was satisfied, as done by the straggler timer.

The fundamental problem is that routers have limited memory, so you have 
to remove the information about previously seen Interests at some point. 
Any loop that takes longer than the router's ability to remember 
previous Interests/nonces cannot be detected that way.

The "Dead Nonce List" is really only a performance optimization: Only 
store nonces, not the whole PIT entry + only store some nonces which 
seem more likely to loop (the ones in out-records). This saves some 
memory, but doesn't solve the fundamental problem that you would need 
unlimited memory for perfect loop detection.


>
>>             So you only compute the RTT for the first Data packet
>>             which satisfies
>>             the Interest, right ? If you're only interested in RTT,
>>             the OUT-Records
>>             do not enable you
>>             to do anything useful regarding that so they could be removed
>>             straightaway without waiting for STRAGGLER.
>>
>>
>>         I don't know about the specifics, but in principle the
>>         straggler timer should help you to do measurements of more
>>         then the fastest interface. Whenever you send out Interests on
>>         multiple faces (either in parallel or sequential) it can be
>>         useful to wait a little longer for responses (Data or NACKs).
>>
>>
>>     I agree, that would be one reason to have the STRAGGLER timer.
>>
>>     But as the RTT is a measure of how fast the last Interest up a
>>     certain path was satisfied, wouldn't it make more sense to use the
>>     FIB to keep track of the RTT ?
>     I disagree with this last statement too.  There is nothing in a
>     response that identifies which request triggered the response.  If a
>     forwarder has sent two Interests upstream on the same path you don’t
>     know if you are measuring the time from the 1st interest to the
>     response (a long time) or the time from the 2nd interest to the
>     response (a shorter time).  Because you have replaced the out
>     record, I think you will only measure the shorter time, which could
>     be incorrect.
>
>     Personally, I think measuring response time at the granularity of
>     the FIB (which I believe is what these come down to) is not a
>     principled thing to do.  A producer may be serving multiple classes
>     of traffic under one FIB entry, such as very quick static content
>     and very slow dynamically generated content.  In that example, there
>     is really a bi-modal RTT distribution and if you average them you
>     will have an RTT estimate that is wrong for both classes of
>     traffic.  If one were to measure 2nd order statistics, perhaps one
>     could get a 2-sigma or 3-sigma interval, but I’m not sure that’s
>     really useful for anything at a forwarder.
>
>
> I was describing what I understand is the RTT that can be computed under
> the existing implementation. My original concern here is about how to do
> Data measurements without the need to keep the OUT-Records longer in the
> PIT entry. The solution to that should make it easy to implement
> whatever measurements to whichever granularity someone desires. I think
> I have a good solution to this but I need to think it through (short
> answer; put it entirely in the strategy and add a callback to it in the
> beginning of the onIncomingData pipeline).

How is it possible to do an RTT measurement without the out-record?

Let's say you send out two Interests and Face A and Face B. The Data 
returns on Face A and you remove the whole PIT entry.

Now that second Data returns on Face B. How could you know its RTT? You 
just deleted the information about when you sent that Interest.

Of course, you can store this information inside the strategy and then 
implement what you want in onUnsolicitedData(). But what's the benefit 
compared to just using the out-records?

Best regards,
Klaus



>
>
> Best regards,
>
> S.
>
> +----------------------------------------------+
> | Dynerowicz Seweryn                           |
> | PostDoc Researcher                           |
> | SITI, COPELABS, Building U                   |
> | Universidade Lusófona                        |
> | Campo Grande, 388, 1749-024 Lisboa, Portugal |
> +----------------------------------------------+
>
> I hate the empty set; he's so full of himself.
>
> "Judge a man by his questions rather than his answers",
> Pierre-Marc Gaston, Duc de Lévis
>
> "Ignorance more frequently begets confidence than does knowledge.",
> C. Darwin
>
> "Seek freedom and become captive of your desires. Seek discipline
> and find your liberty.", F. Herbert
>