https://redmine.named-data.net/https://redmine.named-data.net/favicon.ico?14759811232015-09-05T03:28:05ZNDN project issue tracking systemNFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=125532015-09-05T03:28:05ZJunxiao Shi
<ul><li><strong>Blocked by</strong> <i><a class="issue tracker-2 status-5 priority-3 priority-high3 closed" href="/issues/3156">Feature #3156</a>: NACK in forwarding and best-route</i> added</li></ul> NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=125542015-09-05T03:30:21ZJunxiao Shi
<ul><li><strong>Assignee</strong> set to <i>Anonymous</i></li></ul><p>Design can start now.<br><br>
Implementation cannot start until code for <a class="issue tracker-2 status-5 priority-3 priority-high3 closed" title="Feature: NACK in forwarding and best-route (Closed)" href="https://redmine.named-data.net/issues/3156">#3156</a> is approved.</p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=127312015-09-11T18:57:08ZAnonymous
<ul></ul><p>I think the design we talked about is as follows:</p>
<p>If all upstreams return a NACK: Return a NACK of the lowest severity to all downstreams. </p>
<p>This leads to the question: How to rank the severity among NACK reasons? NoRoute > DuplicateNonce > Congestion? </p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=127392015-09-12T20:53:55ZJunxiao Shi
<ul></ul><p>Answer to note-3: see <a class="issue tracker-3 status-5 priority-2 priority-default closed" title="Task: Determine rules to combine NackReasons (Closed)" href="https://redmine.named-data.net/issues/3032">#3032</a>.</p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=160832016-07-14T13:51:14ZAshlesh Gawande
<ul><li><strong>Assignee</strong> changed from <i>Anonymous</i> to <i>Ashlesh Gawande</i></li></ul> NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=160852016-07-14T14:16:24ZAnonymous
<ul></ul><p>Let me know if you need any help with the design. But I think it should be rather straight forward, as written above.</p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=162232016-07-21T14:03:20ZAshlesh Gawande
<ul></ul><p>So just to make sure, does this sound good:</p>
<p>on afterReceiveInterest: send Nack [No-Route] if no eligible next hop</p>
<p>on afterReceiveNack: send Nack to downstream(s) if all the upstreams have been Nacked else wait</p>
<p>?</p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=162252016-07-21T14:47:36ZJunxiao Shi
<ul></ul><p>I agree with note-7. This is basically the same procedure as best-route v4.<br><br>
Therefore, you should introduce a base class; both best-route v4 and multicast v2 (yes, you need to increment the version number) should inherit from that base class.</p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=162292016-07-21T17:26:11ZAnonymous
<ul></ul><p>I agree with the design, but think you should be more specific about which NACK Reasons you use in afterReceiveNack.</p>
<p>When you get 3 different NACK Reasons, which one do you send on?</p>
<p>Also: what happens on a PIT timeout? Is the PIT entry lifetime always the same as the Interest lifetime? Can different links have different timeouts? </p>
<p>I already have my guesses on what the answers to these questions are, but I would prefer them to be written down. </p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=162492016-07-22T14:24:54ZAshlesh Gawande
<ul></ul><p>Junxiao Shi wrote:</p>
<blockquote>
<p>I agree with note-7. This is basically the same procedure as best-route v4.<br><br>
Therefore, you should introduce a base class; both best-route v4 and multicast v2 (yes, you need to increment the version number) should inherit from that base class.</p>
</blockquote>
<p>Okay, does this include consumer retransmissions?</p>
<p>Klaus Schneider wrote:</p>
<blockquote>
<p>I agree with the design, but think you should be more specific about which NACK Reasons you use in afterReceiveNack.</p>
<p>When you get 3 different NACK Reasons, which one do you send on?</p>
<p>Also: what happens on a PIT timeout? Is the PIT entry lifetime always the same as the Interest lifetime? Can different links have different timeouts? </p>
<p>I already have my guesses on what the answers to these questions are, but I would prefer them to be written down.</p>
</blockquote>
<p>Lowest severity NACK (note-3) using the ranking from note-4 will be sent when all OutRecords are nacked.</p>
<p>To the best of my knowledge (pray enlighten if wrong):<br>
On PIT timeout, NACK is sent anyway<br>
PIT entry life time is the same as the last interest's lifetime (as per dev guide).<br>
Different links shouldn't have different timeouts</p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=163052016-07-25T18:22:44ZJunxiao Shi
<ul></ul><blockquote>
<blockquote>
<p>I agree with note-7. This is basically the same procedure as best-route v4.<br><br>
Therefore, you should introduce a base class; both best-route v4 and multicast v2 (yes, you need to increment the version number) should inherit from that base class.</p>
</blockquote>
<p>Okay, does this include consumer retransmissions?</p>
</blockquote>
<p>First, I want to correct note-8: the shared functionality can either be implemented as a base class or as a helper class/function.<br>
Helper class/function should be preferred over a base class because it allows better composability.</p>
<p>Second, it's better to keep consumer retransmission out of the base class or helper class/function, because the policy of consumer retransmission suppression is independent from how Nacks are handled.</p>
<blockquote>
<p>On PIT timeout, NACK is sent anyway</p>
</blockquote>
<p>When PIT entry times out (<em>before expire pending Interest</em> trigger), don't send Nacks.<br>
At this moment, the PIT entry at downstream is also timed out, and Nacks won't match a PIT entry and would be dropped.</p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=169492016-09-09T13:28:46ZAshlesh Gawande
<ul><li><strong>Status</strong> changed from <i>New</i> to <i>In Progress</i></li></ul><p>1)<br>
Please find first patch at: <a href="https://gerrit.named-data.net/#/c/3195/1">https://gerrit.named-data.net/#/c/3195/1</a>, abandoned</p>
<p>Patch at: <a href="https://gerrit.named-data.net/#/c/3013/">https://gerrit.named-data.net/#/c/3013/</a></p>
<p>I moved compareLessSevere and <code>predicate_NextHop_Eligible</code> to pit-algorithm.</p>
<p>Seems like afterReceiveNack is almost similar to that of BestRoute2, but I am not sure how to pull out common things?</p>
<p>2) <br>
For the tests should I delete multicast v1 test?<br>
I will add more test in patchset2. I am looking into BestRoute2 tests to see how best to test.</p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=171102016-09-23T04:34:47ZJunxiao Shi
<ul></ul><p><a href="https://gerrit.named-data.net/3013">https://gerrit.named-data.net/3013</a> patchset5 has a major difference from best-route v4: "one out-record not Nacked, which is also a downstream" special case (see <a class="issue tracker-3 status-5 priority-3 priority-high3 closed" title="Task: Forwarding design: Nack (Closed)" href="https://redmine.named-data.net/issues/3033#note-7">#3033-7</a> and <a class="issue tracker-3 status-5 priority-3 priority-high3 closed" title="Task: Forwarding design: Nack (Closed)" href="https://redmine.named-data.net/issues/3033#note-10">#3033-10</a>) is not considered.<br>
I wonder what's the rationale?</p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=171112016-09-23T09:51:13ZAshlesh Gawande
<ul></ul><p>Overlooked it (I ran the test for it from best-route in multicast but forgot to change the strategy on each node to multicast and it passed. So I thought it does not pertain to multicast - should have gone through the scenario). Will include it in next patchset. Should I post something here about it before doing that?</p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=171252016-09-26T11:29:05ZAshlesh Gawande
<ul></ul><p><a href="https://gerrit.named-data.net/#/c/3013/6">https://gerrit.named-data.net/#/c/3013/6</a></p>
<p>The functions for afterReceiveNack are same in multicast and best route now to handle <a href="https://redmine.named-data.net/issues/3033#note-7">https://redmine.named-data.net/issues/3033#note-7</a>.</p>
<p>Can someone please suggest how to use a common function - I am not sure how to separate the logging messages for the different strategies.</p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=173862016-10-25T08:37:12ZAshlesh Gawande
<ul></ul><p>So we were discussing about handling Duplicate NACKs. Would this be a desired behavior:</p>
<p>When a duplicate NACK is received, check the inRecords of the PIT Entry and see if there is any interest with the same name pending. Then send that interest which will have a different Nonce (with preference given to local application, ex NLSR) to the inFace of the NACK.</p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=173882016-10-25T11:30:28ZAnonymous
<ul></ul><p>So a "Duplicate NACK" means that the sender has received an Interest with a duplicate nonce, right? (I still think that the term "Duplicate NACK" isn't descriptive/intuitive enough) </p>
<p>I think it makes sense to then try other nonces in the PIT entry, but the question is in which order to try them? </p>
<p>An alternative would be to, after the NACK, send an Interest packet that contains all received nonces so far. If at least one of them isn't duplicate, the upstream host will add the face to the inRecord. Otherwise, it will send another NACK. </p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=173982016-10-27T10:52:08ZJunxiao Shi
<ul></ul><p>Reply to note-16 and note-17:</p>
<p>I have a recommendation of Nack-Duplicate processing applicable to all strategies (and may involve forwarding pipelines).<br>
See <a class="issue tracker-1 status-1 priority-2 priority-default" title="Bug: Interest unsatisfied due to Interest aggregation combined with duplicate Nonce suppression (New)" href="https://redmine.named-data.net/issues/1966#note-7">#1966-7</a>.</p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=173992016-10-27T13:36:40ZAnonymous
<ul></ul><p>Here's the text from Junxiao's note-18</p>
<blockquote>
<p>Iterate through all unexpired PIT in-records, and pick a PIT in-record whose<br>
last incoming Nonce is not recorded as duplicated in the PIT out-record. When<br>
multiple PIT in-records are eligible, the newest PIT in-record should be used<br>
because its Nonce is less likely to be seen by the upstream.<br>
Implementation concern</p>
<p>In NFD strategy API, send Interest action does not allow strategy to specify which<br>
Nonce to use in an outgoing Interest packet. Either this API should be extended, or<br>
this procedure should be implemented in the outgoing Interest pipeline.</p>
</blockquote>
<p>I agree with the design, as it seems simpler as my suggestion of sending multiple nonces. </p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=174002016-10-27T14:32:13ZLan Wanglanwang@memphis.edu
<ul></ul><p>how about give the first preference to local applications that sent the same interest (same name)? if there are multiple local faces or there are no local faces, then use time to decide (newest nonce is preferred). </p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=174022016-10-27T16:05:25ZAnonymous
<ul></ul><p>Can you state the reason for preferring local interfaces?</p>
<p>Is the assumption that local applications will always use an unseen nonce? What if a local app, for whatever reason, retransmits with the same nonce on a different interface? </p>
<p>Maybe we can think about the probability of getting a duplicate nonce for different decision rules and then create a hierarchy like:</p>
<ol>
<li>Choose nonce of local face (criteria A)</li>
<li>If none or multiple of (A), choose face with highest/lowest of criteria B.</li>
<li>If none or multiple choices left, choose highest/loweest of criteria C.</li>
<li>...</li>
<li>Choose randomly.</li>
</ol>
<p>The assumptions that we already have are:</p>
<ul>
<li>Newer PIT in-records are less likely to result in a duplicate nonce than older ones.</li>
<li>PIT in-records from local faces are less likely to result in a duplicate nonce than in-records from non-local faces.</li>
</ul>
<p>Maybe there are others.</p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=175042016-11-06T07:55:39ZJunxiao Shi
<ul><li><strong>Related to</strong> <i><a class="issue tracker-2 status-5 priority-2 priority-default closed" href="/issues/1756">Feature #1756</a>: Let strategy pick outgoing Interest packet</i> added</li></ul> NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=178982016-12-22T14:25:54ZAshlesh Gawande
<ul></ul><p>I have run experiments with the following code to determine whether retransmission with new Nonce from pitEntry on Duplicate benefits NLSR convergence speed or reduces Duplicate NACKs.<br>
Currently NLSR uses /localhop prefix for Sync and non-localhop for application prefix which are on multicast strategy.</p>
<p>The code is same as BestRoutev4 for NACK handling except it has the simple retransmission code based on Junxiao's suggestion in <a href="https://redmine.named-data.net/issues/3176#note-19">https://redmine.named-data.net/issues/3176#note-19</a>.</p>
<pre><code>
void
MulticastStrategy::afterReceiveNack(const Face& inFace, const lp::Nack& nack,
const shared_ptr<pit::Entry>& pitEntry)
{
if (nack.getReason() == lp::NackReason::DUPLICATE) {
time::steady_clock::TimePoint newest = time::steady_clock::TimePoint::min();
pit::InRecord* newest_inR = nullptr;
bool existInOutRecord = false;
for (const pit::InRecord& inR : pitEntry->getInRecords()) {
// Is outRecord.getLastNonce in not in inRecords
existInOutRecord = false;
for (const pit::OutRecord& outR : pitEntry->getOutRecords()) {
if (inR.getLastNonce() == outR.getLastNonce()) {
existInOutRecord = true;
break;
}
}
// If does not exist in outRecord and is the newest and the inR is not from inFace
if (!existInOutRecord && inR.getLastRenewed() > newest && inFace.getId() != inR.getFace().getId()) {
newest = inR.getLastRenewed();
newest_inR = &const_cast<pit::InRecord&>(inR);
}
} // for outRecords
// send interest with new Nonce to inFace
if (newest_inR != nullptr) {
this->sendInterest(pitEntry, const_cast<Face&>(inFace), newest_inR->getInterest());
NFD_LOG_ERROR("Special: " << newest_inR->getInterest() << " from=" << newest_inR->getFace().getId() <<
" newPitEntry-to=" << inFace.getId());
}
}
Followed by same code as BestRoutev4
</code></pre>
<p>I ran experiments with and without (i.e. NACK handling is the same as BestRoutev4) this retransmission code and found no significant reduction in Duplicate NACks or faster convergence.<br>
I ran 10 experiments for each with 34 node topology (current testbed) in Mini-NDN.<br>
Avg Dupl NACKs with retransmission code: 87223<br>
Avg Dupl NACKs w/o retransmission code: 90879</p>
<p>Convergence time is 30 seconds, I cannot go lower for either.</p>
<p>Since it does not help, it seems like I should not put it in?</p>
<hr>
<p>So for NLSR we are using /localhop prefix to reduce Duplicate NACKs on Sync and plan to do it for LSA prefix as well.</p>
<p>Otherwise if I put both sync and LSA prefix on non-localhop prefix, NLSR stops converging for bigger topology and there is a storm of NACK duplicates. I am not sure if this is because of computing power available.</p>
<p>I have tried to turn off all logging (no ndndump, NFD, or NLSR logs) and still the topology does not converge in any reasonable time (I have tried up to 5 minutes but it still does not converge).</p>
<p>The largest topology I have that converges is the 10 node topology.</p>
<p>(And this is on a two octacore (each has 16 threads) machine - with 160 GB RAM, 30GB dedicated to RAMDISK for these experiments).</p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=181302017-01-13T09:46:00ZAshlesh Gawande
<ul></ul><p>I have run more experiments to determine whether the retransmission of interest with new Nonce on duplicate NACK reduces duplicate NACKs. On average the number of Duplicate NACKs is very slightly higher for the patch with retransmission. So I will skip it and push a new patch.</p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=181992017-01-24T09:43:28ZJunxiao Shi
<ul><li><strong>Target version</strong> changed from <i>v0.5</i> to <i>v0.6</i></li></ul> NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=182752017-02-02T16:25:17ZJunxiao Shi
<ul><li><strong>Related to</strong> <i><a class="issue tracker-2 status-7 priority-2 priority-default closed" href="/issues/3879">Feature #3879</a>: ASF strategy should propagate NACK if all nexthops are NACKed</i> added</li></ul> NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=183892017-02-16T08:29:31ZJunxiao Shi
<ul><li><strong>Blocks</strong> <i><a class="issue tracker-2 status-5 priority-2 priority-default closed" href="/issues/3968">Feature #3968</a>: Forward Interest to ad hoc incoming face</i> added</li></ul> NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=184562017-02-25T17:25:45ZJunxiao Shi
<ul><li><strong>Status</strong> changed from <i>In Progress</i> to <i>Resolved</i></li><li><strong>% Done</strong> changed from <i>0</i> to <i>100</i></li></ul><p>Code is merged in <a href="https://gerrit.named-data.net/3013">https://gerrit.named-data.net/3013</a>. NFD devguide update is needed, but can be deferred to be together with <a class="issue tracker-2 status-5 priority-2 priority-default closed" title="Feature: MulticastStrategy: permit consumer retransmission (Closed)" href="https://redmine.named-data.net/issues/2062">#2062</a>.</p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=185382017-03-08T10:12:43ZAshlesh Gawande
<ul></ul><p>NFD devguide is updated, can somebody please review?<br>
(Should I add myself to the author list?)</p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=185392017-03-08T10:15:14ZAlex Afanasyev
<ul></ul><blockquote>
<p>(Should I add myself to the author list?)</p>
</blockquote>
<p>Yes</p>
NFD - Feature #3176: NACK in multicast strategyhttps://redmine.named-data.net/issues/3176?journal_id=187092017-03-28T13:55:44ZJunxiao Shi
<ul><li><strong>Status</strong> changed from <i>Resolved</i> to <i>Closed</i></li></ul><p>NFD-devguide looks correct.</p>