* Re: [Bloat] Thoughts on Stochastic Fair Blue
[not found] ` <1300973556.3747.9.camel@edumazet-laptop>
@ 2011-03-24 13:44 ` Dave Taht
2011-03-24 13:55 ` Eric Dumazet
2011-03-24 13:57 ` Jonathan Morton
0 siblings, 2 replies; 4+ messages in thread
From: Dave Taht @ 2011-03-24 13:44 UTC (permalink / raw)
To: Eric Dumazet; +Cc: bloat-devel
Can we try to keep coding stuff on bloat-devel? The traffic level on
bloat is (wonderfully) huge as it is, but a goodly percentage of the
audience can't deal at this level.
Eric had also sent me an interesting attempt at a 4 band pfifo_fast,
which explicitly prioritized ecn-enabled packets, I was wondering if
he could resend?
How does all these stuff cope with encapsulated (vpn/6in4) packets? UDP packets?
On Thu, Mar 24, 2011 at 9:32 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> Le jeudi 24 mars 2011 à 14:40 +0200, Jonathan Morton a écrit :
>
>> Finally, it might also be interesting and useful to add bare-bones ECN
>> support to the existing "dumb" qdiscs, such as SFQ and the FIFO
>> family. Simply start marking (and dropping non-supporting flows) when
>> the queue is more than half full.
>
> Three months ago, I played with a SFQ patch to add ECN support, based on
> delay of packet in queue.
>
> http://www.spinics.net/lists/netdev/msg151594.html
>
> This patch is a hack of course (units are jiffies ticks, not ms)
>
>
> --------------------------------------
>
> Here is the POC patch I am currently testing, with a probability to
> "early drop" a packet of one percent per ms (HZ=1000 here), only if
> packet stayed at least 4 ms on queue.
>
> Of course, this only apply where SFQ is used, with known SFQ limits :)
>
> The term "early drop" is a lie. RED really early mark/drop a packet at
> enqueue() time, while I do it at dequeue() time [since I need to compute
> the delay]. But effect is the same on sent packets. This might use a bit
> more memory, but no more than current SFQ [and only if flows dont react
> to mark/drops]
>
> insmod net/sched/sch_sfq.ko red_delay=4
>
> By the way, I do think we should lower SFQ_DEPTH a bit and increase
> SFQ_SLOTS by same amount. Allowing 127 packets per flow seems not
> necessary in most situations SFQ might be used.
>
> net/sched/sch_sfq.c | 37 +++++++++++++++++++++++++++++++++----
> 1 files changed, 33 insertions(+), 4 deletions(-)
>
> diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
> index d54ac94..4f958e3 100644
> --- a/net/sched/sch_sfq.c
> +++ b/net/sched/sch_sfq.c
> @@ -24,6 +24,8 @@
> #include <net/ip.h>
> #include <net/netlink.h>
> #include <net/pkt_sched.h>
> +#include <net/inet_ecn.h>
> +#include <linux/moduleparam.h>
>
>
> /* Stochastic Fairness Queuing algorithm.
> @@ -86,6 +88,10 @@
> /* This type should contain at least SFQ_DEPTH + SFQ_SLOTS values */
> typedef unsigned char sfq_index;
>
> +static int red_delay; /* default : no RED handling */
> +module_param(red_delay, int, 0);
> +MODULE_PARM_DESC(red_delay, "mark/drop packets if they stay in queue longer than red_delay ticks");
> +
> /*
> * We dont use pointers to save space.
> * Small indexes [0 ... SFQ_SLOTS - 1] are 'pointers' to slots[] array
> @@ -391,6 +397,7 @@ sfq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
>
> sch->qstats.backlog += qdisc_pkt_len(skb);
> slot_queue_add(slot, skb);
> + qdisc_skb_cb(skb)->timestamp = jiffies;
> sfq_inc(q, x);
> if (slot->qlen == 1) { /* The flow is new */
> if (q->tail == NULL) { /* It is the first flow */
> @@ -402,11 +409,8 @@ sfq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
> q->tail = slot;
> slot->allot = q->scaled_quantum;
> }
> - if (++sch->q.qlen <= q->limit) {
> - sch->bstats.bytes += qdisc_pkt_len(skb);
> - sch->bstats.packets++;
> + if (++sch->q.qlen <= q->limit)
> return NET_XMIT_SUCCESS;
> - }
>
> sfq_drop(sch);
> return NET_XMIT_CN;
> @@ -432,6 +436,7 @@ sfq_dequeue(struct Qdisc *sch)
> sfq_index a, next_a;
> struct sfq_slot *slot;
>
> +restart:
> /* No active slots */
> if (q->tail == NULL)
> return NULL;
> @@ -455,12 +460,36 @@ next_slot:
> next_a = slot->next;
> if (a == next_a) {
> q->tail = NULL; /* no more active slots */
> + /* last packet queued, dont even try to apply RED */
> return skb;
> }
> q->tail->next = next_a;
> } else {
> slot->allot -= SFQ_ALLOT_SIZE(qdisc_pkt_len(skb));
> }
> + if (red_delay) {
> + long delay = jiffies - qdisc_skb_cb(skb)->timestamp;
> +
> + if (delay >= red_delay) {
> + long Px = delay * (0xFFFFFF / 100); /* 1 percent per jiffy */
> + if ((net_random() & 0xFFFFFF) < Px) {
> + if (INET_ECN_set_ce(skb)) {
> + /* no ecnmark counter yet :) */
> + sch->qstats.overlimits++;
> + } else {
> + /* penalize this flow : we drop the
> + * packet while we changed slot->allot
> + */
> + kfree_skb(skb);
> + /* no early_drop counter yet :) */
> + sch->qstats.drops++;
> + goto restart;
> + }
> + }
> + }
> + }
> + sch->bstats.bytes += qdisc_pkt_len(skb);
> + sch->bstats.packets++;
> return skb;
> }
>
>
>
> _______________________________________________
> Bloat mailing list
> Bloat@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/bloat
>
--
Dave Täht
SKYPE: davetaht
US Tel: 1-239-829-5608
http://the-edge.blogspot.com
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [Bloat] Thoughts on Stochastic Fair Blue
2011-03-24 13:44 ` [Bloat] Thoughts on Stochastic Fair Blue Dave Taht
@ 2011-03-24 13:55 ` Eric Dumazet
2011-03-24 13:57 ` Jonathan Morton
1 sibling, 0 replies; 4+ messages in thread
From: Eric Dumazet @ 2011-03-24 13:55 UTC (permalink / raw)
To: Dave Taht; +Cc: bloat-devel
Le jeudi 24 mars 2011 à 09:44 -0400, Dave Taht a écrit :
> Can we try to keep coding stuff on bloat-devel? The traffic level on
> bloat is (wonderfully) huge as it is, but a goodly percentage of the
> audience can't deal at this level.
>
> Eric had also sent me an interesting attempt at a 4 band pfifo_fast,
> which explicitly prioritized ecn-enabled packets, I was wondering if
> he could resend?
Hmm, this attempt was a bit stupid, since packets for a given TCP flow
are not all ECN marked. Just forget it, since using two different queues
would allow OOO (Out Of Order) packets.
To make this work, we could need support from netfilter conntracking for
example...
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [Bloat] Thoughts on Stochastic Fair Blue
2011-03-24 13:44 ` [Bloat] Thoughts on Stochastic Fair Blue Dave Taht
2011-03-24 13:55 ` Eric Dumazet
@ 2011-03-24 13:57 ` Jonathan Morton
2011-03-24 14:20 ` Eric Dumazet
1 sibling, 1 reply; 4+ messages in thread
From: Jonathan Morton @ 2011-03-24 13:57 UTC (permalink / raw)
To: Dave Taht; +Cc: bloat-devel, Eric Dumazet
On 24 Mar, 2011, at 3:44 pm, Dave Taht wrote:
>> Here is the POC patch I am currently testing, with a probability to
>> "early drop" a packet of one percent per ms (HZ=1000 here), only if
>> packet stayed at least 4 ms on queue.
A fixed time threshold doesn't take into account the wildly varying bandwidths of connections. For example, 4ms will cause almost any queued packet on a 33.6K modem uplink (or a 3G or GSM tether) to be marked, yet with the 128-packet default size for SFQ, a GigE NIC will typically empty the queue before any packets reach the marking threshold.
But perhaps a heuristic such as not marking packets which are the last in their bucket would be okay, and mark everything else when the queue is more than half full.
- Jonathan
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [Bloat] Thoughts on Stochastic Fair Blue
2011-03-24 13:57 ` Jonathan Morton
@ 2011-03-24 14:20 ` Eric Dumazet
0 siblings, 0 replies; 4+ messages in thread
From: Eric Dumazet @ 2011-03-24 14:20 UTC (permalink / raw)
To: Jonathan Morton; +Cc: bloat-devel
Le jeudi 24 mars 2011 à 15:57 +0200, Jonathan Morton a écrit :
> On 24 Mar, 2011, at 3:44 pm, Dave Taht wrote:
>
> >> Here is the POC patch I am currently testing, with a probability to
> >> "early drop" a packet of one percent per ms (HZ=1000 here), only if
> >> packet stayed at least 4 ms on queue.
>
> A fixed time threshold doesn't take into account the wildly varying
> bandwidths of connections. For example, 4ms will cause almost any
> queued packet on a 33.6K modem uplink (or a 3G or GSM tether) to be
> marked, yet with the 128-packet default size for SFQ, a GigE NIC will
> typically empty the queue before any packets reach the marking
> threshold.
>
If an ideal value would exist, we would use them, and provide a black
box. On my particular test setup I used 4 ms threshold, thats it.
You cant solve any problems with a single "super qdisc". We provide many
different qdisc (and params) to be able to build complex setups.
DRR for example is nice, because it provides an extensive
infrastructure. SFQ is good only because its space optimized (I know
some setups using 100.000 SFQ qdiscs on a single router)
You might want to play with QFQ, we are about to release it.
> But perhaps a heuristic such as not marking packets which are the last
> in their bucket would be okay, and mark everything else when the queue
> is more than half full.
Mark everything is not good, RED like algo use probabilities.
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2011-03-24 14:20 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <AB70D849-EC48-438E-B009-E22223CAF5E2@gmail.com>
[not found] ` <7imxklz5vu.fsf@lanthane.pps.jussieu.fr>
[not found] ` <160809C8-284C-4463-97FE-0E2F03C08589@gmail.com>
[not found] ` <1300973556.3747.9.camel@edumazet-laptop>
2011-03-24 13:44 ` [Bloat] Thoughts on Stochastic Fair Blue Dave Taht
2011-03-24 13:55 ` Eric Dumazet
2011-03-24 13:57 ` Jonathan Morton
2011-03-24 14:20 ` Eric Dumazet
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox