Traffic differentiation with CSMA/ECA [Part 1]

NOTE: this is a highly specialised post. If you need further information, don’t hesitate to contact me or comment.

In order to continue the adaptation of CSMA/ECA [1][2] into today’s standards of Quality of Service, in the followings I detail how our protocol can provide traffic differentiation by just a simple modification to the backoff procedure. Further, we see that it is possible to achieve a collision-free schedule for small number of contenders while differentiating traffic under saturated conditions.

How is traffic differentiation implemented at the MAC layer?

Basically, each node has as many instances of the MAC protocol as “Access Categories” (AC). Priorities are assigned to each AC (defined by the standard), meaning that the AC with the highest priority will access the channel quicker, an consequently transmit more than other ACs.

There are four traffic differentiation queues (or ACs) defined for Enhanced Distributed Channel Access (EDCA) (EDCA is the coordination function used in the standard). These are (lowest to highest priority): Background (BK), Best-effort (BE), Video (VI) and Voice (VO). Each category conforms an individual queue in the node.

EDCA considers several ways to provide priority, like the Transmission Oportunity (TXOP) and the Arbitration inter-frame Spacing (AIFS). These topics (hopefully) will be explained and contrasted with CSMA/ECA on a later post.

Differences with EDCA

The main difference between CSMA/ECA and the current coordination function used in the standard is that in CSMA/ECA ACs will use a deterministic backoff after successful transmissions.

Providing priority via the backoff mechanism

Each MAC queue has different minimum Contention Window values (CWmin). Additionally, they all share the same Maximum Backoff Stage and the Maximum Retransmission Limit. That is, all CWmax are defined and a packet is dropped once it reaches the retransmission limit.

The AC with the lowest CWmin is the one with the highest priority. This is because the expected value of the random backoff, E[B(i)], is the smallest among the ACs; where B(i)~U∈[0,2^k(i)*CWmin(i)] and k(i) is the backoff stage for ACi.

The following figure is a temporal example of CSMA/ECA+Hysteresis+FairShare with two ACs. [Briefly, Hysteresis prevent nodes from resetting their backoff stage after a successful transmission. FairShare instructs AC i at backoff stage k(i), to transmit 2^k(i) packets in each attempt.]

NOTE: We refer to the whole CSMA/ECA+Hysteresis+FairShare suit, as CSMA/ECA from this point forward.

Figure 1: Temporal example of CSMA/ECA with two ACs

In the example figure, numbers indicate the number of slots left until the expiration of the backoff counter. As you can see, there are two stations, STA 1 and STA 2. Each station has two ACs, AC1 and AC2; where AC1 is the one with the highest priority. For the sake of the example, CWmin[2] = {7, 15}, for AC1 and AC2 respectively; also, Bd(i) = 2^k(i)*ceil(CWmin[i]/2), for all i = {1,2} and ceil() is the ceiling operator.

The first outline (blue) indicates an Internal Collision (IC). These collisions are produced when the backoff counter of two or more AC from the same node expire at the same instant. The lower priority AC(s) acts as if it has just collided, while the highest priority AC wins access to the channel. The second outline (red) shows a collision, while the third outline shows another IC. A successful AC uses a deterministic backoff, while losers of an IC or colliding ACs use a random backoff (incrementing their respective backoff stages and retransmission attempts. All of what involves a real collision). The last outline just shows an upcoming collision between STA 1’s AC2 and STA 2’s AC1.

In the first outline, AC1 from STA 2 wins the contention in the IC. After the successful transmission it uses Bd(1) = 3 (which means that the transmission will happen at the 4th slot). Also, notice how AC1 from STA 1 uses Bd(1), and AC2 from STA 1 uses Bd(2) = 7. Nevertheless, a real collision occurs (second outline) and the colliding ACs use a random backoff. Particularly, this collision provokes an IC between AC1 and AC2 from STA 1 (third outline); postponing STA 1 AC2’s transmission. Furthermore, even though STA 1’s AC2 has successfully transmitted in the past, the selection of the random backoff after the IC with AC1 provokes a collision with STA 1’s AC1 (fourth outline).

This way, AC1 on both nodes will (on average) access the channel more times than AC2. This is how traffic differentiation is performed at the MAC layer.

Are we able to eliminate collisions?

Because of the nature of its backoff mechanism, EDCA is unable to eliminate collisions. ACs will always pick a random backoff. The following shows the aggregated throughput under saturated conditions for EDCA and CSMA/ECA with four access categories.

Aggregated Throughput

Figure 2: Aggregated Throughput

Figure 2 only shows the aggregated throughput. Each AC constitutes a predefined share of the curve shown. We can see that CSMA/ECA achieves greater throughput than EDCA. This is in part due to the aggregation performed by FairShare. The following figure shows the total number of collisions slots.

Figure 3: Total number of collision slots

As we can see from the figure, the number of collisions experienced when using CSMA/ECA is lower than EDCA, which contributes to the higher aggregated throughput seen in Figure 2. Nevertheless, Figure 2 and Figure 3 suggest that collisions are not eliminated, degrading CSMA/ECA throughput towards EDCA’s.

A collision-free schedule should be able to accommodate the transmissions of all ACs, without collisions. The following figure shows the number of collisions in the last thousand slots on a five hundred seconds simulation with 70 nodes.

Accumulated collisions in the last 1000 slots

Figure 4: Accumulated collisions in the last 1000 slots

CSMA/ECA has a lower number of accumulated collisions every 1000 nodes, sadly, this means that a collision-free schedule is not built (it should be 0). The reason for this is that the schedule length to accommodate all transmissions should be greater or equal than 70*ACs = 70*4 = 280 empty slots, or the closest power of 2 which is 512. This is not possible with the current CWmin values for highest priority AC given by the standard. For example, the highest priority AC0 in our simulator has CWmin[0] = 8 (which follows CWmin values given by Perahia). Meaning that its maximum schedule length is 2^m*CWmin[0] /2= 2^5*8/2 = 128 empty slots. This is equivalent to the minimum collision-free schedule for 32 nodes with 4 ACs in saturation.

Figures 5-7 show the accumulated collisions in the last 1000 slots for networks with 8, 16 and 32 nodes.

Accumulated collisions in the last 1000 slots: 8 nodes

Figure 5: Accumulated collisions in the last 1000 slots: 8 nodes

Figure 6: Accumulated collisions in the last 1000 slots: 16 nodes

Figure 6: Accumulated collisions in the last 1000 slots: 16 nodes

Accumulated collisions in the last 1000 slots: 32 nodes

Figure 7: Accumulated collisions in the last 1000 slots: 32 nodes

For 8 and 16 nodes, CSMA/ECA is able to built a collision-free schedule at around 5 and 143 seconds into the simulation, respectively. For 32 nodes the transitory state seems to never end, or at least it lasts longer than the simulation time.

Can we built a collision-free schedule? Sort of, yes! The problem seems to be that the schedule length is constrained by the maximum deterministic backoff of the highest priority AC.

What if you increase all CWmins to a maximum value, say CWmin = 1024 with MAXSTAGE = 5? Wouldn’t it eliminate collisions and make possible a collision-free schedule? Yes, you will be able to accommodate much more contenders. Furthermore, the throughput won’t be degraded the same for either protocol. Seems good, but it eliminates any traffic differentiation. In Figure 8 and 9, the curve number 1 (one) shows EDCA, while 2 (two) shows CSMA/ECA with CWmin = 1024 for all ACs. The figures show better aggregated throughput for both protocols, evenly shared among ACs. The same goes for Figure 9, if compared with Figure 3 we can see reduction in the total number of collisions. But again, this is not the desired behaviour. Traffic is not being differentiated. What you can do is to assign bigger CWmin to all ACs, this way more contenders can be accommodated in a collision-free schedule with traffic differentiation.

Figure 8: Aggregated throughput. Maximum CWmin for all ACs.

Figure 8: Aggregated throughput. Maximum CWmin for all ACs.

Figure 9: Collisions. Maximum CWmin for all ACs.

Figure 9: Collisions. Maximum CWmin for all ACs.

I am currently working on reducing the transitory state (time spent building a collision-free schedule, if possible). We came out with a pseudo-random backoff that eliminates internal collisions, consequently reducing the transitory state.

This, as it turned out to be, would be another Series. If you are interested on the implementation on the simulator read the first and second reports.



Edit 1 (Jan 22): Corrected Figure 6.

Edit 2 (Jan 28): Fixed Figure 1.

Edit 3 (March 5): The priorities, from low to high priority: Background, Best-effort, Video and Voice. In some of the figures, the Background and Best-effort priorities are inverted. Nevertheless it does not alter the explanation given.

Posted under: CSMA/ECA, EDCA, Fair Share, Hysteresis, MAC, QoS, WiFi