From patchwork Wed Oct 31 16:19:31 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Leslie Monis X-Patchwork-Id: 991535 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="gXm1XGxy"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 42lYTM6tqpz9s1x for ; Thu, 1 Nov 2018 03:20:07 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1729823AbeKABSr (ORCPT ); Wed, 31 Oct 2018 21:18:47 -0400 Received: from mail-pf1-f196.google.com ([209.85.210.196]:33704 "EHLO mail-pf1-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1729287AbeKABSr (ORCPT ); Wed, 31 Oct 2018 21:18:47 -0400 Received: by mail-pf1-f196.google.com with SMTP id a15-v6so7873129pfn.0 for ; Wed, 31 Oct 2018 09:20:05 -0700 (PDT) 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=QvOinuQ6ETSN1mLVrCbA5b7aOdllwP2VtcWdZ2PwhUw=; b=gXm1XGxytD5b/lBXaxV4MNOcIkHDyrE1xU+YqcRTap+6wqT3POWLDw53EXUZqzn3hA m3AiOtyvg2bKGuHE1KaNpmgtmby3EPou5GION2YsOVecmuVWYQQ8Z47li6aBIv9aHJaZ I43GHgbjP95PyKW/D32k7Z/JFuIpByHXnJly5acCjjYjxZ7/vlU58gpudmu5CZpm/0+v F2RxS273A2BaMqrEDsVPwWOHEZa257J0Cfc0gaPyx9aNTmr9VctcvIk7QmEIsD0s8Q4v yU71XQcdXLs1UFNV69dQ4bKAE8gXuNCqmQBpZLmtg4tbrrL70CT6VAPyO1UCg/xqQiyH 5sCQ== 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=QvOinuQ6ETSN1mLVrCbA5b7aOdllwP2VtcWdZ2PwhUw=; b=mmkYiamHCZJSFtXSd0xeX/vUrGON/XOYsFnv1vr/0T3iDz0X5Fnx2NOyyvjI69JtoQ 681YVm7S3oKhwsFvvBsfs6VqFo80U75dNLAYpEeQheUxBvOMc6cgQBGM+AKM0YnYqXb2 lMiyTKHSFVCn/ynAmiXqAeebppOcpMe+/SYnVRsFgZ0ASuq5KosqI4PvAIvAtokL9MLK lJ/Ltr4kQKEjap30EMtxGIQvMuHHeWalC6p5vqWZFXGvAjrr1989fWbdw4NAcjszf1ca Q6ALUQXUQyIvwSX0j9u1uofIj5eB1zNxh6Smkh9eQFhUow6vWKlZvxM1T/5lZORYRzqS nNFA== X-Gm-Message-State: AGRZ1gLHfxtKkotlMtNm1qS711c1CDz590f8V6nNBCcUAY4FWpQs/7Sy Kk711mE1gjd6NuWwtXs0mPo= X-Google-Smtp-Source: AJdET5e8fZfj5pZUCWsY+O7WtZ94q3R9TefXYiVj0U9K1E6BmHL/5zmWBCZ/9dt/DCK1wQodcKtNHQ== X-Received: by 2002:a63:1066:: with SMTP id 38-v6mr3837005pgq.254.1541002805514; Wed, 31 Oct 2018 09:20:05 -0700 (PDT) Received: from Inspiron.nitk.ac.in ([106.193.104.195]) by smtp.gmail.com with ESMTPSA id i21-v6sm33812969pgj.55.2018.10.31.09.20.02 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 31 Oct 2018 09:20:05 -0700 (PDT) From: Leslie Monis To: jhs@mojatatu.com Cc: netdev@vger.kernel.org, tahiliani@nitk.edu.in, dhavaljkhandla26@gmail.com, hrishihiraskar@gmail.com, bmanish15597@gmail.com, sdp.sachin@gmail.com Subject: [PATCH net-next 7/8] net: sched: pie: add derandomization mechanism Date: Wed, 31 Oct 2018 21:49:31 +0530 Message-Id: <1541002772-28040-8-git-send-email-lesliemonis@gmail.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1541002772-28040-1-git-send-email-lesliemonis@gmail.com> References: <1541002772-28040-1-git-send-email-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 | 17 ++++++++++++++++- 1 file changed, 16 insertions(+), 1 deletion(-) 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); }