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

From: Ingemar Johansson S <[email-masked]>
Date: Tue, 3 Nov 2015 13:18:34 +0000

Hi

Thanks for doing the experiments. 
It may be possible that HyStart may need more extensive modifications. 
Need to ask the dumb question first though. Is HYSTART_DELAY_MAX modified in your experiment or is it still 16ms ?
I guess HYSTART_DELAY_MAX may need to be set to 
    HYSTART_DELAY_MAX = MAX(16ms, HYSTART_DELAY_MIN*2) 
Or something similar, one can always argue around the factor 2 above.

/Ingemar

> -----Original Message-----
> From: Veaceslav ROMAN [mailto:[email-masked]]
> Sent: den 17 oktober 2015 22:48
> To: Neal Cardwell
> Cc: Eric Dumazet; Ingemar Johansson S; Eric Dumazet; [email-masked]; Piers
> O'Hanlon; Sangtae Ha; [email-masked]
> Subject: RE: [tcpm] [e2e] TCP HyStart patch deployment
> 
> Hi,
> Recompiled kernel to HYSTART_DELAY_MIN  20 ms:
> 
>   Download 10MB, High Bandwidths, HYSTART_DELAY_MIN  20 ms:
>            Hystart average download time: 1.18 s
>            NoHystart average download time: 1.00  s
> 
> No significant improvement against the case with HYSTART_DELAY_MIN  10
> ms.
> 
> Sill Hystart early exit is visible.
> 
> Other tests with HYSTART_DELAY_MIN  20 ms and files of 3MB.
> 
>   Download 3MB, High Bandwidths, HYSTART_DELAY_MIN  20 ms:
>            Hystart average download time: 0.47 s
>            NoHystart average download time: 0.39  s
> 
> compare with 4 ms
> 
>   Download 3MB, High Bandwidths, HYSTART_DELAY_MIN  4 ms:
>            Hystart average download time: 0.65 s
>            NoHystart average download time: 0.37  s
> 
> Few more comment: High Bandwidth is typically above 30-40 Mbps.
> For Low Bandwidth, when radio do not permit above 40 Mbps Hystart early
> exit does not have a significant impact. I do explain it with the fact that the
> minimum exit CWND for Hysstart is 29 which, for RTT of ~15ms (minimum
> possible in LTE and visible in majority of traces) leads to ~25 Mbps, so Hystart
> exit, at least, at 25 Mbps and then it takes not too long to cubic to reach 30-40
> Mbps.
> 
> Veaceslav Roman
> 
> -----Original Message-----
> From: Neal Cardwell [mailto:[email-masked]]
> Sent: Tuesday, 06 October 2015 04:06
> To: Veaceslav ROMAN
> Cc: Eric Dumazet; Ingemar Johansson S; Eric Dumazet; [email-masked]; Piers
> O'Hanlon; Sangtae Ha; [email-masked]
> Subject: Re: [tcpm] [e2e] TCP HyStart patch deployment
> 
> On Mon, Oct 5, 2015 at 6:07 PM, Veaceslav ROMAN
> <[email-masked]> wrote:
> > We've managed to recompile the kernel 4.1 with tcp_cubic
> HYSTART_DELAY_MIN  (10U<<3) , 10ms.
> > Well, we had time only for one test cycle, but results are very promising:
> >
> > Download 10MB, High Bandwidths, HYSTART_DELAY_MIN  10 ms:
> >            Hystart average download time: 1.16 s
> >            NoHystart average download time: 0.93  s
> ...
> >  Download 10MB, High Bandwidths, HYSTART_DELAY_MIN  4 ms:
> >            Hystart average download time: 1.42 s
> >            NoHystart average download time: 0.89  s
> 
> Thanks! That is very useful and interesting data. Would you be able to try a
> few other values, like 15ms and 20ms?
> 
> neal

---

From: Veaceslav ROMAN <[email-masked]>
Date: Tue, 3 Nov 2015 19:05:36 +0000

You are right, it wasn't modified and stayed at 16. Thank you for suggestion.
Currently we are trying to make an experimental version were this would be possible to make these parameters and few other things externally settable.

But, honestly, the further we dig in the code and traces the more the confusion and more questions arises.
	Hystart rely on correct identification of round borders. For this hystart_reset sets the border at snd_nxt. 
But, if several ACK arrive at high speed when the current round border is crossed and the sender has not time to transmit two packets immediately after ACK, then the snd_nxt does not progress and hystart_reset sets the round of the border to a pretty random value and then in the next round the hystart measure pieces of two rounds.
	Also, the code is calling hystart_update on each ACK before the hystart_reset, as a result at the border of rounds the head of line (HOL) ACK delay of round N+1 is accounted in the round N and, because, the HOL usually has less delay, it is frequently become delay_min but not in round N+1 and, as a result early exit in round N+1 after counting delays of packets 2 through 9. 
	This should also affect train detect as, when crossing the round border, instead of subtracting the time of the first and the last ACK of the train N there will be subtracted times of first ACK of train N and first ACK of the train N+1 which will be approximately equal to RTT and definitely bigger than RTT/2 as per expected algorithm. This shall typically lead to always exit in train 2. This will affect high speed networks with RTT less than hystart_ack_delta (2ms).
             Then call of hystart_reset is subject of check of several conditions like may_rise_cwnd or is_cwnd_limited, while it doesn't look that hystart_update is, so that it may become totally out of sync with round border.
 
	We are still doing efforts to try to find parameters which would make hystart better, but analysis of many traces make much impression of randomness of exit and not sure whether parameters may help. 

Veaceslav Roman

-----Original Message-----
From: Ingemar Johansson S [mailto:[email-masked]] 
Sent: Tuesday, 03 November 2015 15:19
To: Veaceslav ROMAN; Neal Cardwell
Cc: Eric Dumazet; Eric Dumazet; [email-masked]; Piers O'Hanlon; Sangtae Ha; [email-masked]; Ingemar Johansson S
Subject: RE: [tcpm] [e2e] TCP HyStart patch deployment

Hi

    HYSTART_DELAY_MAX = MAX(16ms, HYSTART_DELAY_MIN*2) Or something similar, one can always argue around the factor 2 above.

/Ingemar

> Cc: Eric Dumazet; Ingemar Johansson S; Eric Dumazet; [email-masked]; 
> Piers O'Hanlon; Sangtae Ha; [email-masked]
> For Low Bandwidth, when radio do not permit above 40 Mbps Hystart 
> early exit does not have a significant impact. I do explain it with 
> the fact that the minimum exit CWND for Hysstart is 29 which, for RTT 
> of ~15ms (minimum possible in LTE and visible in majority of traces) 
> leads to ~25 Mbps, so Hystart exit, at least, at 25 Mbps and then it 
> takes not too long to cubic to reach 30-40 Mbps.
> 
> Veaceslav Roman
> 
> Cc: Eric Dumazet; Ingemar Johansson S; Eric Dumazet; [email-masked]; 
> Piers O'Hanlon; Sangtae Ha; [email-masked]
> Thanks! That is very useful and interesting data. Would you be able to 
> try a few other values, like 15ms and 20ms?
> 
> neal

---

From: Veaceslav ROMAN <[email-masked]>
Date: Tue, 17 Nov 2015 21:04:48 +0000

Hi
Still experimenting with Hystart in LTE by trying different parameters for HYSTART_DELAY_MIN and HYSTART_DELAY_MAX.
In an attempt to easy the testing we've modified the 4.1.10 kernel to make these parameters externally modifiable plus an attempt is done to fix what I do perceive as a significand deviation of implementation from the original idea of Hystart, which, in my view, does have a negative impact, especially in networks with high throughput and delay variability, like radio networks. 
Unfortunately 4.1.10 was very unstable, server frequently freezing and, not completely unsure, whether this is due to the kernel of due to modified code. No kernel development experience here.
Anyway we decided to move to 3.19.0-33 and we try currently to recompile. 
I will be grateful if someone can  review the code in the link bellow, at least to check if these modification are not illegal from the kernel point of view. 

https://drive.google.com/open?id=0BwRC1qzsBK0kYS1JSnlIaWJ4SE0

Two source files modified:  inet_connection_sock.h and tcp_cubic.c.

Inet_connection_sock.h is modified with the purpose to extend the size of the icsk_ca_priv in struct inet_connection_sock  to accommodate two more u32 variables in the struct bictcp in tcp_cubic.c.

Tcp_cubic.c is modified in such a way that:
	1. it become possible to modify by using module parameters the value of what in the current implementations are constants: HYSTART_DELAY_MIN and HYSTART_DELAY_MAX. They are replaced with two module parameters hystart_delay_min and hystart_delay_max.
	2. the current algorithm of Hystart,  where the function hystart_update is called before function hystart_reset is kept, but also is introduced an alternative algorithm, where hystart_update is called after hystart_reset, as in my view, corresponds to the original idea and logic. Algorithm to use can be selected by using the new module parameter hystart_new. An additional member in the struct bictcp u32 delay use to store the current delay calculated in function bictcp_acked for function bictcp_cong_avoid which calls  hystart_reset and then hystart_update with parameter delay.
             3. the current algorithm of Hystart HYSTART_DELAY does compare delay_min of the 8 packets of the round with the curr_rtt, so, while the original idea supposed to compare with the delay_min of the previous round. Here this alternative is added and it can be selected by module  parameter hystart_delay_new.  An additional member in the struct bictcp  u32 prev_round_delay_min use to store the previous round delay_min to be used in comparison in the current round.

In this code, the default module parameters are: hystart_delay_min=4 (ms), hystart_delay_max=16 (ms) (parameters values in ms, no need to <<3 parameters, this is done in the code), hystart_new=1, corresponding to the hysart_reset called before hystart_update,  hystart_delay_new=1 corresponding to comparison of the current first 8 RTT with the delay_min of the previous round. To have the algorithm behaving like in the current standard implementation one do need to set the hystart_new=0 and hystart_delay_new=0.

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

HYSTART_DELAY also suffers due to this shift: the first ACK of the train N+1 will not be accounted in the round N+1 but have chances to become a new delay_min (as usual HOL have less RTT then following packets), while, following ACK 2...9 of the round N+1 have bigger chances to exceed the delay_min, even though, would the ACK No 1 be accounted in round N+1, this exit from Hystart will not take place. For the radio networks, with high variability of throughput and delay and scheduling delay this might be critical and, many traces shows this is critical in LTE.

For the current implementation comparison in  HYSTART_DELAY of the minimum of the delay of the 8 packets at the beginning of the round (No 2...9, or, if fixed, No 1...8) with the delay after these 8 ACK look and exit if following ACK has lower RTT looks to me not totally logical: if, the RTT at the end of the round become lower than RTT at the beginning of the round that can only mean that link gained additional performance (either the queue decreased or throughput increase, or both, they are interrelated). Isn't it more logical to let the slow start to probe more for this additional capacity instead of breaking it exactly at this moment ?

Probably, these considerations, induced only by tests in one type of network (LTE)  and analysis of the code by not a professional kernel might be not totally correct, but I will appreciate any comments, and mostly suggestion for improvement which may help to improve the algorithm.
   
The few tests done in (unstable) modified 4.1.10 shown signs of good results, but we are going to perform extensive tests with 3.19.  

Veaceslav Roman

-----Original Message-----
From: Veaceslav ROMAN 
Sent: Tuesday, 03 November 2015 21:06
To: 'Ingemar Johansson S'; Neal Cardwell
Cc: Eric Dumazet; Eric Dumazet; [email-masked]; Piers O'Hanlon; Sangtae Ha; [email-masked]
Subject: RE: [tcpm] [e2e] TCP HyStart patch deployment

 

Veaceslav Roman

-----Original Message-----
From: Ingemar Johansson S [mailto:[email-masked]]
Sent: Tuesday, 03 November 2015 15:19
To: Veaceslav ROMAN; Neal Cardwell
Cc: Eric Dumazet; Eric Dumazet; [email-masked]; Piers O'Hanlon; Sangtae Ha; [email-masked]; Ingemar Johansson S
Subject: RE: [tcpm] [e2e] TCP HyStart patch deployment

Hi

/Ingemar

---

From: Eric Dumazet <[email-masked]>
Date: Tue, 17 Nov 2015 14:48:12 -0800

> Anyway we decided to move to 3.19.0-33 and we try currently to recompile. 

v-4.1.13 should be stable, 4.1.10 had tcp bugs.

---

From: Veaceslav ROMAN <[email-masked]>
Date: Wed, 18 Nov 2015 07:37:19 +0000

Thank you.
I will give a try to 3.19 then move to 4.1.13.

Veaceslav Roman
Technical and IT director
Orange Moldova S.A.
Fix: +37322575400
Mob: +37369198400
Fax: +37322575306