From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wm0-x233.google.com (mail-wm0-x233.google.com [IPv6:2a00:1450:400c:c09::233]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id 9AEBD3CC3C for ; Wed, 6 Apr 2016 03:17:00 -0400 (EDT) Received: by mail-wm0-x233.google.com with SMTP id v188so12360457wme.1 for ; Wed, 06 Apr 2016 00:17:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=tieto.com; s=google; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-transfer-encoding; bh=vtQc+OEVnF1t1BXPAxIzGii811ULPnGRyKIutWKBg0k=; b=vK+xy4vtixpOiUTvF/L6TOgXKvdhFoVb2CjONX2A+9hZHU2mM3dLSDMWb3dn4vZwIv nmJraK5SW2obpnG5hAjUl4e+riYqt0T6SwC5Tt4t1es8bMqyyS1OQDVB9YD+kve31gba nM1MwJGFU919/m1eDYLUc9WBiG2xPFLiGKTPE= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-transfer-encoding; bh=vtQc+OEVnF1t1BXPAxIzGii811ULPnGRyKIutWKBg0k=; b=J/cUZHAQDmTcUQAJ5iBB7JNXXk589r08dAfcOI8M52Ua7cBvnknNuyrsj+HWLnGLwn sNhk/2sio24qWJa9hjaebzG87wJg8VRH59z51qdHUPdWRkuw7XfUjUfBwKgL/0cKyEGY 90+AYuB+jaVImKSGhoFMRMdOFIKKsjFafZpU7NERlgeAjKZVdb4dpystZhV5kdF9GPFx fDe7qLItsNw2jxX0VEcm1WqBVax7A1HURBxSF+qnBeN/Ti7xao01mQULYp9HyyqqHd+k /LBjYVhJgPxRamNHd3zi9NBCXxCrhl6QcFYM64IdpJsooI/+cMF2tpTZnhU3VhteQNBX Z8gA== X-Gm-Message-State: AD7BkJKPojJ9lHjalpgnq3Jvgj4K328OtDDaCNBnHHjifbIX5XFBhyGjRpF2hNKUCEAd7KSkh89dSafSZps4Le/eFoIhipJrmwsfRcOYIS+6+v2OnwhhlyuP9m3o44O9XLCsRWdUcJE/9W6YU/eKCiFF62mOT4fe8rxhLw== MIME-Version: 1.0 X-Received: by 10.28.45.212 with SMTP id t203mr22159389wmt.71.1459927019756; Wed, 06 Apr 2016 00:16:59 -0700 (PDT) Received: by 10.194.115.3 with HTTP; Wed, 6 Apr 2016 00:16:59 -0700 (PDT) In-Reply-To: <2233FCEB-7412-4F22-B262-068AFBB2FDCB@gmail.com> References: <1458898052-20601-1-git-send-email-michal.kazior@tieto.com> <1459420104-31554-1-git-send-email-michal.kazior@tieto.com> <1459420104-31554-2-git-send-email-michal.kazior@tieto.com> <1459864656.18188.60.camel@sipsolutions.net> <2233FCEB-7412-4F22-B262-068AFBB2FDCB@gmail.com> Date: Wed, 6 Apr 2016 09:16:59 +0200 Message-ID: From: Michal Kazior To: Jonathan Morton Cc: Johannes Berg , make-wifi-fast@lists.bufferbloat.net, linux-wireless , codel@lists.bufferbloat.net Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-DomainID: tieto.com Subject: Re: [Make-wifi-fast] [PATCHv2 1/2] mac80211: implement fair queuing per txq X-BeenThere: make-wifi-fast@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 06 Apr 2016 07:17:00 -0000 On 6 April 2016 at 08:03, Jonathan Morton wrote: > >> On 6 Apr, 2016, at 08:35, Michal Kazior wrote: >> >> Packets can be destined to different stations/txqs. At enqueue time I >> do a partial hash of a packet to get an "index" which I then use to >> address a txq_flow from per-radio list (out of 4096 of them). You can >> end up with a situtation like this: >> - packet A hashing to X destined to txq P which is VI >> - packet B hashing to X destined to txq Q which is BK >> >> You can't use the same txq_flow for both A and B because you want to >> maintain packets per txqs more than you want to maintain them per flow >> (you don't want to queue BK traffic onto VI or vice versa as an >> artifact, do you? ;). When a txq_flow doesn't have a txqi it is bound. >> Later, if a collision happens (i.e. resulting txq_flow has non-NULL >> txqi) the "embedded" per-txq flow is used: >> >> struct txq_info { >> - struct sk_buff_head queue; >> + struct txq_flow flow; // <--- this >> >> When txq_flow becomes empty its txqi is reset. >> >> The embedded flow is otherwise treated like any other flow, i.e. it >> can be linked to old_flows and new_flows. > > This smells like a very fragile and complex solution to the collision pro= blem. You may want to look at how Cake solves it. > > I use a separate pool of flows per traffic class (essentially, VO/VI/BE/B= K), and there is also a set-associative hash to take care of the birthday p= roblem. The latter has an order-of-magnitude effect on the general flow co= llision rate once you get into the tens of flows, for very little CPU cost. When a driver asks mac80211 to dequeue given txq it implies a destination station as well. This is important because 802.11 aggregation can be performed only on groups of packets going to a single station on a single tid. Cake - as I understand it - doesn't really *guarantee* maintaining this. Keep in mind you can run with hundreds of stations connected. You don't really want to burden drivers with sorting this grouping up themselves (and hence coerce them into introducing another level of intermediate queues, bis). Without the per-txq fallback flow (regardless of using fq_codel-like scheme or cake-like scheme in mac80211) you'll need to modify codel_dequeue() itself to compensate and re-queue/skip frames not belonging to requested txq. I'm not sure it's worth it for initial fair-queuing implementation. Micha=C5=82