Understanding Collisions under CSMA/CA [3/3]

Carrier Sense Multiple Access with Enhanced Collision Avoidance (CSMA/ECA), is the evolution of L-BEB. It is able to build a collision-free schedule in WLANs by picking a deterministic backoff (Bd = CWmin/2) after successful transmissions. As mentioned in a previous chapter, this mechanism works well because the number of contenders (n) is less or equal than the deterministic backoff (n <= Bd). Meaning that there are enough empty slots in the schedule (of length CWmin) to allocate n transmitters.

One might suggest an increase of the deterministic backoff so it would be equal to the schedule length (Bd = CWmin), this way more contenders can be allocated. Nevertheless, it takes too much time to build the collision-free schedule with this measure (see Jaume’s first proposal of L-BEB).

Hysteresis and its unfairness issues

When nCWmin/2, the network enters in a hybrid mode, that it: some nodes are colliding thus picking a random backoff; and others successfully transmit and pick a deterministic backoff. Although it is still better in terms of throughput (when compared with CSMA/CA), this mixed scenario’s throughput is lower than what can be achieved in a collision-free schedule.

The figure below shows the throughput comparison between a pure CSMA/CA network versus a hybrid 1/2 CSMA/CA and 1/2 CSMA/ECA. Even at the initial number of contenders (n = 2), the mixed scenario provides higher aggregated throughput.

Mixed Scenario vs. CSMA/CA only: Basic ECA is CSMA/ECA without the enhancements yet to be introduced later in this post

Mixed Scenario vs. CSMA/CA only: Basic ECA is CSMA/ECA without the enhancements yet to be introduced later in this post (Hysteresis and Fair Share)

To eliminate this effect, Hysteresis was introduced. It is based on the same concept of L-BEB and extends the number of contenders CSMA/ECA can allocate in a collision-free schedule to CWmax/2. To do so, two modifications to CSMA/ECA took place:

  1. Nodes won’t reset the backoff stage after successful transmissions.
  2. The deterministic backoff will be equal to: Bd = CW(k)/2.

By implementing Hysteresis CSMA/ECA is able to allocate many more contenders. The following bullets describe a sample CSMA/ECA + Hysteresis scenario:

  • If a node has something to transmit, it picks a random backoff, as explained before.
  • The sender waits for an ACKnowledgement from the receiver:
    • If an ACK is received, the node will pick a deterministic backoff Bd = CW(k)/2.
    • If not, then the backoff stage is increased (k+=1) and a random backoff is drawn (B ∈ [0, CW(k)]).

By not resetting the backoff stage after successful transmissions, previous collisions will cause the colliding nodes to wait longer to transmit. Although it helps in the construction of a bigger collision-free schedule, Hysteresis is unfair in terms of unevenly sharing the channel time among all contenders.

Fair Share: aggregation put to work

A quick fix to this problem was first envisioned by Fang et al. We call it Fair Share, and it consist on allowing nodes at backoff stage k to send 2^k packets on each attempt. So, nodes waiting longer for transmission (at a higher backoff stage) will also send proportionally more packets. The figure below serves as a good example of both Hysteresis and Fair Share when applied to CSMA/ECA.

CSMA/ECA + Hysteresis and Fair Share

CSMA/ECA + Hysteresis and Fair Share

With Hysteresis and Fair Share, CSMA/ECA is able to allocate much more contenders in a collision-free schedule, provide throughput fairness and, as the figure below shows, an important increase in the attained throughput.

How Hysteresis and Fair Share impact CSMA/ECA performance

How Hysteresis and Fair Share impact CSMA/ECA performance

Future directions

It is important to highlight that the results shown throughout the three posts of Collisions in WLANs are generated under saturated conditions. We have performed tests under non-saturated scenarios, but later posts will focus on that.

The implementation on real hardware of CSMA/ECA (without Hysteresis and Fair Share) was tested with encouraging results. It is also to be demoed at Multiple Access Communications 2013 (MACOM 2013) by the end of 2013. More posts will assess the process of the demo construction and preliminary results.



Posted under: CSMA/ECA, Fair Share, Hysteresis, MAC