<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
<div class="">Navdeep,</div>
<div class=""><br class="">
</div>
<div class="">These comments are based on the ccnd code Junxiao mentioned. I didn’t write it, but this is my understanding of it. I have not looked at the NDN implementation of this in a long time, so I don’t remember if it does exactly this or not.</div>
<div class=""><br class="">
</div>
The timeout is initialized between 8 and 12 msec. If we get a response within the timeout it is decreased by 1/128th (i.e. t = .992 * t). Else it times out, it is increased by 1/8th (t = 1.125 t).
<div class=""><br class="">
<div class="">The general rational was that about every 15th packet would timeout, that’s why the decrease factor is 1/128th and the increase factor is 1/8th. After the i-th decrease, the timeout will be t = (1-1/128)^i * t. After you hit the timeout, you
then increase it to t = t * (1 + 1/8). You find the equilibrium solving 1 / (1 - 1/128) ^i = (1 + 1/8). Taking the log and rearranging gives i = 15.02, so about ever 15th packet you will cross the RTT timeout (assuming it’s constant and you started at about
the right value). I have not analyzed the convergence of stability, but because the decrease is so much less than the increase I assume it will not ring too much once you cross the lower boundary and start increasing. However, if the RTT is much less than
the initial value it could take a while to converge.</div>
<div class=""><br class="">
</div>
<div class="">For example, if you have a 10,000 usec RTT and the timeout is 10,000, then the first hit will decrease to 9922 and you’ll miss. This will increase it to 11162, then decrease to 11075, …, 10001 (14th decrease), 9923 (15th decrease). Clearly 9923
is almost the same as 9922, so the next increase will keep oscillating in the same ballpark.</div>
<div class="">
<div class=""><br class="">
</div>
<div class="">I think the initial value, minimum, and maximum are largely arbitrary (unlike the /128 and /8).</div>
<div class="">The minimum value of 127 usec is the maximum value less than the division factor of 1/128th. So, once you reach the floor it will not be decreased any more. One could theorize that an 8000 byte datagram at 1 Gbps takes 64 usec (each way), so
having the minimum oscillate around 128 usec would be about the minimum on a fast network. But, that might be reading too much in to it. Also, it clearly does not scale for very fast networks (10G and beyond) nor for very slow networks (over 160 msec). </div>
<div class=""><br class="">
</div>
<div class="">For example, I could have a 10G link and a 40G link. If I first tried the 10G link I would never timeout so never probe the 40G link. Likewise, if all my links are slow, say a 200msec and a 600 msec, I will timeout every time and always oscillate
between them, even though trying the 600 msec every other packet is not a good idea.</div>
<div class=""><br class="">
</div>
<div class="">The decrease / increase trick used here is pretty solid, I think, though the three constants need adjusting based on the type of network. I think some applied statistics could give you reasonable learned values that would adjust for very fast
or very slow. Clearly for very fast you need to work in nanos not micros, so you will have a uint32 problem.</div>
<div class="">
<div class=""><br class="">
</div>
<div class="">Marc</div>
<div class=""><br class="">
<div>
<blockquote type="cite" class="">
<div class="">On Jul 25, 2015, at 9:29 PM, Junxiao Shi <<a href="mailto:shijunxiao@email.arizona.edu" class="">shijunxiao@email.arizona.edu</a>> wrote:</div>
<br class="Apple-interchange-newline">
<div class="">
<div dir="ltr" class="">Hi Navdeep
<div class=""><br class="">
</div>
<div class="">NCC is a re-implementation of ccnd 0.7.2 forwarding strategy.</div>
<div class="">The algorithm is summarized at <a href="http://redmine.named-data.net/projects/nfd/wiki/CcndStrategy" target="_blank" class="">
http://redmine.named-data.net/projects/nfd/wiki/CcndStrategy</a></div>
<div class="">The three quoted constants come from CCNx 0.7.2 <a href="http://www.ccnx.org/releases/ccnx-0.7.2/doc/ccode/html/ccnd_8c_source.html" target="_blank" class="">
ccnd.c</a> line 4236, 1898, 5886.</div>
<div class=""><br class="">
</div>
<div class="">I do not know the design rationale behind this algorithm, or how these constants are chosen.</div>
<div class="">You may be able to obtain more information on <a href="http://www.ccnx.org/mailman/listinfo/ccnx" target="_blank" class="">
ccnx mailing list</a>.</div>
<div class=""><br class="">
</div>
<div class="">Yours, Junxiao</div>
<div class="gmail_extra"><br class="">
<div class="gmail_quote">On Thu, Jul 23, 2015 at 7:34 AM, Navdeep Uniyal <span dir="ltr" class="">
<<a href="mailto:navdeep.uniyal@neclab.eu" target="_blank" class="">navdeep.uniyal@neclab.eu</a>></span> wrote:<br class="">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div lang="DE" link="blue" vlink="purple" class="">
<div class="">
<p class="MsoNormal">Hello,<u class=""></u><u class=""></u></p>
<p class="MsoNormal"><u class=""></u> <u class=""></u></p>
<p class="MsoNormal"><span lang="EN-US" class="">I am trying to understand the NCC Strategy as implemented in NFD. While going through the code, I could have a clear understanding of why the prediction function is used and what is the use of INITIAL_PREDICTION,
MIN_PREDICTION, MAX_PREDICTION. If someone can please explain me.<u class=""></u><u class=""></u></span></p>
<p class="MsoNormal"><span lang="EN-US" class=""><u class=""></u> <u class=""></u></span></p>
<p class="MsoNormal"><span lang="EN-US" class=""><u class=""></u> <u class=""></u></span></p>
<p class="MsoNormal"><span lang="EN-US" class="">Best Regards,<u class=""></u><u class=""></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:Consolas" class="">Navdeep Uniyal</span></p>
</div>
</div>
</blockquote>
</div>
</div>
</div>
_______________________________________________<br class="">
Nfd-dev mailing list<br class="">
<a href="mailto:Nfd-dev@lists.cs.ucla.edu" class="">Nfd-dev@lists.cs.ucla.edu</a><br class="">
http://www.lists.cs.ucla.edu/mailman/listinfo/nfd-dev<br class="">
</div>
</blockquote>
</div>
<br class="">
</div>
</div>
</div>
</div>
</body>
</html>