<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta http-equiv="Content-Type" content="text/xhtml; charset=utf-8">
</head>
<body>
<div style="font-family:sans-serif"><div style="white-space:normal">
<p dir="auto">May not be worth continuing this now, as some of the design issues are delicate, but here goes anyway. See below.</p>
<p dir="auto">On 3 Apr 2018, at 11:43, Junxiao Shi wrote:</p>
</div>
<div style="white-space:normal"><blockquote style="border-left:2px solid #777; color:#777; margin:0 0 5px; padding-left:5px"><p dir="auto">Hi Dave<br>
<br>
Thanks for your quick response. It is very valuable.<br>
I agree that not incrementing either counter makes sense.<br>
</p>
<blockquote style="border-left:2px solid #777; color:#999; margin:0 0 5px; padding-left:5px; border-left-color:#999"><blockquote style="border-left:2px solid #777; color:#BBB; margin:0 0 5px; padding-left:5px; border-left-color:#BBB"><p dir="auto">I have a related question: what does "Interest satisfaction rate" for<br>
a<br>
nexthop means on a forwarder?<br>
<br>
Consider the scenario where a forwarder G has one downstream node C,<br>
and<br>
two upstream nodes (aka nexthops) P and Q:<br>
<br>
/---P<br>
C---G<br>
\---Q<br>
<br>
G is using multicast strategy.<br>
When it receives an Interest from C and forwards it to both P and Q, P<br>
responds immediately and the Data goes back to C.<br>
As in a recent NFD commit<br>
<</p>
</blockquote><p dir="auto"><a href="https://github.com/named-data/NFD/commit/7003e0bc669c113bc112c784119750581b83d2a6" style="color:#999">https://github.com/named-data/NFD/commit/7003e0bc669c113bc112c784119750581b83d2a6</a></p>
<blockquote style="border-left:2px solid #777; color:#BBB; margin:0 0 5px; padding-left:5px; border-left-color:#BBB"><p dir="auto">(which will appear in ndnSIM sooner or later), there isn't a<br>
"straggler<br>
timer" anymore so the PIT entry is removed immediately.<br>
Q responds several milliseconds later, at which time the PIT entry at<br>
G is<br>
already gone and G drops the Data.<br>
<br>
Should G count a "Interest satisfaction" on nexthop Q, or count a<br>
"Interest<br>
timeout" on nexthop Q, or neither?</p>
</blockquote><p dir="auto">Well, you clearly can’t just increment the interest satisfaction<br>
counter, since that would allow a compromised upstream forwarder to blast<br>
unrequested data packets in order to divert traffic onto its path.<br>
<br>
Conversely (although not quite as bad), counting as an interest timeout<br>
would penalize an upstream forwarder who in fact just responded second<br>
(which could be due to something as simple as a slightly longer RTT.)<br>
<br>
Doing neither seems the right compromise if one removes PIT state on<br>
satisfaction rather than just marking the PIT satisfied and cleaning it<br>
up in a lazy fashion. Unless you’re under memory pressure, leaving the<br>
satisfied PIT around until the Interest expiration timer goes off is<br>
likely to be a much better approach overall and renders this question<br>
moot.<br>
</p>
</blockquote><p dir="auto">NFD used to have "straggler timer" and keep the PIT entry for 100ms longer,<br>
although it never had the Interest satisfaction rate metric.</p>
</blockquote></div>
<div style="white-space:normal">
<p dir="auto">Well, a straggler timer seems the wrong solution since picking the value statically is going to always wind up with the wrong value. One <em>could</em> 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.</p>
</div>
<div style="white-space:normal"><blockquote style="border-left:2px solid #777; color:#777; margin:0 0 5px; padding-left:5px"><p dir="auto">In practice, keeping the PIT entry causes lots of engineering complexity:<br>
* It needs a timer to clean up, which increases the overhead on the global<br>
scheduler.</p>
</blockquote></div>
<div style="white-space:normal">
<p dir="auto">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.</p>
</div>
<div style="white-space:normal"><blockquote style="border-left:2px solid #777; color:#777; margin:0 0 5px; padding-left:5px"><p dir="auto">* If the CS entry is evicted, forwarding has to distinguish whether the PIT<br>
entry is active so it aggregates the Interest, or the PIT entry is waiting<br>
for deletion so it reactivates the PIT entry and sends the Interest.</p>
</blockquote></div>
<div style="white-space:normal">
<p dir="auto">this complexity I think exists independent of whether PIT entries are deleted or marked satisfied. Perhaps I’m missing something.</p>
</div>
<div style="white-space:normal"><blockquote style="border-left:2px solid #777; color:#777; margin:0 0 5px; padding-left:5px"><p dir="auto">* I cannot apply the technique in *Named data networking on a router: Fast<br>
and DoS-resistant forwarding with hash tables* and use the same hash table<br>
entry for PIT entry and CS entry, when they happen to have an exact name.<br>
</p>
</blockquote></div>
<div style="white-space:normal">
<p dir="auto">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.</p>
<p dir="auto">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).</p>
<p dir="auto">Cheers, DaveO.</p>
</div>
<div style="white-space:normal"><blockquote style="border-left:2px solid #777; color:#777; margin:0 0 5px; padding-left:5px"><p dir="auto">Yours, Junxiao<br>
</p>
<blockquote style="border-left:2px solid #777; color:#999; margin:0 0 5px; padding-left:5px; border-left-color:#999"></blockquote></blockquote></div>
<div style="white-space:normal">
</div>
</div>
</body>
</html>