Reducing the collision-free schedule’s length in CSMA/ECA Part I

One of the jewels of CSMA/ECA is its ability to build collision-free schedules with many nodes. The mechanism we came up with is called Hysteresis. It just instructs nodes not to reset their backoff stage, k∈[0,m], after a successful transmission. This results in a deterministic backoff after successul transmissions, Bd(k) = 2^k*CWmin/2.

The above means that if the node misinterprets the channel condition (sees it as busy when was free), it will not decrement the deterministic backoff counter, would disrupt the collision-free schedule and will double its future Bd(k). This is particularly disadvantageous when working in networks with few nodes, like 10.

If stations continuously collide due to misinterpretations of the channel conditions, their respective Bd will rapidly reach its maximum value (Bd(m)); increasing the time between successful transmissions and degrading the throughput.

Halving the schedule: from Bd(k) to Bd(k-1)

Note: well, actually: k-1 = max(0, k-1).

– Why?

  1. Empty slots affect negatively the overall throughput.
  2. With few users, CSMA/ECA+Hysteresis is unable to outperform DCF (in real hardware implementations).

– Consequences?

  1. Another possible transitory state.
  2. Unfairness?
    1. DCF is very unfair in real hardware implementations. Mostly because of the capture effect and the location of the nodes.

– Precautions?

  1. There should be condition to determine when a halving of the schedule should be done.
  2. Another conditions should be determined to know when NOT to halve the schedule.
  3. You can only halve the cycle if the current cycle is collision-free.

– Trade-off?: Sacrificing collisions for shorter collision-free schedules.

How?

1. A complete schedule is defined as:

C = 2^m*CWmin/2

(1)

, where m is the maximum backoff stage.

2. In order to halve its schedule length, station i should check if its desired schedule Ci(k-1) is collision-free in the complete schedule C.

Lets introduce a variable containing the state of a slot.

σ(s) = 0, if slot s is busy

σ(s) = 1, if slot s is empty

(2)

3. Regardless of the stations i‘s backoff stage (k), we should check if Ci(k-1) fits in an already collision-free C.

Because station i transmits C/Ci(k) times per complete schedule, to check the availability of a slot in a Ci(k-1) cycle a node should check the respective slot β times, where β = C/Ci(k) – 1.

Φ(k-1) = (∏σ(s))/2; over all s∈A.

(3)

, where A is a set containing all slots of schedule Ci(k-1) not in Ci(k) in the complete schedule C. It has β members.

Ci(k-1) = Φ(k-1)Ci(k)

(4)

If Ci(k-1) = 0, then the station schedule will remain Ci(k). Otherwise, Ci(k-1) = Ci(k)/2.

Example

Given: Ci = 32; k = 1, CWmin = 32; C = 512.

T = {0, 32, 64, … , 512} // set of slots containing transmissions of the node in Ci.

A = {16, 48, … , 496} // set of slots to be checked. That is, slots in Ci(k-1)

                                 // but not in Ci(k) in the complete schedule C.

β = C/Ci -1 = 512/32 -1 = 15 // number of members of set A.

In the example above, if all the slots in A are empty, then the station’s schedule length will be halved. Otherwise, the process will be restarted after β consecutive successful transmissionsi.e.: after a complete schedule.

Preliminary results

We tested this approach with a non-perfect channel. This channel reports a collision after 100 successful transmissions. Note that this is just for exemplifying and testing the halving of the schedule.

TL;DR: halving the schedule seems to provide more throughput when working with low number of nodes. Nevertheless, the channel should be better modelled in order to reveal its level of effectiveness.

We will keep working on this to enhance the implementation of CSMA/ECA+Hysteresis on real hardware.

Regards,

L.

——Results——

One collision every 100 successful transmissions (from the Channel perspective)

1) ECA+Hyst, 10 seconds, 10 nodes in saturation
./ECA_exec 10 10 1024 65e6 1 1 1 0 0 0 0 0 322

Normal:
#col = 167
throughput = 1.24838e+07

Halving:
#col = 170
throughput = 1.26083e+07

2) ECA+Hyst, 10 seconds, 20 nodes in saturation
./ECA_exec 10 20 1024 65e6 1 1 1 0 0 0 0 0 322

Normal:
#col = 265
throughput = 1.76341e+07

Halving:
#col = 267
throughput = 1.79782e+07

3) ECA+Hyst, 100 seconds, 70 nodes in saturation
./ECA_exec 100 70 1024 65e6 1 1 1 0 0 0 0 0 322

Normal:
#col = 3878
throughput = 2.54985e+07

Halving:
#col = 3944
throughput = 2.54968e+07

Posted under: CSMA/ECA, Hysteresis, MAC, WiFi