Subject: Re: [tcpm] Review of draft-ietf-tcpm-dctcp-01

From: Bob Briscoe <[email-masked]>
Date: Wed, 2 Dec 2015 15:07:38 +0000

Andrew,

On 01/12/15 23:50, Andrew Shewmaker wrote:
>
>
> On Fri, Nov 6, 2015 at 11:27 AM, Bob Briscoe <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     Praveen & co-authors,
>
>     As promised, here's my review of draft-ietf-tcpm-dctcp-01
>
> ​ ...​
>
>
>     _*Section-by-section review.*__*
>     *_
>
> ​ ...​
>
>     *3. DCTCP Algo**
>     *
>     *3.3 **
>     *
>
>         DCTCP.Alpha, which is initialized to 1 and MUST be updated
>         as follows:
>
>     s/MUST/SHOULD/
>     And add "An alternative congestion avoidance algorithm MAY be
>     used, but it MUST lead to flow rate inversely proportional to 1/M".
>
>     Rationale: There are many ways to implement interoperable 1/p cc.
>     This is just one.
>
> ​...​
>
>     the sender MUST update cwnd as follows:
>            cwnd = cwnd * (1 - DCTCP.Alpha / 2)
>
>     s/MUST/SHOULD/
>     Rationale: Alternative interoperable response functions are
>     possible. For instance an algorithm like Relentless TCP that
>     simply reduces cwnd by half the size of any CE-marked segment.
>     Then there is no Alpha and no g variable.
>
>
> After reading this, I had to try it out. I couldn't get it to work by 
> reducing the cwnd by half the size of each CE-marked segment. However, 
> I did get something similar to work. In limited Mininet experiments of 
> a Linux module, I found the best backoff to be 1/8th of each CE-marked 
> segment.
Thanks for picking this up.

Without knowing the symptoms of "couldn't get it to work", I can't 
really respond. There is logic for reducing by half a segment:
* 100% marking leads to cwnd halving each RTT, which emulates the aim of 
the EWMA in DCTCP at the moment.
* Reducing by half a CE-marked segment naturally reduces at the round 
trip timescale, whereas in DCTCP you have to choose a value of g for the 
timescale, which is feasible in one particular data centre, but not for 
all different RTTs.

I don't see the logic for reducing by 1/8 of each CE-marked segment, and 
I don't see why that works and 1/2 doesn't.
All I can say is that, as well as reducing CWND by half the size of each 
CE-marked segment, there would still need to be a lower bound on CWND 
{Note 1}.

And for the avoidance of doubt, I was talking solely about congestion 
avoidance, and I was assuming the response to a non-CE marked ACK 
(additive increase of 1/CWND) would be unchanged.

{Note 1} A number of people who met in Prague to discuss DCTCP evolution 
informally agreed that DCTCP for the public Internet should not have 
this lower limit on cwnd (because otherwise, for low RTT, TCP overrides 
an AQM's attempt to keep the queue short). However that would require 
more code to pace once you've lost the ACK clock, so for your rough 
testing I am suggesting you just implement the normal 2MSS lower bound.

> In addition, I changed the Slow Start and Congestion Avoidance 
> behavior---every CE-marked segment increases CWND by 1/CWND, 
> and non-marked segment increases the CWND by 1.
I think there must be some typos here. CE-marked and non-marked segments 
both increase CWND!? And the same behaviour in SS and CA!?
>
> I also made a variant that treats each ACK with a RTT > RTTMIN * 1.17 
> as if it were CE-marked, and it backs off by 1/16th of the number of 
> segments ACKed. It does not grow the CWND if it sees a "marked" ACK, 
> otherwise it increases CWND by 1.
Why oh why? I can see you're trying to detect queue growth or variation 
and treat delay as CE-marking. However, I don't subscribe to "invent a 
number that works well in my tests or in my deployment scenario".

Parodying St Francis of Assisi (or Margaret Thatcher for that matter), 
"Where there is simplicity, may we bring complexity. Where there is 
harmony, may we bring discord." The point of the suggestion to reduce 
cwnd by half a CE-marked segment was to remove an arbitrarily chosen 
time constant (g). The idea is to make the code work in a wider range of 
scenarios, and to save having IETF arguments over choices of numbers.

>
> ​I've attached a few bandwidth and latency graphs from a simple 
> Mininet experiment. It's very similar to the convergence test shown in 
> Figure 16 ​of the first DCTCP paper. My Mininet network has 500Mbps 
> links and a 4ms RTT, with 5 iperf flows converging to one server. It 
> compares DCTCP, CUBIC, and the variants I described above which I 
> refer to as Relentless+ECN and Relentless+RTT.
By "the variants I described above" do you mean the ones you say 
"worked"? What did the the one you say "didn't work" look like?

>
> ​ srtt-cdf-relentless.png shows Relentless+ECN achieving a tighter 
> SRTT distribution than DCTCP. CUBIC+ECN does too, but you can see from 
> iperf-stacked-cubic+ecn.png that it only achieves an aggregate 
> bandwidth of ~300 Mbps, compared to the ~400 Mbps of DCTCP. 
> Relentless+ECN's aggregate throughput is 350-400 Mbps, and 
> Relentless+RTT is 400-450 Mbps, at the cost of a CDF shifted to the 
> right by about 0.5 ms. Nearly all of Relentless+RTT's SRTTs are below 
> 5.5 ms. As a point of reference, without ECN CDG's 20th percentile is 
> 10 ms and CUBIC's is over 20 ms.
>
> ​Of course, these results are preliminary, but they seem pertinent. 
> I'm not sure why reducing cwnd by half the size of a CE-marked segment 
> didn't work as expected. I'd be happy to share code, more graphs, and 
> ​test environment/scripts.
Yes. First-of all I would be interested to see answers to above questions.
>
>
> Back to DCTCP itself: srtt-relentless.png is a time series scatterplot 
> of SRTTs, and it shows that the long tail of DCTCP's SRTT distribution 
> corresponds to when a single flow is active at each end of the 
> experiment. At first I thought that perhaps DCTCP needed to have an 
> immediate cwnd reduction response to the first ECN-marked segment in 
> an RTT, especially during slowstart. However, my attempts to fix the 
> behavior have produced mixed results; I can reduce the tail at the 
> cost of instability. Obviously, I don't yet understand what's going on 
> well enough, but I thought I'd bring it up.
>
>
>     *6. Known Issues**
>     *
>     First para could refer to appendix A of RFC7560, which describes
>     the problem precisely.
>
>     A method for improving the fairness of DCTCP has been proposed
>         in [ADCTCP
>     <https://tools.ietf.org/html/draft-ietf-tcpm-dctcp-01#ref-ADCTCP>], but requires additional experimental evaluation.
>
>     s/fairness/RTT fairness/
>
>     (In our experiments, it's much better than without.)--
>
>
> I'm curious about the details of those experiments. Where may I learn 
> more?

Mohammad Alizadeh proposed a change to the algo to cope with a wider 
range of RTTs and reported the results in his SIGMETRICS paper:
<http://simula.stanford.edu/~alizade/Site/DCTCP_files/dctcp_analysis-full.pdf 
<http://simula.stanford.edu/%7Ealizade/Site/DCTCP_files/dctcp_analysis-full.pdf>>
 From memory, the RTT stuff is in a section near the end - section 5 I 
think?

We used the code written into Linux (as a result of the above, I 
believe) in the experiments written up here:
<http://bobbriscoe.net/projects/latency/>
When I said "it worked much better", I meant with a longer base RTT 
(7ms) we could get the DCTCP window to be equivalent to New Reno flows 
alongside it using the DualQ AQM in that paper. But with the earlier 
DCTCP code we couldn't.
However, that paper only reports experiments with a single RTT.

Since, we've done experiments with a range of RTTs and we're still doing 
more. But  you'll have to wait for the write up of them (next couple of 
months).

Bob

> ​Thanks,​
> Andrew Shewmaker

-- 
________________________________________________________________
Bob Briscoe                               http://bobbriscoe.net/

---

From: Andrew Shewmaker <[email-masked]>
Date: Tue, 1 Dec 2015 16:50:15 -0700

​...​

>
> *Section-by-section review.*
>
> ​...​

> *3. DCTCP Algo*
> *3.3 *
> And add "An alternative congestion avoidance algorithm MAY be used, but it
> MUST lead to flow rate inversely proportional to 1/M".
>
> Rationale: There are many ways to implement interoperable 1/p cc. This is
> just one.
>
​...​

> Rationale: Alternative interoperable response functions are possible. For
> instance an algorithm like Relentless TCP that simply reduces cwnd by half
> the size of any CE-marked segment. Then there is no Alpha and no g variable.
>

After reading this, I had to try it out. I couldn't get it to work by
reducing the cwnd by half the size of each CE-marked segment. However, I
did get something similar to work. In limited Mininet experiments of a
Linux module, I found the best backoff to be 1/8th of each CE-marked
segment. In addition, I changed the Slow Start and Congestion Avoidance
behavior---every CE-marked segment increases CWND by 1/CWND, and non-marked
segment increases the CWND by 1.

I also made a variant that treats each ACK with a RTT > RTTMIN * 1.17 as if
it were CE-marked, and it backs off by 1/16th of the number of segments
ACKed. It does not grow the CWND if it sees a "marked" ACK, otherwise it
increases CWND by 1.

​I've attached a few bandwidth and latency graphs from a simple Mininet
experiment. It's very similar to the convergence test shown in Figure 16
​of the first DCTCP paper. My Mininet network has 500Mbps links and a 4ms
RTT, with 5 iperf flows converging to one server. It compares DCTCP, CUBIC,
and the variants I described above which I refer to as Relentless+ECN and
Relentless+RTT.

​srtt-cdf-relentless.png shows Relentless+ECN achieving a tighter SRTT
distribution than DCTCP. CUBIC+ECN does too, but you can see from
iperf-stacked-cubic+ecn.png that it only achieves an aggregate bandwidth of
~300 Mbps, compared to the ~400 Mbps of DCTCP. Relentless+ECN's aggregate
throughput is 350-400 Mbps, and Relentless+RTT is 400-450 Mbps, at the cost
of a CDF shifted to the right by about 0.5 ms. Nearly all of
Relentless+RTT's SRTTs are below 5.5 ms. As a point of reference, without
ECN CDG's 20th percentile is 10 ms and CUBIC's is over 20 ms.

​Of course, these results are preliminary, but they seem pertinent. I'm not
sure why reducing cwnd by half the size of a CE-marked segment didn't work
as expected. I'd be happy to share code, more graphs, and ​test
environment/scripts.

Back to DCTCP itself: srtt-relentless.png is a time series scatterplot of
SRTTs, and it shows that the long tail of DCTCP's SRTT distribution
corresponds to when a single flow is active at each end of the experiment.
At first I thought that perhaps DCTCP needed to have an immediate cwnd
reduction response to the first ECN-marked segment in an RTT, especially
during slowstart. However, my attempts to fix the behavior have produced
mixed results; I can reduce the tail at the cost of instability. Obviously,
I don't yet understand what's going on well enough, but I thought I'd bring
it up.

> *6. Known Issues*
>
> First para could refer to appendix A of RFC7560, which describes the
> problem precisely.
>
>    in [ADCTCP <https://tools.ietf.org/html/draft-ietf-tcpm-dctcp-01#ref-ADCTCP>], but requires additional experimental evaluation.
>
> s/fairness/RTT fairness/
>

I'm curious about the details of those experiments. Where may I learn more?

​Thanks,​

Andrew Shewmaker

---

From: Andrew Shewmaker <[email-masked]>
Date: Wed, 2 Dec 2015 22:03:43 -0700

On Wed, Dec 2, 2015 at 8:07 AM, Bob Briscoe <[email-masked]> wrote:

>> And add "An alternative congestion avoidance algorithm MAY be used, but
>> it MUST lead to flow rate inversely proportional to 1/M".
>>
> Without knowing the symptoms of "couldn't get it to work", I can't really
> respond. There is logic for reducing by half a segment:
> * Reducing by half a CE-marked segment naturally reduces at the round trip
> timescale, whereas in DCTCP you have to choose a value of g for the
> timescale, which is feasible in one particular data centre, but not for all
> different RTTs.
>
> I don't see the logic for reducing by 1/8 of each CE-marked segment, and I
> don't see why that works and 1/2 doesn't.
> CE-marked segment, there would still need to be a lower bound on CWND {Note
> 1}.
>
>
​Sorry, I should have included the results for the half segment reduction.
You can see in iperf-stacked-relentless+ecn-half.png (which has standard
SS, CA, and lower 2MSS bound) that a single flow gets less than 300 Mbps
out of the 500 Mbps link and even five flows barely surpass 300 Mbps.

I had expected the logic for half segment reduction to work because your
reasoning seems sound. I only tried smaller reductions because it appeared
to be backing off too much. I've thought of two things that might cause a
1/8th reduction to work better in my experiments:

* segmentation offloading is enabled

I haven't tried it yet without segmentation offloading. I generally don't
disable it since it forces Mininet to use lower link rates, and I'd like to
ensure modifications work with offloading.

* by responding more quickly, TCP can use smaller adjustments (less
oversteering)

> avoidance, and I was assuming the response to a non-CE marked ACK (additive
> increase of 1/CWND) would be unchanged.
>
> informally agreed that DCTCP for the public Internet should not have this
> lower limit on cwnd (because otherwise, for low RTT, TCP overrides an AQM's
> attempt to keep the queue short). However that would require more code to
> pace once you've lost the ACK clock, so for your rough testing I am
> suggesting you just implement the normal 2MSS lower bound.
>

​Understood.​

> both increase CWND!? And the same behaviour in SS and CA!?

​Yes, I know it's weird. I tried it because ​I was trying to keep the half
reduction logic while attempting to achieve better bandwidth utilization.
Relentless+ecn-half-ss (half reduction for marked ACK with +1 segment to
CWND for every unmarked ACK) achieves better throughput and a shorter tail
to its latency distribution than with just the half reduction. Likewise,
relentless+ecn-half-ss-ca (increases CWND by 1/CWND for every marked ACK)
improves throughput again while keeping the same latency curve (I left
half-ss-ca out of srtt-cdf-relentless.png since it was the same as half-ss).

​Then, since I still wasn't getting full throughput, I decided to decrease
the reduction. One quarter was still too much, but one eighth works for the
most part. I've run it more experiments now, and half the time, it pushes a
little too hard​. In the bad cases, the bandwidth graph isn't too far off
the mark, and the latency curve is slightly worse than standard DCTCP's.

>
>
> I also made a variant that treats each ACK with a RTT > RTTMIN * 1.17 as
> if it were CE-marked, and it backs off by 1/16th of the number of segments
> harmony, may we bring discord." The point of the suggestion to reduce cwnd
> by half a CE-marked segment was to remove an arbitrarily chosen time
> constant (g). The idea is to make the code work in a wider range of

​I should have said that threshold is the same as that in the ADCTCP paper.
K is approximately 0.17Cd, where C is the bottleneck capacity and d is the
delay. The corresponding delay threshold is K/C, or 0.17d.

So, it's not really new ... it's moving the threshold from the switch to
the endpoint. In many ways applying the threshold at the endpoint is
simpler than applying throughout the network. Certainly, there would be
less configuration.

> Mohammad Alizadeh proposed a change to the algo to cope with a wider range
> of RTTs and reported the results in his SIGMETRICS paper:
> <
> <http://simula.stanford.edu/%7Ealizade/Site/DCTCP_files/dctcp_analysis-full.pdf>
> http://simula.stanford.edu/~alizade/Site/DCTCP_files/dctcp_analysis-full.pdf
> >

> We used the code written into Linux (as a result of the above, I believe)
> in the experiments written up here:
> When I said "it worked much better", I meant with a longer base RTT (7ms)
> we could get the DCTCP window to be equivalent to New Reno flows alongside
> it using the DualQ AQM in that paper. But with the earlier DCTCP code we
> couldn't.

​​I had thought that change had only been implemented in simulation. It
doesn't appear to be in the current Linux implementation.

​Thanks for sharing your insight,

Andrew