From owner-freebsd-ipfw  Sun Feb  9  7:17:28 2003
Delivered-To: freebsd-ipfw@freebsd.org
Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125])
	by hub.freebsd.org (Postfix) with ESMTP id DE43237B405
	for <freebsd-ipfw@FreeBSD.ORG>; Sun,  9 Feb 2003 07:17:26 -0800 (PST)
Received: from mail0.ewetel.de (mail0.ewetel.de [212.6.122.12])
	by mx1.FreeBSD.org (Postfix) with ESMTP id 7BD1143F3F
	for <freebsd-ipfw@FreeBSD.ORG>; Sun,  9 Feb 2003 07:17:25 -0800 (PST)
	(envelope-from Peter.Ewert@ewetel.de)
Received: from ewetel.de (dynadsl-080-228-66-219.ewetel.net [80.228.66.219])
	by mail0.ewetel.de (8.12.1/8.12.1) with ESMTP id h19FHGbq012222
	for <freebsd-ipfw@FreeBSD.ORG>; Sun, 9 Feb 2003 16:17:17 +0100 (MET)
Message-ID: <3E4670F4.8010507@ewetel.de>
Date: Sun, 09 Feb 2003 16:17:08 +0100
From: Peter Ewert <Peter.Ewert@ewetel.de>
Reply-To: Peter.Ewert@ewetel.de
User-Agent: Mozilla/5.0 (Windows; U; Win98; en-US; rv:1.2.1) Gecko/20021130
X-Accept-Language: en-us, en
MIME-Version: 1.0
To: freebsd-ipfw@FreeBSD.ORG
Subject: Is the RED implementation correct?
X-Enigmail-Version: 0.71.0.0
X-Enigmail-Supports: pgp-inline, pgp-mime
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
X-CheckCompat: OK
Sender: owner-freebsd-ipfw@FreeBSD.ORG
Precedence: bulk
List-ID: <freebsd-ipfw.FreeBSD.ORG>
List-Archive: <http://docs.freebsd.org/mail/> (Web Archive)
List-Help: <mailto:majordomo@FreeBSD.ORG?subject=help> (List Instructions)
List-Subscribe: <mailto:majordomo@FreeBSD.ORG?subject=subscribe%20freebsd-ipfw>
List-Unsubscribe: <mailto:majordomo@FreeBSD.ORG?subject=unsubscribe%20freebsd-ipfw>
X-Loop: FreeBSD.ORG

Hi all,

ipfw pipe 1 config bw 100kbit/s queue 50 red 0.002/5/15/0.1

sets up a 50 slot queue with limited bandwitdh and RED queue
management.
In particular it calculates the parameters for setting up a lookup
table, which is used for calculating the average queue length for
recently exhausted queues.

1)
I do not understand the calculation of the pipe.fs.lookup_weight in
ipfw.c/ipfw2.c:

weight = 1 - w_q;
for (t = pipe.fs.lookup_step; t > 0; --t)
	weight *= weight;
pipe.fs.lookup_weight = (int)(weight * (1 << SCALE_RED));

which gives for typical parameters a lookup_weight equal to zero due to
the small accuracy of the fixed point notation and the relative fast
convergence of ((1-w_q)^(2^pipe.fs.lookup_step)) -> 0 for weight<1.

I would have expected something like:

weight = 1 - w_q;
for (t = (int)(3. / (w_q*lookup_depth)); t > 0; --t)
	weight *= (1 - w_q);
pipe.fs.lookup_weight = (int)(weight * (1 << SCALE_RED));

which calculates weight as weight=(1-w_q)^(3/(w_q*lookup_depth)).
This would make more sense to me as weight should not depend on s (ticks 
for sending medium-sized packet).
Together with the following lines from ip_dummynet.c:

for (i = 1; i < x->lookup_depth; i++)
  x->w_q_lookup[i] = SCALE_MUL(x->w_q_lookup[i - 1], x->lookup_weight);

we would have a correct initialized lookuptable in w_q_lookup.

2)
The line
	s = clock.hz * avg_pkt_size * 8 / pipe.bandwidth;
in ipfw.c/ipfw2.c
should give a "better" accuracy for s using floating point division:
	s = clock.hz * avg_pkt_size * 8 / (double)pipe.bandwidth;

3)
In ip_dummynet.c:
I think in
q->avg=(t < fs->lookup_depth) ? SCALE_MUL(q->avg,fs->w_q_lookup[t]) : 0;

the 32Bit multiply overflows. Using
	SCALE_MUL((int64_t) q->avg, (int64_t)(fs->w_q_lookup[t]))
should solve the problem.

Any comments?

Regards,
Peter Ewert


To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-ipfw" in the body of the message