[Nfd-dev] [ndnSIM] Interest Satisfaction Rate (ISR) Calculation

[David R. Oran]

May not be worth continuing this now, as some of the design issues are 
delicate, but here goes anyway. See below.

On 3 Apr 2018, at 11:43, Junxiao Shi wrote:

> Hi Dave
>
> Thanks for your quick response. It is very valuable.
> I agree that not incrementing either counter makes sense.
>
>>> I have a related question: what does "Interest satisfaction rate" 
>>> for
>>> a
>>> nexthop means on a forwarder?
>>>
>>> Consider the scenario where a forwarder G has one downstream node C,
>>> and
>>> two upstream nodes (aka nexthops) P and Q:
>>>
>>>      /---P
>>> C---G
>>>      \---Q
>>>
>>> G is using multicast strategy.
>>> When it receives an Interest from C and forwards it to both P and Q, 
>>> P
>>> responds immediately and the Data goes back to C.
>>> As in a recent NFD commit
>>> <
>> https://github.com/named-data/NFD/commit/7003e0bc669c113bc112c784119750581b83d2a6
>>>
>>> (which will appear in ndnSIM sooner or later), there isn't a
>>> "straggler
>>> timer" anymore so the PIT entry is removed immediately.
>>> Q responds several milliseconds later, at which time the PIT entry 
>>> at
>>> G is
>>> already gone and G drops the Data.
>>>
>>> Should G count a "Interest satisfaction" on nexthop Q, or count a
>>> "Interest
>>> timeout" on nexthop Q, or neither?
>> Well, you clearly can’t just increment the interest satisfaction
>> counter, since that would allow a compromised upstream forwarder to 
>> blast
>> unrequested data packets in order to divert traffic onto its path.
>>
>> Conversely (although not quite as bad), counting as an interest 
>> timeout
>> would penalize an upstream forwarder who in fact just responded 
>> second
>> (which could be due to something as simple as a slightly longer RTT.)
>>
>> Doing neither seems the right compromise if one removes PIT state on
>> satisfaction rather than just marking the PIT satisfied and cleaning 
>> it
>> up in a lazy fashion. Unless you’re under memory pressure, leaving 
>> the
>> satisfied PIT around until the Interest expiration timer goes off is
>> likely to be a much better approach overall and renders this question
>> moot.
>>
>
> NFD used to have "straggler timer" and keep the PIT entry for 100ms 
> longer,
> although it never had the Interest satisfaction rate metric.
Well, a straggler timer seems the wrong solution since picking the value 
statically is going to always wind up with the wrong value. One *could* 
geta reasonable value by keeping track of RTT dispersion on a per-FIB 
entry basis, and use that to compute a straggler timer. However, to me 
the only reason to erase a satisfied PIT entry is to recover memory 
faster than the worst-case of Interest Lifetime.

> In practice, keeping the PIT entry causes lots of engineering 
> complexity:
> * It needs a timer to clean up, which increases the overhead on the 
> global
> scheduler.
You still need to clean up after the Interest Lifetime expires, so I 
don’t see why an extra timer is needed. In fact, you could take the 
approach of a classic generational garbage collector, which has 
well-understood properties.

> * If the CS entry is evicted, forwarding has to distinguish whether 
> the PIT
> entry is active so it aggregates the Interest, or the PIT entry is 
> waiting
> for deletion so it reactivates the PIT entry and sends the Interest.
this complexity I think exists independent of whether PIT entries are 
deleted or marked satisfied. Perhaps I’m missing something.

> * I cannot apply the technique in *Named data networking on a router: 
> Fast
> and DoS-resistant forwarding with hash tables* and use the same hash 
> table
> entry for PIT entry and CS entry, when they happen to have an exact 
> name.
>
Sure you can. The existence of the actual CS data is handled by a 
pointer. When you evict a CS entry you recover the memory reserved for 
the payload and you zero the pointer. If an Interest arrives you mark 
the entry as an active PIT entry and continue to process it.

What you may not be able to do straightforwardly is to achieve prefix 
match on CS data, which the forwarding paper did not support anyway (and 
should be eliminated from NDN as well in my well-known opinion).

Cheers, DaveO.
> Yours, Junxiao
>
>>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.lists.cs.ucla.edu/pipermail/nfd-dev/attachments/20180403/1b7b1c39/attachment.html>