From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-vb0-f43.google.com (mail-vb0-f43.google.com [209.85.212.43]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority" (verified OK)) by huchra.bufferbloat.net (Postfix) with ESMTPS id CAF86208AAD; Sun, 2 Dec 2012 14:07:55 -0800 (PST) Received: by mail-vb0-f43.google.com with SMTP id fs19so1390047vbb.16 for ; Sun, 02 Dec 2012 14:07:54 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=subject:from:to:cc:in-reply-to:references:content-type:date :message-id:mime-version:x-mailer:content-transfer-encoding; bh=1XA2jFGQdhxHvnuHIR9W1hihsEzzITRk2BfgopbrVfw=; b=Y58pYf6930Z6b38iPgIx1mfsrGxxGviOELzxuVSf1BJ64nfp0BJvcMvWM3MDluhckW 7qCHL4SggdNZVB4BWYZQ7H1puf/Qjrn+YaTTBlUJpy7YwF7gheTQ75Qrgeu6YxH0Fuaw +w4k+SbecAvtg230ayqhWSWsMxo4zzaspZYQCQMqGPj3REHMl7ExMajv70sEoGfY0z3Y il0TbkWKHEt+9OFQ0k+Qc7UhEZ1n0QtRiNzFJPM6TCgI8oZfHE9L589J0fzL7/34eIO7 ExpI2vliuVEZqnuRV20M9sszv3qvy7OxUbCeY+K5Jb9rTDNBK84UasvOmwaCKdDqxNLs dcKQ== Received: by 10.52.98.196 with SMTP id ek4mr6168759vdb.38.1354486074512; Sun, 02 Dec 2012 14:07:54 -0800 (PST) Received: from [172.26.38.113] ([172.26.38.113]) by mx.google.com with ESMTPS id dl18sm4842659vdb.2.2012.12.02.14.07.51 (version=SSLv3 cipher=OTHER); Sun, 02 Dec 2012 14:07:53 -0800 (PST) From: Eric Dumazet To: Toke =?ISO-8859-1?Q?H=F8iland-J=F8rgensen?= In-Reply-To: <87vcckb0el.fsf@toke.dk> References: <20121127224915.GM2474@linux.vnet.ibm.com> <20121128002710.GS2474@linux.vnet.ibm.com> <50B5887C.7010605@pollere.com> <20121128043838.GX2474@linux.vnet.ibm.com> <20121128160133.GA16995@linux.vnet.ibm.com> <20121128174440.GD2474@linux.vnet.ibm.com> <1354129222.14302.508.camel@edumazet-glaptop> <87vcckb0el.fsf@toke.dk> Content-Type: text/plain; charset="UTF-8" Date: Sun, 02 Dec 2012 14:07:49 -0800 Message-ID: <1354486069.20109.1206.camel@edumazet-glaptop> Mime-Version: 1.0 X-Mailer: Evolution 2.28.3 Content-Transfer-Encoding: 8bit Cc: Paolo Valente , "codel@lists.bufferbloat.net" , "cerowrt-devel@lists.bufferbloat.net" , bloat , paulmck@linux.vnet.ibm.com, John Crispin Subject: Re: [Codel] [Bloat] [Cerowrt-devel] FQ_Codel lwn draft article review X-BeenThere: codel@lists.bufferbloat.net X-Mailman-Version: 2.1.13 Precedence: list List-Id: CoDel AQM discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 02 Dec 2012 22:07:56 -0000 On Sun, 2012-12-02 at 22:37 +0100, Toke Høiland-Jørgensen wrote: > Eric Dumazet writes: > > > This can help if you really want to avoid a thick flow sharing a thin > > flow bucket, but given that all packets are going eventually into the > > Internet (or equivalent crowded network), its not really a clear win. > > I've been trying to grok the fq_codel code by reading through it while > following the discussion in the article, and I'm having a bit of trouble > squaring the thin/thick (or "hog"/"non-hog") flow designation of the > article with the code. As far as I can tell from the code, there are two > lists, called new_flows and old_flows; and a flow starts out as 'new' > and stays that way until it has sent a quantum of bytes or codel fails > to dequeue a packet from it, whereupon it is moved to the end of the > old_flows list. It then stays in the old_flows list for the rest of its > "life". Not at all. If a cell has : - a positive credit/deficit - no more packets to send Then if is part of old_flows list, we remove it else we move it from new_flows to old_flows The algo has a special shortcut to avoid a pass to old_flows if old_flows is empty, but thats basically : /* force a pass through old_flows to prevent starvation */ if (head == &q->new_flows) list_move_tail(&flow->flowchain, &q->old_flows); else list_del_init(&flow->flowchain); Next time a packet re-activates the flow (or more exactly the bucket in hash table), we move it to 'new_flows' only for one quantum. > > Now, talking about thin flows being distinguished from thick ones, it > seems to me that if a flow sends packets at a low enough rate it can in > principle stay 'thin' indefinitely. So I'm assuming I've missed > something in the code that allows a flow to stay in the new_flows list > if it is sufficiently thin. Could someone please point out to me what > I'm missing? :) > I dont know, this new_flow/old_flows seems too hard to understand for most readers of the code. I saw many people confused by this algo. Of course, a thin flow stay thin, if the bucket can be in the following states, forever : - empty - packet arrives -> bucket queued to end of new_flows - packet is dequeued. - as bucket is empty, move bucket to end of old_flows - next time we hit this bucket (because we processed all packets from old_flows), we remove it from the list and its state becomes 'empty' If the next packet arrives while the bucket is still in old_flows, we wont put the bucket in new_flow, its bucket have to wait its turn in the RR list. Think of it this way : If a bucket lost its turn in the RRR mechanism and became idle, it has its deficit refilled to 'q->quantum', and it has the right to be elected as a new_flow next time a packet wants to use this bucket.