NFD » ndn-tools

FYI, Andrea has recently implemented a rudimentary version of TCP congestion control in ndncatchunks. The main reason was to prevent NFD from overloading due to too many incoming interests (it's pretty easy to hit the limit at the moment). I believe we can share the code, although I'm afraid it's more of a quick hack than a well-designed implementation.

The design looks pretty solid and is practically the same that I used for my experimentation in ndnSIM (we can talk about it during the seminar on Thursday).

Just two comments:

"Consumer takes one RTT sample per RTT;"

Why is that?

slow start threshold, initial value: 200;

200 might be too low, if the optimal congestion window is higher than that. The only requirement for the sstreshhold is that it is "sufficiently high" and there is no harm in setting it to 100.000 or even to MAX_INTEGER.

Regarding Junxiao's comment: I think the choice of congestion control algorithm can be made more specific, by enabling/disabling certain features. For example:

• Enabling/Disabling the SACK mechanism (that is, only considering one loss event per RTT). The default should be enabled.
• Per loss event: Resetting the cwnd to 1 vs. resetting it to the sstresh (default: reset to sstresh).
• Consider gaps in sequence numbers (receiving out-of-order data packets) as congestion event? The default should be disabled.

Klaus Schneider wrote:

"Consumer takes one RTT sample per RTT;"

Why is that?

I think that's the traditional TCP behavior. See also https://tools.ietf.org/html/rfc6298#section-3 and https://tools.ietf.org/html/rfc7323#section-4.2

slow start threshold, initial value: 200;

200 might be too low, if the optimal congestion window is higher than that. The only requirement for the sstreshhold is that it is "sufficiently high" and there is no harm in setting it to 100.000 or even to MAX_INTEGER.

Agreed, ssthresh should start from MAX_INT.

Thanks for all your comments and suggestions.

I just uploaded the code here: http://gerrit.named-data.net/2872. It's basically Shuo's original implementation of the design(except initSsthresh is modified to MAX_INT). And command line options for congestion control have not been added yet, we are still working on it.

Davide Pesavento wrote:
Klaus Schneider wrote:

"Consumer takes one RTT sample per RTT;"

Why is that?

I think that's the traditional TCP behavior. See also https://tools.ietf.org/html/rfc6298#section-3 and https://tools.ietf.org/html/rfc7323#section-4.2

Wouldn't it be more accurate to take the RTT of each data packet? What's the benefit of only using one per RTT?

In rfc7323, it says research has shown that "taking additional RTT samples within each RTT has little effect on the ultimate retransmission timeout value". But in Shuo's code, it seems that he actually takes RTT sample per data packet(retransmitted segments excluded) instead of per RTT. I'll confirm this with him.

Klaus Schneider wrote:

Davide Pesavento wrote:
Klaus Schneider wrote:

"Consumer takes one RTT sample per RTT;"

Why is that?

I think that's the traditional TCP behavior. See also https://tools.ietf.org/html/rfc6298#section-3 and https://tools.ietf.org/html/rfc7323#section-4.2

Wouldn't it be more accurate to take the RTT of each data packet? What's the benefit of only using one per RTT?

I was wrong, Shuo actually took care of that inside the rtt-estimator. So actually he does take one rtt sample per RTT. And in fact, he tried to take one rtt sample per packet, but somehow the performance was bad especially when transferring large file. So he switched to taking one rtt sample per rtt.

Weiwei Liu wrote:

In rfc7323, it says research has shown that "taking additional RTT samples within each RTT has little effect on the ultimate retransmission timeout value". But in Shuo's code, it seems that he actually takes RTT sample per data packet(retransmitted segments excluded) instead of per RTT. I'll confirm this with him.

Klaus Schneider wrote:

Davide Pesavento wrote:
Klaus Schneider wrote:

"Consumer takes one RTT sample per RTT;"

Why is that?

I think that's the traditional TCP behavior. See also https://tools.ietf.org/html/rfc6298#section-3 and https://tools.ietf.org/html/rfc7323#section-4.2

Wouldn't it be more accurate to take the RTT of each data packet? What's the benefit of only using one per RTT?

"And in fact, he tried to take one rtt sample per packet, but somehow the performance was bad especially when transferring large file."

I don't think that the performance should suffer by taking one rtt sample per packet. It's just one operation (for the exponential moving average) per packet and doesn't require any memory.

Can we try to figure out the root cause? Or implement both with a parameter to choose the rtt sampling method.

Regarding to Klaus' question about RTT sampling frequency, I've read corresponding RFC (7323 & 6298) and one related paper: on estimating end-to-end network path properties (http://www.icir.org/mallman/pubs/AP01/AP01.pdf).

I quoted the corresponding explanations below:

1. The [RFC6298] RTT estimator has weighting factors,
   alpha and beta, based on an implicit assumption that at most one RTTM
   will be sampled per RTT. (https://tools.ietf.org/html/rfc7323#section-4.2)

2. [Ludwig00] and [Floyd05] have highlighted the problem that an
   unmodified RTO calculation, which is updated with per-packet RTT
   samples, will truncate the path history too soon. This can lead to
   an increase in spurious retransmissions, when the path properties
   vary in the order of a few RTTs, but a high number of RTT samples are
   taken on a much shorter timescale. (https://tools.ietf.org/html/rfc7323#section-4.2)

3. As we found for [WS95], timing every packet makes little difference over
   timing only one packet per RTT, even though by timing every packet we run
   many more measurements through the EWMAs per unit time.
   
   This in turn causes the EWMAs to adapt SRTT and RTTVAR more quickly to
   current network conditions, and to more rapidly lose memory of conditions
   further in the past. (http://www.icir.org/mallman/pubs/AP01/AP01.pdf)

Also the paper concluded that the performance of the RTO estimators
is dominated by their minimum values, and to a lesser extent,
the timer granularity, while being virtually unaffected by how
often round-trip time measurements are made.

In https://tools.ietf.org/html/rfc7323#appendix-G, it gives a modified RTO calculation
for taking multiple RTT per window. I think it'd interesting to try it out in our application.

Thanks for looking up the references. Yeah, I think we should implement the Appendix G as Shuo said:

Appendix G. RTO Calculation Modification

Taking multiple RTT samples per window would shorten the history
calculated by the RTO mechanism in [RFC6298], and the below algorithm
aims to maintain a similar history as originally intended by
[RFC6298].

It is roughly known how many samples a congestion window worth of
data will yield, not accounting for ACK compression, and ACK losses.
Such events will result in more history of the path being reflected
in the final value for RTO, and are uncritical. This modification
will ensure that a similar amount of time is taken into account for
the RTO estimation, regardless of how many samples are taken per
window:

  ExpectedSamples = ceiling(FlightSize / (SMSS * 2))

  alpha' = alpha / ExpectedSamples

  beta' = beta / ExpectedSamples

Note that the factor 2 in ExpectedSamples is due to "Delayed ACKs".

Instead of using alpha and beta in the algorithm of [RFC6298], use
alpha' and beta' instead:

  RTTVAR <- (1 - beta') * RTTVAR + beta' * |SRTT - R'|

  SRTT <- (1 - alpha') * SRTT + alpha' * R'

  (for each sample R')

With the latest code (change https://gerrit.named-data.net/#/c/2872/), a "Segmentation fault" error occurs when running ndncatchunks. Could someone confirm this?

Latest code doesn't even compile due to #3665-7.

Yes, I noticed that.. But it should work with an old ndn-cxx version, right?

I think the problem is the following code in consumer.cpp, discover should be replaced with m_discover.

m_discover = std::move(discover);

m_pipeline = std::move(pipeline);

m_nextToPrint = 0;

m_bufferedData.clear();

discover->onDiscoverySuccess.connect(bind(&Consumer::startPipeline, this, _1));

discover->onDiscoveryFailure.connect(bind(&Consumer::onFailure, this, _1));

Weiwei Liu wrote:

I think the problem is the following code in consumer.cpp, discover should be replaced with m_discover.

Yes, that's correct. Can you submit a fix?

Consumer::run is not unit-tested at all. Could you add a (very simple) test case for it as well?

Sure. In the test case, we just need to simply call consumer.run() right? And what can we check?

Davide Pesavento wrote:

Weiwei Liu wrote:

I think the problem is the following code in consumer.cpp, discover should be replaced with m_discover.

Yes, that's correct. Can you submit a fix?

Consumer::run is not unit-tested at all. Could you add a (very simple) test case for it as well?

I submitted a fix for cosnumer::run:
https://gerrit.named-data.net/#/c/2957/

backport c++ 17 std::clamp
https://gerrit.named-data.net/#/c/3147/