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

From: Ingemar Johansson S <[email-masked]>
Date: Tue, 30 Aug 2016 07:02:33 +0000

Hi

An old thread resumed from our side as we see issues with the HyStart algorithm in Cubic when we evaluate some new LTE and 5G access concepts. 
One problem is the packet train algorithm : I understand that it does not work well with packet pacing and is therefore disabled in QUIC. Is the packet train algorithm used in general, I guess not in the cases when packet pacing is enabled or ?

The other problem is the delay algorithm, my impression based on limited simulation experiments is that the HYSTART_DELAY_MIN needs to be set to ~16ms to avoid that HyStart exits prematurely. The question is if this causes problem with other access types (DSL ?)

Comments welcome 
/Ingemar

> -----Original Message-----
> From: Veaceslav ROMAN [mailto:[email-masked]]
> Sent: den 3 november 2015 20:06
> To: Ingemar Johansson S <[email-masked]>; Neal
> Cardwell <[email-masked]>
> Cc: Eric Dumazet <[email-masked]>; Eric Dumazet
> <[email-masked]>; [email-masked]; Piers O'Hanlon
> <[email-masked]>; Sangtae Ha <[email-masked]>; end2end-
> [email-masked]
> Subject: RE: [tcpm] [e2e] TCP HyStart patch deployment
> 
> 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
> 
> 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: Neal Cardwell <[email-masked]>
Date: Tue, 30 Aug 2016 10:00:24 -0400

Hi,

As one data point, at Google the google.com and YouTube TCP stacks use
Eric Dumazet's fq pacing qdisc:
  https://www.ietf.org/proceedings/88/slides/slides-88-tcpm-9.pdf
  https://lwn.net/Articles/564978/
Eric discovered that the Hystart Ack Train mechanism does not work
well with pacing, so for TCP at Google we have long ago disabled the
Hystart Ack Train mechanism, and just use the delay mechanism.

It is also our experience that the Hystart delay mechanism often
triggers spuriously for cellular and wifi links, and is difficult to
tune in a way that works well generally. It may be useful for someone
in the community to do a broad investigation to see if there are
HYSTART_DELAY_MIN,  HYSTART_DELAY_MAX, and threshold ratio values that
work better than the current values across a variety of important
last-mile technologies (cellular, cable, DSL, wifi,...).

neal