Better algorithm for stream flow control

[agrover]

What we have now is the thing we did that was fast to implement, rather than a fully thought-out implementation. We should improve our algorithm, when possible.

from #726 (comment):

We have an estimate of BDP we might use to tune this. We should aim for BDP*2 at a minimum if we have an algorithm like this, otherwise we will need more frequent sending of updates.

[mxinden]

Status quo neqo

Static connection flow-control limit:

neqo/neqo-transport/src/connection/params.rs

Line 21 in 4fc4d16

const LOCAL_MAX_DATA: u64 = 0x3FFF_FFFF_FFFF_FFFF; // 2^62-1

Static stream receive window limit:

neqo/neqo-transport/src/recv_stream.rs

Line 33 in c004359

const RX_STREAM_DATA_WINDOW: u64 = 0x10_0000; // 1MiB

Static stream send window limit:

neqo/neqo-transport/src/send_stream.rs

Line 36 in c004359

pub const SEND_BUFFER_SIZE: usize = 0x10_0000; // 1 MiB

Other implementations

• Chromium:
  • limits: https://github.com/chromium/chromium/blob/904ed34564cd5482d88cfc96abf7187a1455fa16/net/quic/quic_context.cc#L20-L22
• Google Quiche:
  • limits: https://github.com/google/quiche/blob/792c6e7d8658d7b7b27f780efec71c67930b4c9f/quiche/quic/core/quic_constants.h#L82-L86
• quic-go:
  • auto-tuning: https://github.com/quic-go/quic-go/blob/e48e1d465dffafc1cfd55dc6a4e4642087dcd5eb/internal/flowcontrol/base_flow_controller.go#L95-L118
  • limits: https://github.com/quic-go/quic-go/blob/b096e94092e97b998e396c5c67735b97e403edd3/interface.go#L291-L294

Potential solution

Implement auto-tuning based on Google's QUIC design document:

Algorithm

• As above, the flow control window update triggered when:
  available window < max window size / 2,
  where available window = max receive window offset - bytes consumed
• to realize auto-tuning, add the following logic just before issuing a window update
  • keep track of time interval between subsequent window updates, call this since_last_update.
  • if ( since_last_update < RTT * trigger factor ) then max window size = MIN(max window size * increase factor, upper bound).
    • trigger factor is 2
    • increase factor is 2
• As above, window update sets:
  max_received window offset += (max window size - available window)

https://docs.google.com/document/d/1F2YfdDXKpy20WVKJueEf4abn_LVZHhMUMS5gX6Pgjl4/edit#heading=h.j3nq4bn2eaud

Used in quic-go.

Also I implemented this for a muxer on top of TCP in the past libp2p/rust-yamux#176.

Alternatives

More research needed. Pointers very much appreciated.

[martinthomson]

I believe that a better approach would be not to double the window, but to increase the window by an amount equal to the amount consumed since the last increase if the time taken to consume the windows is less than one RTT (increased by a small fudge factor to allow slack for reporting delays). This is similar to the increase in Reno CC. The effect then would be that the window increases less rapidly and maybe more often, but it would end up with a commitment that is closer to a 2x factor of BDP, rather than being 4x or more.