Re: [aqm] CoDel's control law that determines drop frequency

Toke Høiland-Jørgensen <toke@toke.dk> Sun, 07 June 2015 19:28 UTC

Return-Path: <toke@toke.dk>
X-Original-To: aqm@ietfa.amsl.com
Delivered-To: aqm@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id E66811A88E0 for <aqm@ietfa.amsl.com>; Sun, 7 Jun 2015 12:28:04 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 2.007
X-Spam-Level: **
X-Spam-Status: No, score=2.007 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HELO_EQ_DK=1.009, MIME_8BIT_HEADER=0.3, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 36YI3t_kxbrZ for <aqm@ietfa.amsl.com>; Sun, 7 Jun 2015 12:28:03 -0700 (PDT)
Received: from mail2.tohojo.dk (mail2.tohojo.dk [77.235.48.147]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 856251A8854 for <aqm@ietf.org>; Sun, 7 Jun 2015 12:28:02 -0700 (PDT)
X-Virus-Scanned: amavisd-new at mail2.tohojo.dk
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=toke.dk; s=201310; t=1433705273; bh=WWnIvawANrBdkQUB8zODOL7gDsfpdWzq6RnLiXsPxy4=; h=From:To:Cc:Subject:References:Date:In-Reply-To; b=Dey979M9+RHx8dqgyrADhcBxwUmXY61jUcQGu9VL3hCbsCB1V6VFlU8uS6VM62I+N 4uyXODC3DmY0qhVNHSeTustyCln1+D9hc30LSmM20NAGb+WRkRFv7A0asZA67h5Lpm H2+SfPN3fjfyrnezKiCA/OFowwcosfXsc/aIRNi4=
Sender: toke@toke.dk
Received: by alrua-karlstad.karlstad.toke.dk (Postfix, from userid 1000) id 9D4AF3B37A4; Sun, 7 Jun 2015 21:27:52 +0200 (CEST)
From: =?utf-8?Q?Toke_H=C3=B8iland-J=C3=B8rgensen?= <toke@toke.dk>
To: Bob Briscoe <ietf@bobbriscoe.net>
References: <201311122230.rACMUBmH003536@bagheera.jungle.bt.co.uk>
Date: Sun, 07 Jun 2015 21:27:52 +0200
In-Reply-To: <201311122230.rACMUBmH003536@bagheera.jungle.bt.co.uk> (Bob Briscoe's message of "Tue, 12 Nov 2013 22:30:10 +0000")
X-Clacks-Overhead: GNU Terry Pratchett
Message-ID: <87wpzfpbd3.fsf@alrua-karlstad.karlstad.toke.dk>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="=-=-="
Archived-At: <http://mailarchive.ietf.org/arch/msg/aqm/PTeyaiB8KqQub91OLPywChoU7Vw>
Cc: nichols@pollere.com, AQM IETF list <aqm@ietf.org>, vanj@google.com
Subject: Re: [aqm] CoDel's control law that determines drop frequency
X-BeenThere: aqm@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "Discussion list for active queue management and flow isolation." <aqm.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/aqm>, <mailto:aqm-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/aqm/>
List-Post: <mailto:aqm@ietf.org>
List-Help: <mailto:aqm-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/aqm>, <mailto:aqm-request@ietf.org?subject=subscribe>
X-List-Received-Date: Sun, 07 Jun 2015 19:28:05 -0000

Hi Bob

Apologies for reviving this ancient thread; been meaning to get around
to it sooner, but well... better late than never I suppose.

(Web link to your original mail, in case Message-ID referencing breaks:
https://www.ietf.org/mail-archive/web/aqm/current/msg00376.html ).

Having recently had a need to understand CoDel's behaviour in more
detail, your analysis popped out of wherever it's been hiding in the
back of my mind and presented itself as maybe a good place to start. :)

So anyhow, I'm going to skip the initial assertions in your email and
focus on the analysis:

> Here's my working (pls check it - I may have made mistakes)
> _________________
> For brevity, I'll define some briefer variable names:
>         interval =      I [s]
>         next_drop =     D [s]
>         packet-rate =   R [pkt/s]
>         count =         n [pkt]
>
> From the CoDel control law code:
>         D(n) = I / sqrt(n)
> And the instantaneous drop probability is:
>         p(n) = 1/( R * D(n) )
>
> Then the slope of the rise in drop probability with time is:
>         Delta p / Delta t       = [p(n+1) - p(n)] / D(n)
>                                 = [1/D(n+1) - 1/D(n)] / [ R * D(n) ]
>                                 = sqrt(n) * [sqrt(n+1) - sqrt(n)] / [R*I*I]
>                                 = [ sqrt(n(n+1)) - n ] / R*I^2

I couldn't find anything wrong with the derivation. I'm not entirely
sure that I think it makes sense to speak about an "instantaneous drop
probability" for an algorithm that is not probabilistic in nature.
However, interpreting p(n) as "the fraction of packets dropped over the
interval from D(n) to D(n+1)" makes sense, I guess, and for this
analysis that works.

> At count = 1, the numerator starts at sqrt(2)-1 = 0.414.
> Amd as n increases, it rapidly tends to 1/2.
>
> So CoDel's rate of increase of drop probability with time is nearly constant (it
> is always between 0.414 and 0.5) and it rapidly approaches 0.5 after a few
> drops, tending towards:
>         dp/dt = 1/(2*R*I^2)
>
> This constant increase clearly has very little to do with the square-root law of
> TCP Reno.
>
> In the above formula, drop probability increases inversely proportional to the
> packet rate. For instance, with I = 100ms and 1500B packets
> at 10Mb/s =>    R = 833 pkt/s =>        dp/dt = 6.0% /s
> at 100Mb/s =>   R = 8333 pkt/s =>       dp/dt = 0.6% /s

I also tried to test this. I configured CoDel (on a Linux 4.0 box) on
1Mbps, 2Mbps and 10Mbps links with interval settings of 1 second and
500ms, and a total packet limit of 100k packets. This was to make it
deliberately slower to react (so the change in drop probability is more
visible), and to make sure no packets are dropped from queue overflow.

I then sent an unresponsive UDP stream over the link at 110% of the link
capacity (as passed to Iperf, so approximately), and collected the
output of `tc -s qdisc` every 0.2 seconds.

The attached plot is of 'pkts dropped / (pkts sent + pkts dropped)' in a
2-second sliding window over the duration of the test (the plot is also
available here:
https://kau.toke.dk/ietf/codel-drop-rate/codel-drop-rate.svg ).

I've included linear trend lines from the initial time to the point of
maximum drop probability, and as is apparent from the plot, got quite a
good fit (r>0.99 for all six data sets). The legend includes the slopes
of the linear fits for each of the data sets, which are not too far from
what your analysis predicts (and I'm guessing the difference can be
attributed to the difference in exact packet rates, but I haven't
checked).

The Flent data files with the qdisc stats over time (readable by the
newest git version of Flent), as well as the Python script I used to
create the graph are available here: https://kau.toke.dk/ietf/codel-drop-rate/

So, in short: It seems that CoDel's "drop rate" does increase linearly
in the presence of a persistent queue, and that the rate of increase
depends on both the interval and the link rate.

Now, I'll refrain from commenting on whether or not this is "bad", or
indeed if it is contrary to design. It was surprising to me at least, so
I thought I'd share my findings, in the hope that someone would either
find them useful or tell me how they're wrong (or both!). :)

-Toke