Skip site navigation (1)Skip section navigation (2) 
Date:      Sun, 09 Feb 2003 16:17:08 +0100
From:      Peter Ewert <Peter.Ewert@ewetel.de>
To:        freebsd-ipfw@FreeBSD.ORG
Subject:   Is the RED implementation correct?
Message-ID:  <3E4670F4.8010507@ewetel.de>
next in thread | raw e-mail | index | archive | help 
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

Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?3E4670F4.8010507>