Some thoughts about background scanning

Some thoughts about background scanning

[Helmut Schaa]

Hey,

just thought a bit about background scanning (not triggering scans at
any time but just hopping back to the operating channel once in a while
to allow RX/TX).

My current approach is quite easy but works well: Extend the scan state
machine with a new state (OPERATION) which restores the channel and the
correct filter flags and notifies the AP that we're back. The state
machine moves there after every scanned channel. The result is that
the complete scan can take quite some time, something a round 15 seconds.
Scanning multiple channels before switching back would allow us to
reduce the amount of time the scan takes. So, what I'd like to have is
integration with pm_qos in order to determine how much channels may be
scanned at once before we have to switch back. Shouldn't be that
difficult ;) However, the current scan state machine is very inflexible
and I'd have to add a lot of ugly stuff to make it work really good (at
least that's my impression currently).

So, a completely new approach would be to pre-compute all necessary scan
states. Based on the cfg80211 scan request, the current pm_qos values
and the beacon characteristics we could derive a table of necessary scan
states and extend it by operation states. 

For example:
Channel 1, Active Scan, 30ms
Channel 2, Active Scan, 30ms
Channel 3, Active Scan, 30ms
Channel 4, Active Scan, 30ms
Channel 11, Operation Mode, 120ms
Channel 52, Passive Scan, 120ms
Channel 11, Operation Mode, 120ms
...

Advantages:

We could split the actual scan algorithm out of the scan state machine,
for example if pm_qos allows us to stay away for 150ms we could reorder
the channels to scan one active channel followed by one passive channel
before switching back to the operating channel. Should allow us to use
all sorts of insane optimizations.

Disadvantages:

If we compute the table while we're associated but lose association in
the middle of the scan we would either have to update the scan table to
reflect the current state or leave it as is which of course lengthens the
scan. And of course we need more memory to store the table.

In some cases we might shorten the pre-computed values. For example if
we switch back to the operating channel and receive a beacon without
TIM being set for our association and our TX queue is empty we might
immediately proceed with the scan without having to stay on the channel
for the full amount of time. Not sure if we can do this properly without
recomputing the whole table (depends on the actual algorithm used).

I'd like to first get some comments on that idea before thinking about
implementing it :)

Does that kind of approach sound useful? Is it overkill?

Thanks,
Helmut

Re: Some thoughts about background scanning

[Johannes Berg]

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

Hi,

> just thought a bit about background scanning (not triggering scans at
> any time but just hopping back to the operating channel once in a while
> to allow RX/TX).

:)

> My current approach is quite easy but works well: Extend the scan state
> machine with a new state (OPERATION) which restores the channel and the
> correct filter flags and notifies the AP that we're back. 

Makes sense. You can optimise scanning for the _current_ channel by a
combination of OPERATION and scanning, leaving the filter flags at the
scan version, and sending the probe requests. In fact, if you scan that
channel first, you can avoid IEEE80211_PROBE_DELAY since the NAV should
be known on that channel.

Tangentially related, we can also move into SCAN_SEND_PROBE _before_
IEEE80211_PROBE_DELAY has passed, if we receive a frame (which means NAV
update).

> The state
> machine moves there after every scanned channel. The result is that
> the complete scan can take quite some time, something a round 15 seconds.

That doesn't sound too bad. How long are you staying on the operational
channel though?

> Scanning multiple channels before switching back would allow us to
> reduce the amount of time the scan takes. So, what I'd like to have is
> integration with pm_qos in order to determine how much channels may be
> scanned at once before we have to switch back. Shouldn't be that
> difficult ;) 

You might be able to use local->hw.conf.max_sleep_period from
ieee80211_recalc_ps? Or probably better move the calculation into a
helper function since it needs to work across all managed interfaces, if
there are multiple.

> However, the current scan state machine is very inflexible
> and I'd have to add a lot of ugly stuff to make it work really good (at
> least that's my impression currently).
> 
> So, a completely new approach would be to pre-compute all necessary scan
> states. Based on the cfg80211 scan request, the current pm_qos values
> and the beacon characteristics we could derive a table of necessary scan
> states and extend it by operation states. 
> 
> For example:
> Channel 1, Active Scan, 30ms
> Channel 2, Active Scan, 30ms
> Channel 3, Active Scan, 30ms
> Channel 4, Active Scan, 30ms
> Channel 11, Operation Mode, 120ms
> Channel 52, Passive Scan, 120ms
> Channel 11, Operation Mode, 120ms
> ...

Sounds reasonable.

> Advantages:
> 
> We could split the actual scan algorithm out of the scan state machine,
> for example if pm_qos allows us to stay away for 150ms we could reorder
> the channels to scan one active channel followed by one passive channel
> before switching back to the operating channel. Should allow us to use
> all sorts of insane optimizations.

:)
It might be better to have even more states, e.g. make the list look
like this:
 - SWITCH_TO 2412 MHz
 - NAV_WAIT max 33ms
 - SEND_PROBES
 - WAIT_PROBES
 - SWITCH_TO (operation channel)
 - OPERATION
...

That way we can short-circuit the NAV_WAIT on receiving a frame, for
example. We don't receive all frames, of course, so it would be useful
to have some driver assistance for that at some point too.

> Disadvantages:
> 
> If we compute the table while we're associated but lose association in
> the middle of the scan we would either have to update the scan table to
> reflect the current state or leave it as is which of course lengthens the
> scan. And of course we need more memory to store the table.

The memory consumption wouldn't be a problem, and if we lose association
we can always skip the operational states, i.e. check whether we lost
association during that state and if not go to the next.

> In some cases we might shorten the pre-computed values. For example if
> we switch back to the operating channel and receive a beacon without
> TIM being set for our association and our TX queue is empty we might
> immediately proceed with the scan without having to stay on the channel
> for the full amount of time. Not sure if we can do this properly without
> recomputing the whole table (depends on the actual algorithm used).

I think short-circuiting states should be possible from the outside for
the NAV wait too.

> I'd like to first get some comments on that idea before thinking about
> implementing it :)
> 
> Does that kind of approach sound useful? Is it overkill?

Seems useful to me :)

johannes

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

Re: Some thoughts about background scanning

[Helmut Schaa]

Am Mittwoch, 1. Juli 2009 schrieb Johannes Berg:
> > My current approach is quite easy but works well: Extend the scan state
> > machine with a new state (OPERATION) which restores the channel and the
> > correct filter flags and notifies the AP that we're back. 
> 
> Makes sense. You can optimise scanning for the _current_ channel by a
> combination of OPERATION and scanning, leaving the filter flags at the
> scan version, and sending the probe requests. In fact, if you scan that
> channel first, you can avoid IEEE80211_PROBE_DELAY since the NAV should
> be known on that channel.
> 
> Tangentially related, we can also move into SCAN_SEND_PROBE _before_
> IEEE80211_PROBE_DELAY has passed, if we receive a frame (which means NAV
> update).

Correct, that would be another minor optimzation.

> > The state
> > machine moves there after every scanned channel. The result is that
> > the complete scan can take quite some time, something a round 15 seconds.
> 
> That doesn't sound too bad. How long are you staying on the operational
> channel though?

I used the beacon interval of the currently associated AP (100ms here).
Hence, we can be sure that we receive at least one beacon from that AP
and would notice if the AP is gone in the meantime. Of course that can
be optimized by the approach I described in the last mail by proceeding
with the scan once we receive a beacon without TIM bit set.

> > Scanning multiple channels before switching back would allow us to
> > reduce the amount of time the scan takes. So, what I'd like to have is
> > integration with pm_qos in order to determine how much channels may be
> > scanned at once before we have to switch back. Shouldn't be that
> > difficult ;) 
> 
> You might be able to use local->hw.conf.max_sleep_period from
> ieee80211_recalc_ps? Or probably better move the calculation into a 
> helper function since it needs to work across all managed interfaces, if
> there are multiple.

Yep. Already thought about that one. It only needs minor adjustments (for
example it is only available if powersave is done within mac80211).

[...]

> > Advantages:
> > 
> > We could split the actual scan algorithm out of the scan state machine,
> > for example if pm_qos allows us to stay away for 150ms we could reorder
> > the channels to scan one active channel followed by one passive channel
> > before switching back to the operating channel. Should allow us to use
> > all sorts of insane optimizations.
> 
> :)
> It might be better to have even more states, e.g. make the list look
> like this:
>  - SWITCH_TO 2412 MHz
>  - NAV_WAIT max 33ms
>  - SEND_PROBES
>  - WAIT_PROBES
>  - SWITCH_TO (operation channel)
>  - OPERATION
> ...
> 
> That way we can short-circuit the NAV_WAIT on receiving a frame, for
> example. We don't receive all frames, of course, so it would be useful
> to have some driver assistance for that at some point too.

Yeah, cool idea. Have to think about which states make sense and which
don't.

> > In some cases we might shorten the pre-computed values. For example if
> > we switch back to the operating channel and receive a beacon without
> > TIM being set for our association and our TX queue is empty we might
> > immediately proceed with the scan without having to stay on the channel
> > for the full amount of time. Not sure if we can do this properly without
> > recomputing the whole table (depends on the actual algorithm used).
> 
> I think short-circuiting states should be possible from the outside for
> the NAV wait too.

Agreed.

> > Does that kind of approach sound useful? Is it overkill?
> 
> Seems useful to me :)

Great, thanks. I'll look into it some more.

Helmut