Message-ID: <CADVnQy=C+9ogbtS7fVM9cev5iT+6Fz88H2FTKcjwKFnDbsUe2A@mail.gmail.com>
Date: Fri, 16 May 2025 13:54:54 -0400
From: Neal Cardwell <ncardwell@...gle.com>
To: Anup Agarwal <anupa@...rew.cmu.edu>
Cc: netdev@...r.kernel.org
Subject: Re: Potential bug in Linux TCP vegas implementation

On Tue, May 13, 2025 at 7:20 PM Anup Agarwal <anupa@...rew.cmu.edu> wrote:
...
> From cccf2ef01acade18015977fabda56a619aa2084f Mon Sep 17 00:00:00 2001
> From: Anup Agarwal <anupa@...rew.cmu.edu>
> Date: Tue, 13 May 2025 22:57:19 +0000
> Subject: [PATCH] tcp: tcp_vegas fix diff computation
>
> Commit 8d3a564da34e5844aca4f991b73f8ca512246b23 changed the algebraic
> expression for computing "diff = expected throughput - actual
> throughput" compared to the prior implementation. This change was not
> intended by that commit. This commit reverts this change ensuring that
> the kernel implementation better reflects the algorithm description in
> the original Vegas paper and the original Linux implementation.
> ---
>  net/ipv4/tcp_vegas.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/net/ipv4/tcp_vegas.c b/net/ipv4/tcp_vegas.c
> index 786848ad37ea..fd4ca1fbdf63 100644
> --- a/net/ipv4/tcp_vegas.c
> +++ b/net/ipv4/tcp_vegas.c
> @@ -224,7 +224,7 @@ static void tcp_vegas_cong_avoid(struct sock *sk, u32 ack, u32 acked)
>   * and the window we would like to have. This quantity
>   * is the "Diff" from the Arizona Vegas papers.
>   */
> - diff = tcp_snd_cwnd(tp) * (rtt-vegas->baseRTT) / vegas->baseRTT;
> + diff = tcp_snd_cwnd(tp) * (rtt-vegas->baseRTT) / rtt;
>
>   if (diff > gamma && tcp_in_slow_start(tp)) {
>   /* Going too fast. Time to slow down
> --
> 2.34.1

Hi Anup,

Many thanks for the patch!

> I am not fully sure about the process for communicating the patch.
> It seems like Linux uses emails instead of pull requests.
> I am also not sure about the standard of
> unit/integration/performance testing for such changes.

Here are some notes on the process:

Please  read the following for documentation on the process for
networking patches:
  https://docs.kernel.org/process/maintainer-netdev.html
  https://docs.kernel.org/process/submitting-patches.html

I would suggest including in the commit message more of the details
you shared earlier in this thread about the nature of the bug and
rationale for your bug fix.

I would suggest adding some commit message text like the following:

The following 2008 commit:

8d3a564da34e ("tcp: tcp_vegas cong avoid fix")

...introduced a bug in Vegas implementation.

And then would suggest pasting in your previous notes:

"""
Before this commit, the implementation compares "diff = cwnd * (RTT -
baseRTT) / RTT" with alpha_pkts. However, after this commit, diff is
changed to "diff = cwnd * (RTT - baseRTT) / baseRTT". This small
change in denominator potentially changes Vegas's steady-state
performance properties.

Specifically, before the commit, Vegas's steady-state rate is "rate =
alpha_pkts / delay", by substituting rate = cwnd/RTT and delay = RTT -
baseRTT in the equation "diff = alpha_pkts" (i.e., when flows do not
have incentive to change cwnd). After the commit, we get "rate =
alpha_pkts/delay * baseRTT/RTT". When baseRTT is small this is close
to "rate = alpha_pkts / delay^2".

"rate = alpha_pkts / delay" is the key to ensuring weighted
proportional fairness which Vegas has been analyzed to ensure (e.g.,
in https://www.cs.princeton.edu/techreports/2000/628.pdf or
https://link.springer.com/book/10.1007/978-0-8176-8216-3).
"rate = alpha_pkts/delay^2" would not give proportional fairness. For
instance on a parking lot topology, proportional fairness corresponds
to a throughput ratio of O(hops), whereas the delay^2 relation gives a
throughput ratio of O(hops^2) (derived in
https://arxiv.org/abs/2504.18786).
"""

While you are changing this pline, please address the style issue in
this line (missing space around the - operator). So instead of:

  diff = tcp_snd_cwnd(tp) * (rtt-vegas->baseRTT) / rtt;

Please use something more like:

  diff = tcp_snd_cwnd(tp) * (rtt - vegas->baseRTT) / rtt;

Please compile and test your change on top of the "net" branch:

git remote add net git://git.kernel.org/pub/scm/linux/kernel/git/netdev/net.git
git fetch net
git checkout net/main
git cherry-pick $YOUR_PATCH_SHA1

Then please compile, boot, and test the patch, and add a few sentences
about how you tested the patch, and what results you saw. Sadly, I
don't think there are any automated tests for Linux TCP vegas in the
kernel source tree, so for this commit, I would suggest the minimal
testing would be something like reporting throughput and average RTT
and average loss rate for:

(1) a test with a single Vegas flow
(2) a test with multiple Vegas flows sharing a bottleneck

(Reporting the bottleneck bandwidth and min_rtt for each case, and
whether the test was with netem or a real network, etc.)

Please add a Signed-off-by: footer in the commit message, if you can
certify the items documented here:

  https://docs.kernel.org/process/submitting-patches.html#sign-your-work-the-developer-s-certificate-of-origin

Since this is a bug fix, please add a Fixes: footer in the commit
message before your Signed-off-by: footer, so maintainers know what
commit has the bug you are fixing, so they know how far back in
history to backport the fix for stable releases. In this case, based
on the commit you mentioned you are fixing, I think we want:

Fixes: 8d3a564da34e ("tcp: tcp_vegas cong avoid fix")

You can run "git log" in your Linux source directory to get a sense of
the formatting for the Signed-off-by:  and Fixes:  footer.

Finally, please check the patch for style/formatting problems with the
checkpatch.pl script:

  ./scripts/checkpatch.pl *.patch

After compiling and testing the patch, adding those footers, and
verifying the patch with scripts/checkpatch.pl, please format the
patch and email it to the mailing list:

git format-patch --subject-prefix='PATCH net' HEAD~1..HEAD

git send-email \
  --to 'David Miller <davem@...emloft.net>' \
  --to 'Jakub Kicinski <kuba@...nel.org>' \
  --to 'Eric Dumazet <edumazet@...gle.com>' \
  --cc 'netdev@...r.kernel.org'  *.patch


Thanks!
neal

Powered by blists - more mailing lists