Some thoughts about background scanning
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
Hi,
Quoted 3 lines
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).
:)
Quoted 3 lines
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).
Quoted 3 lines
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?
Quoted 5 lines
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_qosin 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.
Quoted 9 lines
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_qosvalues and the beacon characteristics we could derive a table of necessary scan states and extend it by operation states.
Quoted 9 lines
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.
Quoted 7 lines
Advantages:
We could split the actual scan algorithm out of the scan state machine, for example if
pm_qosallows 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.
Quoted 6 lines
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.
Quoted 6 lines
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.
Quoted 4 lines
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
Am Mittwoch, 1. Juli 2009 schrieb Johannes Berg:
Quoted 10 lines
Quoted 3 lines
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_DELAYsince the NAV should be known on that channel.
Quoted 3 lines
Tangentially related, we can also move into
SCAN_SEND_PROBE_before_IEEE80211_PROBE_DELAYhas passed, if we receive a frame (which means NAV update).
Correct, that would be another minor optimzation.
Quoted 6 lines
Quoted 3 lines
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.
Quoted 10 lines
Quoted 5 lines
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_qosin 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_periodfromieee80211_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).
[...]
Quoted 19 lines
Quoted 7 lines
Advantages:
We could split the actual scan algorithm out of the scan state machine, for example if
pm_qosallows 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_TO2412 MHz
-NAV_WAITmax 33ms
-SEND_PROBES
-WAIT_PROBES
-SWITCH_TO(operation channel)
- OPERATION
...
Quoted 3 lines
That way we can short-circuit the
NAV_WAITon 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.
Quoted 9 lines
Quoted 6 lines
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.
Quoted 3 lines
Quoted 1 line
Does that kind of approach sound useful? Is it overkill?
Seems useful to me :)
Great, thanks. I'll look into it some more.
Helmut