Since properly handling of IBSS merges seems to be tricky, this page is intented for collecting three types of informations:
- How IBSS merges should be handled in theory, according to 802.11 specs
- How IBSS merges are handled by Atheros hardware
- How IBSS merges should be handled by the madwifi software
IBSS merges according to 802.11 specs
Here are the various extract from the IEEE 802.11-1999 standards.
220.127.116.11.3 BSSID ﬁeld
The BSSID ﬁeld is a 48-bit ﬁeld of the same format as an IEEE 802 MAC address. This ﬁeld uniquely identiﬁes each BSS. The value of this ﬁeld, in an infrastructure BSS, is the MAC address currently in use by the STA in the AP of the BSS.
The value of this ﬁeld in an IBSS is a locally administered IEEE MAC address formed from a 46-bit random number generated according to the procedure deﬁned in 11.1.3, as deﬁned in 5.2 of IEEE Std 802-1990.
The individual/group bit of the address is set to 0. The universal/local bit of the address is set to 1. This mechanism is used to provide a high probability of selecting a unique BSSID. The value of all 1s is used to indicate the broadcast BSSID. A broadcast BSSID may only be used in the BSSID ﬁeld of management frames of subtype probe request.
18.104.22.168 TSF for an independent BSS (IBSS)
The TSF in an IBSS shall be implemented via a distributed algorithm that shall be performed by all of the members of the BSS. Each STA in the BSS shall transmit beacons according to the algorithm described in this clause. Each STA in an IBSS shall adopt the timing received from any beacon or probe response that has a TSF value later than its own TSF timer.
22.214.171.124 Beacon generation in an IBSS
Beacon generation in an IBSS is distributed. The beacon period is included in Beacon and Probe Response frames, and STAs shall adopt that beacon period when joining the IBSS. All members of the IBSS participate in beacon generation. Each STA shall maintain its own TSF timer that is used for aBeaconPeriod timing. The beacon interval within an IBSS is established by the STA that instantiates the IBSS. This deﬁnes a series of TBTTs exactly aBeaconPeriod time units apart. Time zero is deﬁned to be a TBTT. At each TBTT the STA shall:
- Suspend the decrementing of the backoff timer for any pending non-beacon or non-ad hoc trafﬁc indication (ATIM) transmission,
- Calculate a random delay uniformly distributed in the range between zero and twice aCWmin x aSlotTime,
- Wait for the period of the random delay, decrementing the random delay timer using the same algorithm as for backoff,
- Cancel the remaining random delay and the pending beacon transmission, if a beacon arrives before the random delay timer has expired, and the ATM backoff timer shall resume decrementing.
- Send a beacon if the random delay has expired and no beacon has arrived during the delay period. (See Figure 65.)
The beacon transmission shall always occur during the Awake Period of STAs that are operating in a low-power mode. This is described in more detail in 11.2.
126.96.36.199 Beacon reception
STAs in an IBSS shall use other information in any received Beacon frame for which the IBSS subﬁeld of the Capability ﬁeld is set to 1 and the content of the SSID element is equal to the SSID of the IBSS. Use of this information is speciﬁed in 11.1.4.
11.1.3 Acquiring synchronization, scanning
When a STA starts a BSS, that STA shall determine the BSSID of the BSS. If the BSSType indicates an infrastructure BSS, then the STA shall start an infrastructure BSS and the BSSID shall be equal to the STA’s dot11StationID. The value of the BSSID shall remain unchanged, even if the value of dot11StationID is changed after the completion of the MLME-Start.request. If the BSSType indicates an IBSS, the STA shall start an IBSS, and the BSSID shall be an individual locally administered IEEE MAC address as defined in 5.2 of IEEE Std 802-1990. The remaining 46 bits of that MAC address shall be a number selected in a manner that minimizes the probability of STAs generating the same number, even when those STAs are subjected to the same initial conditions. The value SSID parameter shall be used as the SSID of the new BSS. It is important that designers recognize the need for statistical independence among the random number streams among STAs.
11.1.4 Adjusting STA timers
In the infrastructure network, STAs shall always adopt the timer in a beacon or probe response coming from the AP in their BSS.
In an IBSS, a STA shall always adopt the information in the contents of a Beacon or Probe Response frame when that frame contains a matching SSID and the value of the time stamp is later than the STA’s TSF timer. In response to an MLME-Join.request, a STA shall initialize its TSF timer to 0 and shall not transmit a beacon or probe response until it hears a beacon or probe response from a member of the IBSS with a matching SSID.
All Beacon and Probe Response frames carry a Timestamp ﬁeld. A STA receiving such a frame from another STA in an IBSS with the same SSID shall compare the Timestamp ﬁeld with its own TSF time. If the Timestamp ﬁeld of the received frame is later than its own TSF time, the STA shall adopt all parameters contained in the Beacon frame.
IBSS merges hardware handling
From a discussion on #madwifi : The BSSID passed to the HAL with the function ath_hal_setassocid() has influence on when the hardware merge takes place. The hardware only updates the hardware TSF value when the last written BSSID through the function ath_hal_setassocid() is the same as the one in the received beacon. So when the BSSID does not match with the received beacon, the hardware TSF is NOT updated. The BSSID is NOT updated automatically by the hardware : this is done by software. So, what we think normally happens:
- Step 1: beacon is received, BSSID does not match with one in associd, software does detect that TSF value is higher in beacon than hardware TSF and performs a software merge
- Step 2: after software merge the bssid of the beacon is placed in associd
- Step 3: next beacon is received by hardware, it sees that bssid of beacon matches associd and it performs a hw merge (tsf update)
- Step 4 : the reported tstamp is unreliable in this case because it can be drawn from the old TSF or the new TSF value, so completely useless for this beacon. Step 4 sometimes causes a phantom second software merge now, but this double merge is quickly detected by the ieee80211 stack software and discarded (see ieee80211_ibss_merge in ieee80211_node.c : if (ni == vap->iv_bss) return 0;)
We have adhoc test case 5 DevDocs/AdhocTestScenario which causes all the troubles so far because in test case 5, the IBSS cell created on node A has the same BSSID as the beacon it will receive from B and because this BSSID is written in associd when creating this IBSS cell, the problem arises. It causes the hardware TSF to be updated right when the first beacon is received because the BSSID of the beacon already matches the associd bssid so steps 3 and 4 all happens at the same time but like i said, the tstamp value is unreliable when hardware TSF is updated during reception, so this causes step 1 to fail sometimes and the software doesn't detect a merge at all
Problem A: Race Condition
Probably a race condition exists. Suppose we have nodes A, B and C where A is the oldest. B and C are transmitting beacons to A. We think step 3 will never be reached because a beacon of B or C will will trigger step 1 before step 3 is executed. This is only theory, and not yet tested.
Problem B: Not consistent
Already mentioned, in test case 5 the BSSIDs already match, causing the software to refuse merging.
Solution 1 - Problem B: Initialize associd
The associd can be set to broadcast at initialization, instead of the own IBSSID of the node. It is verified that this solves test case 5, but it doesn't solve the problem in general. This can be illustrated with an example.
The numbers in this table indicate the HW TSF values of the nodes at a given moment in time. Time is increasing from top to bottom.
~ means that nodes can hear each other.
x means that a node is not running.
r means that a node is restarted.
Node 1 is started first. After 11 ticks node 2 is started. 1 and 2 can hear each other so they will merge. Node 1 is restarted. Then node 3 is started and will merge on TSF = 5. The problem remains if we bring node 2 and 3 in each others neighbourhood, because both have an associd which equals that of node 1.
Conclusion: solution not correct (only for test case 5).
Solution 2 - Problem B: update associd
The idea of this solution is that the associd is only set to the ibssid when a merge is pending, and set to broadcast in all other cases. This makes sure step 1 of the merge process is always executed.
This solutions is not tested yet, but discussed on irc.
Conclusion: This is not a good solution, because the hardware should be able to update the TSF when clock drift occurs. The hardware is not able to do this if associd is set to the wrong value.
Solution 3 - Problem B: Improve tstamp
As noted, the tstamp value in step 4 of the merge process is not reliable. We can try to improve this tstamp value, if we can detect the tstamp value is not related to the current hw TSF, we can assume that a update of the TSF value has taken place.
This method is currently evaluated.
Open questions remain:
- Can the tstamp value overflow multiple times, before an interrupt is triggered?
- When is the tstamp correct? Current solution assumes that the TSF may be at most 500 us ahead of the tstamp. But this assumption can change on systems with heavy load.
Solution 4 - Problem B: Random IBSSIDs
When a node is started, it should generate its own random IBSSID. It is clear that test case 5 will not fail in this case.
Note: This solution was also discussed on irc, and a developer noted that random IBSSIDs makes debugging hard. I think this cannot be a valid reason to keep the IBSSIDs constant. A solution to the debugging problem can be to fix the last 8 bits, so that nodes can be traced.
The current madwifi implementation is currently not conform the 802.11-1999 standard because for IBSS the MAC address is used as identifier. See chapter "188.8.131.52.3 BSSID ﬁeld".
Open questions remain:
- What is the chance of a collision? (equal birthday problem)
IBSS merges software handling
As of 2007-11-03, IBSS merges are not properly handled by the software.