netdev - Re: [PATCH] tcp-illinois: incorrect beta usage

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <aa7d2c6d0711281625m44bf3ca3me188a7041d3421da@mail.gmail.com>
Date:	Wed, 28 Nov 2007 16:25:35 -0800
From:	"Lachlan Andrew" <lachlan.andrew@...il.com>
To:	"Stephen Hemminger" <shemminger@...ux-foundation.org>
Cc:	"David S. Miller" <davem@...emloft.net>,
	"Herbert Xu" <herbert@...dor.apana.org.au>, shaoliu@...nceton.edu,
	"Douglas Leith" <doug.leith@...m.ie>,
	"Robert Shorten" <robert.shorten@...m.ie>, netdev@...r.kernel.org
Subject: Re: [PATCH] tcp-illinois: incorrect beta usage

Thanks Stephen.

A related problem (largely due to the published algorithm itself) is
that Illinois is very aggressive when it over-estimates the maximum
RTT.

At high load (say 200Mbps and 200ms RTT), a backlog of packets builds
up just after a loss, causing the RTT estimate to become large.  This
makes Illinois think that *all* losses are due to corruption not
congestion, and so only back off by 1/8 instead of 1/2.

I can't think how to fix this except by better RTT estimation, or
changes to Illinois itself.  Currently, I ignore RTT measurements when
   sacked_out != 0    and have a heuristic "RTT aging" mechanism, but
that's pretty ugly.

Cheers,
Lachlan

On 28/11/2007, Stephen Hemminger <shemminger@...ux-foundation.org> wrote:
> Lachlan Andrew observed that my TCP-Illinois implementation uses the
> beta value incorrectly:
>   The parameter  beta  in the paper specifies the amount to decrease
>   *by*:  that is, on loss,
>      W <-  W -  beta*W
>   but in   tcp_illinois_ssthresh() uses  beta  as the amount
>   to decrease  *to*: W <- beta*W
>
> This bug makes the Linux TCP-Illinois get less-aggressive on uncongested network,
> hurting performance. Note: since the base beta value is .5, it has no
> impact on a congested network.
>
> Signed-off-by: Stephen Hemminger <shemminger@...ux-foundation.org>
>
> --- a/net/ipv4/tcp_illinois.c   2007-08-18 07:50:15.000000000 -0700
> +++ b/net/ipv4/tcp_illinois.c   2007-11-28 15:39:04.000000000 -0800
> @@ -298,7 +298,7 @@ static u32 tcp_illinois_ssthresh(struct
>         struct illinois *ca = inet_csk_ca(sk);
>
>         /* Multiplicative decrease */
> -       return max((tp->snd_cwnd * ca->beta) >> BETA_SHIFT, 2U);
> +       return max(tp->snd_cwnd - ((tp->snd_cwnd * ca->beta) >> BETA_SHIFT), 2U);
>  }
>
>
>


-- 
Lachlan Andrew  Dept of Computer Science, Caltech
1200 E California Blvd, Mail Code 256-80, Pasadena CA 91125, USA
Ph: +1 (626) 395-8820    Fax: +1 (626) 568-3603
http://netlab.caltech.edu/~lachlan
-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html