Subject: [quicwg/base-drafts] Another pacing algorithm (#3655)

From: ianswett <[email-masked]>
Date: Wed, 13 May 2020 15:53:52 -0700

This is based on @martinthomson #3630, but my suggestions were so large I created a new PR.

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

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

-- Commit Summary --

  * Another pacing algorithm

-- File Changes --

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

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/3655.patch
https://github.com/quicwg/base-drafts/pull/3655.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/3655

---

From: ianswett <[email-masked]>
Date: Wed, 13 May 2020 15:55:14 -0700

@ianswett pushed 1 commit.

d6ab1c7712de890c7f18062ef04991476b513927  Update draft-ietf-quic-recovery.md

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

---

From: ianswett <[email-masked]>
Date: Wed, 13 May 2020 15:59:47 -0700

9ee95e1bf7ed80f3dea4c7490fe3c0986aa41f24  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3655/files/d6ab1c7712de890c7f18062ef04991476b513927..9ee95e1bf7ed80f3dea4c7490fe3c0986aa41f24

---

From: ianswett <[email-masked]>
Date: Wed, 13 May 2020 16:01:04 -0700

abfdd75ba37e63e91297b8ae26071cb40304c47f  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3655/files/9ee95e1bf7ed80f3dea4c7490fe3c0986aa41f24..abfdd75ba37e63e91297b8ae26071cb40304c47f

---

From: ianswett <[email-masked]>
Date: Wed, 13 May 2020 16:03:53 -0700

888ea2d281773409c44bf30de4ae29ae112363d9  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3655/files/abfdd75ba37e63e91297b8ae26071cb40304c47f..888ea2d281773409c44bf30de4ae29ae112363d9

---

From: Martin Thomson <[email-masked]>
Date: Wed, 13 May 2020 18:30:55 -0700

@martinthomson commented on this pull request.

I'm ok with either this or the other one.

> +exceed a small multiple, `pacing_gain`, of the congestion window. Larger
+bursts can reduce CPU utilization at the risk of increased retransmits rates.

This last sentence seems a little disconnected from the rest.  A small tweak might might help:

```suggestion
exceed a small multiple, `pacing_gain`, of the congestion window. Endpoints can
trade off sending packets in bursts, which might be done to reduce CPU
utilization, against even pacing, which has a lower risk of inducing packet
loss.
```

> +A `pacing_gain` multiplier greater than 1 allows senders to increase the rate
+of sending. The value of `pacing_gain` might be larger in slow start than
+congestion avoidance to ensure the sender is able to double its congestion
+window every round trip.

There are two reasons.  As the window increases, the rate increases, so you only really need this gain to a) anticipate future increases and b) avoid having scheduling delays eat into your send rate.

The future increases thing is worth noting.  Pacing causes packets to be spaced out over time, and you won't be able to realize an increase in congestion window until an entire round trip has passed if pacing_gain is 1.  Whereas if pacing_gain is matched to the rate of increase in the window, you are already sending at the increased rate, so you never have to worry about the pacer being the cause of you not sending enough.

@janaiyengar argued that you don't need to worry about this effect.  I think that it's worth compensating for, at least partially.  With pacing, increases to the window will be continuous, or at least multiple times per round trip time, so the degree to which your pacer drags your send rate down is based on the rate of updates (i.e., ACKs) you get.

This is a stair-step function bounded by a straight line (well, a logarithm, but just change conceptually to a log vertical scale).  The steps happen as you get ACKs (or timer pops), so the amount you shade is bounded by how often the updates are.  You get closer to shading the area under the line if you update more often.  The realization here is that you can shade a similar area if you are willing to shade above the line :)  If you set pacing_gain == multiplicative increase, you are not keeping the steps below the diagonal, you are putting them on top by assuming that you will get an increase.  Choosing a value between 1 and m hedges a little.

-- 
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/3655#pullrequestreview-411402379

---

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

@janaiyengar commented on this pull request.

This is again too prescriptive to me. I've made a big suggestion to #3630 instead.

To clarify what I said: pacing rate is cwnd/rtt (approximately, for window-based senders). In this world, on each ack, the cwnd increases, and your pacing rate therefore increases. At the end of the first RTT in slow start, your window is 2x the IW, and your pacing rate is 2 x IW / rtt. That is as it should be. Now, to compensate for border conditions, it's a good idea to use a multiplier, and that does not need to be any more than a small delta (say 1.25), and it doesn't need to be higher for slow start.

At any rate, this is way more than you need to be saying in this definition.

> +Timers are not ideal, so intervals will need to be adjusted to ensure the
+average pacing rate is maintained.  Not doing so will result in a decrease
+in average sending rate when timers consistently fire late.

I think what you want to say is that timers usually run with some granularity. I _think_ what you're trying to say is that timers might fire late and that future computations will need to account for that. 

-- 
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/3655#pullrequestreview-411420877

---

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

Closed #3655.

-- 
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/3655#event-3346538815