Subject: [iccrg] Paced Chirping for a fast slow-start with tiny queue

From: Bob Briscoe <[email-masked]>
Date: Thu, 19 Jul 2018 10:36:17 -0400

ICCRG, TCP Prague list,

Joakim Misund and I have been working on the 'TCP Prague requirements' 
to improve the acceleration of DCTCP. without losing its tiny queue.

The solution we've come up with seems applicable to general Internet 
usage, not just DCTCP / TCP Prague, cos it's solely delay-based.

Joakim has open-sourced his code, so you can all try it / build on it / 
bash it.

Here's the slides we shall be presenting in ICCRG in a few hours:
https://riteproject.files.wordpress.com/2018/07/1807paced-chirps.pdf
Joakim's Master's Thesis:
https://riteproject.files.wordpress.com/2018/07/misundjoakimmastersthesissubmitted180515.pdf
Source code over Linux v4.13 kernel
     https://github.com/JoakimMisund/PacedChirping

All are available via respectively:
     https://riteproject.eu/dctth/#presentations
     https://riteproject.eu/dctth/#papers
     https://riteproject.eu/dctth/#code

Bob

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

---

From: Mikael Abrahamsson <[email-masked]>
Date: Fri, 20 Jul 2018 13:37:13 +0200 (CEST)

> usage, not just DCTCP / TCP Prague, cos it's solely delay-based.

This chirping proposal seems promising. It seems to be a nice fit for 
"slowish" connections with proper queuing, but it might give the wrong 
result for connections where there is for instance a fast access medium, 
but a token bucket L3 policer with large burst sizes configured (this is 
not uncommon).

One idea could also be to detect "reverse chirping", ie to detect networks 
that does coalescing of packets (DOCSIS / mobile networks). It's hard to 
detect sub-millisecond events if the network does millisecond quantums on 
the access layer. This chirping, at approximately what intervals would it 
happen? Also, with all the offload that NICs to nowadays both for tx and 
rx directions, how much information is available to the IP stack?

Another thing, I remember quite a lot of discussions about TCP IW10. Can't 
some information be gleaned off of the initial burst of packets, ie to see 
at what temporal spacing these are arriving? If the sender sends an 
initial burst (which I guess is the same thing as a chirp), can't at least 
some information be gathered from knowing the timestamps of this? Or is 
that already done?

-- 
Mikael Abrahamsson    email: [email-masked]

---

From: Yuchung Cheng <[email-masked]>
Date: Fri, 20 Jul 2018 13:43:20 -0700

Hi Bob,

On Thu, Jul 19, 2018 at 7:36 AM, Bob Briscoe <[email-masked]>
wrote:

> ICCRG, TCP Prague list,
>
> Joakim Misund and I have been working on the 'TCP Prague requirements' to
> improve the acceleration of DCTCP. without losing its tiny queue.
>

Paced-chirping looks very interesting -  have you or Joakim compared that
w/ paced-slow-start (e.g. slow-start w/ fq-pacing)?

> _______________________________________________
> iccrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/iccrg
>

---

From: Bob Briscoe <[email-masked]>
Date: Fri, 20 Jul 2018 20:48:00 -0400

Yuchung,

On 20/07/18 16:43, Yuchung Cheng wrote:
> Paced-chirping looks very interesting -  have you or Joakim compared 
> that w/ paced-slow-start (e.g. slow-start w/ fq-pacing)?

Yes.

We included a spare slide to the pack presented in ICCRG, showing the 
comparison with BBR. I think it's the last slide in the set.
https://riteproject.files.wordpress.com/2018/07/1807paced-chirps.pdf 
<https://riteproject.files.wordpress.com/2018/07/1807paced-chirps..pdf>
However, it's the same plot we sent to you and Neal beforehand - based 
on v4.13 kernel. We didn't get time to update to a later kernel as Neal 
advised.
 From the BBR changes Neal described since then, I think a later kernel 
will not change the left hand plot (without a background flow) but it 
will change the right-hand plot (with a background flow).

You might have heard me trying to explain in ICCRG that the intuition 
from paced chirping shows that constant-rate pacing seems to be 
precisely the wrong thing to do during slow-start. As you increase the 
pacing rate, you get zero information about the capacity (other than 
that you are below it), even if slightly below (unless there are short 
flows dithering the queue). {Note 1} However, as soon as you pace even 
slightly over capacity, you build a queue over a round trip. Obviously 
with probes you can mitigate this, which is why we chirping multiple 
times per RTT.

We have a short Paced Chirping paper under submission with comparison 
plots (FCT and queue delay) against hystart as well as DCTCP (and we 
also have comparisons against slow-start without hystart that we 
couldn't fit in the paper). If you want a copy, just ask.

All these comparisons show that existing solutions either focus on 
throughput (BBR or hystart) or queuing harm (DCTCP), while Paced 
Chirping does as well as the best at both, and it can get up to speed 
even faster than the fastest state-of-the-art when it measures that it's 
safe to do so.

Bob

PS. Many caveats (see slides). It might all end in tears, so don't get 
too excited. Just proving the concept at this stage.

{Note 1}: There's already a paper saying this. I'm offline travelling 
home, so I can't remember the details - from memory I think it was 
Joanna Kulik's work.

---

From: Bob Briscoe <[email-masked]>
Date: Fri, 20 Jul 2018 21:09:46 -0400

Mikael,

On 20/07/18 07:37, Mikael Abrahamsson wrote:
>> Joakim Misund and I have been working on the 'TCP Prague 
>> requirements' to improve the acceleration of DCTCP. without losing 
>> its tiny queue.
>>
> result for connections where there is for instance a fast access 
> medium, but a token bucket L3 policer with large burst sizes 
> configured (this is not uncommon).
>
> One idea could also be to detect "reverse chirping", ie to detect 
> networks that does coalescing of packets (DOCSIS / mobile networks). 
> It's hard to detect sub-millisecond events if the network does 
> millisecond quantums on the access layer. 
[BB] Very much aware of this problem, given with my other hat on I'm 
working for CableLabs. We are working on this - paced chirping filters 
noise intra-chirp and inter-chirp, but it might also be necessary to 
actively detect particular types of links like you suggest - I prefer a 
general solution tho.

> This chirping, at approximately what intervals would it happen? 
[BB] The intervals are spread around an average interval expected to 
fill available capacity. The experiments we showed use a constant chirp 
geometry of 2, which spreads the interval between about 180% and 20% of 
the average. The maths is fairly simple arithmetic series stuff - see 
Joakim's thesis.

We have tried naive variation of the chirp geometry (ie vary the spread) 
depending on the consistency between previous measurements. Limited time 
so far for experimentation in that space, but this is where we are 
focusing to solve this problem.

> Also, with all the offload that NICs to nowadays both for tx and rx 
> directions, how much information is available to the IP stack?
[BB] Bear in mind this is /research/ to prove a concept. We know 
engineering will be needed to realize it, but that will only happen if 
there is initial motivation from a promising solution.

An example of how this works: VJ's talk in netdev last week to encourage 
NIC vendors to implement timing wheels in hardware.

>
> Another thing, I remember quite a lot of discussions about TCP IW10. 
> Can't some information be gleaned off of the initial burst of packets, 
> ie to see at what temporal spacing these are arriving? If the sender 
> sends an initial burst (which I guess is the same thing as a chirp), 
> can't at least some information be gathered from knowing the 
> timestamps of this? Or is that already done?
>
[BB] Indeed, the first round is where you get the closed loop started, 
so critical to construct the packet gaps in the first round to get max 
info for the second. You might have some prior cached info, but if you 
don't it's tough to guess the spread and the centre of the spread of 
intervals to get the most from the next round.

...also without blowing the queue from the start. We split the first 
round in two, but even that causes a compromise if the flow ends during 
the IW - it has  ended up adding up to half an RTT of delay 
unnecessarily (if we knew the size of the flow before starting it would 
help, of course).

Bob

---

From: Hesham ElBakoury <[email-masked]>
Date: Sat, 21 Jul 2018 03:53:17 +0000

Hi Bob,
I could not download the file using this link:     https://riteproject.files.wordpress.com/2018/07/1807paced-chirps.pdf<https://riteproject.files.wordpress.com/2018/07/1807paced-chirps..pdf>

Hesham

From: iccrg [mailto:[email-masked]] On Behalf Of Bob Briscoe
Sent: Friday, July 20, 2018 5:48 PM
To: Yuchung Cheng <ycheng=[email-masked]>
Cc: Joakim Misund <[email-masked]>; iccrg IRTF list <[email-masked]>
Subject: Re: [iccrg] Paced Chirping for a fast slow-start with tiny queue

Yuchung,
On 20/07/18 16:43, Yuchung Cheng wrote:
Paced-chirping looks very interesting -  have you or Joakim compared that w/ paced-slow-start (e.g. slow-start w/ fq-pacing)?

Yes.

We included a spare slide to the pack presented in ICCRG, showing the comparison with BBR. I think it's the last slide in the set.
    https://riteproject.files.wordpress.com/2018/07/1807paced-chirps.pdf<https://riteproject.files.wordpress.com/2018/07/1807paced-chirps..pdf>
However, it's the same plot we sent to you and Neal beforehand - based on v4.13 kernel. We didn't get time to update to a later kernel as Neal advised.
From the BBR changes Neal described since then, I think a later kernel will not change the left hand plot (without a background flow) but it will change the right-hand plot (with a background flow).

You might have heard me trying to explain in ICCRG that the intuition from paced chirping shows that constant-rate pacing seems to be precisely the wrong thing to do during slow-start. As you increase the pacing rate, you get zero information about the capacity (other than that you are below it), even if slightly below (unless there are short flows dithering the queue). {Note 1} However, as soon as you pace even slightly over capacity, you build a queue over a round trip. Obviously with probes you can mitigate this, which is why we chirping multiple times per RTT.

We have a short Paced Chirping paper under submission with comparison plots (FCT and queue delay) against hystart as well as DCTCP (and we also have comparisons against slow-start without hystart that we couldn't fit in the paper). If you want a copy, just ask.

All these comparisons show that existing solutions either focus on throughput (BBR or hystart) or queuing harm (DCTCP), while Paced Chirping does as well as the best at both, and it can get up to speed even faster than the fastest state-of-the-art when it measures that it's safe to do so.

Bob

PS. Many caveats (see slides). It might all end in tears, so don't get too excited. Just proving the concept at this stage.

{Note 1}: There's already a paper saying this. I'm offline travelling home, so I can't remember the details - from memory I think it was Joanna Kulik's work.

--

---

From: Bob Briscoe <[email-masked]>
Date: Sat, 21 Jul 2018 22:48:59 +0100

Hesham,

Here's the link I put in my original email, which works:
https://riteproject.files.wordpress.com/2018/07/1807paced-chirps.pdf

The destination of the link I put in my second email about this somehow 
ended with ..pdf (two full-stops), although the human-readable text of 
the hyperlink was correct. Sorry about that.

Bob

On 21/07/18 04:53, Hesham ElBakoury wrote:
>
> Hi Bob,
>
> I could not download the file using this link: 
> *From:*iccrg [mailto:[email-masked]] *On Behalf Of *Bob Briscoe
> *Sent:* Friday, July 20, 2018 5:48 PM
> *To:* Yuchung Cheng <ycheng=[email-masked]>
> *Cc:* Joakim Misund <[email-masked]>; iccrg IRTF list 
> <[email-masked]>
> *Subject:* Re: [iccrg] Paced Chirping for a fast slow-start with tiny 
> queue
>
> Yuchung,
>
>     Paced-chirping looks very interesting -  have you or Joakim
>     compared that w/ paced-slow-start (e.g. slow-start w/ fq-pacing)?
>
>
> Yes.
>
> on v4.13 kernel. We didn't get time to update to a later kernel as 
> Neal advised.
> even faster than the fastest state-of-the-art when it measures that 
> it's safe to do so.
>
>
>
>
> Bob
>
> Bob Briscoehttp://bobbriscoe.net/
>
>

---

From: Hesham ElBakoury <[email-masked]>
Date: Sat, 21 Jul 2018 22:12:42 +0000

Thanks Bob!
It works.
Hesham

From: Bob Briscoe [mailto:[email-masked]]
Sent: Saturday, July 21, 2018 2:49 PM
To: Hesham ElBakoury <[email-masked]>; Yuchung Cheng <ycheng=[email-masked]>
Cc: Joakim Misund <[email-masked]>; iccrg IRTF list <[email-masked]>
Subject: Re: [iccrg] Paced Chirping for a fast slow-start with tiny queue

Hesham,

The destination of the link I put in my second email about this somehow ended with ..pdf (two full-stops), although the human-readable text of the hyperlink was correct. Sorry about that.

Bob

Hesham

From: iccrg [mailto:[email-masked]] On Behalf Of Bob Briscoe
Sent: Friday, July 20, 2018 5:48 PM
To: Yuchung Cheng <ycheng=[email-masked]><mailto:ycheng=[email-masked]>
Cc: Joakim Misund <[email-masked]><mailto:[email-masked]>; iccrg IRTF list <[email-masked]><mailto:[email-masked]>
Subject: Re: [iccrg] Paced Chirping for a fast slow-start with tiny queue

Yuchung,

Yes.

Bob

--

iccrg mailing list

[email-masked]<mailto:[email-masked]>

--

---

From: Bob Briscoe <[email-masked]>
Date: Sun, 22 Jul 2018 12:03:33 +0100

Yuchung,

Now I'm online again, I've added the paper that Joakim found about paced 
slow-start with shallow buffers below. My memory was right; it was 
Joanna Kulik's - pre Google, when she was at BBN.

> home, so I can't remember the details - from memory I think it was 

Kulik, J., Coulter, R., Rockwell, D. & Partridge, C., "A simulation 
study of paced TCP," NASA Technical Report NASA/CR-2000-209416, NAS 
1.26:209416, E-12041 (January 2000)

Bob

---

From: Christian Huitema <[email-masked]>
Date: Sun, 22 Jul 2018 16:33:10 +0200

The other reference that comes to mind is packet pair flow control (http://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/95/pp.pdf). The trains of 8 packets in the chirping proposal are of course more elaborate than basic packet pair, but the principle seems very similar.

-- Christian Huitema 

> On Jul 22, 2018, at 1:03 PM, Bob Briscoe <[email-masked]> wrote:
> 
> Yuchung,
> 
> Now I'm online again, I've added the paper that Joakim found about paced slow-start with shallow buffers below. My memory was right; it was Joanna Kulik's - pre Google, when she was at BBN.
> 
> Kulik, J., Coulter, R., Rockwell, D. & Partridge, C., "A simulation study of paced TCP," NASA Technical Report NASA/CR-2000-209416, NAS 1.26:209416, E-12041 (January 2000)
> 
> 
> Bob
> 
> 
> --

---

From: Bob Briscoe <[email-masked]>
Date: Sun, 22 Jul 2018 23:25:22 +0100

Chirping was introduced in the pathchirp tool to overcome the 
deficiencies of packet pair.

Joakim's Masters Thesis 
<https://riteproject.files.wordpress.com/2018/07/misundjoakimmastersthesissubmitted180515.pdf> 
outlines all the research into the problems with packet-pair and the 
attempts to find better approaches, as you would expect from a good thesis.

Bob

On 22/07/18 15:33, Christian Huitema wrote:
> The other reference that comes to mind is packet pair flow control 
> (http://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/95/pp.pdf). 
> The trains of 8 packets in the chirping proposal are of course more 
> elaborate than basic packet pair, but the principle seems very similar.
>
> -- Christian Huitema
>
> On Jul 22, 2018, at 1:03 PM, Bob Briscoe <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>> Yuchung,
>>
>> Now I'm online again, I've added the paper that Joakim found about 
>> paced slow-start with shallow buffers below. My memory was right; it 
>> was Joanna Kulik's - pre Google, when she was at BBN.
>>
>>> You might have heard me trying to explain in ICCRG that the 
>>> intuition from paced chirping shows that constant-rate pacing seems 
>>> to be precisely the wrong thing to do during slow-start. As you 
>>> increase the pacing rate, you get zero information about the 
>>> capacity (other than that you are below it), even if slightly below 
>>> (unless there are short flows dithering the queue). {Note 1} 
>>> However, as soon as you pace even slightly over capacity, you build 
>>> a queue over a round trip. Obviously with probes you can mitigate 
>>> this, which is why we chirping multiple times per RTT.
>>>
>>> {Note 1}: There's already a paper saying this. I'm offline 
>>> travelling home, so I can't remember the details - from memory I 
>>> think it was Joanna Kulik's work.
>>
>> [email-masked] <mailto:[email-masked]>

---

From: Christian Huitema <[email-masked]>
Date: Mon, 23 Jul 2018 08:22:05 +0200

> On Jul 23, 2018, at 12:25 AM, Bob Briscoe <[email-masked]> wrote:
> 
> Chirping was introduced in the pathchirp tool to overcome the deficiencies of packet pair.
> 
> Joakim's Masters Thesis outlines all the research into the problems with packet-pair and the attempts to find better approaches, as you would expect from a good thesis.
> 
> 
> Bob
> 
Actually, I did not find a discussion of chirps vs packet pairs in the master thesis. I also did not find Keshav's paper in the reference.

-- Christian Huitema

---

From: Bob Briscoe <[email-masked]>
Date: Mon, 23 Jul 2018 19:13:27 +0100

Christian,

No, sorry, the packet pair paper is not specifically cited, 'cos he 
cites the paper by Devrolis that compares packet pair and packet train. 
See the whole of S.5.2 of the thesis, which summarizes the Devrolis paper.

Bob

On 23/07/18 07:22, Christian Huitema wrote:
>
> On Jul 23, 2018, at 12:25 AM, Bob Briscoe <[email-masked] 
> Actually, I did not find a discussion of chirps vs packet pairs in the 
> master thesis. I also did not find Keshav's paper in the reference.
>
> -- Christian Huitema
>
>

---

From: Yuchung Cheng <[email-masked]>
Date: Tue, 24 Jul 2018 17:58:09 -0700

> <https://riteproject.files.wordpress.com/2018/07/1807paced-chirps..pdf>
Bob: I was not asking about BBR. I was asking about comparing these three
1. plain classic slow start, i.e. dctcp w/o fq/pacing
2. paced slow-start i.e. dctcp w/ fq-pacing
3. paced-chirping i.e. dctcp w/ pace-chirping

Please correct me if I am wrong but it seems the slides are about 1 vs 3?

Comparing BBR is nice but BBR startup mode is slightly different. So for
more apple-to-apple it'd be good to use same C.C. but different startups

>
> However, it's the same plot we sent to you and Neal beforehand - based on
> v4.13 kernel. We didn't get time to update to a later kernel as Neal
> advised.
> will not change the left hand plot (without a background flow) but it will
> change the right-hand plot (with a background flow).
>
> You might have heard me trying to explain in ICCRG that the intuition from
> paced chirping shows that constant-rate pacing seems to be precisely the
> wrong thing to do during slow-start. As you increase the pacing rate, you
> get zero information about the capacity (other than that you are below it),
> even if slightly below (unless there are short flows dithering the queue).
> {Note 1} However, as soon as you pace even slightly over capacity, you
> build a queue over a round trip. Obviously with probes you can mitigate
> plots (FCT and queue delay) against hystart as well as DCTCP (and we also
> have comparisons against slow-start without hystart that we couldn't fit in
> the paper). If you want a copy, just ask.
>
> throughput (BBR or hystart) or queuing harm (DCTCP), while Paced Chirping
> does as well as the best at both, and it can get up to speed even faster
> than the fastest state-of-the-art when it measures that it's safe to do so.
>
>
>
>
> Bob
>
> PS. Many caveats (see slides). It might all end in tears, so don't get too
> excited. Just proving the concept at this stage.
>
> home, so I can't remember the details - from memory I think it was Joanna
> Kulik's work.
>
>
> --

---

From: Emmanuel Lochin <[email-masked]>
Date: Mon, 30 Jul 2018 12:11:41 +0200

Dear Bob, all,

This solution remembers me RAPID : Vishnu Konda et al. "RAPID: Shrinking 
the Congestion-control Timescale". In Proc. IEEE INFOCOM IEEE, 2009. 
Note that the authors did recent experiments within GNU/Linux kernel : 
"TCP Rapid: From Theory to Practice", their work is available here: 
http://www.cs.unc.edu/~jasleen/papers/infocom17.pdf

EL

Le 23/07/2018 à 20:13, Bob Briscoe a écrit :
> cites the paper by Devrolis that compares packet pair and packet 
> train. See the whole of S.5.2 of the thesis, which summarizes the 
> Devrolis paper.
>
>
> Bob
>
>> Actually, I did not find a discussion of chirps vs packet pairs in 
>> the master thesis. I also did not find Keshav's paper in the reference.
>>
>> -- Christian Huitema
>>
>>

-- 
Emmanuel LOCHIN
Professeur ISAE
ISAE SUPAERO - Institut Supérieur de l'Aéronautique et de l'Espace
10 avenue Edouard Belin - BP 54032 - 31055 TOULOUSE CEDEX 4 FRANCE -
http://www.isae-supaero.fr
Tel +33 5 61 33 84 85 - Fax (+33) 5 61 33 83 45
Web : http://personnel.isae.fr/emmanuel-lochin/