-
Notifications
You must be signed in to change notification settings - Fork 53
Mesh Synchronization Implementation Notes
Mesh Synchronization is specified in the IEEE 802.11 Standard. For our implementation, we've used IEEE Draft P802.11-REVmbTM/D12, November 2011.
There have been changes required to nl80211, cfg80211 and mac80211. But the bulk of the mesh synchronization takes place in net/mac80211/mesh_sync.c. This should be your starting point if you intend to review and/or extend this code.
The 802.11s specification defines an extensible mesh synchronization framework. To achieve this extensibility, the framework has been implemented using the common operations table pattern frequently used in the kernel.
The table is an array of struct ieee80211_mesh_sync_ops which provides definitions for the following functions (operations):
struct ieee80211_mesh_sync_ops {
void (*rx_bcn_presp)(...);
void (*adjust_tbtt)(...);
void (*add_vendor_ie)(...);
};The functions will be called by the open80211s protocol at different times as required to track timing offset and correct drift.
- rx_bcn_presp() - this is called every time a mesh beacon is received.
- adjust_tbtt() - this is called immediately before a beacon is about to be transmitted.
- add_vendor_ie() - this is called every time a beacon or a peer link management frame is about to be transmitted.
Per-peer offset tracking takes place inside mesh_sync_offset_rx_bcn_presp(). The function is passed an struct ieee80211_rx_status that contains a filed (rx_status->mactime) with the local tsf value recorded at the reception of the first symbol of the beacon. If the beacon comes from a known station (either an established peer or a peer candidate), the t_offset for that station (sta) is recorded in ```sta->t_offset``.
Once the t_offset for a particular peer is known, the flag WLAN_STA_TOFFSET_KNOWN is set on the station so that the can be reported to userspace (e.g. iw).
Jitter mitigation is essential for the correct adjustment of clock drifts, but the 802.11 specification does not define any jitter mitigation method. Instead, there is only an implicit reference to it. See Section 13.13.2.2.3:
When the previous TClockDrift values have been stable for a neighbor mesh STA, the mesh STA may substitute the previous TClockDrift value for the TClockDrift value in the measurement procedure and process the step d), at the time of a TBTT of the neighbor STA, without receiving a Beacon frame.
(The italics above are not on the original text)
In our implementation, it was simpler to compensate for jitter in the t_offset measurement that we record for each peer. We do this using the following weighted average formula:
[ avg_t_offset_{n+1} = {T_{offset} + 7 * avg_t_offset_{n} \over 8} ]
When you review the code you will surely be tempted to re-order some statements to optimize the offset calculations: think twice before doing so. In particular, you have to consider that any access to the sta pointer must take place within the rcu_read_lock/unlock section, and also one cannot call any functions that might sleep within that section. That includes the evident spin_lock() calls but also the calls to the driver to get or set the TSF counter (drv_get/set_tsf()).
The function mesh_sync_offset_rx_bcn_presp() will record the maximum drift for all the stations and store it in the mesh interface variable ifmsh->sync_offset_clockdrift_max. Note there is only one such variable per mesh interface, and it will store the maximum clock drift for all the stations at any given time. This calculation is omitted when the node is adjusting its tbtt (i.e. when ``ifmsh->adjusting_tbtt``` is non-zero).
In a different execution thread, every time a beacon is about to be sent, the function mesh_sync_offset_adjust_tbtt() will check if the sync_offset_clockdrift_max exceeds a certain threshold. The specification does not mention this minimum adjustment threshold (TBTT_MINIMUM_ADJUSTMENT) but it is necessary to prevent TSF adjustments that are smaller than the minimum TSF adjustment latency. We are currently using a value of [ 10 \mu{}s] for this threshold, and may probably have to be revisited in the future. This function is also responsible for determining if the adjustment is small enough to be applied all at once or gradually applied over several beacons.
Note that ifmsh->sync_offset_clockdrift_max is only incremented while ifmsh->adjusting_tbtt is zero, and only decremented (or reset to zero) when ifmsh->adjusting_tbtt is non-zero.
mesh_sync_offset_adjust_tbtt() is invoked within an rcu_read section, and therefore it is not possible to make calls to the driver tsf functions from within that function. To resolve this we use the mesh workqueue which is only scheduled if the function determines that a TSF adjustment is needed.
The call that schedules the workqueue is set_bit(MESH_WORK_DRIFT_ADJUST, &ifmsh->wrkq_flags);.
And the handler that is invoked when the work queue is scheduled is on that same file, mesh_sync_offset_adjust_tbtt. The workqueue handler is scheduled in process context and therefore is allowed to make any driver calls it requires.
TODO: document new options, show new Toffset output
iw mesh0 station dump
TODO: show new Toffset output
TODO: Explain how to switch from default to vendor specific modes.
Testing synchronization can get tricky on a real mesh network. To be able to test synchronization in a controlled environment, we modified the wireless driver simulator (mac80211_hwsim) to report TSF time based on the kernel high-resolution clock. We also introduced the ability to independently change the offset of each radio instantiated by mac80211_hwsim so we could introduce drift and observe the mesh synchronization mechanism in action.
We also introduced a new kernel configuration option CONFIG_MAC80211_VERBOSE_MESH_SYNC_DEBUG that will dump a lot real-time information about mesh synchronization.
Once you have convinced yourself that mesh synchronization works you can try it on real hardware. To manually introduce drift you can use the new tsf control variable via debugfs.
TODO: example
To introduce small TSF jumps, you can use the following syntax:
echo +=000002000 > /debugfs/path/to/tsf
or
echo -=000002000 > /debugfs/path/to/tsf
This work was a collaboration between Marco Porsch <marco.porsch_AT_etit.tu-chemnitz.de>, Pavel Zubarev <pavel.zubarev_AT_gmail.com> and the friendly folks for cozybit Inc.