net: sched: pie: align PIE implementation with RFC 8033
Subsystems (3)
v2 cover net: sched: pie: align PIE implementation with RFC 8033
The current implementation of the PIE queuing discipline is according to the IETF draft [http://tools.ietf.org/html/draft-pan-aqm-pie-00] and the paper [PIE: A Lightweight Control Scheme to Address the Bufferbloat Problem]. However, a lot of necessary modifications and enhancements have been proposed in RFC 8033, which have not yet been incorporated in the source code of Linux. This patch series helps in achieving the same.
Performance tests carried out using Flent [https://flent.org/]
Changes from v1 to v2:
- Excluded the patch setting PIE dynamically active/inactive as the test results were unsatisfactory
- Fixed a scaling issue when adding more auto-tuning cases which caused local variables to underflow
- Changed the long if/else chain to a loop as suggested by Stephen
- Changed the position of the accu_prob variable in the pie_vars structure as recommended by Stephen
Mohit P. Tahiliani (7):
net: sched: pie: change value of QUEUE_THRESHOLD
net: sched: pie: change default value of pie_params->target
net: sched: pie: change default value of pie_params->tupdate
net: sched: pie: change initial value of pie_vars->burst_time
net: sched: pie: add more cases to auto-tune alpha and beta
net: sched: pie: add derandomization mechanism
net: sched: pie: update references
include/uapi/linux/pkt_sched.h | 2 +- net/sched/sch_pie.c | 107 ++++++++++++++++++++------------- 2 files changed, 66 insertions(+), 43 deletions(-)
Signature · 1 line
2.17.1
PATCH v2 1/7 net: sched: pie: change value of QUEUE_THRESHOLD
From: "Mohit P. Tahiliani" <[email protected]>
RFC 8033 recommends a value of 16384 bytes for the queue threshold.
--- net/sched/sch_pie.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
net/sched/sch_pie.c +1 -1
@@ -31,7 +31,7 @@#include <net/pkt_sched.h> #include <net/inet_ecn.h> -#define QUEUE_THRESHOLD 10000 +#define QUEUE_THRESHOLD 16384#define DQCOUNT_INVALID -1#define MAX_PROB 0xffffffff#define PIE_SCALE 8
Signature · 1 line
2.17.1
PATCH v2 2/7 net: sched: pie: change default value of pie_params->target
In reply to Leslie MonisFrom: "Mohit P. Tahiliani" <[email protected]>
RFC 8033 suggests a default value of 15 milliseconds for the target queue delay.
--- net/sched/sch_pie.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
net/sched/sch_pie.c +1 -1
@@ -83,7 +83,7 @@ static void pie_params_init(struct pie_params *params) params->beta =20 ; params->tupdate =usecs_to_jiffies (30 *USEC_PER_MSEC );/* 30 ms */ params->limit =1000 ;/* default of 1000 packets */ - params->target =PSCHED_NS2TICKS (20 *NSEC_PER_MSEC );/* 20 ms */ + params->target =PSCHED_NS2TICKS (15 *NSEC_PER_MSEC );/* 15 ms */ params->ecn = false; params->bytemode = false; }
Signature · 1 line
2.17.1
PATCH v2 3/7 net: sched: pie: change default value of pie_params->tupdate
In reply to Leslie MonisFrom: "Mohit P. Tahiliani" <[email protected]>
RFC 8033 suggests a default value of 15 milliseconds for the update interval.
--- net/sched/sch_pie.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
net/sched/sch_pie.c +1 -1
@@ -81,7 +81,7 @@ static void pie_params_init(struct pie_params *params) { params->alpha =2 ; params->beta =20 ; - params->tupdate =usecs_to_jiffies (30 *USEC_PER_MSEC );/* 30 ms */ + params->tupdate =usecs_to_jiffies (15 *USEC_PER_MSEC );/* 15 ms */ params->limit =1000 ;/* default of 1000 packets */ params->target =PSCHED_NS2TICKS (15 *NSEC_PER_MSEC );/* 15 ms */ params->ecn = false;
Signature · 1 line
2.17.1
PATCH v2 4/7 net: sched: pie: change initial value of pie_vars->burst_time
In reply to Leslie MonisFrom: "Mohit P. Tahiliani" <[email protected]>
RFC 8033 suggests an initial value of 150 milliseconds for the maximum time allowed for a burst of packets.
--- net/sched/sch_pie.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
net/sched/sch_pie.c +2 -2
@@ -92,8 +92,8 @@ static void pie_vars_init(struct pie_vars *vars) { vars->dq_count =DQCOUNT_INVALID ; vars->avg_dq_rate =0 ; -/* default of 100 ms in pschedtime */ - vars->burst_time =PSCHED_NS2TICKS (100 *NSEC_PER_MSEC ); +/* default of 150 ms in pschedtime */ + vars->burst_time =PSCHED_NS2TICKS (150 *NSEC_PER_MSEC ); }static bool drop_early (struct Qdisc *sch,u32 packet_size)
Signature · 1 line
2.17.1
PATCH v2 5/7 net: sched: pie: add more cases to auto-tune alpha and beta
In reply to Leslie MonisFrom: "Mohit P. Tahiliani" <[email protected]>
The current implementation scales the local alpha and beta variables in the calculate_probability function by the same amount for all values of drop probability below 1%.
RFC 8033 suggests using additional cases for auto-tuning alpha and beta when the drop probability is less than 1%.
In order to add more auto-tuning cases, MAX_PROB must be scaled by u64 instead of u32 to prevent underflow when scaling the local alpha and beta variables in the calculate_probability function.
--- include/uapi/linux/pkt_sched.h | 2 +- net/sched/sch_pie.c | 65 +++++++++++++++++----------------- 2 files changed, 33 insertions(+), 34 deletions(-)
include/uapi/linux/pkt_sched.h +1 -1
@@ -954,7 +954,7 @@ enum {#define TCA_PIE_MAX (__TCA_PIE_MAX - 1)struct tc_pie_xstats { -__u32 prob;/* current probability */ +__u64 prob;/* current probability */ __u32 delay;/* current delay in ms */ __u32 avg_dq_rate;/* current average dq_rate in bits/pie_time */ __u32 packets_in;/* total number of packets enqueued */
net/sched/sch_pie.c +32 -33
112 lines not on this page · raw message
Signature · 1 line
2.17.1
David Miller
maintainerRe: [PATCH net-next v2 5/7] net: sched: pie: add more cases to auto-tune alpha and beta
From: Leslie Monis <[email protected]>
Date: Mon, 25 Feb 2019 15:50:49 +0530
net/sched/sch_pie.c static void calculate_probability(struct Qdisc *sch) · line 357
Quoted 2 lines
net/sched/sch_pie.c +2
-0+ power =100 ; + while (q->vars.prob < MAX_PROB / (u64)power &&
You have to use div_u64() or similar when doing 64-bit divisons otherwise you'll get build failures on 32-bit platforms.
Re: [PATCH net-next v2 5/7] net: sched: pie: add more cases to auto-tune alpha and beta
Quoted 8 lines · David Miller
From: Leslie Monis <[email protected]>
Date: Mon, 25 Feb 2019 15:50:49 +0530net/sched/sch_pie.c static void calculate_probability(struct Qdisc *sch) · line 357
Quoted 2 lines
net/sched/sch_pie.c +2
-0+ power =100 ; + while (q->vars.prob < MAX_PROB / (u64)power &&You have to use
div_u64()or similar when doing 64-bit divisons otherwise you'll get build failures on 32-bit platforms.
Alright. Thanks for the feedback.
kbuild test robot
build botRe: [PATCH net-next v2 5/7] net: sched: pie: add more cases to auto-tune alpha and beta
In reply to Leslie MonisThank you for the patch! Yet something to improve:
Hi Mohit,
Thank you for the patch! Yet something to improve:
[auto build test ERROR on net-next/master]
url: https://github.com/0day-ci/linux/commits/Leslie-Monis/net-sched-pie-align-PIE-implementation-with-RFC-8033/20190226-041701
config: arm-allyesconfig (attached as .config)
compiler: arm-linux-gnueabi-gcc (Debian 8.2.0-11) 8.2.0
reproduce:
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
GCC_VERSION=8.2.0 make.cross ARCH=arm
All errors (new ones prefixed by >>):
arm-linux-gnueabi-ld: net/sched/sch_pie.o: in function `pie_timer':
>> sch_pie.c:(.text+0xc3c): undefined reference to `__aeabi_uldivmod' >> arm-linux-gnueabi-ld: sch_pie.c:(.text+0xed8): undefined reference to `__aeabi_uldivmod'
arm-linux-gnueabi-ld: net/sched/sch_pie.o: in function `pie_qdisc_enqueue':
sch_pie.c:(.text+0x168c): undefined reference to `__aeabi_uldivmod'
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation
kbuild test robot
build botRe: [PATCH net-next v2 5/7] net: sched: pie: add more cases to auto-tune alpha and beta
In reply to Leslie MonisThank you for the patch! Yet something to improve:
Hi Mohit,
Thank you for the patch! Yet something to improve:
[auto build test ERROR on net-next/master]
url: https://github.com/0day-ci/linux/commits/Leslie-Monis/net-sched-pie-align-PIE-implementation-with-RFC-8033/20190226-041701
config: mips-allmodconfig (attached as .config)
compiler: mips-linux-gnu-gcc (Debian 8.2.0-11) 8.2.0
reproduce:
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
GCC_VERSION=8.2.0 make.cross ARCH=mips
All errors (new ones prefixed by >>):
>> ERROR: "__udivdi3" [net/sched/sch_pie.ko] undefined!
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation
PATCH v2 6/7 net: sched: pie: add derandomization mechanism
In reply to Leslie MonisFrom: "Mohit P. Tahiliani" <[email protected]>
Random dropping of packets to achieve latency control may introduce outlier situations where packets are dropped too close to each other or too far from each other. This can cause the real drop percentage to temporarily deviate from the intended drop probability. In certain scenarios, such as a small number of simultaneous TCP flows, these deviations can cause significant deviations in link utilization and queuing latency.
RFC 8033 suggests using a derandomization mechanism to avoid these deviations.
--- net/sched/sch_pie.c | 28 +++++++++++++++++++++++++++- 1 file changed, 27 insertions(+), 1 deletion(-)
net/sched/sch_pie.c +27 -1
@@ -55,8 +55,10 @@ struct pie_vars {psched_time_t qdelay_old;u64 dq_count;/* measured in bytes */ psched_time_t dq_tstamp;/* drain rate */ +u64 accu_prob;/* accumulated drop probability */ u32 avg_dq_rate;/* bytes per pschedtime tick,scaled */ u32 qlen_old;/* in bytes */ +u8 accu_prob_overflows;/* overflows of accu_prob */ };/* statistics gathering */
@@ -91,9 +93,11 @@ static void pie_params_init(struct pie_params *params)static void pie_vars_init (struct pie_vars *vars) { vars->dq_count =DQCOUNT_INVALID ; + vars->accu_prob =0 ; vars->avg_dq_rate =0 ;/* default of 150 ms in pschedtime */ vars->burst_time =PSCHED_NS2TICKS (150 *NSEC_PER_MSEC ); + vars->accu_prob_overflows =0 ; }static bool drop_early (struct Qdisc *sch,u32 packet_size)
@@ -128,9 +132,29 @@ static bool drop_early(struct Qdisc *sch, u32 packet_size)else local_prob = q->vars.prob; +if (local_prob ==0 ) { + q->vars.accu_prob =0 ; + q->vars.accu_prob_overflows =0 ; + } + +if (local_prob >MAX_PROB - q->vars.accu_prob) + q->vars.accu_prob_overflows++; + + q->vars.accu_prob += local_prob; + +if (q->vars.accu_prob_overflows ==0 && + q->vars.accu_prob < (MAX_PROB /100 ) *85 ) +return false; +if (q->vars.accu_prob_overflows ==8 && + q->vars.accu_prob >=MAX_PROB /2 ) +return true; +prandom_bytes (&rnd,8 ); -if (rnd < local_prob) +if (rnd < local_prob) { + q->vars.accu_prob =0 ; + q->vars.accu_prob_overflows =0 ;return true; + }return false; }
@@ -168,6 +192,8 @@ static int pie_qdisc_enqueue(struct sk_buff *skb, struct Qdisc *sch, out: q->stats.dropped++; + q->vars.accu_prob =0 ; + q->vars.accu_prob_overflows =0 ;return qdisc_drop (skb, sch, to_free); }
Signature · 1 line
2.17.1
PATCH v2 7/7 net: sched: pie: update references
In reply to Leslie MonisFrom: "Mohit P. Tahiliani" <[email protected]>
RFC 8033 replaces the IETF draft for PIE
--- net/sched/sch_pie.c | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-)
net/sched/sch_pie.c +1 -3
@@ -17,9 +17,7 @@* University of Oslo, Norway. * * References: -* IETF draft submission: http://tools.ietf.org/html/draft-pan-aqm-pie-00 -* IEEE Conference on High Performance Switching and Routing 2013 : -* "PIE: A * Lightweight Control Scheme to Address the Bufferbloat Problem" +* RFC 8033: https://tools.ietf.org/html/rfc8034 */ #include <linux/module.h>
Signature · 1 line
2.17.1
Jamal Hadi Salim
maintainerQuoted 9 lines · Leslie Monis
The current implementation of the PIE queuing discipline is according to the IETF draft [http://tools.ietf.org/html/draft-pan-aqm-pie-00] and the paper [PIE: A Lightweight Control Scheme to Address the Bufferbloat Problem]. However, a lot of necessary modifications and enhancements have been proposed in RFC 8033, which have not yet been incorporated in the source code of Linux. This patch series helps in achieving the same.
Performance tests carried out using Flent [https://flent.org/]
+Cc the authors of PIE to double check these values. Please respond (it is how open source works!) and N/ACK
cheers,
jamal
Jamal Hadi Salim
maintainerQuoted 8 lines · Jamal Hadi Salim
Quoted 7 lines · Leslie Monis
The current implementation of the PIE queuing discipline is according to the IETF draft [http://tools.ietf.org/html/draft-pan-aqm-pie-00] and the paper [PIE: A Lightweight Control Scheme to Address the Bufferbloat Problem]. However, a lot of necessary modifications and enhancements have been proposed in RFC 8033, which have not yet been incorporated in the source code of Linux. This patch series helps in achieving the same.
Quoted 5 lines
Quoted 2 lines
Performance tests carried out using Flent [https://flent.org/]
+Cc the authors of PIE to double check these values. Please respond (it is how open source works!) and N/ACK
Great. Bouncing addresses.
D. Taht - can you look at this?
cheers,
jamal
Dave Taht
Acked-byQuoted 13 lines · Jamal Hadi Salim
Quoted 12 lines · Jamal Hadi Salim
Quoted 11 lines · Leslie Monis
The current implementation of the PIE queuing discipline is according to the
IETF draft [http://tools.ietf.org/html/draft-pan-aqm-pie-00] and the paper
[PIE: A Lightweight Control Scheme to Address the Bufferbloat Problem]. However, a lot of necessary modifications and enhancements have been proposed
in RFC 8033, which have not yet been incorporated in the source code of Linux.
This patch series helps in achieving the same.
Quoted 8 lines
Quoted 5 lines
Quoted 2 lines
Performance tests carried out using Flent [https://flent.org/]
+Cc the authors of PIE to double check these values. Please respond (it is how open source works!) and N/ACK
Great. Bouncing addresses.
D. Taht - can you look at this?
Whose addresses are bouncing? The folk that did pie originally were mostly contractors and long ago moved on to other things.
My taht.net address tends to bounce to vger as I long ago mandated starttls on all email transactions which is why I use my gmail account for postings there. I keep hoping that one day vger will support starttls... posting it here as I'm an optimist. I wasn't expecting to be cc'd on this submittal....
Pie seems to be mostly an abandoned CISCO effort outside of docsis-pie, at least at the moment. I've heard not a peep from them in years. (fq_codel seems to have mostly "won" in our world)
I did review all these changes when they went by in v1, and aside from the ecn mistake ending up in the final RFC when I wasn't looking[1], approve of these changes to sch_pie to make it compliant with the rfc, finally.
[1] We proposed refining pie's ecn handling here:
https://github.com/gautamramk/FQ-PIE-for-Linux-Kernel/issues/2
Anyway:
Quoted 18 lines · Dave Taht
Quoted 16 lines · Jamal Hadi Salim
Quoted 15 lines · Jamal Hadi Salim
Quoted 13 lines · Leslie Monis
The current implementation of the PIE queuing discipline is according to the
IETF draft [http://tools.ietf.org/html/draft-pan-aqm-pie-00] and the paper
[PIE: A Lightweight Control Scheme to Address the Bufferbloat Problem]. However, a lot of necessary modifications and enhancements have been proposed
in RFC 8033, which have not yet been incorporated in the source code of Linux.
This patch series helps in achieving the same.Performance tests carried out using Flent [https://flent.org/]
Quoted 9 lines
Quoted 5 lines
Quoted 2 lines
+Cc the authors of PIE to double check these values. Please respond (it is how open source works!) and N/ACK
Great. Bouncing addresses.
D. Taht - can you look at this?Whose addresses are bouncing? The folk that did pie originally were mostly contractors and long ago moved on to other things.
The Cisco addresses - listed as authors of PIE were bouncing.
Note: they are still listed as authors of the referenced IETF draft with those email addresses.
Quoted 15 lines
My taht.net address tends to bounce to vger as I long ago mandated starttls on all email transactions which is why I use my gmail account for postings there. I keep hoping that one day vger will support starttls... posting it here as I'm an optimist. I wasn't expecting to be cc'd on this submittal....
Pie seems to be mostly an abandoned CISCO effort outside of docsis-pie, at least at the moment. I've heard not a peep from them in years. (
fq_codelseems to have mostly "won" in our world)I did review all these changes when they went by in v1, and aside from the ecn mistake ending up in the final RFC when I wasn't looking[1], approve of these changes to
sch_pieto make it compliant with the rfc, finally.
Quoted 8 lines
[1] We proposed refining pie's ecn handling here:
https://github.com/gautamramk/FQ-PIE-for-Linux-Kernel/issues/2
Anyway:
Acked-by Dave Taht <[email protected]>
Thats what i was hoping for. FWIW,
cheers,
jamal
Quoted 42 lines · Dave Taht
Quoted 13 lines · Jamal Hadi Salim
Quoted 12 lines · Jamal Hadi Salim
Quoted 11 lines · Leslie Monis
The current implementation of the PIE queuing discipline is according to the
IETF draft [http://tools.ietf.org/html/draft-pan-aqm-pie-00] and the paper
[PIE: A Lightweight Control Scheme to Address the Bufferbloat Problem]. However, a lot of necessary modifications and enhancements have been proposed
in RFC 8033, which have not yet been incorporated in the source code of Linux.
This patch series helps in achieving the same.Quoted 8 lines
Quoted 5 lines
Quoted 2 lines
Performance tests carried out using Flent [https://flent.org/]
+Cc the authors of PIE to double check these values. Please respond (it is how open source works!) and N/ACK
Great. Bouncing addresses.
D. Taht - can you look at this?Whose addresses are bouncing? The folk that did pie originally were mostly contractors and long ago moved on to other things.
My taht.net address tends to bounce to vger as I long ago mandated starttls on all email transactions which is why I use my gmail account for postings there. I keep hoping that one day vger will support starttls... posting it here as I'm an optimist. I wasn't expecting to be cc'd on this submittal....
Pie seems to be mostly an abandoned CISCO effort outside of docsis-pie, at least at the moment. I've heard not a peep from them in years. (
fq_codelseems to have mostly "won" in our world)I did review all these changes when they went by in v1, and aside from the ecn mistake ending up in the final RFC when I wasn't looking[1], approve of these changes to
sch_pieto make it compliant with the rfc, finally.
Quoted 8 lines
[1] We proposed refining pie's ecn handling here:
https://github.com/gautamramk/FQ-PIE-for-Linux-Kernel/issues/2
Anyway:
Acked-by Dave Taht <[email protected]>
Hi Dave,
For now we would just like to make the PIE implementation meet the standards as expressed by the RFC. As ECN handling is outside the scope of the RFC we can consider refinements to it in the code later.
Thanks,
Leslie