netdev - Re: [RFC] net_sched: mark packet staying on queue too long

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: <1294153329.3579.99.camel@edumazet-laptop>
Date:	Tue, 04 Jan 2011 16:02:09 +0100
From:	Eric Dumazet <eric.dumazet@...il.com>
To:	Jesper Dangaard Brouer <hawk@...u.dk>
Cc:	Stephen Hemminger <shemminger@...tta.com>, hadi@...erus.ca,
	Jarek Poplawski <jarkao2@...il.com>,
	David Miller <davem@...emloft.net>,
	Patrick McHardy <kaber@...sh.net>,
	netdev <netdev@...r.kernel.org>
Subject: Re: [RFC] net_sched: mark packet staying on queue too long

Le mardi 04 janvier 2011 à 15:19 +0100, Jesper Dangaard Brouer a écrit :
> On Mon, 3 Jan 2011, Stephen Hemminger wrote:
> 
> > On Sun, 02 Jan 2011 22:27:11 +0100
> > Eric Dumazet <eric.dumazet@...il.com> wrote:
> >
> >> While playing with SFQ and other AQM, I was bothered to see how easy it
> >> was for a single tcp flow to 'fill the pipe' and consume lot of memory
> >> buffers in queues. I know Jesper use more than 50.000 SFQ on his
> >> routers, and with GRO packets this can consume a lot of memory.
> 
> That is true, operations department went kind of crazy when they started 
> to add/move customers to our new Nehalem Xeon 5550 systems.  I have 
> stopped them now ;-)
> 
> The use of an SFQ per customer, actually also solves the buffer bloat 
> issue for our customers...
> 
> 
> >> I played a bit adding ECN in SFQ, first by marking packets for a
> >> particular flow if this flow qlen was above a given threshold, and later
> >> using another trick : ECN mark packet if it stayed longer than a given
> >> delay in the queue. This of course could be done on other modules, what
> >> do you think ?
> 
> This is very interesting stuff! :-)
> 
> Are you inspired by Jim Gettys buffer bloat discussions?
> 

Not at all, I had to install an AQM here at work, I chose SFQ because
the machines only handle tcp flows (and limited number of flows)

> > ...
> > You might want to look into CHOKe and ECSFQ which are other AQM models
> > that have shown up in research.
> 
> Have you looked at the SFB (Stochastic Fair Blue) implementation by 
> Juliusz Chroboczek?
> 
> http://www.pps.jussieu.fr/~jch/software/sfb/

Yes I did, but after some reading, I think there is an issue with BLUE,
regarding number of cache misses and complexity because of Bloom filter
(and double hashing)
For workloads with many flows, all bits are marked very fast.

I'd like to try kind of a SFQRED implementation, ie :

classify flows, then instead of using plain pfifo queues (currently done
in SFQ), use N pseudo RED queues.

RED is a bit complex because it tries to make the probability estimation
given queue backlog average. It has to use expensive time services (on
some machines at least, if TSC not available)

My idea was to take into account the delay packets stay in its queue, so
that no extra state is needed : Only take a timestamp when packet is
enqueued, compute delta when dequeued, get 

Px = delta * Prob_per_time_unit;
and drop/mark packet with Px probability.

Ram usage of SFQRED would be the same than SFQ, and cost roughly the
same (because we could use jiffies based time sampling, (and HZ=1000 for
a ms unit)).



--
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