Blue and SFB
Subsystems (2)
Quoted 2 lines · Patrick McHardy
There is a blue implementation for Linux at
http://home.sch.bme.hu/~bartoki/projects/thesis/2001-May-26/
Nice!
I briefly scanned the implementation and it didn't look too bad. Some oddities here and there (such as changing HZ from 100 to 1024??).
But, as the implementation is rather old, it would require a complete overhaul for 2.6 I think. It is a shame it wasn't worked in to the Linux kernel when it was still current, as I think the algorithm could have a lot of uses.
What is the process of getting new traffic schedulers in the kernel? I guess most of the netfilter stuff goes through netfilter development and patch-o-matic - but there isn't anything similar for QoS, is there?
Quoted 2 lines
BTW: Regarding your remaining HFSC questions (I just discovered them on lartc), I'm going to answer them tomorrow.
No rush. I did realize that I posted the reply only to the list through gmane, but didn't consider it important enough to resend directly.
-- Naked
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
Quoted 10 lines · Nuutti Kotivuori
Quoted 2 lines · Patrick McHardy
There is a blue implementation for Linux at
http://home.sch.bme.hu/~bartoki/projects/thesis/2001-May-26/Nice!
I briefly scanned the implementation and it didn't look too bad. Some oddities here and there (such as changing HZ from 100 to 1024??).
Yes, it seems to be in a good form. The HZ change doesn't make much sense for a work-conserving scheduler, the PSCHED_CLOCK_SOURCE change is there to get a higher clock resolution.
Quoted 4 lines
But, as the implementation is rather old, it would require a complete overhaul for 2.6 I think. It is a shame it wasn't worked in to the Linux kernel when it was still current, as I think the algorithm could have a lot of uses.
I couldn't sleep this morning so I started to fix up the code for 2.6 ;) It's almost no work, the QoS-subsystem hasn't changed much since 2.4.3. I should be done today or tommorrow.
Quoted 4 lines
What is the process of getting new traffic schedulers in the kernel? I guess most of the netfilter stuff goes through netfilter development and patch-o-matic - but there isn't anything similar for QoS, is there?
No, there isn't. The usual way it to submit new stuff to netdev for discussion, if it is useful and of good quality it usually is accepted.
Regards
Patrick
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
Quoted 6 lines
Quoted 4 lines · Nuutti Kotivuori
But, as the implementation is rather old, it would require a complete overhaul for 2.6 I think. It is a shame it wasn't worked in to the Linux kernel when it was still current, as I think the algorithm could have a lot of uses.
I've completed the port and tested it yesterday, unfortunately it's not useable in the real world as is. There is a strong bias against non-ECN flows because their packets are simply dropped instead of marked. At high load (50 ECN vs. 1 non-ECN flow) and a marking probability of about 10% the non-ECN flow simply stalls. I can send you the patch if you're interested ..
Regards
Patrick
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
Quoted 6 lines · Patrick McHardy
I've completed the port and tested it yesterday, unfortunately it's not useable in the real world as is. There is a strong bias against non-ECN flows because their packets are simply dropped instead of marked. At high load (50 ECN vs. 1 non-ECN flow) and a marking probability of about 10% the non-ECN flow simply stalls. I can send you the patch if you're interested ..
Thank you, I am really interested.
I will try how it behaves for me in various circumstances.
What you say, though, is probably true - and the situation is even more accentuated when considering that different TCP stacks react to ECN and packet drops differently - a single drop percent will not be enough.
Which ofcourse brings us to SFB - with Stochastic Fair Blue, the drop percentage for the non-ECN flow should be significantly lower and the connections should transfer more or less fairly.
-- Naked
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
Quoted 11 lines · Nuutti Kotivuori
Quoted 6 lines · Patrick McHardy
I've completed the port and tested it yesterday, unfortunately it's not useable in the real world as is. There is a strong bias against non-ECN flows because their packets are simply dropped instead of marked. At high load (50 ECN vs. 1 non-ECN flow) and a marking probability of about 10% the non-ECN flow simply stalls. I can send you the patch if you're interested ..
Thank you, I am really interested.
Patch is attached. Use the original tc patch.
Quoted 7 lines
I will try how it behaves for me in various circumstances.
What you say, though, is probably true - and the situation is even more accentuated when considering that different TCP stacks react to ECN and packet drops differently - a single drop percent will not be enough.
OTOH, with only ECN flows it works great, not a single packet drop after a couple of minutes, without BLUE there were multiple thousands.
Quoted 3 lines
Which ofcourse brings us to SFB - with Stochastic Fair Blue, the drop percentage for the non-ECN flow should be significantly lower and the connections should transfer more or less fairly.
I'm going to check this out, don't know anything about it.
Regards
Patrick
Quoted 3 lines
-- Naked
# This is a BitKeeper generated diff -Nru style patch. #
# ChangeSet
# 2004/03/06 16:57:42+01:00 [email protected]
# Add BLUE scheduler
#
# net/sched/sch_blue.c # 2004/03/06 16:57:35+01:00 [email protected] +453 -0 # # net/sched/sch_blue.c # 2004/03/06 16:57:35+01:00 [email protected] +0 -0 # BitKeeper file /home/kaber/src/blue/linux-2.6/net/sched/sch_blue.c # # net/sched/Makefile # 2004/03/06 16:57:35+01:00 [email protected] +1 -0 # Add BLUE scheduler # # net/sched/Kconfig # 2004/03/06 16:57:35+01:00 [email protected] +19 -0 # Add BLUE scheduler # # include/linux/pkt_sched.h # 2004/03/06 16:57:35+01:00 [email protected] +31 -0 # Add BLUE scheduler # diff -Nru a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h --- a/include/linux/pkt_sched.h Sat Mar 6 16:58:06 2004 +++ b/include/linux/pkt_sched.h Sat Mar 6 16:58:06 2004 @@ -321,6 +321,37 @@ TCA_HFSC_MAX = TCA_HFSC_USC };
+/* BLUE section */
+
+enum
+{
+ TCA_BLUE_UNSPEC,
+ TCA_BLUE_PARMS,
+};
+
+struct tc_blue_qopt
+{
+ __u32 limit; /* Limit on queue length, bytes */
+ __s32 freeze_time; /* Minimum time between Pmark updates, usec! */
+ __s32 pmark_init; /* Initial Pmark */
+ __s32 pmark_inc; /* Pmark increment step */
+ __s32 pmark_dec; /* Pmark decrement step */
+ __s32 pmark_max; /* Pmark never exceeds this maximum */
+ __u32 flags;
+};
+
+/* Flags: */
+#define TC_BLUE_ECN 1 /* Do ECN marking, if ECT is set in the packet */
+
+struct tc_blue_xstats
+{
+ __s32 pmark; /* Current Pmark */
+ __u32 marked; /* Marked packets */
+ __u32 early_drops; /* Early drops */
+ __u32 limit_drops; /* Drops due to queue limits */
+ __u32 other_drops; /* Drops due to drop() calls */
+};
+
/* CBQ section */
#define TC_CBQ_MAXPRIO 8
net/sched/Kconfig +19 -0
@@ -101,6 +101,25 @@ To compile this code as a module, choose M here: the module will be called sch_red. +config NET_SCH_BLUE + tristate "BLUE queue" + depends on NET_SCHED + help + Say Y here if you want to use the BLUE queue management algorithm + for some of your network devices. BLUE is similar to RED as it + randomly ECN-marks or drops packets, but uses a different approach + to select the packets to be marked/dropped, which is intended to + perform better under high load. + + For details and references about BLUE see: + + - http://thefengs.com/wuchang/blue/ + - http://www.sch.bme.hu/~bartoki/projects/thesis/ + - The top of net/sched/sch_blue.c + + To compile this code as a module, choose M here: the + module will be called sch_blue. + config NET_SCH_SFQ tristate "SFQ queue" depends on NET_SCHED
net/sched/Makefile +1 -0
@@ -15,6 +15,7 @@ obj-$(CONFIG_NET_SCH_HFSC) += sch_hfsc.o obj-$(CONFIG_NET_SCH_RED) += sch_red.o obj-$(CONFIG_NET_SCH_GRED) += sch_gred.o +obj-$(CONFIG_NET_SCH_BLUE) += sch_blue.o obj-$(CONFIG_NET_SCH_INGRESS) += sch_ingress.o obj-$(CONFIG_NET_SCH_DSMARK) += sch_dsmark.o obj-$(CONFIG_NET_SCH_SFQ) += sch_sfq.o
net/sched/sch_blue.c new file +453 -0
453 lines not on this page · raw message