Re: [aqm] avoiding the sqrt
"Agarwal, Anil" <Anil.Agarwal@viasat.com> Mon, 10 August 2015 18:38 UTC
Return-Path: <prvs=9664d75c30=anil.agarwal@viasat.com>
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 E90A51B3C5E for <aqm@ietfa.amsl.com>; Mon, 10 Aug 2015 11:38:19 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.823
X-Spam-Level:
X-Spam-Status: No, score=0.823 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FRT_FUCK2=3.434, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, T_RP_MATCHES_RCVD=-0.01] 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 xzjmSz79xN4k for <aqm@ietfa.amsl.com>; Mon, 10 Aug 2015 11:38:18 -0700 (PDT)
Received: from mta-us-west-01.viasat.com (mta-us-west-01.viasat.com [8.37.96.47]) (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 BC2651B3C5F for <aqm@ietf.org>; Mon, 10 Aug 2015 11:38:18 -0700 (PDT)
Received: from pps.filterd (VCASPAM01.hq.corp.viasat.com [127.0.0.1]) by VCASPAM01.hq.corp.viasat.com (8.15.0.59/8.15.0.59) with SMTP id t7AIS0eC023224; Mon, 10 Aug 2015 18:38:18 GMT
From: "Agarwal, Anil" <Anil.Agarwal@viasat.com>
To: Jeff Weeks <jweeks@sandvine.com>, "aqm@ietf.org" <aqm@ietf.org>
Thread-Topic: avoiding the sqrt
Thread-Index: AdDThuCernObp5LLTKGgLqHu7Sbl8QAEwKGg
Date: Mon, 10 Aug 2015 18:38:17 +0000
Message-ID: <7A2801D5E40DD64A85E38DF22117852C70AF58FE@wdc1exchmbxp05.hq.corp.viasat.com>
References: <274D3A0FA900FD47AA6B56991AAA32FDC53BAA3F@wtl-exchp-1.sandvine.com>
In-Reply-To: <274D3A0FA900FD47AA6B56991AAA32FDC53BAA3F@wtl-exchp-1.sandvine.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:, , definitions=2015-08-10_03:, , signatures=0
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 kscore.is_bulkscore=0 kscore.compositescore=1 compositescore=0.9 suspectscore=0 malwarescore=0 phishscore=0 bulkscore=0 kscore.is_spamscore=0 rbsscore=0.9 spamscore=0 urlsuspectscore=0.9 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1506180000 definitions=main-1508100269
Archived-At: <http://mailarchive.ietf.org/arch/msg/aqm/5hCWXU6gVCGR-FtO8gq6QvAFXdE>
Subject: Re: [aqm] avoiding the sqrt
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: <https://mailarchive.ietf.org/arch/browse/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: Mon, 10 Aug 2015 18:38:20 -0000
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