Message-ID: <CAFYr1XNeLcCx4pur-RTHGcn_2hE-w6TYFFuOKFFohAXxTxCSag@mail.gmail.com>
Date: Fri, 16 May 2025 15:54:00 -0400
From: Anup Agarwal <anupa@...rew.cmu.edu>
To: Neal Cardwell <ncardwell@...gle.com>
Cc: netdev@...r.kernel.org
Subject: Re: Potential bug in Linux TCP vegas implementation

Thanks for the detailed guidance Neal. I will get back to you with
this. I am assuming this is low priority/there is no pressing timeline
on this.


On Fri, May 16, 2025 at 1:55 PM Neal Cardwell <ncardwell@...gle.com> wrote:
>
> 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