Subject: Re: [tcpm] [e2e] TCP HyStart patch deployment

From: Kenneth Klette Jonassen <[email-masked]>
Date: Mon, 23 Nov 2015 02:02:51 +0100

On Tue, 2015-11-17 at 21:05 +0000, Veaceslav ROMAN wrote:
...
> The reason for what I believed the call of hystart_update before the hystart_update is a big deviation from the initial logic is as follow.
> Both HYSTART_ACK_TRAIN and  HYSTART_DELAY algorithms in function hystart_update are supposed to do some computing starting with the first ACK of the train. The beginning of the train itself is determined by the function hystart_reset. But, because, in the current implementation the hystart_update is called for each ACK before the hystart_reset, the first ACK of the train N+1 is still considered in hystart_update as an ACK of the previous train N. (in tcp_input.c: tcp_ack() -> tcp_clean_rtx_queue() ->  pkts_acked()=bictcp_acked() -> hystart_update();  then  tcp_input.c: tcp_ack() -> tcp_cong_avoid() -> cong_avoid=bictcp_cong_avoid() -> hystart_reset(); and, btw, tcp_slow_start() is called next ).
> Therefor HYSTART_ACK_TRAIN, in the current implementation, will not measure, as it was supposed in the original paper, the length of the ACK train, but a duration between the 2-nd ACK of the train N and the first ACK of the train N+1. This will usually result in approximately one full RTT. Due to protection (now - ca->last_ack) <= hystart_ack_delta (2 ms) this would lead:
> - in sub 2 ms RTT networks to always too early exit (in the second round)
>              - in over 2 ms RTT networks to always too late exit (due to RTT > RTT/2 while  now - ca->last_ack) <= 2 ms when the HOL ACK of N+1 approaches tail ACK of N to less than 2 ms.
> Means that current implementation of HYSTART_ACK_TRAIN does not work as expected (did it ever ?).

+1

Would you submit a patch to netdev that fixes this?

It would be nice of you to fix tcp_cdg's HyStart as well. Just move
the call to tcp_cdg_hystart_update() a few lines:

diff --git a/net/ipv4/tcp_cdg.c b/net/ipv4/tcp_cdg.c
index 167b6a3..a02d944 100644
--- a/net/ipv4/tcp_cdg.c
+++ b/net/ipv4/tcp_cdg.c
@@ -264,9 +264,6 @@ static void tcp_cdg_cong_avoid(struct sock *sk,
u32 ack, u32 acked)
        u32 prior_snd_cwnd;
        u32 incr;

-       if (tcp_in_slow_start(tp) && hystart_detect)
-               tcp_cdg_hystart_update(sk);
-
        if (after(ack, ca->rtt_seq) && ca->rtt.v64) {
                s32 grad = 0;

@@ -282,6 +279,9 @@ static void tcp_cdg_cong_avoid(struct sock *sk,
u32 ack, u32 acked)
                        return;
        }

+       if (tcp_in_slow_start(tp) && hystart_detect)
+               tcp_cdg_hystart_update(sk);
+
        if (!tcp_is_cwnd_limited(sk)) {
                ca->shadow_wnd = min(ca->shadow_wnd, tp->snd_cwnd);
                return;

I set up a server<>client scenario with 1 sec OWD to verify.

Before the change, the last ACK of each round mistakenly gets a train
length of ~1 sec:
2231665.726383: tcp_cdg_cong_avoid: round 0 train_len 0 rtt_seq
1401191661 ack_seq 1401191685 sample_cnt 0
2231665.726408: tcp_cdg_cong_avoid: round 1 train_len 0 rtt_seq
1401204717 ack_seq 1401193133 sample_cnt 0
2231665.726415: tcp_cdg_cong_avoid: round 1 train_len 8 rtt_seq
1401204717 ack_seq 1401194581 sample_cnt 1
2231665.726424: tcp_cdg_cong_avoid: round 1 train_len 16 rtt_seq
1401204717 ack_seq 1401196029 sample_cnt 2
2231665.726429: tcp_cdg_cong_avoid: round 1 train_len 22 rtt_seq
1401204717 ack_seq 1401197477 sample_cnt 3
2231665.726502: tcp_cdg_cong_avoid: round 1 train_len 95 rtt_seq
1401204717 ack_seq 1401198925 sample_cnt 4
2231665.726516: tcp_cdg_cong_avoid: round 1 train_len 108 rtt_seq
1401204717 ack_seq 1401200373 sample_cnt 5
2231665.726521: tcp_cdg_cong_avoid: round 1 train_len 114 rtt_seq
1401204717 ack_seq 1401201821 sample_cnt 6
2231665.726528: tcp_cdg_cong_avoid: round 1 train_len 121 rtt_seq
1401204717 ack_seq 1401203269 sample_cnt 7
2231665.726577: tcp_cdg_cong_avoid: round 1 train_len 167 rtt_seq
1401204717 ack_seq 1401204717 sample_cnt 8
2231666.726340: tcp_cdg_cong_avoid: round 1 train_len 999932 rtt_seq
1401204717 ack_seq 1401206165 sample_cnt 8
2231666.726363: tcp_cdg_cong_avoid: round 2 train_len 0 rtt_seq
1401233677 ack_seq 1401207613 sample_cnt 0
2231666.726369: tcp_cdg_cong_avoid: round 2 train_len 6 rtt_seq
1401233677 ack_seq 1401209061 sample_cnt 1
...

After the change:
2231763.680223: tcp_cdg_cong_avoid: round 1 train_len 0 rtt_seq
4218529922 ack_seq 4218518338 sample_cnt 0
2231763.680232: tcp_cdg_cong_avoid: round 1 train_len 12 rtt_seq
4218529922 ack_seq 4218519786 sample_cnt 1
2231763.680240: tcp_cdg_cong_avoid: round 1 train_len 21 rtt_seq
4218529922 ack_seq 4218521234 sample_cnt 2
2231763.680315: tcp_cdg_cong_avoid: round 1 train_len 96 rtt_seq
4218529922 ack_seq 4218522682 sample_cnt 3
2231763.680328: tcp_cdg_cong_avoid: round 1 train_len 109 rtt_seq
4218529922 ack_seq 4218524130 sample_cnt 4
2231763.680333: tcp_cdg_cong_avoid: round 1 train_len 114 rtt_seq
4218529922 ack_seq 4218525578 sample_cnt 5
2231763.680339: tcp_cdg_cong_avoid: round 1 train_len 119 rtt_seq
4218529922 ack_seq 4218527026 sample_cnt 6
2231763.680345: tcp_cdg_cong_avoid: round 1 train_len 126 rtt_seq
4218529922 ack_seq 4218528474 sample_cnt 7
2231763.680387: tcp_cdg_cong_avoid: round 1 train_len 167 rtt_seq
4218529922 ack_seq 4218529922 sample_cnt 8
2231764.680125: tcp_cdg_cong_avoid: round 2 train_len 0 rtt_seq
4218558882 ack_seq 4218531370 sample_cnt 0
2231764.680151: tcp_cdg_cong_avoid: round 2 train_len 28 rtt_seq
4218558882 ack_seq 4218532818 sample_cnt 1
...