Re: [aqm] avoiding the sqrt

Jeff Weeks <jweeks@sandvine.com> Tue, 11 August 2015 13:05 UTC

From: Jeff Weeks <jweeks@sandvine.com>
To: "Agarwal, Anil" <Anil.Agarwal@viasat.com>, "aqm@ietf.org" <aqm@ietf.org>
Thread-Topic: avoiding the sqrt
Thread-Index: AdDThuCernObp5LLTKGgLqHu7Sbl8QAEwKGgACbzQIE=
Date: Tue, 11 Aug 2015 13:05:55 +0000
Message-ID: <274D3A0FA900FD47AA6B56991AAA32FDC53BB02B@wtl-exchp-1.sandvine.com>
References: <274D3A0FA900FD47AA6B56991AAA32FDC53BAA3F@wtl-exchp-1.sandvine.com>, <7A2801D5E40DD64A85E38DF22117852C70AF58FE@wdc1exchmbxp05.hq.corp.viasat.com>
In-Reply-To: <7A2801D5E40DD64A85E38DF22117852C70AF58FE@wdc1exchmbxp05.hq.corp.viasat.com>
Accept-Language: en-US
Content-Language: en-US
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Archived-At: <http://mailarchive.ietf.org/arch/msg/aqm/QFYFb0O7iNcgP-DmbTGl9qXP8DA>
Subject: Re: [aqm] avoiding the sqrt
Precedence: list

Indeed, the microsec granularity means the lookup table would be quite large, or would need to use a reduced index into a smaller table.
After looking at modern cycle counts for integer multiply, I'm realizing that they're not nearly as expensive as I remember them to be, so the Linux implementation's approach is likely more efficient.

--Jeff
________________________________________
From: Agarwal, Anil [Anil.Agarwal@viasat.com]
Sent: Monday, August 10, 2015 2:38 PM
To: Jeff Weeks; aqm@ietf.org
Subject: RE: avoiding the sqrt

Jeff,

Did you mean -
    pre-calculate a set of interval/sqrt(count) for some range of count --  probably (1..interval^2),
    and for any count > interval^2, the next interval can just be set to t+1

Also, interval is generally kept in microseconds, hence a nominal value for interval is 100000.

The current Codel Linux implementation of 1/sqrt(count) uses 4 multiplications.

Anil

-----Original Message-----
From: aqm [mailto:aqm-bounces@ietf.org] On Behalf Of Jeff Weeks
Sent: Monday, August 10, 2015 12:18 PM
To: aqm@ietf.org
Subject: [aqm] avoiding the sqrt

The CoDel control_law is defined as 't + interval/sqrt(count)'

The sample implementation (https://urldefense.proofpoint.com/v2/url?u=http-3A__queue.acm.org_appendices_codel.html&d=BQICAg&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=Mwm2-08h6DG8dG8A8i_FAQ9gIL67_jeiZA_pVQpEnIU&s=dMb61gcX82gBDxDv3nIAN4_lJma52tJT57lEdcXrVko&e= ) suggests that sqrt(count) can be calculated using only integer multiplication, but I'm wondering if it even needs to be calculated.

Would it not be more efficient to pre-calculate a set of 1/sqrt(count) for some range --  probably (1..interval), and for any count > interval, the next interval can just be set to t+1.

Is there any reason to not use this approach (assuming sufficient memory exists, of course)?

--Jeff

________________________________
/dev/jeff_weeks.x2936
Sandvine Incorporated

_______________________________________________
aqm mailing list
aqm@ietf.org
https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_aqm&d=BQICAg&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=Mwm2-08h6DG8dG8A8i_FAQ9gIL67_jeiZA_pVQpEnIU&s=guSznYIkwKsTZpoAOLCaLdhlKa4GUMNrO7mu4sv3nMM&e=

[aqm] avoiding the sqrt Jeff Weeks
Re: [aqm] avoiding the sqrt Mikael Abrahamsson
Re: [aqm] avoiding the sqrt Jonathan Morton
Re: [aqm] avoiding the sqrt Agarwal, Anil
Re: [aqm] avoiding the sqrt Jeff Weeks
Re: [aqm] avoiding the sqrt Andrew Mcgregor
Re: [aqm] avoiding the sqrt Dave Taht