Campuses:

Team 2: 802.11 WLAN MAC layer modeling

Wednesday, August 8, 2007 - 10:00am - 10:20am
EE/CS 3-180
Radu Balan (Siemens Corporate Research, Inc.)
802.11 Wireless Local Area Networks (WLANs) have become as
ubiquitous as Internet access for personal computers. The basic
unit of a WLAN is composed of one Access Point (AP), and
several mobile stations (STAs), all forming a Basic Service Set
(BSS). A typical WLAN setup is depicted in Figure 1.





Figure 1: A typical Basic Service Set (BSS), with one AP, and
several mobile stations.



The IEEE Standard governing WLANs describes two modes of
operation: Distributed Coordination Function (DCF), and Point
Coordination Function (PCF). By and large, chipset
manufacturers implement only the DCF mode, and compatibility
testing is done for this mode exclusively. The DCF is a
contention-based mechanism where each wireless device (AP, or
STA) competes for air time. More specifically, the 802.11
standard is implemented as follows:



  1. At regular intervals (typically hundreds of ms) the AP
    broadcasts a beacon signal, which resets all devices internal
    clocks;


  2. Assume a transmission opportunity ended at time t0.
    Depending on the status of the internal Backoff counter (BCK)
    of the device, the following actions can take place:



    • If BCKr=0, and there is no activity on air for DIFS
      (Distributed Inter Frame Spacing = 50us in 802.11b) time, then
      station starts transmitting its data packet;

    • If BCK=0 and during the DIFS period there is activity
      on air then device generates a random BCK between 0 and CW-1
      (initially CW=CWmin = 16, in 802.11b); Then the following rules
      apply:


      • For each slot time (Ts) of medium inactivity, the BCK
        decrements;

      • The countdown is stopped whenever medium is busy, and
        the the countdown is resumed only after a supplemental AIFS
        (Arbitration Inter Frame Spacing, =DIFS in 802.11b) wait;

      • When BCK reaches 0, the device transmits its packet
        data;

      • If receiver (AP, or STA) receives successfully the
        packet, then it sends back on the air an Acknowledgement (ACK)
        frame, after a SIFT (Short Inter Frame Spacing = 10us) period
        after transmitter finishes its transmission;


      • If transmitter receives the ACK correctly, then it
        assumes data was received correctly, and transmission ends; On
        the other hand, if ACK is not broadcast, or the transmitter
        does not receive correctly the ACK, then it assumes the
        transmission was not successful, and the following rules apply:


        1. If current number of retransmissions has not reached a
          max threshold, then increment the Number of Retransmissions
          counter

        2. If CW

        3. A new random BCK is generated between 0 and CW-1;

        4. Transmission process is restarted from step
          b. above

    • When transmission ends, a post-backoff mechanism is
      implemented, by which a random BCK between 0 and CWmin-1 is
      generated, and a virtual countdown process is started obeying
      b.i and b.ii above.


These (somewhat simplified) rules govern the behavior of 802.11
devices.
A big challenge in WLAN research is in modeling such a system.
The purpose of this research group is to advance the current
state-of-the-art model to allow for effective network control
algorithm design.


Description of the problem


Basically there are two distinct regimes, completely opposite
from one another:


  1. Deterministic Regime: when no collision happen, and the
    initial MAC instance time are sufficiently far apart, then
    transmission happens in a deterministic mode. Such a case may
    happen when only voice data (such as VoIP stations are
    connected to the AP), or periodic transmitting stations are
    present. The deterministic regime analysis gives an upper bound
    on system performance;

  2. Stochastic Regime: once collisions happen, or medium is
    detected busy during a packet arrival, the random generation of
    a Backoff counter happens, and the contention-based mechanism
    kicks in.


The deterministic regime is used to compute maximal performance
of a WLAN. In such a case, performance may be superior even to
the PCF mode, where AP acts as a transmission controller.
However, in highly loaded networks, collisions are quite
frequent, and the stochastic regime is more likely. Several
works proposed stochastic models for this regime. Each work
concerned one feature or another of network behavior. Bianchi
[1] was the first to propose the use of Markov Chain in
modeling the saturation regime of a WLAN. Since his paper,
several others considered saturation, and non-saturation
modeling of WLANs, increasing the model complexity, and taking
into account more phenomena observed in experimental setups. In
particular [2] represents a relatively good stochastic model
for several regimes of WLAN. A somewhat refined diagram is
presented in Figure 2.
However the current state-of-the-art model is not sufficient
for several reasons:

  1. It does not take into account the deterministic regime,
    nor does the performance converge to that upper bound;

  2. The Markovianity assumption is not always justifiable;
    is it possible to introduce a deterministic-stochastic hybrid
    model?

  3. Subsequent improvements of the standard are not yet
    captured by the current model; in particular the 802.11n draft
    introduces new MAC mechanisms.


The goal of this research group is to address one or more of
the issues above.
Ideally, students should have:


- familiarity with basic stochastic modeling concepts
(such as Markov chains)

- familiarity with use of network simulation software
(such as ns2);

- familiarity with time-series data analysis software
(such as perl, Matlab);







Figure 2: A Markov Chain Model for a WLAN device.



Bibliography


[1] G.Bianchi, Performance Analysis of the IEEE 802.11
Distributed Coordination Function
, IEEE Journal on Selected
Areas of Communications, 18 (3), 2000, 535-547.


[2] P.E.Engelstad and O.N.Osterbo, Non-Saturation and
Saturation Analysis of IEEE 802.11e EDCA with Starvation
Prediction
, MSWiM.05: Proceedings of the 8th ACM international
symposium on Modeling, analysis and simulation of wireless and
mobile systems, Montreal, Canada, 2005.