|
As per request from WG, I am forwarding the following to the reflector for
review.
My request is to add a note next to equation 10.7, p276,
LowPassFilterRates().
The note would be of the form:
NOTE: The calculations in Equation 10.7 require signed divide operations
for correct operation. These equations can also be rephrased to only use
unsigned arithmetic. For example:
lpfwRate = ((lpCoef - 1) * lpfwRate +
fwRate) / lpCoef;
Regards,
Michael Allen
-----Original Message-----
From: Mike Takefman
[mailto:tak@xxxxxxxxx]
Sent: Fri 2/13/2004 2:31 PM
To:
Michael Allen
Cc: Necdet Uzun; Bob Sultan (E-mail); John Lemon
Subject: Re: Worries about fairness algorithm
We can make a motion at the conference
call.
mike
Michael Allen wrote:
> From my
understanding, there are no "formal" CRD comments for D3.0a --
> it
seems to be based on e-mail type exchanges.
>
>
Michael
>
> -----Original
Message-----
> *From:* Necdet Uzun [mailto:nuzun@xxxxxxxxx]
>
*Sent:* Friday, February 13, 2004 2:01 PM
>
*To:* Michael Allen
> *Cc:* Bob Sultan (E-mail);
tak@xxxxxxxxx; John Lemon
> *Subject:* Re:
Worries about fairness algorithm
>
>
Michael,
>
> Yes, we can do it, if no one
objects? Did you submit a comment for
it?
>
>
Thanks.
>
>
Necdet
>
> Michael Allen
wrote:
>
>> Necdet,
Bob:
>>
>>
I never heard anything back regarding this...Can we at least add
a
>> note around those equations indicating
caution, and that either
>> signed arithmetic
is required, or the alternate expanded
>>
calculation should be
performed.
>>
>>
Regards,
>>
>>
Michael
>>
>>
-----Original
Message-----
>>
*From:* John Lemon [mailto:JLemon@xxxxxxxxxxxx]
>>
*Sent:* Thursday, January 29, 2004 4:50
PM
>> *To:* Michael
Allen
>> *Cc:* Necdet
Uzun (E-mail); Bob Sultan
(E-mail)
>>
*Subject:* RE: Worries about fairness
algorithm
>>
>>
Michael,
>>
Interesting. I'm not sure that it matters that lpfwRate
goes
>> negative. It
just means that the add rate will always
be
>> greater than
the forward rate. Not sure it matters, but
it
>> does certainly
seem
odd.
>>
>>
Necdet, Bob,
>> What
do you think about this? Do we have a
bug?
>>
>>
jl
>> -----Original
Message-----
>>
*From:* Michael Allen [mailto:mallen@xxxxxxxx]
>>
*Sent:* Thursday, January 29, 2004 3:43
PM
>> *To:* John
Lemon
>> *Subject:*
RE: Worries about fairness
algorithm
>>
>>
I guess I am going to partially answer my
own
>>
problem...(although I still think this is an issue that
will
>>
bite).
>>
>>
If fwRate & lpfwRate are changed to "SIGNED" numbers,
the
>> calculation
works. It is interesting that this came from
a
>> Cisco algorithm
that I believe works without needing
signed
>> numbers. It
is actually an UNoptimized version that only
needs
>> additions
and does not suffer from the cross-over -Ve
numbers.
>>
>>
The Cisco base operation
is:
>>
lpfwRate = ((lpCoef - 1) * lpfwRate + fwRate) /
lpCoef;
>>
>>
Mathematically, this is the same
as:
>>
lpfwRate += (fwRate - lpfwRate) /
lpCoef;
>>
>>
UNLESS you use SIGNED numbers. I am guessing that
most
>> hardware
devices do UNSIGNED
arithmetic!!
>>
>>
Should this be brought onto the
reflector?
>>
>>
Michael
>>
>>
-----Original
Message-----
>>
*From:* Michael
Allen
>>
*Sent:* Thursday, January 29, 2004 3:06
PM
>>
*To:* 'John
Lemon'
>>
*Subject:* Worries about fairness
algorithm
>>
>>
John:
>>
>>
I am concerned about the equations used for fairness.
I
>>
was monitoring the fairness algorithm while I had a
single
>>
packet burst through the transit path. Below is a
C
>>
program + output that pulls out the areas of concern
(the
>>
NR stuff has the same problem). Essentially, start from
a
>>
state of no traffic (lpfwRate == 0). Then inject a
single
>>
256 byte packet. fwRate instantaneously becomes 256.
Then
>>
wait a few aging intervals, and it can be seen
that
>>
lpfwRate is not following fwRate very well. In fact,
it
>>
goes -VE finally stabalizing with a value of FFFFFFCB
or
>>
FFFFFFC4.
>>
>>
To me, this seems like it shouldn't happen. What do you
think?
>>
>>
Michael
>>
>>
#include
<stdio.h>
>>
#include
<stdlib.h>
>>
>>
#define lpCoef
64
>>
#define ageCoef
4
>>
>>
int main
(
>>
int
argc,
>>
char * argv
[]
>>
)
>>
{
>>
unsigned long fwRate =
0x100;
>>
unsigned long lpfwRate =
0;
>>
unsigned long
loop;
>>
unsigned long
loop_max;
>>
>>
if (argc ==
2)
>>
{
>>
loop_max = atoi (argv
[1]);
>>
>>
printf ("fwRate
lpfwRate
>>
(fwRate-lpfwRate)\r\n");
>>
for (loop = 0; loop < loop_max;
loop++)
>>
{
>>
printf ("0x%08lX
0x%08lX
>>
0x%08lX\r\n", fwRate, lpfwRate, (fwRate -
lpfwRate));
>>
lpfwRate += (fwRate - lpfwRate) /
lpCoef;
>>
>>
printf ("0x%08lX 0x%08lX\r\n",
fwRate,
>>
lpfwRate);
>>
>>
fwRate -= fwRate /
ageCoef;
>>
}/*FOR*/
>>
}
>>
else
>>
{
>>
printf ("Need to specify number of itterations
on
>>
command
line.\r\n");
>>
}/*IF*/
>>
>>
exit
(0);
>>
}
>>
>>
fwRate
lpfwRate
(fwRate-lpfwRate)
>>
0x00000100
0x00000000
0x00000100
>>
0x00000100
0x00000004
>>
0x000000C0
0x00000004
0x000000BC
>>
0x000000C0
0x00000006
>>
0x00000090
0x00000006
0x0000008A
>>
0x00000090
0x00000008
>>
0x0000006C
0x00000008
0x00000064
>>
0x0000006C
0x00000009
>>
0x00000051
0x00000009
0x00000048
>>
0x00000051
0x0000000A
>>
0x0000003D
0x0000000A
0x00000033
>>
0x0000003D
0x0000000A
>>
0x0000002E
0x0000000A
0x00000024
>>
0x0000002E
0x0000000A
>>
0x00000023
0x0000000A
0x00000019
>>
0x00000023
0x0000000A
>>
0x0000001B
0x0000000A
0x00000011
>>
0x0000001B
0x0000000A
>>
0x00000015
0x0000000A
0x0000000B
>>
0x00000015
0x0000000A
>>
0x00000010
0x0000000A
0x00000006
>>
0x00000010
0x0000000A
>>
0x0000000C
0x0000000A
0x00000002
>>
0x0000000C
0x0000000A
>>
0x00000009
0x0000000A
0xFFFFFFFF
>>
0x00000009
0x04000009
>>
0x00000007
0x04000009
0xFBFFFFFE
>>
0x00000007
0x07F00008
>>
0x00000006
0x07F00008
0xF80FFFFE
>>
0x00000006
0x0BD04007
>>
0x00000005
0x0BD04007
0xF42FBFFE
>>
0x00000005
0x0FA0FF06
>>
0x00000004
0x0FA0FF06
0xF05F00FE
>>
0x00000004
0x13627B09
>>
0x00000003
0x13627B09
0xEC9D84FA
>>
0x00000003
0x1714F11C
>>
0x00000003
0x1714F11C
0xE8EB0EE7
>>
0x00000003
0x1AB89D57
>>
0x00000003
0x1AB89D57
0xE54762AC
>>
0x00000003
0x1E4DBAE1
>>
>
--
Michael
Takefman
tak@xxxxxxxxx
Distinguished Engineer,
Cisco Systems
Chair IEEE 802.17 Stds WG
3000 Innovation Dr, Ottawa,
Canada, K2K 3E8
voice: 613-254-3399
cell:613-220-6991
|