net: sched: pie: align PIE implementation with RFC 8033
Subsystems (3)
v3 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 v2 to v3:
- Used div_u64() instead of direct division after explicit type casting as recommended by David
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 v3 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 v3 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 v3 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 v3 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 v3 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
PATCH v3 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 v3 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
David Miller
maintainerFrom: Leslie Monis <[email protected]>
Date: Tue, 26 Feb 2019 00:39:54 +0530
Quoted 13 lines
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 v2 to v3:
- Useddiv_u64()instead of direct division after explicit type casting as recommended by David
Quoted 8 lines
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 theaccu_probvariable in thepie_varsstructure as recommended by Stephen
Series applied, thanks.
Quoted 31 lines · On Tue, 26 Feb 2019 00:39:54 +0530 Leslie Monis <[email protected]> wrote:
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 v2 to v3:
- Useddiv_u64()instead of direct division after explicit type casting as recommended by DavidChanges 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 theaccu_probvariable in thepie_varsstructure as recommended by StephenMohit P. Tahiliani (7):
net: sched: pie: change value ofQUEUE_THRESHOLD
net: sched: pie: change default value ofpie_params->target
net: sched: pie: change default value ofpie_params->tupdate
net: sched: pie: change initial value ofpie_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
Quoted 3 lines
include/uapi/linux/pkt_sched.h | 2 +- net/sched/sch_pie.c | 107 ++++++++++++++++++++------------- 2 files changed, 66 insertions(+), 43 deletions(-)
Are you concerned at all that changes to default values might change expected behavior of existing users?
Quoted 35 lines · Stephen Hemminger
Quoted 31 lines · On Tue, 26 Feb 2019 00:39:54 +0530 Leslie Monis <[email protected]> wrote:
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 v2 to v3:
- Useddiv_u64()instead of direct division after explicit type casting as recommended by DavidChanges 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 theaccu_probvariable in thepie_varsstructure as recommended by StephenMohit P. Tahiliani (7):
net: sched: pie: change value ofQUEUE_THRESHOLD
net: sched: pie: change default value ofpie_params->target
net: sched: pie: change default value ofpie_params->tupdate
net: sched: pie: change initial value ofpie_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
Quoted 6 lines
Quoted 3 lines
include/uapi/linux/pkt_sched.h | 2 +- net/sched/sch_pie.c | 107 ++++++++++++++++++++------------- 2 files changed, 66 insertions(+), 43 deletions(-)Are you concerned at all that changes to default values might change expected behavior of existing users?
There's existing users?
Most of these changes are really subtle and came out as we went along. I'd have to *really search* to find my notes from that period, and I have not evaluated the sum of these new changes, but overall they were a slight improvement from the defaults as we shipped it way back when.
I'm not being snarky - are there existing users? Every last person I know that ever evaluated pie switched to fq_codel. Cisco ended up going with another bufferbloat-fighting solution in one new device and that team dissolved.
docsis-pie, well, that's a standard. and that's a bit different from this pie, but this pie is closer to that pie. And it works ok.
I certainly hope leslie's group has done similar testing to what we did then ? If there's results I can dig up my old results and see what compares. I imagine they plan a paper. our old flent test code and data is all published, but am not willing to spend another minute of my life on a single queued aqm design unless someone writes me a very big check for it, which I'd then spend on fixing P4 to run fq-codel.
fq-pie (which is waiting in the wings behind this set of patches) is ok, as at least, the BSD version was competetive with fq_codel in most respects. I told 'em they needed to look hard at the rate estimator.
The ECN handling problem mentioned is there on all known versions of pie, but it's that it reverts to drop too soon for ecn to be as much benefit as it could be.
and then l4s, which is the subject of 3 upcoming talks at netdevconf, well... not gonna talk about it. I'm willing to give them their day in court.
sorry to come across as grumpy. should linux be rfc compliant even if the rfc has issues? damned if I know.
Signature · 4 lines
Dave Täht CTO, TekLibre, LLC http://www.teklibre.com Tel: 1-831-205-9740
Quoted 34 lines · Stephen Hemminger
Quoted 31 lines · On Tue, 26 Feb 2019 00:39:54 +0530 Leslie Monis <[email protected]> wrote:
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 v2 to v3:
- Useddiv_u64()instead of direct division after explicit type casting as recommended by DavidChanges 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 theaccu_probvariable in thepie_varsstructure as recommended by StephenMohit P. Tahiliani (7):
net: sched: pie: change value ofQUEUE_THRESHOLD
net: sched: pie: change default value ofpie_params->target
net: sched: pie: change default value ofpie_params->tupdate
net: sched: pie: change initial value ofpie_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
Quoted 6 lines
Quoted 3 lines
include/uapi/linux/pkt_sched.h | 2 +- net/sched/sch_pie.c | 107 ++++++++++++++++++++------------- 2 files changed, 66 insertions(+), 43 deletions(-)Are you concerned at all that changes to default values might change expected behavior of existing users?
Hi Stephen,
As Dave mentioned, the changes which we have made do not really change the behaviour of the aqm drastically. Our performance tests show that these changes improve performance without any side-effects. So existing users (if there are any) should not be negatively affected in any way.
Leslie
Quoted 42 lines · On Tue, 26 Feb 2019 13:50:46 +0530 Leslie Monis <[email protected]> wrote:
Quoted 34 lines · Stephen Hemminger
Quoted 31 lines · On Tue, 26 Feb 2019 00:39:54 +0530 Leslie Monis <[email protected]> wrote:
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 v2 to v3:
- Useddiv_u64()instead of direct division after explicit type casting as recommended by DavidChanges 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 theaccu_probvariable in thepie_varsstructure as recommended by StephenMohit P. Tahiliani (7):
net: sched: pie: change value ofQUEUE_THRESHOLD
net: sched: pie: change default value ofpie_params->target
net: sched: pie: change default value ofpie_params->tupdate
net: sched: pie: change initial value ofpie_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 referencesQuoted 6 lines
Quoted 3 lines
include/uapi/linux/pkt_sched.h | 2 +- net/sched/sch_pie.c | 107 ++++++++++++++++++++------------- 2 files changed, 66 insertions(+), 43 deletions(-)Are you concerned at all that changes to default values might change expected behavior of existing users?
Quoted 6 lines
Hi Stephen,
As Dave mentioned, the changes which we have made do not really change the behaviour of the aqm drastically. Our performance tests show that these changes improve performance without any side-effects. So existing users (if there are any) should not be negatively affected in any way.
Thanks for answering. Looks good