From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-la0-x22d.google.com (mail-la0-x22d.google.com [IPv6:2a00:1450:4010:c03::22d]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by huchra.bufferbloat.net (Postfix) with ESMTPS id 44E8B21F26A for ; Wed, 25 Feb 2015 12:00:35 -0800 (PST) Received: by lamq1 with SMTP id q1so6392021lam.5 for ; Wed, 25 Feb 2015 12:00:33 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=content-type:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=fUfmBbsS4eYeKYcvbquzMdt9B9JKDBYFtQJXOhTol5w=; b=nb7js8jlB8XurewGI3xInkgBbHA40Y6+qf1RS75UmOIkGgen1O/d+Df2MrBXYkNSZ8 Fo/PpwgTJetmtrb8iELpTP3gUWeRBpCFZESjzVHC7uYQ6oeh8tO8Ogm5834NXgDTDkso I9MBu7ORSkhnsFM+Ht6qhQ+8eG99AXqfysZMSkl/+QDBj0+ZrjtUj922wlffzkDoOwey rMWKLfUpcE2/Aow+PJo5Lt5HKF6mSy/Sw16dUKETAomhCXuxaXCs2DZzyR3x+W1JYmoC 3qiGla8gBtJcBX0lQGGsyXDPNxGKED1U0rF2FXjXnBBfqEcTl2w2BhFIf6mprFTVKoMe 0fAQ== X-Received: by 10.112.215.35 with SMTP id of3mr4408922lbc.101.1424894432941; Wed, 25 Feb 2015 12:00:32 -0800 (PST) Received: from [192.168.43.25] (37-219-125-17.nat.bb.dnainternet.fi. [37.219.125.17]) by mx.google.com with ESMTPSA id pf1sm4231628lbc.32.2015.02.25.12.00.30 (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Wed, 25 Feb 2015 12:00:32 -0800 (PST) Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2070.6\)) From: Jonathan Morton In-Reply-To: <20150225192515.1D738406057@ip-64-139-1-69.sjc.megapath.net> Date: Wed, 25 Feb 2015 22:00:28 +0200 Content-Transfer-Encoding: quoted-printable Message-Id: <45F96412-5317-42A0-A426-E342DD221C7C@gmail.com> References: <20150225192515.1D738406057@ip-64-139-1-69.sjc.megapath.net> To: Hal Murray X-Mailer: Apple Mail (2.2070.6) Cc: bloat@lists.bufferbloat.net Subject: Re: [Bloat] RED against bufferbloat X-BeenThere: bloat@lists.bufferbloat.net X-Mailman-Version: 2.1.13 Precedence: list List-Id: General list for discussing Bufferbloat List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 25 Feb 2015 20:01:03 -0000 > On 25 Feb, 2015, at 21:25, Hal Murray wrote: >=20 >> That's easy enough. You can fit an awful lot of linked list pointers = into >> the space of a single IP packet. Even if you're only assigning 64KB = per >> subscriber, you can store 43 full packets and still have pointers to = spare. >> A properly functioning AQM should mostly keep the queue smaller than = that.=20 >=20 > Is a slot for the head-of-list pointer all the information you need to=20= > remember for an empty queue? Or do you need some memory of recent = traffic? The Linux implementation of fq_codel uses DRR for the FQ bit. For that, you need a head pointer (for fast dequeue), a tail pointer = (for fast enqueue), and a deficit counter (to implement the fairness) = per flow. With some granularity in the pointers, or else with a fixed = queue arena of some tens of megabytes maximum, you can squeeze all that = into 8 bytes per flow quite comfortably. You also need a set of codel variables per flow (these are not large), a = free-list of spaces to put new packets, and a =E2=80=98next=E2=80=99 = pointer per enqueued packet. The latter two might already be present in = some form, depending on the FIFO implementation - that is, if it=E2=80=99s= not just a ring buffer. With these taken into account, I think we=E2=80=99re still looking at = 40+ full-size packets in a 64KB arena, or a larger number if smaller = packets are mixed in. DRR will tend to service flows with smaller = packets more often, leading to bandwidth fairness. - Jonathan Morton