From patchwork Mon Feb 25 19:10:00 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Leslie Monis X-Patchwork-Id: 1047959 X-Patchwork-Delegate: davem@davemloft.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.b="a2FUpo2Q"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 447WkJ62S9z9sC3 for ; Tue, 26 Feb 2019 06:10:48 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727277AbfBYTKq (ORCPT ); Mon, 25 Feb 2019 14:10:46 -0500 Received: from mail-pf1-f193.google.com ([209.85.210.193]:41257 "EHLO mail-pf1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726950AbfBYTKo (ORCPT ); Mon, 25 Feb 2019 14:10:44 -0500 Received: by mail-pf1-f193.google.com with SMTP id d25so4925916pfn.8 for ; Mon, 25 Feb 2019 11:10:44 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=bbbifAdEYBM445FndubE8vpyZcAmIVRNnZ/uXVxeiEo=; b=a2FUpo2QS7dTekhdnRkYvGfWSxzIbyMjYfhwn8j7gG2Q66KZUVxWehUL95FAkbCawA b1voJDOBFDcXZCV7/zNuUvRBxmvPJoC8T6ATsDx2GKgPXdKCyG2u3sYSWPMydPsMwMGq NT19IusWJEVMrEzDTH3ulUlS3/i0AlBLdJkHbVYN7teNDxXeTs3G+YOrsMYBRLVp49as tq9/IDJN5Do6iA3U6TdEqt70eietOvqG+EB882lI065xW+wtfHeIIHQpd4/tKL2Rsj63 aDGvIjKsCLU0bRWjrUH23FSWmNon8eZDEulf8/7mKUxPnjRtQX4gBuPiYEsu+UCdO8hd PErw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=bbbifAdEYBM445FndubE8vpyZcAmIVRNnZ/uXVxeiEo=; b=lFG7+CIgF8TS5mUbQOEU0Kgbawsc1fFJro11pmvkYyaQi2RNzWTZfEfWQuB5+PdVCZ dXNrM5L+XBkME3L2dG7BP87B5B0zhtFnzfh09jRe/0claeKCepwxOowQfmnHGGUWpWfK CaUBWBgLEgmyCEqWAx8HS6f8k07dKyu5ZT9BlniSYwNuKDipeA1wqUkpbEgeNmaBO595 WEVFRWGqsdH3tTCXWHaRPhY045Ip93ZLUbRZIrxe6lr3Z/ZM4Zdi9a/1OMOYcpMKlnYl knhWUnK98ZflcRMrNAiIF44QTL94VYqYUdgcyBR5KpEoTWPlZBIx0wL7Trle5+HxxS7G nAKg== X-Gm-Message-State: AHQUAuZXS51oxG26mrJXQzvqxOHuMCjOPV/N+YVNZ3l9UMVbiENvHVWR emWLvWHwXkCROCaQUsahwZE= X-Google-Smtp-Source: AHgI3IYV2zhzZvGZK4FdWLn6TFcetp/U8ngWE9jhBkmlkeSVK3TVnzIHJ+AiJFW09z0q3dgFamghNQ== X-Received: by 2002:a62:ae04:: with SMTP id q4mr19616421pff.213.1551121843801; Mon, 25 Feb 2019 11:10:43 -0800 (PST) Received: from localhost.localdomain ([106.216.180.155]) by smtp.gmail.com with ESMTPSA id g15sm13296394pfo.35.2019.02.25.11.10.39 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 25 Feb 2019 11:10:43 -0800 (PST) From: Leslie Monis To: davem@davemloft.net Cc: netdev@vger.kernel.org, "Mohit P. Tahiliani" , Dave Taht , Jamal Hadi Salim , Dhaval Khandla , Hrishikesh Hiraskar , Manish Kumar B , "Sachin D . Patil" , Leslie Monis Subject: [PATCH net-next v3 6/7] net: sched: pie: add derandomization mechanism Date: Tue, 26 Feb 2019 00:40:00 +0530 Message-Id: <20190225191001.26797-7-lesliemonis@gmail.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190225191001.26797-1-lesliemonis@gmail.com> References: <20190225191001.26797-1-lesliemonis@gmail.com> Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org From: "Mohit P. Tahiliani" 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 Signed-off-by: Dhaval Khandla Signed-off-by: Hrishikesh Hiraskar Signed-off-by: Manish Kumar B Signed-off-by: Sachin D. Patil Signed-off-by: Leslie Monis Acked-by: Dave Taht Acked-by: Jamal Hadi Salim --- net/sched/sch_pie.c | 28 +++++++++++++++++++++++++++- 1 file changed, 27 insertions(+), 1 deletion(-) diff --git a/net/sched/sch_pie.c b/net/sched/sch_pie.c index 30f158582499..916b878d3491 100644 --- a/net/sched/sch_pie.c +++ b/net/sched/sch_pie.c @@ -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); }