[PATCH] sch_sfq: revert dont put new flow at the end of flows

[PATCH] sch_sfq: revert dont put new flow at the end of flows

[Eric Dumazet]

This reverts commit d47a0ac7b6 (sch_sfq: dont put new flow at the end of
flows)

As Jesper found out, patch sounded great but has bad side effects.

In stress situation, pushing new flows in front of the queue can prevent
old flows doing any progress. Packets can stay in SFQ queue for
unlimited amount of time.

It's possible to add heuristics to limit this problem, but this would
add complexity outside of SFQ scope.

A more sensible answer to Dave Taht concerns (who reported the issued I
tried to solve in original commit) is probably to use a qdisc hierarchy
so that high prio packets dont enter a potentially crowded SFQ qdisc.

Reported-by: Jesper Dangaard Brouer <jdb@comx.dk>
Cc: Dave Taht <dave.taht@gmail.com>
Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
---
I tried various tricks to avoid a revert but in the end it sounds better
to use a single queue.

 net/sched/sch_sfq.c |    6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index 60d4718..02a21ab 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -469,11 +469,15 @@ enqueue:
 	if (slot->qlen == 1) {		/* The flow is new */
 		if (q->tail == NULL) {	/* It is the first flow */
 			slot->next = x;
-			q->tail = slot;
 		} else {
 			slot->next = q->tail->next;
 			q->tail->next = x;
 		}
+		/* We put this flow at the end of our flow list.
+		 * This might sound unfair for a new flow to wait after old ones,
+		 * but we could endup servicing new flows only, and freeze old ones.
+		 */
+		q->tail = slot;
 		/* We could use a bigger initial quantum for new flows */
 		slot->allot = q->scaled_quantum;
 	}

Re: [PATCH] sch_sfq: revert dont put new flow at the end of flows

[Dave Taht]

On Wed, Mar 14, 2012 at 4:04 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> This reverts commit d47a0ac7b6 (sch_sfq: dont put new flow at the end of
> flows)
>
> As Jesper found out, patch sounded great but has bad side effects.

Well under most circumstances it IS great.

As the depth of the sfq queue increases it gets increasingly hard to
trigger the problem. I've been using values in the 200-300 range, and
in combination with red, haven't seen it happen.

Also in part the sfq behavior observed is due to an interaction with
htb's 'capture' of a packet rather than peek. The situation that
jesper encountered this issue (trying to regulate flows to hundreds of
downstream clients on a very deterministic test) was different from
where I don't encounter it (trying to regulate flows up from a very
few clients)

For more details:

http://www.bufferbloat.net/issues/332

But I concur in reverting this for now. Sadly. wouldn't mind if there
was a way to keep it as is as an option...

>
> In stress situation, pushing new flows in front of the queue can prevent
> old flows doing any progress. Packets can stay in SFQ queue for
> unlimited amount of time.
>
> It's possible to add heuristics to limit this problem, but this would
> add complexity outside of SFQ scope.
>
> A more sensible answer to Dave Taht concerns (who reported the issued I
> tried to solve in original commit) is probably to use a qdisc hierarchy
> so that high prio packets dont enter a potentially crowded SFQ qdisc.

Um, er, in today's port 80/433 world, there isn't any such thing as high
prio packets.

I am curious as to whether this problem can be made to happen with qfq.

> Reported-by: Jesper Dangaard Brouer <jdb@comx.dk>
> Cc: Dave Taht <dave.taht@gmail.com>
> Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
> ---
> I tried various tricks to avoid a revert but in the end it sounds better
> to use a single queue.

I had some hope for a semi-random alternating queue

>
>  net/sched/sch_sfq.c |    6 +++++-
>  1 file changed, 5 insertions(+), 1 deletion(-)
>
> diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
> index 60d4718..02a21ab 100644
> --- a/net/sched/sch_sfq.c
> +++ b/net/sched/sch_sfq.c
> @@ -469,11 +469,15 @@ enqueue:
>        if (slot->qlen == 1) {          /* The flow is new */
>                if (q->tail == NULL) {  /* It is the first flow */
>                        slot->next = x;
> -                       q->tail = slot;
>                } else {
>                        slot->next = q->tail->next;
>                        q->tail->next = x;
>                }
> +               /* We put this flow at the end of our flow list.
> +                * This might sound unfair for a new flow to wait after old ones,
> +                * but we could endup servicing new flows only, and freeze old ones.
> +                */
> +               q->tail = slot;
>                /* We could use a bigger initial quantum for new flows */
>                slot->allot = q->scaled_quantum;
>        }
>
>



-- 
Dave Täht
SKYPE: davetaht
US Tel: 1-239-829-5608
http://www.bufferbloat.net

Re: [PATCH] sch_sfq: revert dont put new flow at the end of flows

[Eric Dumazet]

Le mercredi 14 mars 2012 à 04:52 +0000, Dave Taht a écrit :

> I had some hope for a semi-random alternating queue
> 

I spent some time implementing two queues, one for new flows, one for
old flows. As soon as a new flow uses its initial quantum, its moved at
the tail of 'old flows queue'.

But I always could find a way to starve some flows, even adding some
kind of persistence. Right now, as soon as we empty one flow, we forget
its history.

Next packet coming will create a "new flow" with a full quantum credit,
even if we nearly consume all flow quantum in the last micro second.

Thats definitely not a trivial problem.

Re: [PATCH] sch_sfq: revert dont put new flow at the end of flows

[Dave Taht]

On Wed, Mar 14, 2012 at 5:02 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> Le mercredi 14 mars 2012 à 04:52 +0000, Dave Taht a écrit :
>
>> I had some hope for a semi-random alternating queue
>>
>
> I spent some time implementing two queues, one for new flows, one for
> old flows. As soon as a new flow uses its initial quantum, its moved at
> the tail of 'old flows queue'.
>
> But I always could find a way to starve some flows, even adding some
> kind of persistence. Right now, as soon as we empty one flow, we forget
> its history.
>
> Next packet coming will create a "new flow" with a full quantum credit,
> even if we nearly consume all flow quantum in the last micro second.
>
> Thats definitely not a trivial problem.

I've expended brain cells on this too (nobody has any experience with head drop,
aqm managed queues!), and was unable to come up with a way of dealing with
the corner case of too many new streams inside of sfq's current architecture.

But I gotta say that the overall effect of this on optimizing sparse streams
(dns,dhcp,tcp syn,ra,other routing packets,gaming packets,etc) was pretty
freaking amazing, and it nearly eliminated any need for classification and
prioritization, BE, and BK were enough.

Ah, well. The other stuff in 3.3 is really good, too.

Sometimes you win, sometimes you lose, sometimes... it rains.

>
>
>



-- 
Dave Täht
SKYPE: davetaht
US Tel: 1-239-829-5608
http://www.bufferbloat.net

Re: [PATCH] sch_sfq: revert dont put new flow at the end of flows

[Jesper Dangaard Brouer]

ons, 14 03 2012 kl. 04:52 +0000, skrev Dave Taht:
> On Wed, Mar 14, 2012 at 4:04 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> > This reverts commit d47a0ac7b6 (sch_sfq: dont put new flow at the end of
> > flows)
> >
> > As Jesper found out, patch sounded great but has bad side effects.
> 
> Well under most circumstances it IS great.

Yes, I had really high hopes for this patch.  It unfortunately it can
cause starvation in some situations :-(.


> As the depth of the sfq queue increases it gets increasingly hard to
> trigger the problem. I've been using values in the 200-300 range, and
> in combination with red, haven't seen it happen.

I don't think you should adjust the "depth", but instead "limit" or
"flows".

The problem can be solved by SFQ parameter tuning.  Perhaps, we could
just change the default parameters?

The problem occurs when all flows have ONE packet, then sfq_drop()
cannot find a good flow to drop packets from...

This situation can occur because the default setting is "limit=127"
packets and "flows=127".  If we just make sure that "limit" > "flows",
then one flow with >=2 packets should exist, which is then chosen for
drop.
My practical experiments show that "limit" should be between 10-20
packets larger than "flows" (I'm not completely sure why this is
needed).  

[cut]
> > In stress situation, pushing new flows in front of the queue can prevent
> > old flows doing any progress. Packets can stay in SFQ queue for
> > unlimited amount of time.

In my experiments, one "existing" flow would get all the bandwidth,
while other flows got starved.   And new flows could not be established.


--Jesper Brouer

Re: [PATCH] sch_sfq: revert dont put new flow at the end of flows

[Eric Dumazet]

Le mercredi 14 mars 2012 à 12:32 +0100, Jesper Dangaard Brouer a écrit :
> ons, 14 03 2012 kl. 04:52 +0000, skrev Dave Taht:
> > On Wed, Mar 14, 2012 at 4:04 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:

> > As the depth of the sfq queue increases it gets increasingly hard to
> > trigger the problem. I've been using values in the 200-300 range, and
> > in combination with red, haven't seen it happen.
> 
> I don't think you should adjust the "depth", but instead "limit" or
> "flows".
> 
> The problem can be solved by SFQ parameter tuning.  Perhaps, we could
> just change the default parameters?
> 
> The problem occurs when all flows have ONE packet, then sfq_drop()
> cannot find a good flow to drop packets from...
> 
> This situation can occur because the default setting is "limit=127"
> packets and "flows=127".  If we just make sure that "limit" > "flows",
> then one flow with >=2 packets should exist, which is then chosen for
> drop.
> My practical experiments show that "limit" should be between 10-20
> packets larger than "flows" (I'm not completely sure why this is
> needed).  
> 

There are many ways to starve SFQ if we dont revert the patch or add new
logic in linux-3.4

Even if we change default settings, we can have following situation :

SFQ in a state with several regular flows in queue, correctly behaving
because they are nice.

loop repeat_as_many_times_you_can_think
 enqueue : packet comes for a new flow X.
           OK lets favor this new flow against 'old' ones.
 dequeue : takes the packet for flow X.
           forget about flow X since dequeue all its packets.
endloop

All other flows are in a frozen state.

Re: [PATCH] sch_sfq: revert dont put new flow at the end of flows

[Dave Taht]

On Wed, Mar 14, 2012 at 2:04 PM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> Le mercredi 14 mars 2012 à 12:32 +0100, Jesper Dangaard Brouer a écrit :
>> ons, 14 03 2012 kl. 04:52 +0000, skrev Dave Taht:
>> > On Wed, Mar 14, 2012 at 4:04 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
>
>> > As the depth of the sfq queue increases it gets increasingly hard to
>> > trigger the problem. I've been using values in the 200-300 range, and
>> > in combination with red, haven't seen it happen.
>>
>> I don't think you should adjust the "depth", but instead "limit" or
>> "flows".

Sorry, I'd meant 'limit' above, with limiting the per flow depth (at
4Mbit depths of 12-24 are good + red doing byte limiting starting at
3000), and having lots of flows in the hash....

Anyway, as this change to sfq currently has pathological edge cases, I suggest:

1) reverting this patch (the new features of sfq - hugely increased
number of flows, and increased limit, head drop/marking support, red,
ecn, etc, can stay - and are rather nice in and of themselves)

2) trying again, but not in the context of sfq - starting with sfq as
a base, with a copy and rename, getting the iproute infrastructure
around it working, more thorough tests going. I'll note that while
flow management is needed, it needent be red-based.

nsfq? efq?


>>
>> The problem can be solved by SFQ parameter tuning.  Perhaps, we could
>> just change the default parameters?

I can't think of a way to make existing users of sfq not hit this problem
if they are overriding the default params in the first place. thus my
suggestion we start again in a new namespace.

>> The problem occurs when all flows have ONE packet, then sfq_drop()
>> cannot find a good flow to drop packets from...
>>
>> This situation can occur because the default setting is "limit=127"
>> packets and "flows=127".  If we just make sure that "limit" > "flows",
>> then one flow with >=2 packets should exist, which is then chosen for
>> drop.
>> My practical experiments show that "limit" should be between 10-20
>> packets larger than "flows" (I'm not completely sure why this is
>> needed).

flows and/or depth?

if flows, then we could drop the flows parameter entirely and just use limit
to calculate flows. But I think that it's more subtle than just this.

more thorough tests exploring the pathological cases are needed. I'm on it.

>>
>
> There are many ways to starve SFQ if we dont revert the patch or add new
> logic in linux-3.4
>
> Even if we change default settings, we can have following situation :
>
> SFQ in a state with several regular flows in queue, correctly behaving
> because they are nice.
>
> loop repeat_as_many_times_you_can_think
>  enqueue : packet comes for a new flow X.
>           OK lets favor this new flow against 'old' ones.
>  dequeue : takes the packet for flow X.
>           forget about flow X since dequeue all its packets.
> endloop
>
> All other flows are in a frozen state.

some thoughts

1) Keeping more history around during the next X packet deliveries would help.
2) in case of being close up against various limits randomly enqueue on tail

I note that htb introduces a window for new flows to win
pathologically by holding onto a packet
which perhaps it should be peeking (or so I understand it)
>
>
>



-- 
Dave Täht
SKYPE: davetaht
US Tel: 1-239-829-5608
http://www.bufferbloat.net

Re: [PATCH] sch_sfq: revert dont put new flow at the end of flows

[David Miller]

From: Eric Dumazet <eric.dumazet@gmail.com>
Date: Tue, 13 Mar 2012 21:04:25 -0700

> This reverts commit d47a0ac7b6 (sch_sfq: dont put new flow at the end of
> flows)
> 
> As Jesper found out, patch sounded great but has bad side effects.
> 
> In stress situation, pushing new flows in front of the queue can prevent
> old flows doing any progress. Packets can stay in SFQ queue for
> unlimited amount of time.
> 
> It's possible to add heuristics to limit this problem, but this would
> add complexity outside of SFQ scope.
> 
> A more sensible answer to Dave Taht concerns (who reported the issued I
> tried to solve in original commit) is probably to use a qdisc hierarchy
> so that high prio packets dont enter a potentially crowded SFQ qdisc.
> 
> Reported-by: Jesper Dangaard Brouer <jdb@comx.dk>
> Cc: Dave Taht <dave.taht@gmail.com>
> Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>

Applied, thanks Eric.