| Message ID | 20240124134001.20453-2-prestwoj@gmail.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | [v2,1/4] knownnetworks: pass scan_bss to known_network_add_frequency | expand |
| Context | Check | Description |
|---|---|---|
| tedd_an/pre-ci_am | success | Success |
| prestwoj/iwd-ci-gitlint | success | GitLint |
Hi James, On 1/24/24 07:39, James Prestwood wrote: > Currently a quick scan uses the entire known frequency list so > ordering really doesn't matter but improvements will be made here > to make quick scans "quicker" for large network deployments (with > many known frequencies). > > To prepare for this the known frequency list has been changed to > be sorted by BSS rank rather than most recently seen. This makes > a lot more sense because IWD should prefer to scan frequencies > that had higher ranked BSS's, not just frequencies that were scanned > last on the most recent scan. Interesting. I definitely agree with the argument for treating frequencies with higher-ranked candidates as preferred, but I'm not sure that directly basing the frequency preference on the bss rank is the right thing to do. A client might start right under an AP, ranking it quite high, but then rapidly move away where no APs exist on this frequency. So you end up always scanning the original AP's frequency. Some sort of temporal rank decay would be needed? Perhaps an easier way to accomplish this would be to add known frequencies in reverse bss->rank sorted order. That way last seen frequency with best ranked BSS would be first? Do note however that the quick scan approach is really meant for smallish networks, to cut down scanning time when moving between Home / Office location for example. It works surprisingly well, but might not be appropriate for rapid roaming in a large network. > > As far as the disk sync goes the ranking is not included, but > ordering is. This really isn't a limitation because when IWD starts > up there isn't any guarantee its in the same physical location so > old scan ranks are likely not valid anymore. The first set of scans > will begin replacing the frequencies loaded from disk. > --- > src/knownnetworks.c | 16 ++++++++++++++-- > src/knownnetworks.h | 1 + > 2 files changed, 15 insertions(+), 2 deletions(-) > Regards, -Denis
Hi Denis, On 1/24/24 10:10 AM, Denis Kenzior wrote: > Hi James, > > On 1/24/24 07:39, James Prestwood wrote: >> Currently a quick scan uses the entire known frequency list so >> ordering really doesn't matter but improvements will be made here >> to make quick scans "quicker" for large network deployments (with >> many known frequencies). >> >> To prepare for this the known frequency list has been changed to >> be sorted by BSS rank rather than most recently seen. This makes >> a lot more sense because IWD should prefer to scan frequencies >> that had higher ranked BSS's, not just frequencies that were scanned >> last on the most recent scan. > > Interesting. I definitely agree with the argument for treating > frequencies with higher-ranked candidates as preferred, but I'm not > sure that directly basing the frequency preference on the bss rank is > the right thing to do. A client might start right under an AP, > ranking it quite high, but then rapidly move away where no APs exist > on this frequency. So you end up always scanning the original AP's > frequency. Some sort of temporal rank decay would be needed? Yeah, I see your point... > > Perhaps an easier way to accomplish this would be to add known > frequencies in reverse bss->rank sorted order. That way last seen > frequency with best ranked BSS would be first? I'm not sure I understand, how would this be any different than just reversing the list I already have? Or are you saying sort by both rank and last seen? Essentially have the list segmented into chunks of frequencies found with prior scans: [Last Scan] [N - 1] [N - 2] [ etc ] And if a duplicate is found, move it to the front, sorted by rank? > > Do note however that the quick scan approach is really meant for > smallish networks, to cut down scanning time when moving between Home > / Office location for example. It works surprisingly well, but might > not be appropriate for rapid roaming in a large network. Exactly, e.g. with 50 APs (assuming you've seen them all) a "quick" scan takes 5 seconds. > >> >> As far as the disk sync goes the ranking is not included, but >> ordering is. This really isn't a limitation because when IWD starts >> up there isn't any guarantee its in the same physical location so >> old scan ranks are likely not valid anymore. The first set of scans >> will begin replacing the frequencies loaded from disk. >> --- >> src/knownnetworks.c | 16 ++++++++++++++-- >> src/knownnetworks.h | 1 + >> 2 files changed, 15 insertions(+), 2 deletions(-) >> > > Regards, > -Denis >
Hi James, >> Perhaps an easier way to accomplish this would be to add known frequencies in >> reverse bss->rank sorted order. That way last seen frequency with best ranked >> BSS would be first? > > I'm not sure I understand, how would this be any different than just reversing Well, right now we maintain the least recently seen frequency list in a very simple way: - When scan results become available - Walk the result list (which is sorted by bss_rank?) - Add each result's frequency to the frequency cache - Remove any matching entry in the cache - Add it to head Since the result list is sorted, the top entry in the frequency cache is the least ranked. This doesn't matter for small networks since there would only be a couple results. What we should do is to add the frequencies to the frequency cache in reverse order. That way the highest ranked bss is at the top of the frequency cache. Hope that made sense. Regards, -Denis
On 1/24/24 10:44 AM, Denis Kenzior wrote: > Hi James, > >>> Perhaps an easier way to accomplish this would be to add known >>> frequencies in reverse bss->rank sorted order. That way last seen >>> frequency with best ranked BSS would be first? >> >> I'm not sure I understand, how would this be any different than just >> reversing > > Well, right now we maintain the least recently seen frequency list in > a very simple way: > > - When scan results become available > - Walk the result list (which is sorted by bss_rank?) > - Add each result's frequency to the frequency cache > - Remove any matching entry in the cache > - Add it to head > > Since the result list is sorted, the top entry in the frequency cache > is the least ranked. This doesn't matter for small networks since > there would only be a couple results. > > What we should do is to add the frequencies to the frequency cache in > reverse order. That way the highest ranked bss is at the top of the > frequency cache. Oh I see, I didn't realize the list was already sorted since its coming from network->bss_list. But wouldn't we have the same problem here? Old frequencies with a high rank would remain at the front unless they were seen by a recent scan. So if you saw a really high ranked AP once then never again it would always stay at the front. Another thing I didn't consider is multiple BSS's on the same frequency :) Maybe introducing a last seen time would help, though that adds even more complication. > > Hope that made sense. > Regards, > -Denis >
Hi James, On 1/24/24 12:55, James Prestwood wrote: > > On 1/24/24 10:44 AM, Denis Kenzior wrote: >> Hi James, >> >>>> Perhaps an easier way to accomplish this would be to add known frequencies >>>> in reverse bss->rank sorted order. That way last seen frequency with best >>>> ranked BSS would be first? >>> >>> I'm not sure I understand, how would this be any different than just reversing >> >> Well, right now we maintain the least recently seen frequency list in a very >> simple way: >> >> - When scan results become available >> - Walk the result list (which is sorted by bss_rank?) >> - Add each result's frequency to the frequency cache >> - Remove any matching entry in the cache >> - Add it to head >> >> Since the result list is sorted, the top entry in the frequency cache is the >> least ranked. This doesn't matter for small networks since there would only >> be a couple results. >> >> What we should do is to add the frequencies to the frequency cache in reverse >> order. That way the highest ranked bss is at the top of the frequency cache. > > Oh I see, I didn't realize the list was already sorted since its coming from > network->bss_list. But wouldn't we have the same problem here? Old frequencies There are a few paths. One if network becoming promoted from unknown -> known, one for scan results being reported. But in all or most cases the order is predetermined and would be by bss rank. > with a high rank would remain at the front unless they were seen by a recent No, because each time the frequency cache is updated, new entries are put at the top of the list. This automatically pushes older (as in least recently seen order) entries further down. > scan. So if you saw a really high ranked AP once then never again it would > always stay at the front. Nope. Not in the current used implementation. > > Another thing I didn't consider is multiple BSS's on the same frequency :) This is generally not a problem since frequencies are stored per SSID, so for well planned networks you wouldn't have this. But yes, this possibility is something you need to take into account. My suggestion would still handle this nicely. > > Maybe introducing a last seen time would help, though that adds even more > complication. Yep. Only reason to do so would be for serialization to disk I think. Regards, -Denis
Hi Denis, On 1/24/24 11:06 AM, Denis Kenzior wrote: > Hi James, > > On 1/24/24 12:55, James Prestwood wrote: >> >> On 1/24/24 10:44 AM, Denis Kenzior wrote: >>> Hi James, >>> >>>>> Perhaps an easier way to accomplish this would be to add known >>>>> frequencies in reverse bss->rank sorted order. That way last seen >>>>> frequency with best ranked BSS would be first? >>>> >>>> I'm not sure I understand, how would this be any different than >>>> just reversing >>> >>> Well, right now we maintain the least recently seen frequency list >>> in a very simple way: >>> >>> - When scan results become available >>> - Walk the result list (which is sorted by bss_rank?) >>> - Add each result's frequency to the frequency cache >>> - Remove any matching entry in the cache >>> - Add it to head >>> >>> Since the result list is sorted, the top entry in the frequency >>> cache is the least ranked. This doesn't matter for small networks >>> since there would only be a couple results. >>> >>> What we should do is to add the frequencies to the frequency cache >>> in reverse order. That way the highest ranked bss is at the top of >>> the frequency cache. Ok I understand what your getting at now, but providing the list in reverse order is somewhat problematic. The majority of additions are going to be from station's can results, via network_bss_add(). We _could_ reverse the BSS list in station but that seems like an expensive operation for each scan, and I really don't want to muck with that code. The only somewhat simple place to reverse the list is when a known network is added. But again its expensive. To avoid refactoring elsewhere, I think the only way would be to timestamp entries (based on bss->time_stamp) and sort by both rank and timestamp. We could also limit the list to e.g. 5 values if we wanted to avoid storing a ton of u64's in memory. Thanks, James >> > Regards, > -Denis
Hi James, On 1/25/24 07:21, James Prestwood wrote: > Hi Denis, > > On 1/24/24 11:06 AM, Denis Kenzior wrote: >> Hi James, >> >> On 1/24/24 12:55, James Prestwood wrote: >>> >>> On 1/24/24 10:44 AM, Denis Kenzior wrote: >>>> Hi James, >>>> >>>>>> Perhaps an easier way to accomplish this would be to add known frequencies >>>>>> in reverse bss->rank sorted order. That way last seen frequency with best >>>>>> ranked BSS would be first? >>>>> >>>>> I'm not sure I understand, how would this be any different than just reversing >>>> >>>> Well, right now we maintain the least recently seen frequency list in a very >>>> simple way: >>>> >>>> - When scan results become available >>>> - Walk the result list (which is sorted by bss_rank?) >>>> - Add each result's frequency to the frequency cache >>>> - Remove any matching entry in the cache >>>> - Add it to head >>>> >>>> Since the result list is sorted, the top entry in the frequency cache is the >>>> least ranked. This doesn't matter for small networks since there would only >>>> be a couple results. >>>> >>>> What we should do is to add the frequencies to the frequency cache in >>>> reverse order. That way the highest ranked bss is at the top of the >>>> frequency cache. > > Ok I understand what your getting at now, but providing the list in reverse > order is somewhat problematic. The majority of additions are going to be from > station's can results, via network_bss_add(). We _could_ reverse the BSS list in > station but that seems like an expensive operation for each scan, and I really Nah, it is a trivial operation. In fact, l_queue_reverse() already exists. What you can also do is remove the known frequency update from network_bss_add() and have station manage it explicitly. You can then do all sorts of fancy things in station_set_scan_results(). Couple of examples. example 1 - allocate array of l_queue_size(new_bss_list) pairs: [network, frequency] - After calling station_add_seen_bss, jot down network/frequency into the array - Run another loop after to add the frequencies in reverse bss rank order example 2: - Allocate array of l_queue_size(new_bss_list) struct scan_bss pointers - run qsort and sort the entries however you want (say by bss->time_stamp) > don't want to muck with that code. The only somewhat simple place to reverse the > list is when a known network is added. But again its expensive. > > To avoid refactoring elsewhere, I think the only way would be to timestamp > entries (based on bss->time_stamp) and sort by both rank and timestamp. We could > also limit the list to e.g. 5 values if we wanted to avoid storing a ton of > u64's in memory. > See above. I'm really not sure that sorting by timestamp AND rank will do anything. If the driver does things properly then it will report NL80211_BSS_LAST_SEEN_BOOTTIME value, so all entries will have a unique time_stamp. Another thing I thought of is that we probably should be updating the known frequency list based on any neighbor reports we obtain. Just in case we get disconnected for whatever reason before we attempt to roam. Regards, -Denis
diff --git a/src/knownnetworks.c b/src/knownnetworks.c index f6284fdc..6e549e02 100644 --- a/src/knownnetworks.c +++ b/src/knownnetworks.c @@ -562,9 +562,19 @@ static bool known_frequency_match(const void *a, const void *b) return known_freq->frequency == *frequency; } +static int known_frequency_compare(const void *a, const void *b, + void *user_data) +{ + const struct known_frequency *kf_a = a; + const struct known_frequency *kf_b = b; + + return (kf_b->rank > kf_a->rank) ? 1 : -1; +} + /* * Adds a frequency to the 'known' set of frequencies that this network - * operates on. The list is sorted according to most-recently seen + * operates on. The list is sorted according to the rank of the BSS on that + * frequency. */ int known_network_add_frequency(struct network_info *info, struct scan_bss *bss) { @@ -578,9 +588,11 @@ int known_network_add_frequency(struct network_info *info, struct scan_bss *bss) if (!known_freq) { known_freq = l_new(struct known_frequency, 1); known_freq->frequency = bss->frequency; + known_freq->rank = bss->rank; } - l_queue_push_head(info->known_frequencies, known_freq); + l_queue_insert(info->known_frequencies, known_freq, + known_frequency_compare, NULL); return 0; } diff --git a/src/knownnetworks.h b/src/knownnetworks.h index 9f81e308..36106501 100644 --- a/src/knownnetworks.h +++ b/src/knownnetworks.h @@ -96,6 +96,7 @@ typedef void (*known_networks_destroy_func_t)(void *user_data); struct known_frequency { uint32_t frequency; + uint16_t rank; }; void __network_config_parse(const struct l_settings *settings,