<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 14 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:70.85pt 70.85pt 2.0cm 70.85pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="DE" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Thank You Marc for such a detailed explanation .<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<div>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Best Regards,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:Consolas;color:#1F497D">Navdeep Uniyal<o:p></o:p></span></p>
</div>
<div>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span lang="EN-US" style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> Marc.Mosko@parc.com [mailto:Marc.Mosko@parc.com]
<br>
<b>Sent:</b> Samstag, 25. Juli 2015 23:31<br>
<b>To:</b> shijunxiao@email.arizona.edu<br>
<b>Cc:</b> Navdeep Uniyal; nfd-dev@lists.cs.ucla.edu<br>
<b>Subject:</b> Re: [Nfd-dev] Clarification needed for NCCStrategy<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">Navdeep,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">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.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<p class="MsoNormal">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).
<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">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.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">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.<o:p></o:p></p>
</div>
<div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I think the initial value, minimum, and maximum are largely arbitrary (unlike the /128 and /8).<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">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).
<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">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.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">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.<o:p></o:p></p>
</div>
<div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Marc<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal">On Jul 25, 2015, at 9:29 PM, Junxiao Shi <<a href="mailto:shijunxiao@email.arizona.edu">shijunxiao@email.arizona.edu</a>> wrote:<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal">Hi Navdeep <o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">NCC is a re-implementation of ccnd 0.7.2 forwarding strategy.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">The algorithm is summarized at <a href="http://redmine.named-data.net/projects/nfd/wiki/CcndStrategy" target="_blank">
http://redmine.named-data.net/projects/nfd/wiki/CcndStrategy</a><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">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">
ccnd.c</a> line 4236, 1898, 5886.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I do not know the design rationale behind this algorithm, or how these constants are chosen.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">You may be able to obtain more information on <a href="http://www.ccnx.org/mailman/listinfo/ccnx" target="_blank">
ccnx mailing list</a>.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Yours, Junxiao<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On Thu, Jul 23, 2015 at 7:34 AM, Navdeep Uniyal <<a href="mailto:navdeep.uniyal@neclab.eu" target="_blank">navdeep.uniyal@neclab.eu</a>> wrote:<o:p></o:p></p>
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">Hello,<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span lang="EN-US">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.</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span lang="EN-US"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span lang="EN-US"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span lang="EN-US">Best Regards,</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span lang="EN-US" style="font-size:10.5pt;font-family:Consolas">Navdeep Uniyal</span><o:p></o:p></p>
</div>
</div>
</div>
</div>
</div>
<p class="MsoNormal"><span lang="EN-US">_______________________________________________<br>
Nfd-dev mailing list<br>
</span><a href="mailto:Nfd-dev@lists.cs.ucla.edu"><span lang="EN-US">Nfd-dev@lists.cs.ucla.edu</span></a><span lang="EN-US"><br>
</span><a href="http://www.lists.cs.ucla.edu/mailman/listinfo/nfd-dev"><span lang="EN-US">http://www.lists.cs.ucla.edu/mailman/listinfo/nfd-dev</span></a><span lang="EN-US"><o:p></o:p></span></p>
</div>
</blockquote>
</div>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
</div>
</div>
</div>
</div>
</div>
</body>
</html>