Update WifiRemoteStationManager Lookup data structures
Background
WifiRemoteStationManager
class is the main class for storing remote stations records in wifi
module. This class includes following data structures
typedef std::vector <WifiRemoteStation*> Stations;
typedef std::vector <WifiRemoteStationState *> StationStates;
In many places inside WifiRemoteStationManager
implementation, following functions are called quite frequently e.g. construction of WifiTxVector
.
WifiRemoteStation* Lookup (Mac48Address address) const;
WifiRemoteStationState* LookupState (Mac48Address address) const;
In the above functions, input parameter address
is compared with WifiRemoteStationState::m_address
that uniquely identifies the WifiRemoteStationState
and corresponding WifiRemoteStation
. Due to vector
data structure for Stations
and StationStates
, linear search is performed to compare the function input parameter. Such linear search can be inefficient in reference to time complexity in dense deployment scenarios with many remote stations, a key scenario of 802.11ax WLANs.
In WifiRemoteStationManager::GetMostRecentRssi (Mac48Address address) const
function, the looping over m_stations
is not interrupted even after WifiRemoteStation
with matching address is found.
Proposal
As input parameter in the lookup functions is compared with WifiRemoteStationState::m_address
, std::unordered_map
can be used directly with key as Mac48Address
instead of std::vector
for Stations
and StationStates
.
using Stations = std::unordered_map <Mac48Address, WifiRemoteStation *, WifiAddressHash>;
using StationStates = std::unordered_map <Mac48Address, WifiRemoteStationState *, WifiAddressHash>;
This update has potential reduce the lookup time complexity with consideration of additional hash processing time. In the attached patch, for simplicity, the existing WifiAddressHash
is used similar to other usage found in wifi
module.
Moreover, having a map
-like data structure would make it easier to update station records over time e.g. erasing old records to further reduce Stations
and StationStates
size.