Subject: [tcpPrague] Pacing IW

From: Bob Briscoe <[email-masked]>
Date: Tue, 2 Feb 2021 12:18:36 +0000

Olivier,

I notice you've pushed code to TCP Prague, to optionally pace out IW 
over the estimated rtt (srtt).
https://github.com/L4STeam/linux/commit/aea3ff36380bec82804eba8e3f99e5f14342978c
Thanks for this. Some thoughts:

srtt can tend to be rather wildly wrong at the start of a connection. 
I'd say a high estimate will be more concerning than a low, by this 
reasoning:

- If the initial srtt estimate is too low, there will be a queuing delay 
spike, but it will never be worse than just sending IW at line rate.
- If srtt is too high, a short flow would take longer to complete 
because the first ACK will return before the IW has finished sending.

I recall Mark Handley presenting data showing longer RTT outliers at the 
start of connections (cause was unknown, but could have been a CDN 
getting its act together to serve the connection from an optimal 
location). Sorry, can't find the paper - it was perhaps 5-10 years ago. 
Whatever, in general, an over-high initial estimate is surely more 
likely than over-low, given the initial handshake might be delayed more 
than other packets, but it's unlikely to find some worm-hole that gets 
it back home faster than the speed of light.

So, possible solutions (either or both):

1. In tcp_prague.c, multiply the rate returned from 
prague_update_pacing_rate() by N(where N=2, say). So IW is at least 
paced over the first half of the RTT on average. Then, if the initial 
srtt estimate is longer than reality, the error has to be 2x before IW 
will be delayed more than a whole round.
2. Introduce a third sysctl option (tcp_pace_iw = 2) that only paces IW 
if srtt was initialized using the destination cache?

Altho this is in TCP Prague now, I guess eventually it could be taken up 
by any transport with any CC.

Cheers

Bob

PS. Defensive coding nit: In tcp_output.c, I noticed you've kept the 
condition
     if ( ... || tp->data_segs_out >= 10 )
Surely this shouldn't have been a hard-coded '10' in the first place?

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

---

From: "Tilmans, Olivier (Nokia - BE/Antwerp)" <[email-masked]>
Date: Tue, 2 Feb 2021 13:07:48 +0000

Hi Bob,

 > I notice you've pushed code to TCP Prague, to optionally pace out IW over
 > the estimated rtt (srtt).

Note that this is disabled by default: this approach is quite fragile as
you rightfully point later on; it enables quick experimentation. I'd expect
someone willing to use this in production to have a finer-grained approach,
e.g., using the destination cache to get recent srtt/cwnd values.

 > [...]

Agreed--I would expect this to happen, e.g., with PEPS terminating a
connection.

 > - If srtt is too high, a short flow would take longer to complete because
 > the first ACK will return before the IW has finished sending.

Agreed. More generally, that tradeoff is extremely application dependent,
so applications sensitive to this extra delay would either not use this or
control the pacing rate used themselves by overwriting the socket max pacing
rate.

 > [...]
 > prague_update_pacing_rate() by N (where N=2, say). So IW is at least

This is already the case, given the connection is seen as in slowstart (
ssthresh=infinity), the pacing rate will be (2 * IW/srtt)
https://github.com/L4STeam/linux/blob/testing/net/ipv4/tcp_prague.c#L306

 > if srtt was initialized using the destination cache?
 
I'd happily merge any addition or better ways to do this.

 > by any transport with any CC.

Indeed, this was the quickest way to get it to work. It can definitely be
altered to use the destination cache, and/or to use sk_max_pacing_rate in a
smarter way (e.g.,!= infinity indicates the application explicitly
requested it before queuing data for its IW, which could/should be preferred
to any generic in-kernel computation/assumption), and/or to be CCA
independent.

Best,
Olivier

---

From: Ingemar Johansson S <[email-masked]>
Date: Fri, 5 Feb 2021 10:48:30 +0000

On the pacing matters based on (initial RTT).

It is true that an initial RTT based on e.g. 3WHS can give values that are 
higher than the actual values when for instance cellular access is used.
There are a few reasons to this :
1) DRX (Discontinous reception) : A battery saving feature that makes the cell 
phone (a.k.a UE) sleep periodically. This feature is noticeable e.g. when ping 
measurements are done
2) UL scheduling : To transmit in uplink, an UE must first send a scheduling 
request (SR) to the base station, the base station then transmits a grant a 
short while after. The grant may however be too small, in which case the UE 
must piggy back a buffer status report (BSR) to the transmitted data.

All this gives the potential that the RTT may become higher than the true 
value

/Ingemar

> -----Original Message-----
> From: Tilmans, Olivier (Nokia - BE/Antwerp) <olivier.tilmans@nokia-bell-
> labs.com>
> Sent: den 2 februari 2021 14:08
> To: Bob Briscoe <[email-masked]>
> Cc: TCP Prague List <[email-masked]>
> Subject: Re: [tcpPrague] Pacing IW
>
> Hi Bob,
>
> https://github.com/L4STeam/linux/commit/aea3ff36380bec82804eba8e3f99
> e5f14
>  > 342978c
>
> Note that this is disabled by default: this approach is quite fragile as you
> rightfully point later on; it enables quick experimentation. I'd expect
>  > spike,
> but it will never be worse than just sending IW at line rate.
>
> control the pacing rate used themselves by overwriting the socket max
> pacing rate.
>
>  > [...]
>  > 1. In tcp_prague.c, multiply the rate returned from  >
> prague_update_pacing_rate() by N (where N=2, say). So IW is at least  >
> paced over the first half of the RTT on average. Then, if the initial  > 
> srtt
> estimate is longer than reality, the error has to be 2x before IW  > will be
> delayed more than a whole round.
>
>  > if
> srtt was initialized using the destination cache?
>
> smarter way (e.g.,!= infinity indicates the application explicitly requested 
> it
> before queuing data for its IW, which could/should be preferred to any
> generic in-kernel computation/assumption), and/or to be CCA independent.
>
>
> Best,
> Olivier
>
>  >
>  > Cheers
>  >
>  >
>  > Bob
>  >
>  > PS. Defensive coding nit: In tcp_output.c, I noticed you've kept the  >
> condition

---

From: Bob Briscoe <[email-masked]>
Date: Fri, 5 Feb 2021 14:58:34 +0000

@Olivier (I've responded to your response in line tagged [BB])
TL;DR: Your point about already pacing over half the RTT estimate 
probably means the code is good enough already.

@Ingemar, Thx for this.
The data I mentioned that Mark Handley presented was for fixed networks. 
But yes, of course, I should have mentioned that mobile networks exhibit 
these (different) extra delays when getting a flow started.

more in response to Olivier below...

>> control the pacing rate used themselves by overwriting the socket max

[BB] The tradeoff is between potentially delaying others with a queue 
spike vs. pacing too slowly and delaying your own flow completion a 
little. in most cases, getting this tradeoff wrong either way should 
only lead to slight extra delay (relative to the base RTT).

So, the goal of my email was merely to try to reach a better default 
position. Then few (if any) apps would have to fiddle with socket options.

>> https://github.com/L4STeam/linux/blob/testing/net/ipv4/tcp_prague.c#L30

[BB] Good point. So, I suspect it could be a good enough default as it 
stands.

It might be useful to allow the app (or the user via a sysctl?) to set a 
different value of N during IW than during slow start (for people who 
want to find a good default N empirically rather than assuming N=2 is 
good enough).

Whether N is the same as for SS or different, this is a nice simple 
mechanism.

>> generic in-kernel computation/assumption), and/or to be CCA independent.

[BB] I just thought of a possible third element to a default solution.
TL;DR: I don't think it's worth implementing by default - too little 
benefit unless you have cached info, in which case you wouldn't need it 
anyway.

For completeness, here's my thought processes anyway.
I was trying to think what sort of app might not be happy with a default 
that paces IW over 1/2 of the estimated RTT (or whatever fraction is 
decided as default, e.g. 1/4). I could only think of a transactional app 
with fewer than 10 packets in the send buffer. The risk of building a 
queue diminishes as the number of packets buffered reduces. So it might 
want to pace faster, the fewer packets it has buffered.

Below is the algorithm for how fast to pace while keeping the queue 
below a certain (constant) delay. But first some terminology, with units 
in [square brackets]:

_Environment_
R [s]: base RTT estimate (from handshake or dst cache)
N []: no of full size segments worth of data in the send buffer (the 
algorithm only applies when N < IW).
W [segment]: window that would fill capacity at the bottleneck (unknown)

_Goal_: avoid qdelay exceeding R/L, where
L []: a constant
     e.g. L=40 would mean the goal is for the queue not to exceed R/40.
     That's a queue limit of 0.5ms when R=20ms or 2.5ms when R=100ms.

_Unknown variable_
T [s]: inter-packet departure time.

_Solution_
T/R = 1/W - 1/L/N
     with a floor at line rate, of course.
If the sender had an estimate of W in its dst cache, it could use that. 
Otherwise it would have to use a conservative guess as another constant.

For conservative (low) values of W, T/R doesn't vary much with N. So the 
algo would only really be useful if the sender had a value of W cached. 
but then it could cache the RTT as well, so it wouldn't need this algo.

Bob