[PATCH 1/1] mac80211: Replace overly "sticky" averaging filters for rssi, signal, noise.

[PATCH 1/1] mac80211: Replace overly "sticky" averaging filters for rssi, signal, noise.

[benmcahill]

From: Ben Cahill <ben.m.cahill@intel.com>

Replace overly "sticky" averaging filters for rssi, signal, noise ...

In old filter, once initial values were set, it took a large deviation (16)
in new input values in order to nudge the filter output.  This made signal
quality displays appear frozen, with (probably) inaccurate data.

The new filter keeps high-precision (16x) running averages, then quantizes
them to create the output value.  Each new input value nudges the running
average a bit, and displays appear reassuringly alive, with accurate data.

Update comments.

Signed-off-by: Ben Cahill <ben.m.cahill@intel.com>
---
 net/mac80211/ieee80211.c     |   20 ++++++++++++++------
 net/mac80211/ieee80211_sta.c |    7 +++++++
 net/mac80211/sta_info.h      |    9 ++++++---
 3 files changed, 27 insertions(+), 9 deletions(-)

diff --git a/net/mac80211/ieee80211.c b/net/mac80211/ieee80211.c
index 873ccb0..b838d9c 100644
--- a/net/mac80211/ieee80211.c
+++ b/net/mac80211/ieee80211.c
@@ -3603,12 +3603,20 @@ ieee80211_rx_h_sta_process(struct ieee80211_txrx_data *rx)
 
 	sta->rx_fragments++;
 	sta->rx_bytes += rx->skb->len;
-	sta->last_rssi = (sta->last_rssi * 15 +
-			  rx->u.rx.status->ssi) / 16;
-	sta->last_signal = (sta->last_signal * 15 +
-			    rx->u.rx.status->signal) / 16;
-	sta->last_noise = (sta->last_noise * 15 +
-			   rx->u.rx.status->noise) / 16;
+
+	/* Low pass filter:  15/16 current avg + new.
+	 * Accumulated values here are 16x values sent from driver. */
+	sta->accum_rssi = sta->accum_rssi - (sta->accum_rssi >> 4) +
+			  rx->u.rx.status->ssi;
+	sta->accum_signal = sta->accum_signal - (sta->accum_signal >> 4) +
+			  rx->u.rx.status->signal;
+	sta->accum_noise = sta->accum_noise - (sta->accum_noise >> 4) +
+			  rx->u.rx.status->noise;
+
+	/* Quantize the averages (divide by 16) */
+	sta->last_rssi = sta->accum_rssi >> 4;
+	sta->last_signal = sta->accum_signal >> 4;
+	sta->last_noise = sta->accum_noise >> 4;
 
 	if (!(rx->fc & IEEE80211_FCTL_MOREFRAGS)) {
 		/* Change STA power saving mode only in the end of a frame
diff --git a/net/mac80211/ieee80211_sta.c b/net/mac80211/ieee80211_sta.c
index b003912..5986183 100644
--- a/net/mac80211/ieee80211_sta.c
+++ b/net/mac80211/ieee80211_sta.c
@@ -1223,9 +1223,16 @@ static void ieee80211_rx_mgmt_assoc_resp(struct net_device *dev,
 		}
 		bss = ieee80211_rx_bss_get(dev, ifsta->bssid);
 		if (bss) {
+			/* Init signal values from beacon or probe response. */
 			sta->last_rssi = bss->rssi;
 			sta->last_signal = bss->signal;
 			sta->last_noise = bss->noise;
+
+			/* Init averaging filter accumulators to 16x values. */
+			sta->accum_rssi = bss->rssi << 4;
+			sta->accum_signal = bss->signal << 4;
+			sta->accum_noise = bss->noise << 4;
+
 			ieee80211_rx_bss_put(dev, bss);
 		}
 	}
diff --git a/net/mac80211/sta_info.h b/net/mac80211/sta_info.h
index 6a067a0..0ee9212 100644
--- a/net/mac80211/sta_info.h
+++ b/net/mac80211/sta_info.h
@@ -83,9 +83,12 @@ struct sta_info {
 	unsigned long rx_fragments; /* number of received MPDUs */
 	unsigned long rx_dropped; /* number of dropped MPDUs from this STA */
 
-	int last_rssi; /* RSSI of last received frame from this STA */
-	int last_signal; /* signal of last received frame from this STA */
-	int last_noise; /* noise of last received frame from this STA */
+	int accum_rssi; /* hi-precision running average (rssi * 16) */
+	int accum_signal; /* hi-precision average (signal-quality * 16) */
+	int accum_noise; /* hi-precision running average (noise * 16) */
+	int last_rssi; /* average RSSI of recent frames from this STA */
+	int last_signal; /* average sig-qual of recent frames from this STA */
+	int last_noise; /* average noise of recent frames from this STA */
 	int last_ack_rssi[3]; /* RSSI of last received ACKs from this STA */
 	unsigned long last_ack;
 	int channel_use;
-- 
1.5.2

Re: [PATCH 1/1] mac80211: Replace overly "sticky" averaging filters for rssi, signal, noise.

[Jiri Benc]

On Tue, 10 Jul 2007 19:05:05 -0400, benmcahill@gmail.com wrote:
> From: Ben Cahill <ben.m.cahill@intel.com>
> 
> Replace overly "sticky" averaging filters for rssi, signal, noise ...
> 
> In old filter, once initial values were set, it took a large deviation (16)
> in new input values in order to nudge the filter output.  This made signal
> quality displays appear frozen, with (probably) inaccurate data.
> 
> The new filter keeps high-precision (16x) running averages, then quantizes
> them to create the output value.  Each new input value nudges the running
> average a bit, and displays appear reassuringly alive, with accurate data.
> 
> Update comments.
> 
> Signed-off-by: Ben Cahill <ben.m.cahill@intel.com>
> ---
>  net/mac80211/ieee80211.c     |   20 ++++++++++++++------
>  net/mac80211/ieee80211_sta.c |    7 +++++++
>  net/mac80211/sta_info.h      |    9 ++++++---
>  3 files changed, 27 insertions(+), 9 deletions(-)
> 
> diff --git a/net/mac80211/ieee80211.c b/net/mac80211/ieee80211.c
> index 873ccb0..b838d9c 100644
> --- a/net/mac80211/ieee80211.c
> +++ b/net/mac80211/ieee80211.c
> @@ -3603,12 +3603,20 @@ ieee80211_rx_h_sta_process(struct ieee80211_txrx_data *rx)
>  
>  	sta->rx_fragments++;
>  	sta->rx_bytes += rx->skb->len;
> -	sta->last_rssi = (sta->last_rssi * 15 +
> -			  rx->u.rx.status->ssi) / 16;
> -	sta->last_signal = (sta->last_signal * 15 +
> -			    rx->u.rx.status->signal) / 16;
> -	sta->last_noise = (sta->last_noise * 15 +
> -			   rx->u.rx.status->noise) / 16;
> +
> +	/* Low pass filter:  15/16 current avg + new.
> +	 * Accumulated values here are 16x values sent from driver. */
> +	sta->accum_rssi = sta->accum_rssi - (sta->accum_rssi >> 4) +
> +			  rx->u.rx.status->ssi;
> +	sta->accum_signal = sta->accum_signal - (sta->accum_signal >> 4) +
> +			  rx->u.rx.status->signal;
> +	sta->accum_noise = sta->accum_noise - (sta->accum_noise >> 4) +
> +			  rx->u.rx.status->noise;
> +
> +	/* Quantize the averages (divide by 16) */
> +	sta->last_rssi = sta->accum_rssi >> 4;
> +	sta->last_signal = sta->accum_signal >> 4;
> +	sta->last_noise = sta->accum_noise >> 4;

First, do not obfuscate the code, please. If you want to divide by 16,
divide by 16. The compiler is perfectly capable of optimizing it.

Second, do not obfuscate the algorithm, please. All this does is postponing
the division by 16 in last_rssi = (last_rssi * 15 + status_rssi) / 16 to
a time when last_rssi is actually used.

Please keep all the buzzwords like "high-precision" for yourself and
explain how postponing a division by 16 helps.


(To make my point more clear, the code above could be rewritten as
follows(*):

sta->last_rssi = sta->last_rssi * 15 / 16 +
		 rx->u.rx.status->ssi;
sta->last_signal = sta->last_signal * 15 / 16 +
		   rx->u.rx.status->signal;
sta->last_noise = sta->last_noise * 15 +
		  rx->u.rx.status->noise;

while initializing sta->last_rssi to (16 * bss->rssi) and doing the
division by 16 when passing last_rssi to the user space.)

Thanks.

 Jiri

(*) And without the three additional variables!

>  
>  	if (!(rx->fc & IEEE80211_FCTL_MOREFRAGS)) {
>  		/* Change STA power saving mode only in the end of a frame
> diff --git a/net/mac80211/ieee80211_sta.c b/net/mac80211/ieee80211_sta.c
> index b003912..5986183 100644
> --- a/net/mac80211/ieee80211_sta.c
> +++ b/net/mac80211/ieee80211_sta.c
> @@ -1223,9 +1223,16 @@ static void ieee80211_rx_mgmt_assoc_resp(struct net_device *dev,
>  		}
>  		bss = ieee80211_rx_bss_get(dev, ifsta->bssid);
>  		if (bss) {
> +			/* Init signal values from beacon or probe response. */
>  			sta->last_rssi = bss->rssi;
>  			sta->last_signal = bss->signal;
>  			sta->last_noise = bss->noise;
> +
> +			/* Init averaging filter accumulators to 16x values. */
> +			sta->accum_rssi = bss->rssi << 4;
> +			sta->accum_signal = bss->signal << 4;
> +			sta->accum_noise = bss->noise << 4;
> +
>  			ieee80211_rx_bss_put(dev, bss);
>  		}
>  	}
> diff --git a/net/mac80211/sta_info.h b/net/mac80211/sta_info.h
> index 6a067a0..0ee9212 100644
> --- a/net/mac80211/sta_info.h
> +++ b/net/mac80211/sta_info.h
> @@ -83,9 +83,12 @@ struct sta_info {
>  	unsigned long rx_fragments; /* number of received MPDUs */
>  	unsigned long rx_dropped; /* number of dropped MPDUs from this STA */
>  
> -	int last_rssi; /* RSSI of last received frame from this STA */
> -	int last_signal; /* signal of last received frame from this STA */
> -	int last_noise; /* noise of last received frame from this STA */
> +	int accum_rssi; /* hi-precision running average (rssi * 16) */
> +	int accum_signal; /* hi-precision average (signal-quality * 16) */
> +	int accum_noise; /* hi-precision running average (noise * 16) */
> +	int last_rssi; /* average RSSI of recent frames from this STA */
> +	int last_signal; /* average sig-qual of recent frames from this STA */
> +	int last_noise; /* average noise of recent frames from this STA */
>  	int last_ack_rssi[3]; /* RSSI of last received ACKs from this STA */
>  	unsigned long last_ack;
>  	int channel_use;
> -- 
> 1.5.2
> 


-- 
Jiri Benc
SUSE Labs

RE: [PATCH 1/1] mac80211: Replace overly "sticky" averaging filters for rssi, signal, noise.

[Cahill, Ben M]

 

> -----Original Message-----
> From: Jiri Benc [mailto:jbenc@suse.cz] 
> Sent: Tuesday, July 10, 2007 8:25 PM
> To: benmcahill@gmail.com
> Cc: flamingice@sourmilk.net; linux-wireless@vger.kernel.org; 
> Cahill, Ben M
> Subject: Re: [PATCH 1/1] mac80211: Replace overly "sticky" 
> averaging filters for rssi, signal, noise.
> 
> On Tue, 10 Jul 2007 19:05:05 -0400, benmcahill@gmail.com wrote:
> > From: Ben Cahill <ben.m.cahill@intel.com>
> > 
> > Replace overly "sticky" averaging filters for rssi, signal, 
> noise ...
> > 
> > In old filter, once initial values were set, it took a 
> large deviation 
> > (16) in new input values in order to nudge the filter output.  This 
> > made signal quality displays appear frozen, with (probably) 
> inaccurate data.
> > 
> > The new filter keeps high-precision (16x) running averages, then 
> > quantizes them to create the output value.  Each new input value 
> > nudges the running average a bit, and displays appear 
> reassuringly alive, with accurate data.
> > 
> > Update comments.
> > 
> > Signed-off-by: Ben Cahill <ben.m.cahill@intel.com>
> > ---
> >  net/mac80211/ieee80211.c     |   20 ++++++++++++++------
> >  net/mac80211/ieee80211_sta.c |    7 +++++++
> >  net/mac80211/sta_info.h      |    9 ++++++---
> >  3 files changed, 27 insertions(+), 9 deletions(-)
> > 
> > diff --git a/net/mac80211/ieee80211.c 
> b/net/mac80211/ieee80211.c index 
> > 873ccb0..b838d9c 100644
> > --- a/net/mac80211/ieee80211.c
> > +++ b/net/mac80211/ieee80211.c
> > @@ -3603,12 +3603,20 @@ ieee80211_rx_h_sta_process(struct 
> > ieee80211_txrx_data *rx)
> >  
> >  	sta->rx_fragments++;
> >  	sta->rx_bytes += rx->skb->len;
> > -	sta->last_rssi = (sta->last_rssi * 15 +
> > -			  rx->u.rx.status->ssi) / 16;
> > -	sta->last_signal = (sta->last_signal * 15 +
> > -			    rx->u.rx.status->signal) / 16;
> > -	sta->last_noise = (sta->last_noise * 15 +
> > -			   rx->u.rx.status->noise) / 16;
> > +
> > +	/* Low pass filter:  15/16 current avg + new.
> > +	 * Accumulated values here are 16x values sent from driver. */
> > +	sta->accum_rssi = sta->accum_rssi - (sta->accum_rssi >> 4) +
> > +			  rx->u.rx.status->ssi;
> > +	sta->accum_signal = sta->accum_signal - 
> (sta->accum_signal >> 4) +
> > +			  rx->u.rx.status->signal;
> > +	sta->accum_noise = sta->accum_noise - (sta->accum_noise >> 4) +
> > +			  rx->u.rx.status->noise;
> > +
> > +	/* Quantize the averages (divide by 16) */
> > +	sta->last_rssi = sta->accum_rssi >> 4;
> > +	sta->last_signal = sta->accum_signal >> 4;
> > +	sta->last_noise = sta->accum_noise >> 4;
> 
> First, do not obfuscate the code, please. If you want to 
> divide by 16, divide by 16. The compiler is perfectly capable 
> of optimizing it.

Cool.  I'm showing some of my old-school habits, I guess.

> 
> Second, do not obfuscate the algorithm, please. All this does 
> is postponing the division by 16 in last_rssi = (last_rssi * 
> 15 + status_rssi) / 16 to a time when last_rssi is actually used.

This is the old (current) algorithm.  With this, the difference between
last_rssi and status_rssi must be at least 16 in order to survive the
division and nudge the new last_rssi value by 1 ...

For example, if last_rssi = -50, and status_rssi is -51, the new
last_rssi will be:

(((-50 * 15) - 51) / 16) = ((-750 - 51) / 16) = (-801 / 16) = -50 

You could have an infinite number of -51s come in, or -65 for that
matter, and this algo will stick at 50.  There is no memory for new
status_rssi samples within 15 dB of last_rssi. 

> 
> Please keep all the buzzwords like "high-precision" for 
> yourself and explain how postponing a division by 16 helps.

Postponing the division keeps the running average using more significant
bits, so each new sample has a meaningful, surviving impact to the
running average.  Sorry, "high-precision" is the best term that I can
think of to describe more bits being used in the running average.  The
"binary point" is between bits 3 and 4; think of bits 3:0 as
"remainder". 

For example, if last_rssi = -50 (represented in new code by -50 * 16 =
-800), and status_rssi is -51 (represented by -51), the new last_rssi
(high precision) = 

((-800 - (-800/16) - 51) = -801   ... see below for explanation of "-
(-800/16)"

With this, there *is* memory for the (just 1 away) new sample.  And 15
more -51s would nudge last_rssi to be -816 (= -51 after a divide by 16).
No stickiness.

There is a subtle difference between:

1)  last_rssi * 15 / 16

2)  last_rssi - (last_rssi / 16)

The first one would get stuck at -801 if there were a series of -51s
coming in.
-801 * 15 / 16 would get quantized to -750 each time, so the output
would be stuck at -801 (-50 dBm).

The second one favors the high precision memory, and would progress from
-801 to -802, etc., as a series of -51s came in:
-801 - (-801/16) = -751

> 
> 
> (To make my point more clear, the code above could be rewritten as
> follows(*):
> 
> sta->last_rssi = sta->last_rssi * 15 / 16 +
> 		 rx->u.rx.status->ssi;
> sta->last_signal = sta->last_signal * 15 / 16 +
> 		   rx->u.rx.status->signal;
> sta->last_noise = sta->last_noise * 15 / 16 +
> 		  rx->u.rx.status->noise;

Very good, although for best memory/precision (see above), these should
be, e.g.:

sta->last_rssi = sta->last_rssi - (sta->last_rssi / 16) +
 		 rx->u.rx.status->ssi;

> 
> while initializing sta->last_rssi to (16 * bss->rssi) and 
> doing the division by 16 when passing last_rssi to the user space.)

Yes, we can do the division when passing to user space.  

> 
> Thanks.
> 
>  Jiri
> 
> (*) And without the three additional variables!

I saw 2 instances of sta->last_rssi being used in ieee80211_ioctl.c, and
STA_FILE(last_rssi, last_rssi, D) in debugfs_sta.c, which I didn't
understand (still don't) and was afraid to touch, so I thought the
safest thing with least impact would be to add the 3 additional
variables, and do the division in one place for each of the 3
rssi/signal/noise.

If we do the division when passing to user space, how should STA_FILE be
handled, if necessary?

Thanks for your comments.  I'll wait for your answer, and try again.

-- Ben --

> -- 
> Jiri Benc
> SUSE Labs
> 

RE: [PATCH 1/1] mac80211: Replace overly "sticky" averaging filters for rssi, signal, noise.

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 291 bytes --]

On Tue, 2007-07-10 at 21:59 -0700, Cahill, Ben M wrote:

> If we do the division when passing to user space, how should STA_FILE be
> handled, if necessary?

This should work due to the way the macros are set up:

STA_READ_D(last_rssi, last_rssi/16)
STA_OPS(last_rssi);

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 190 bytes --]

Re: [PATCH 1/1] mac80211: Replace overly "sticky" averaging filters for rssi, signal, noise.

[Jiri Benc]

On Tue, 10 Jul 2007 21:59:13 -0700, Cahill, Ben M wrote:
> Postponing the division keeps the running average using more significant
> bits, so each new sample has a meaningful, surviving impact to the
> running average.  Sorry, "high-precision" is the best term that I can
> think of to describe more bits being used in the running average.  The
> "binary point" is between bits 3 and 4; think of bits 3:0 as
> "remainder". 

Thanks, that makes sense. Please include something like this
explanation in the description of the patch when you resend it.

> There is a subtle difference between:
> 
> 1)  last_rssi * 15 / 16
> 
> 2)  last_rssi - (last_rssi / 16)
> 
> The first one would get stuck at -801 if there were a series of -51s
> coming in.
> -801 * 15 / 16 would get quantized to -750 each time, so the output
> would be stuck at -801 (-50 dBm).
> 
> The second one favors the high precision memory, and would progress from
> -801 to -802, etc., as a series of -51s came in:
> -801 - (-801/16) = -751

So it's basically just a different rounding - in the current code, it's
like float division with the result rounded down, while your change
makes it to round up (speaking about absolute value). Nothing about
precision here :-)

> I saw 2 instances of sta->last_rssi being used in ieee80211_ioctl.c, and
> STA_FILE(last_rssi, last_rssi, D) in debugfs_sta.c, which I didn't
> understand (still don't) and was afraid to touch, so I thought the
> safest thing with least impact would be to add the 3 additional
> variables, and do the division in one place for each of the 3
> rssi/signal/noise.
> 
> If we do the division when passing to user space, how should STA_FILE be
> handled, if necessary?

Johannes was quicker than me (thanks) :-)

> Thanks for your comments.  I'll wait for your answer, and try again.

Thanks and sorry for the delayed answer,

 Jiri

-- 
Jiri Benc
SUSE Labs

Re: [PATCH 1/1] mac80211: Replace overly "sticky" averaging filters for rssi, signal, noise.

[Larry Finger]

Jiri Benc wrote:
> On Tue, 10 Jul 2007 21:59:13 -0700, Cahill, Ben M wrote:
>> Postponing the division keeps the running average using more significant
>> bits, so each new sample has a meaningful, surviving impact to the
>> running average.  Sorry, "high-precision" is the best term that I can
>> think of to describe more bits being used in the running average.  The
>> "binary point" is between bits 3 and 4; think of bits 3:0 as
>> "remainder". 
> 
> Thanks, that makes sense. Please include something like this
> explanation in the description of the patch when you resend it.
> 
>> There is a subtle difference between:
>>
>> 1)  last_rssi * 15 / 16
>>
>> 2)  last_rssi - (last_rssi / 16)
>>
>> The first one would get stuck at -801 if there were a series of -51s
>> coming in.
>> -801 * 15 / 16 would get quantized to -750 each time, so the output
>> would be stuck at -801 (-50 dBm).
>>
>> The second one favors the high precision memory, and would progress from
>> -801 to -802, etc., as a series of -51s came in:
>> -801 - (-801/16) = -751
> 
> So it's basically just a different rounding - in the current code, it's
> like float division with the result rounded down, while your change
> makes it to round up (speaking about absolute value). Nothing about
> precision here :-)
> 
>> I saw 2 instances of sta->last_rssi being used in ieee80211_ioctl.c, and
>> STA_FILE(last_rssi, last_rssi, D) in debugfs_sta.c, which I didn't
>> understand (still don't) and was afraid to touch, so I thought the
>> safest thing with least impact would be to add the 3 additional
>> variables, and do the division in one place for each of the 3
>> rssi/signal/noise.
>>
>> If we do the division when passing to user space, how should STA_FILE be
>> handled, if necessary?
> 
> Johannes was quicker than me (thanks) :-)
> 
>> Thanks for your comments.  I'll wait for your answer, and try again.
> 
> Thanks and sorry for the delayed answer,

I added the wireless statistics to d80211 (it was that long ago) and I used 16-point averaging based 
on my experiences with an early version of the bcm43xx-softmac driver where the rssi value was quite 
jittery. From a quick test on the current drivers, the assumptions seem not to be valid and it is 
quite possible that averaging may not be needed, or that one can get by with a 2- or 4-point process.

My suggestion would be to circulate a trial patch with averaging removed and ask for testing to see 
if it makes the results too jumpy. I can prepare that patch if you wish.

Larry

RE: [PATCH 1/1] mac80211: Replace overly "sticky" averaging filters for rssi, signal, noise.

[Cahill, Ben M]

 
> I added the wireless statistics to d80211 (it was that long 
> ago) and I used 16-point averaging based on my experiences 
> with an early version of the bcm43xx-softmac driver where the 
> rssi value was quite jittery. From a quick test on the 
> current drivers, the assumptions seem not to be valid and it 
> is quite possible that averaging may not be needed, or that 
> one can get by with a 2- or 4-point process.
> 
> My suggestion would be to circulate a trial patch with 
> averaging removed and ask for testing to see if it makes the 
> results too jumpy. I can prepare that patch if you wish.
> 
> Larry

Thanks for the history, Larry.  I'd be very happy if you did.  Thanks!

-- Ben --
> 

[RFC/T] mac80211: Remove overly "sticky" averaging filters for rssi, signal, noise.

[Larry Finger]

[-- Attachment #1: Type: text/plain, Size: 1439 bytes --]

As has been discussed on the wireless list, the averaging in the current version
of mac80211 has a bug. This trial patch is to see if removing averaging leads to
wireless statistics that are too jittery to be useful.

If you are using a mac80211-based driver, please test and report your findings.

Thanks,

Larry
------ patch follows ------

The current version of wireless statistics contains a bug in the averaging
that makes the numbers be too sticky and not react to small changes. This
test patch removes all averaging for testing if averaging is needed.

Signed-off-by: Larry Finger <Larry.Finger@lwfinger.net>
---

Index: wireless-dev/net/mac80211/ieee80211.c
===================================================================
--- wireless-dev.orig/net/mac80211/ieee80211.c
+++ wireless-dev/net/mac80211/ieee80211.c
@@ -3615,12 +3615,9 @@ ieee80211_rx_h_sta_process(struct ieee80

  	sta->rx_fragments++;
  	sta->rx_bytes += rx->skb->len;
-	sta->last_rssi = (sta->last_rssi * 15 +
-			  rx->u.rx.status->ssi) / 16;
-	sta->last_signal = (sta->last_signal * 15 +
-			    rx->u.rx.status->signal) / 16;
-	sta->last_noise = (sta->last_noise * 15 +
-			   rx->u.rx.status->noise) / 16;
+	sta->last_rssi = rx->u.rx.status->ssi;
+	sta->last_signal = rx->u.rx.status->signal;
+	sta->last_noise = rx->u.rx.status->noise;

  	if (!(rx->fc & IEEE80211_FCTL_MOREFRAGS)) {
  		/* Change STA power saving mode only in the end of a frame



---

[-- Attachment #2: mac80211_no_average --]
[-- Type: text/plain, Size: 1088 bytes --]

The current version of wireless statistics contains a bug in the averaging
that makes the numbers be too sticky and not react to small changes. This
test patch removes all averaging for testing if averaging is needed.

Signed-off-by: Larry Finger <Larry.Finger@lwfinger.net>
---

Index: wireless-dev/net/mac80211/ieee80211.c
===================================================================
--- wireless-dev.orig/net/mac80211/ieee80211.c
+++ wireless-dev/net/mac80211/ieee80211.c
@@ -3615,12 +3615,9 @@ ieee80211_rx_h_sta_process(struct ieee80
 
 	sta->rx_fragments++;
 	sta->rx_bytes += rx->skb->len;
-	sta->last_rssi = (sta->last_rssi * 15 +
-			  rx->u.rx.status->ssi) / 16;
-	sta->last_signal = (sta->last_signal * 15 +
-			    rx->u.rx.status->signal) / 16;
-	sta->last_noise = (sta->last_noise * 15 +
-			   rx->u.rx.status->noise) / 16;
+	sta->last_rssi = rx->u.rx.status->ssi;
+	sta->last_signal = rx->u.rx.status->signal;
+	sta->last_noise = rx->u.rx.status->noise;
 
 	if (!(rx->fc & IEEE80211_FCTL_MOREFRAGS)) {
 		/* Change STA power saving mode only in the end of a frame

RE: [RFC/T] mac80211: Remove overly "sticky" averaging filters for rssi, signal, noise.

[Cahill, Ben M]

Hi Larry,

I like it without the filter just fine.

It might even be better "philosophically", because it does not impose
any particular filtering policy on the signal values, leaving it up to
user space apps to choose whether/how to filter them.

Did anyone else try it or have an opinion?

-- Ben -- 

> -----Original Message-----
> From: Larry Finger [mailto:larry.finger@lwfinger.net] 
> Sent: Friday, July 13, 2007 2:52 PM
> To: Cahill, Ben M
> Cc: Jiri Benc; benmcahill@gmail.com; flamingice@sourmilk.net; 
> linux-wireless@vger.kernel.org
> Subject: [RFC/T] mac80211: Remove overly "sticky" averaging 
> filters for rssi, signal, noise.
> 
> As has been discussed on the wireless list, the averaging in 
> the current version of mac80211 has a bug. This trial patch 
> is to see if removing averaging leads to wireless statistics 
> that are too jittery to be useful.
> 
> If you are using a mac80211-based driver, please test and 
> report your findings.
> 
> Thanks,
> 
> Larry
> ------ patch follows ------
> 
> The current version of wireless statistics contains a bug in 
> the averaging that makes the numbers be too sticky and not 
> react to small changes. This test patch removes all averaging 
> for testing if averaging is needed.
> 
> Signed-off-by: Larry Finger <Larry.Finger@lwfinger.net>
> ---
> 
> Index: wireless-dev/net/mac80211/ieee80211.c
> ===================================================================
> --- wireless-dev.orig/net/mac80211/ieee80211.c
> +++ wireless-dev/net/mac80211/ieee80211.c
> @@ -3615,12 +3615,9 @@ ieee80211_rx_h_sta_process(struct ieee80
> 
>   	sta->rx_fragments++;
>   	sta->rx_bytes += rx->skb->len;
> -	sta->last_rssi = (sta->last_rssi * 15 +
> -			  rx->u.rx.status->ssi) / 16;
> -	sta->last_signal = (sta->last_signal * 15 +
> -			    rx->u.rx.status->signal) / 16;
> -	sta->last_noise = (sta->last_noise * 15 +
> -			   rx->u.rx.status->noise) / 16;
> +	sta->last_rssi = rx->u.rx.status->ssi;
> +	sta->last_signal = rx->u.rx.status->signal;
> +	sta->last_noise = rx->u.rx.status->noise;
> 
>   	if (!(rx->fc & IEEE80211_FCTL_MOREFRAGS)) {
>   		/* Change STA power saving mode only in the end 
> of a frame
> 
> 
> 
> ---
> 

Re: [PATCH 1/1] mac80211: Replace overly "sticky" averaging filters for rssi, signal, noise.

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 1931 bytes --]

On Wed, 2007-07-11 at 02:25 +0200, Jiri Benc wrote:

> > +	/* Quantize the averages (divide by 16) */
> > +	sta->last_rssi = sta->accum_rssi >> 4;
> > +	sta->last_signal = sta->accum_signal >> 4;
> > +	sta->last_noise = sta->accum_noise >> 4;
> 
> First, do not obfuscate the code, please. If you want to divide by 16,
> divide by 16. The compiler is perfectly capable of optimizing it.

No, you're wrong, the compiler can only optimise that if it knows for
sure that the values can't ever be negative. And quoting the patch
further below:

> +	int accum_rssi; /* hi-precision running average (rssi * 16) */
> +	int accum_signal; /* hi-precision average (signal-quality * 16) */
> +	int accum_noise; /* hi-precision running average (noise * 16) */

The compiler does some tricks to avoid the integer division IIRC but it
can't do a simple shift. But in principle you're right, the code should
say "/ 16" because either the variables need to be made unsigned (only
positive values are put into them) or using a shift is wrong (if
negative values can happpen)

Oh btw, is this the difference between "moving average" and "running
average"?

With the algorithm as I see it, each update is done by
update(new_value):
  avg = 15/16*avg + new_value

which means that all old samples are still influencing the current
output.

Doing two updates (update(a), update(b)) yields:
avg = 15/16 * (15/16*orig + a) + b = 225/256 * orig + 15/16 * a + b

And after 16 updates the original values still has an influence of about
3.5% on the output value:
update(a_0),...,update(a_15):
avg = (15/16)^16*orig + \sum_{i=0}^{15} (15/16)^i * a_i
    = 0.3560*orig + 0.3798*a_0 + ... (sum of coefficients is ~10.30)

Is this really what we want? Wouldn't it be better to have a ringbuffer
of the last 16 values and really do an average over those? [which is
what I understand as "moving average"]

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 190 bytes --]

RE: [PATCH 1/1] mac80211: Replace overly "sticky" averagingfilters for rssi, signal, noise.

[Cahill, Ben M]

Sorry, had to put this aside for awhile ... Actually, I like the way
things behave without a filter at all (see other mail), but I just
wanted to follow up ... and thank Johannes for his thoughtful comments.

-- Ben --

> -----Original Message-----
> From: Johannes Berg [mailto:johannes@sipsolutions.net] 
> Sent: Thursday, July 12, 2007 5:16 PM
> To: Jiri Benc
> Cc: benmcahill@gmail.com; flamingice@sourmilk.net; 
> linux-wireless@vger.kernel.org; Cahill, Ben M
> Subject: Re: [PATCH 1/1] mac80211: Replace overly "sticky" 
> averagingfilters for rssi, signal, noise.
> 
> On Wed, 2007-07-11 at 02:25 +0200, Jiri Benc wrote:
> 
> > > +	/* Quantize the averages (divide by 16) */
> > > +	sta->last_rssi = sta->accum_rssi >> 4;
> > > +	sta->last_signal = sta->accum_signal >> 4;
> > > +	sta->last_noise = sta->accum_noise >> 4;
> > 
> > First, do not obfuscate the code, please. If you want to 
> divide by 16, 
> > divide by 16. The compiler is perfectly capable of optimizing it.
> 
> No, you're wrong, the compiler can only optimise that if it 
> knows for sure that the values can't ever be negative. And 
> quoting the patch further below:
> 
> > +	int accum_rssi; /* hi-precision running average (rssi * 16) */
> > +	int accum_signal; /* hi-precision average 
> (signal-quality * 16) */
> > +	int accum_noise; /* hi-precision running average (noise * 16) */
> 
> The compiler does some tricks to avoid the integer division 
> IIRC but it can't do a simple shift. But in principle you're 
> right, the code should say "/ 16" because either the 
> variables need to be made unsigned (only positive values are 
> put into them) or using a shift is wrong (if negative values 
> can happpen)

Actually, "arithmetic" right shift works for either signed or unsigned.
Arithmetic shift looks at the most-significant bit, and shifts more of
that in from the left, preserving the sign.  Our rssi and noise values
are negative (dBm) values, and this integer shift formula worked fine.
It's important that the variable is "int", rather than "unsigned", or
else the compiler would use a "logical" right shift, which simply shifts
in 0s from the left.

> 
> With the algorithm as I see it, each update is done by
> update(new_value):
>   avg = 15/16*avg + new_value
> 
> which means that all old samples are still influencing the 
> current output.

Exactly ... this is the characteristic of an "infinite impulse response"
(IIR) filter.  The output is fed back into the input.  If we had
infinite bits of precision in the output filter variable, the influence
of a single input would constantly decay at the 15/16 rate, but would
last forever.  Since we don't have infinite precision, the effect of a
single sample is limited.

Usually, for a given desired behavior, it's easier to build an IIR
filter than an FIR (finite impulse response) filter ... the FIR filter
does *not* use any feedback from the output ... any history must be in
the form of stored input values, which you suggest below.

> 
> Doing two updates (update(a), update(b)) yields:
> avg = 15/16 * (15/16*orig + a) + b = 225/256 * orig + 15/16 * a + b
> 
> And after 16 updates the original values still has an 
> influence of about 3.5% on the output value:
> update(a_0),...,update(a_15):
> avg = (15/16)^16*orig + \sum_{i=0}^{15} (15/16)^i * a_i
>     = 0.3560*orig + 0.3798*a_0 + ... (sum of coefficients is ~10.30)
> 
> Is this really what we want? Wouldn't it be better to have a 
> ringbuffer of the last 16 values and really do an average 
> over those? [which is what I understand as "moving average"]

This is an FIR approach, which would work just fine, and would give
results based on exactly 16 samples of history, distributed equally
(rather than weighted towards more recent samples, which actually might
be desirable), but would be more complicated to build and would use more
storage.

You might be exactly right about the definition of a "moving average".
I might have mis-used the term.

-- Ben --

> 
> johannes
> 

RE: [PATCH 1/1] mac80211: Replace overly "sticky" averagingfilters for rssi, signal, noise.

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 634 bytes --]

On Wed, 2007-07-25 at 11:50 -0700, Cahill, Ben M wrote:
> Sorry, had to put this aside for awhile ... Actually, I like the way
> things behave without a filter at all (see other mail), but I just
> wanted to follow up ... and thank Johannes for his thoughtful comments.

:)

> Actually, "arithmetic" right shift works for either signed or unsigned.
> Arithmetic shift looks at the most-significant bit, and shifts more of
> that in from the left, preserving the sign.

Eh, right. And I suppose it can actually optimise /16 by an arithmetic
shift.

> [IIR vs FIR]

Ah, cool, I wasn't aware of these terms.

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 190 bytes --]

RE: [PATCH 1/1] mac80211: Replace overly "sticky" averagingfiltersfor rssi, signal, noise.

[Cahill, Ben M]

 
> > Actually, "arithmetic" right shift works for either signed 
> or unsigned.
> > Arithmetic shift looks at the most-significant bit, and 
> shifts more of 
> > that in from the left, preserving the sign.
> 
> Eh, right. And I suppose it can actually optimise /16 by an 
> arithmetic shift.

Not sure if it would or wouldn't ... my by-hand analysis (see earlier
mail on this thread) found a subtle difference between:

(n * 15 / 16) vs. (n - (n >> 16)).

As it turned out, the 15/16 approach would have been slightly more
"sticky", IIRC.

-- Ben --

> 
> johannes
>