[Nfd-dev] Clarification needed for NCCStrategy

Marc.Mosko at parc.com Marc.Mosko at parc.com
Sat Jul 25 14:31:05 PDT 2015


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.

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).

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.

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.

I think the initial value, minimum, and maximum are largely arbitrary (unlike the /128 and /8).
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).

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.

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.


On Jul 25, 2015, at 9:29 PM, Junxiao Shi <shijunxiao at email.arizona.edu<mailto:shijunxiao at email.arizona.edu>> wrote:

Hi Navdeep

NCC is a re-implementation of ccnd 0.7.2 forwarding strategy.
The algorithm is summarized at http://redmine.named-data.net/projects/nfd/wiki/CcndStrategy
The three quoted constants come from CCNx 0.7.2 ccnd.c<http://www.ccnx.org/releases/ccnx-0.7.2/doc/ccode/html/ccnd_8c_source.html> line 4236, 1898, 5886.

I do not know the design rationale behind this algorithm, or how these constants are chosen.
You may be able to obtain more information on ccnx mailing list<http://www.ccnx.org/mailman/listinfo/ccnx>.

Yours, Junxiao

On Thu, Jul 23, 2015 at 7:34 AM, Navdeep Uniyal <navdeep.uniyal at neclab.eu<mailto:navdeep.uniyal at neclab.eu>> wrote:

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.

Best Regards,
Navdeep Uniyal
Nfd-dev mailing list
Nfd-dev at lists.cs.ucla.edu<mailto:Nfd-dev at lists.cs.ucla.edu>

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

More information about the Nfd-dev mailing list