diff mbox series

[net-next,7/8] net: sched: pie: add derandomization mechanism

Message ID 1541002772-28040-8-git-send-email-lesliemonis@gmail.com
State Deferred, archived
Delegated to: David Miller
Headers show
Series net: sched: pie: align PIE implementation with RFC 8033 | expand

Commit Message

Leslie Monis Oct. 31, 2018, 4:19 p.m. UTC 
From: "Mohit P. Tahiliani" <tahiliani@nitk.edu.in>

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.

Signed-off-by: Mohit P. Tahiliani <tahiliani@nitk.edu.in>
Signed-off-by: Dhaval Khandla <dhavaljkhandla26@gmail.com>
Signed-off-by: Hrishikesh Hiraskar <hrishihiraskar@gmail.com>
Signed-off-by: Manish Kumar B <bmanish15597@gmail.com>
Signed-off-by: Sachin D. Patil <sdp.sachin@gmail.com>
Signed-off-by: Leslie Monis <lesliemonis@gmail.com>
---
 net/sched/sch_pie.c | 17 ++++++++++++++++-
 1 file changed, 16 insertions(+), 1 deletion(-)

Comments

Stephen Hemminger Oct. 31, 2018, 4:38 p.m. UTC | #1 
On Wed, 31 Oct 2018 21:49:31 +0530
Leslie Monis <lesliemonis@gmail.com> wrote:

> diff --git a/net/sched/sch_pie.c b/net/sched/sch_pie.c
> index b68b367..88e605c 100644
> --- a/net/sched/sch_pie.c
> +++ b/net/sched/sch_pie.c
> @@ -58,6 +58,7 @@ struct pie_vars {
>  	u32 avg_dq_rate;	/* bytes per pschedtime tick,scaled */
>  	u32 qlen_old;		/* in bytes */
>  	bool active;		/* inactive/active */
> +	u64 accu_prob;		/* accumulated drop probability */
>  };
>  

Although putting it at the end seems like a natural place, it creates
holes in the c structure. My recommendation would be to put the new
field after dq_tsstamp.
diff mbox series

Patch

diff --git a/net/sched/sch_pie.c b/net/sched/sch_pie.c
index b68b367..88e605c 100644
--- a/net/sched/sch_pie.c
+++ b/net/sched/sch_pie.c
@@ -58,6 +58,7 @@  struct pie_vars {
 	u32 avg_dq_rate;	/* bytes per pschedtime tick,scaled */
 	u32 qlen_old;		/* in bytes */
 	bool active;		/* inactive/active */
+	u64 accu_prob;		/* accumulated drop probability */
 };
 
 /* statistics gathering */
@@ -96,6 +97,7 @@  static void pie_vars_init(struct pie_vars *vars)
 	/* default of 150 ms in pschedtime */
 	vars->burst_time = PSCHED_NS2TICKS(150 * NSEC_PER_MSEC);
 	vars->active = true;
+	vars->accu_prob = 0;
 }
 
 static bool drop_early(struct Qdisc *sch, u32 packet_size)
@@ -130,9 +132,21 @@  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 += local_prob;
+
+	if (q->vars.accu_prob < (MAX_PROB / 100) * 85)
+		return false;
+	if (q->vars.accu_prob >= ((u64)MAX_PROB * 17) / 2)
+		return true;
+
 	rnd = prandom_u32();
-	if (rnd < local_prob)
+	if (rnd < local_prob) {
+		q->vars.accu_prob = 0;
 		return true;
+	}
 
 	return false;
 }
@@ -181,6 +195,7 @@  static int pie_qdisc_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 
 out:
 	q->stats.dropped++;
+	q->vars.accu_prob = 0;
 	return qdisc_drop(skb, sch, to_free);
 }