Subject: [quicwg/base-drafts] A pacing algorithm (#3630)

From: Martin Thomson <[email-masked]>
Date: Tue, 05 May 2020 22:19:36 -0700

This isn&#39;t code, because I don&#39;t think we need to do any more than point
at the leaky bucket algorithm, but it does provide more concrete advice
than we&#39;ve had.

It removes the reference to fqdisc as that isn&#39;t especially helpful, as
the original issue observes.

Closes #3122.
You can view, comment on, or merge this pull request online at:

  https://github.com/quicwg/base-drafts/pull/3630

-- Commit Summary --

  * A pacing algorithm

-- File Changes --

    M draft-ietf-quic-recovery.md (26)

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/3630.patch
https://github.com/quicwg/base-drafts/pull/3630.diff

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630

---

From: Martin Thomson <[email-masked]>
Date: Tue, 05 May 2020 22:25:59 -0700

@martinthomson pushed 1 commit.

561df07e9b817460e4006266af1e0acee19c0f8a  Forgot to include smoothed_rtt in the description

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630/files/f001162b89055fad7e837b6f2847277ff0f20177..561df07e9b817460e4006266af1e0acee19c0f8a

---

From: MikkelFJ <[email-masked]>
Date: Wed, 06 May 2020 04:40:27 -0700

Leaky bucket sidesteps the issue of shaping multiple streams, but I agree you do not need that level of detail here.

I don't understand the motivation for the N factor from a casual read. I guess it requires a deeper insight into the congestion controller. If it is a burst thing, it couldn't be for every interval `t[m]..t[n]`?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#issuecomment-624599432

---

From: Martin Thomson <[email-masked]>
Date: Wed, 06 May 2020 16:59:28 -0700

N exists to deal with the potential for the CWND to increase.  Let's say that you have a CWND of 10 packets and an RTT of 1 second.  If you pace evenly over that period, you will send one packet every 100ms.  If the CWND doubles, you want to send every 50ms instead, but that only starts from the point you apply the increase.  This allows you to send a little faster prior to the increase and not need to wait as long for the increase to take effect.

N also exists because timers are terrible and you don't want to lag, which would force the pacer to be an extra constraint on send rate.

Maybe that's too fancy and it should just be N is a number a little larger than 1.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#issuecomment-624952504

---

From: MikkelFJ <[email-masked]>
Date: Wed, 06 May 2020 17:38:38 -0700

So you are consuming the CNWD a bit too fast in anticipation of it growing before you run out and if it shrinks instead, I suppose you enter a period of silence because you over-consumed. But couldn't that also be detrimental? Perhaps more so unreliable transmission with a timing aspect.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#issuecomment-624963153

---

From: Martin Thomson <[email-masked]>
Date: Wed, 06 May 2020 17:54:13 -0700

The definition of the pacer should not ever limit the congestion window.  If the window collapses, then the cap on rate can apply the higher value.  I should make that clearer.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#issuecomment-624967165

---

From: Martin Thomson <[email-masked]>
Date: Wed, 06 May 2020 17:59:52 -0700

Oh, I went back to my code and found why I wanted N.  With the same example as before, you are sending 10 packets per second and the congestion window doubles.  If you apply the formula in one way, you can get some odd spikes in the rate.  Say that you measure over 10s (i.e., 100p/10s), and the rate doubles.  If you attempt to reach the new target in the next second (200p/10s), your send rate goes up by a factor of 10 briefly.  There is less incentive to do that sort of compensation if you have been sending at a higher rate previously.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#issuecomment-624968569

---

From: Martin Thomson <[email-masked]>
Date: Wed, 06 May 2020 18:05:19 -0700

a4b888eab05865e39b40e240bb3abf962f95de9b  Reword rationale somewhat

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630/files/561df07e9b817460e4006266af1e0acee19c0f8a..a4b888eab05865e39b40e240bb3abf962f95de9b

---

From: MikkelFJ <[email-masked]>
Date: Thu, 07 May 2020 01:25:49 -0700

I'm using exponential smoothing in other contexts: x  + (1 - x).

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#issuecomment-625108247

---

From: Martin Thomson <[email-masked]>
Date: Tue, 12 May 2020 15:51:21 -0700

@martinthomson commented on this pull request.

> @@ -897,9 +897,29 @@ congestion window, which is recommended to be the minimum of
 max_datagram_size is the current maximum size of a datagram for the connection,
 not including UDP or IP overhead.
 
-As an example of a well-known and publicly available implementation of a flow
-pacer, implementers are referred to the Fair Queue packet scheduler (fq qdisc)
-in Linux (3.11 onwards).
+Endpoints can implement pacing as they choose, as long as the rate of bytes
+sent over any interval, `t[n] - t[m]`, does not exceed a small multiple, `N`,
+of maximum value of the congestion window, `congestion_window`, averaged over
+the round trip time estimate, `smoothed_rtt`. Allowing for bursts produces the
+following relation for the total number of bytes sent over any interval:
+
+~~~
+sent@t[n] - sent@t[m]

```suggestion
number of bytes sent between t[m] and t[n]
```

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#pullrequestreview-410477097

---

From: Martin Thomson <[email-masked]>
Date: Tue, 12 May 2020 16:15:18 -0700

> +following relation for the total number of bytes sent over any interval:
+
+~~~
+sent@t[n] - sent@t[m]
+    <= N * congestion_window * (t[m] - t[n]) / smoothed_rtt
+       + min(10 * max_datagram_size,
+             max(2 * max_datagram_size, 14720))
+~~~
+
+The inclusion of the factor, `N`, that increases the rate of sending is to
+anticipate increases in sending rate as the congestion window expands. Sending
+at a higher rate also avoids having scheduling delays reduce the send rate
+below that allowed by the congestion controller. A value of 2 ensures that
+pacing is unlikely to limit what is sent any more than the congestion
+controller.
+

```suggestion

An endpoint that does not burst packets and has even spacing between packets
might send packets spaced at intervals of:

~~~
inter-packet time = smoothed_rtt * packet_size / congestion_window / N
~~~
```

> +The inclusion of the factor, `N`, that increases the rate of sending is to
+anticipate increases in sending rate as the congestion window expands. Sending
+at a higher rate also avoids having scheduling delays reduce the send rate
+below that allowed by the congestion controller. A value of 2 ensures that
+pacing is unlikely to limit what is sent any more than the congestion
+controller.

```suggestion
The inclusion of the factor, `N`, with a value of at least 1 increases the rate
of sending. The value of `N` might be increased to avoid having scheduling
delays reduce the send rate below that allowed by the congestion controller.
```

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#pullrequestreview-410481829

---

From: Martin Thomson <[email-masked]>
Date: Tue, 12 May 2020 16:15:56 -0700

b776f4d79e077017b718671b8362650a0b8e62bd  Using suggestions to edit

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630/files/a4b888eab05865e39b40e240bb3abf962f95de9b..b776f4d79e077017b718671b8362650a0b8e62bd

---

From: Martin Thomson <[email-masked]>
Date: Tue, 12 May 2020 16:16:21 -0700

> +number of bytes sent between t[m] and t[n]
+    <= N * congestion_window * (t[m] - t[n]) / smoothed_rtt
+       + min(10 * max_datagram_size,
+             max(2 * max_datagram_size, 14720))
+~~~
+
+The inclusion of the factor, `N`, with a value of at least 1 increases the rate
+of sending. The value of `N` might be increased to avoid having scheduling
+delays reduce the send rate below that allowed by the congestion controller.
+
+An endpoint that does not burst packets and has even spacing between packets
+might send packets spaced at intervals of:
+
+~~~
+inter-packet time = smoothed_rtt * packet_size / congestion_window / N
+~~~

```suggestion
~~~

```

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#pullrequestreview-410487013

---

From: Martin Thomson <[email-masked]>
Date: Tue, 12 May 2020 16:16:31 -0700

37eaf7e767121467227f3fbade7329a7d7b264f3  Add a blank line

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630/files/b776f4d79e077017b718671b8362650a0b8e62bd..37eaf7e767121467227f3fbade7329a7d7b264f3

---

From: Martin Thomson <[email-masked]>
Date: Tue, 12 May 2020 17:17:52 -0700

75791409cdeafdfdb429024dc1ced0ed104f8648  Shorter figure line

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630/files/37eaf7e767121467227f3fbade7329a7d7b264f3..75791409cdeafdfdb429024dc1ced0ed104f8648

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 13 May 2020 19:49:26 -0700

@janaiyengar commented on this pull request.

> @@ -897,9 +897,33 @@ congestion window, which is recommended to be the minimum of

I think this is all too much prescription. I suggest you move this up above the previous paragraph, and lead into the burst paragraphs like so: 

"Endpoints can implement pacing as they choose. A perfectly paced sender spreads bytes exactly evenly over time. For a window-based congestion controller, such as the one in this document, that rate can be computed by averaging the congestion window over the round-trip time. More precisely, `pacing rate = N * congestion_window / smoothed_rtt`, where using a small N (for example, 1.25) protects the sender from short-term variations in round-trip time or from scheduler delays.

Further practical considerations, such as packetization, scheduling delays, and computational efficiency, can cause a sender to deviate from this rate over time periods that are much shorter than a round-trip time. Sending multiple packets into the network without any delay ..."

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#pullrequestreview-411429547

---

From: Martin Thomson <[email-masked]>
Date: Wed, 13 May 2020 23:56:27 -0700

7ddcd1d53039f50f8050ec51912c086016407521  Trying to thread the needle

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630/files/75791409cdeafdfdb429024dc1ced0ed104f8648..7ddcd1d53039f50f8050ec51912c086016407521

---

From: Martin Thomson <[email-masked]>
Date: Wed, 13 May 2020 23:58:49 -0700

I've taken a little of each suggestion here.  I think that the difference between suggesting N=1.25 and N=2 is largely philosophical, so I don't want to get drawn on that.  The only constraints that matter is that it be small and >= 1.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#issuecomment-628430254

---

From: Martin Thomson <[email-masked]>
Date: Wed, 13 May 2020 23:59:46 -0700

954f037f641703d7566f024cc41755f24ef6ae2b  Fix

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630/files/7ddcd1d53039f50f8050ec51912c086016407521..954f037f641703d7566f024cc41755f24ef6ae2b

---

From: Jana Iyengar <[email-masked]>
Date: Thu, 14 May 2020 00:03:32 -0700

> +as the one in this document, that rate can be computed by averaging the
+congestion window over the round-trip time. Expressed as a rate in bytes:
+
+~~~
+rate = N * congestion_window / smoothed_rtt
+~~~
+
+Or, expressed as an inter-packet interval:
+
+~~~
+interval = smoothed_rtt * packet_size / congestion_window / N
+~~~
+
+Using a value for N that is small, but greater than 1 (for example, 1.25)
+ensures that short-term variations in round-trip time or scheduler delays don't
+result in not fully utilizing the congestion window.

```suggestion
result in under-utilization of the congestion window.
```

> +as the one in this document, that rate can be computed by averaging the
+congestion window over the round-trip time. Expressed as a rate in bytes:
+
+~~~
+rate = N * congestion_window / smoothed_rtt
+~~~
+
+Or, expressed as an inter-packet interval:
+
+~~~
+interval = smoothed_rtt * packet_size / congestion_window / N
+~~~
+
+Using a value for `N` that is small, but at least 1 (for example, 1.25) ensures
+that short-term variations in round-trip time or scheduler delays don't result
+in not fully utilizing the congestion window.

```suggestion
in under-utilization of the congestion window.
```

> @@ -897,9 +897,28 @@ congestion window, which is recommended to be the minimum of
 
-As an example of a well-known and publicly available implementation of a flow
-pacer, implementers are referred to the Fair Queue packet scheduler (fq qdisc)
-in Linux (3.11 onwards).
+Endpoints can implement pacing as they choose. A perfectly paced sender spreads

I would propose moving this paragraph up one, and adding this to the start of the previous paragraph: "Practical considerations, such as packetization, scheduling delays, and computational efficiency, can cause a sender to deviate from this rate over time periods that are much shorter than a round-trip time. Sending multiple packets into the network without any delay ..."

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#pullrequestreview-411514042

---

From: Martin Thomson <[email-masked]>
Date: Thu, 14 May 2020 00:20:20 -0700

dbc8ffcf3816c7c88ea997283e7c4ae06a0a2550  under-utilization

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630/files/954f037f641703d7566f024cc41755f24ef6ae2b..dbc8ffcf3816c7c88ea997283e7c4ae06a0a2550

---

From: Martin Thomson <[email-masked]>
Date: Thu, 14 May 2020 00:23:07 -0700

819f4d0d5710830a2e832acac8afa8e38c1439d6  Some editorial rearrangement

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630/files/dbc8ffcf3816c7c88ea997283e7c4ae06a0a2550..819f4d0d5710830a2e832acac8afa8e38c1439d6

---

From: Martin Thomson <[email-masked]>
Date: Thu, 14 May 2020 00:23:40 -0700

Will do.  I also noticed that that paragraph refined the initial congestion window, so I replaced the (re)definition with a section reference.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#discussion_r424922708

---

From: Jana Iyengar <[email-masked]>
Date: Thu, 14 May 2020 00:28:19 -0700

@janaiyengar approved this pull request.

Thanks for working through this! I'll wait for @ianswett to take a look.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#pullrequestreview-411532111

---

From: ianswett <[email-masked]>
Date: Sat, 16 May 2020 12:43:32 -0700

@ianswett commented on this pull request.

Some small suggestions, but this seems close.

> @@ -889,17 +889,36 @@ Timely delivery of ACK frames is important for efficient loss recovery. Packets
 containing only ACK frames SHOULD therefore not be paced, to avoid delaying
 their delivery to the peer.
 
-Sending multiple packets into the network without any delay between them
-creates a packet burst that might cause short-term congestion and losses.
-Implementations MUST either use pacing or limit such bursts to the initial
-congestion window, which is recommended to be the minimum of
-`10 * max_datagram_size` and `max(2 * max_datagram_size, 14720))`, where
-max_datagram_size is the current maximum size of a datagram for the connection,
-not including UDP or IP overhead.
-
-As an example of a well-known and publicly available implementation of a flow
-pacer, implementers are referred to the Fair Queue packet scheduler (fq qdisc)
-in Linux (3.11 onwards).
+Endpoints can implement pacing as they choose. A perfectly paced sender spreads
+bytes exactly evenly over time. For a window-based congestion controller, such

```suggestion
packets exactly evenly over time. For a window-based congestion controller, such
```

Given overheads, spreading bytes evenly is impractical.

> +bytes exactly evenly over time. For a window-based congestion controller, such

```suggestion
that variations in round-trip time don't result
```

I'd address the scheduler delay issue separately(also, 1.25x may not be enough to fix scheduler delay) and the variations in round trip time may not be short term(ie: a buffer draining).

+in under-utilization of the congestion window.

```suggestion
in under-utilization of the congestion window.  Values of 'N' larger than 1 result
in the sender being ack-clocked when the window is fully utilized and
acknowledgements arrive smoothly.
```

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#pullrequestreview-413102330

---

From: Martin Thomson <[email-masked]>
Date: Sun, 17 May 2020 16:59:42 -0700

42a1dd87ae1eb65da2a57d31a5e2212cc5b0c2fe  Some improvements from Ian

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630/files/819f4d0d5710830a2e832acac8afa8e38c1439d6..42a1dd87ae1eb65da2a57d31a5e2212cc5b0c2fe

---

From: ianswett <[email-masked]>
Date: Sun, 17 May 2020 17:19:08 -0700

@ianswett approved this pull request.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#pullrequestreview-413214981

---

From: Martin Thomson <[email-masked]>
Date: Sun, 17 May 2020 17:51:18 -0700

Not really comfortable with saying "ack-clocked" without a definition.  Can you say something else?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#discussion_r426319996

---

From: ianswett <[email-masked]>
Date: Sun, 17 May 2020 17:54:43 -0700

SG, I edited to no longer rely on the term ack-clocked.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#discussion_r426326259

---

From: Martin Thomson <[email-masked]>
Date: Sun, 17 May 2020 18:27:32 -0700

b0a1b1c0db25b4971df0078f14fe68bb50b5da9b  ack-clocking

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630/files/42a1dd87ae1eb65da2a57d31a5e2212cc5b0c2fe..b0a1b1c0db25b4971df0078f14fe68bb50b5da9b

---

From: Martin Thomson <[email-masked]>
Date: Sun, 17 May 2020 18:30:59 -0700

a320b5463d042d2cfdf6b20a2278025687670fe6  Reword ack-clocking again

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630/files/b0a1b1c0db25b4971df0078f14fe68bb50b5da9b..a320b5463d042d2cfdf6b20a2278025687670fe6

---

From: Martin Thomson <[email-masked]>
Date: Sun, 17 May 2020 18:31:12 -0700

I reflowed, then reworded to s/timer/alarm and explain a little more.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#issuecomment-629898522

---

From: ianswett <[email-masked]>
Date: Mon, 18 May 2020 02:58:21 -0700

I have one editorial change on top of this, but I'd like to do it separately.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#pullrequestreview-413445480

---

From: ianswett <[email-masked]>
Date: Mon, 18 May 2020 02:58:29 -0700

Merged #3630 into master.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3630#event-3346537527