From patchwork Mon Feb 25 10:20:50 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Leslie Monis X-Patchwork-Id: 1047651 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="VFUAz7HG"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 447J2w36Cqz9ryj for ; Mon, 25 Feb 2019 21:24:24 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726766AbfBYKYX (ORCPT ); Mon, 25 Feb 2019 05:24:23 -0500 Received: from mail-pf1-f196.google.com ([209.85.210.196]:44543 "EHLO mail-pf1-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726617AbfBYKYX (ORCPT ); Mon, 25 Feb 2019 05:24:23 -0500 Received: by mail-pf1-f196.google.com with SMTP id a3so4284007pff.11 for ; Mon, 25 Feb 2019 02:24:22 -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=BF4261GS/DITgP9ORlcqD0UoIK3lVA36V4n3kfhZP1w=; b=VFUAz7HGDgmpcEqYuwcO9dumkYXc2UaPiQVTC0DKaPH6M6V2x7Mpe/EppOZeuVLIuP NfuZXG6BmbMUt6Pd1dMjD9iDpVradEQfeK/A7v71iZ6/vpbe3MYHxmtro3xyipuIiLTa oHfSEDplYTuhgOCYABW9Wn07IxIyUvezVgvLZAx769nVX5pRVi8cEAPswTSNb5xt9Dit tyJpG/tz4aUP3IOAX8fB10ql03UE4HoAG2k9wfC6tRajIYXqwjOYL1zYn95xKxduraS9 lwBniwcL4D7qHSbvVGQIqrgLEcFB6neI/57RIx/4n5gmWlq+w3seivn8laish3a6ANCb MZeA== 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=BF4261GS/DITgP9ORlcqD0UoIK3lVA36V4n3kfhZP1w=; b=Ab6ooHM4hjmi7K97ZS4qHAkjzg1s9ebZBwid7AaquO4YZzKya6bLoCHgyOpp/jtqa6 t7DSB8k+ggXUc18WZn8IhHuUp/Bsx46PyM8PFDs+Q/fppTUvzhph1BLKzX3VUfUM5/8m 2+NRIgBqYCFGstC+X9SB8+ePmbe/VfBUmOEg9f10c9M9W5sLwoFeE75fz3hcVPdGmRN9 WoO0Cj7/2WmJ5Ayiyv/aoheBEd2vFgKlwcIIr9yPuRlVyFLFFtLpob+0JggMx+6pTx+u Gsat5AKt4YoHe/CwEuzoUjUmWATLlegKOZGJk2sFNi0uYf54jRgt6kCYuqZBQbK4c24P jgBA== X-Gm-Message-State: AHQUAuZaklqy3kMqclDcS3r7Ap77uVUDhps5GgasprrmQAEhyiRf0iGk PZLYmZKQWcE1v11bnfTX5U8= X-Google-Smtp-Source: AHgI3IbcyfIf5mkxUi2k/ZF7EZtYmyDIblz+X3ePXrNro6bJZGq0e82+7W4NEDj4pAGq9Cgsoez9gg== X-Received: by 2002:a62:6f49:: with SMTP id k70mr19452708pfc.7.1551090261752; Mon, 25 Feb 2019 02:24:21 -0800 (PST) Received: from localhost.localdomain ([106.216.180.155]) by smtp.gmail.com with ESMTPSA id q28sm13657439pgl.35.2019.02.25.02.24.17 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 25 Feb 2019 02:24:21 -0800 (PST) From: Leslie Monis To: jhs@mojatatu.com Cc: netdev@vger.kernel.org, dave@taht.net, "Mohit P. Tahiliani" , Dhaval Khandla , Hrishikesh Hiraskar , Manish Kumar B , "Sachin D . Patil" , Leslie Monis Subject: [PATCH net-next v2 6/7] net: sched: pie: add derandomization mechanism Date: Mon, 25 Feb 2019 15:50:50 +0530 Message-Id: <20190225102051.12268-7-lesliemonis@gmail.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190225102051.12268-1-lesliemonis@gmail.com> References: <20190225102051.12268-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 --- 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 b9f586cfb51c..8bfd8ca500f9 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); }