Message-ID: <CAFYr1XMavsEr36TNu5ZxSwju3uwXgKnA36zqwVnPYeEiaK4RdA@mail.gmail.com>
Date: Fri, 16 May 2025 11:38:06 -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

Hi Neal,

(Sorry for potentially duplicate email, I think my previous email got
dropped by the netdev mailing list).
I am happy to do this. 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.

The fix is as simple as the patch below. In the expression for diff,
we just replace the denominator from baseRTT to rtt. I do not
anticipate this requiring any other change for addressing division by
0, integer overflows, or precision loss (e.g., fixed-point
arithmetic). This is because rtt is at least 1 (just like baseRTT),
and numerical values of rtt should lie in a similar range as baseRTT.

I am not fully sure about the precision part as I don't know why the
original 1999 implementation needed fixed-point given the latest one
does not.

Best,
Anup

>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


On Mon, May 12, 2025 at 2:18 PM Neal Cardwell <ncardwell@...gle.com> wrote:
>
> On Mon, May 12, 2025 at 1:44 PM Anup Agarwal <anupa@...rew.cmu.edu> wrote:
> >
> > Hi Neal,
> >
> > I am reaching out to you since you are listed as a point of contact
> > for Linux TCP (https://docs.kernel.org/process/maintainers.html) and
> > http://neal.nu/uw/linux-vegas/ seems to indicate that you also wrote
> > the initial Vegas implementation in Linux kernel.
> >
> > I believe this commit
> > https://github.com/torvalds/linux/commit/8d3a564da34e5844aca4f991b73f8ca512246b23
> > introduced a bug in Vegas implementation.
> >
> > 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).
> >
> > In practice, this issue or fixing it is perhaps not as important
> > because of the 3 reasons below. However, since this seems to be a
> > clear algebraic manipulation mistake in the commit and is an easy fix,
> > the issue can perhaps be fixed nonetheless. Please let me know in case
> > I missed something and this was instead an intentional change.
> >
> > (R1) Few people (outside of perhaps congestion control evaluation) use Vegas.
> > (R2) To trigger this issue, one needs both low baseRTT and low
> > capacity (to ensure delay is large enough to matter (see R3 below)).
> > This implies low BDP networks at which point cwnd clamps may kick in.
> > Alternatively, large alpha_pkts value could trigger the issue instead
> > of low capacity.
> > (R3) In my empirical tests, I start seeing issues due to RTprop
> > (baseRTT) misestimation long before this issue.
> >
> > Best,
> > Anup
>
> Hi Anup,
>
> Thanks for catching this!  Your analysis looks correct to me.
>
> Looks like that
> https://github.com/torvalds/linux/commit/8d3a564da34e5844aca4f991b73f8ca512246b23
> commit was merged in 2008, when I was not involved with Linux TCP
> development, so I didn't notice this modification vs my original 1999
> version of Linux TCP Vegas code (
> http://neal.nu/uw/linux-vegas/patches/linux-vegas-v2-patch-2.3 ).
>
> Anup, are you interested in proposing a commit to fix this, and
> sending it to the list? If you are not interested, or don't have time,
> then I can try to find time to do that (of course, properly crediting
> you with reporting the issue and suggesting the fix).
>
> Thanks!
>
> best,
> neal

Powered by blists - more mailing lists