[Ns-developers] a new 802.11 PHY and MAC

[Mathieu Lacage]

hi,

For the past 4 weeks, I have been working on a new 802.11 PHY and MAC
for ns-2. These new layers are currently implemented as an addon to ns-2
and require very little modifications to the existing codebase. This
means that existing simulations using the current 802.11 layer of ns-2
will work unmodified.

An old design document which describes quickly a few ideas on this code
is attached to this email. Of course, the real code is slightly
different so, don't take that document very seriously.

http://www-sop.inria.fr/dream/personnel/Mathieu.Lacage/ns2/80211.tar.gz

The current code is distributed under the GPLv2. I will change this to
whatever license is deemed preferable for inclusion in ns2.

The current code contains:
  - mostly untested but should be working 802.11 PHY
  - code to simulate different modulation/FEC types
  - code to handle different rate control algorithms

The MAC you can find in this code is still a work in progress which
means that it does not work, is not expected to work and will change.
Every file is pretty heavily commented so I expect the codebase to be
rather easy to review.

Comments are welcome.

regards,
Mathieu
-- 
-------------- next part --------------
The architecture of the whole thing is:

---------- MAC ---------
| MAC-high --> MAC-low | --> PHY  <--> PHY ...
------------------------

The MAC is a single ns2 object which handles everything associated
with 802.11 MAC. It is implemented by two objects:
* The high-level MAC handles association, disassociation, aso...
* The low-level MAC contains a queue of packets to send and 
  handles per-packet transmission and deals with:
    - RTS/CTS
    - ACK
    - fragmentation
The PHY deals with:
    - packet corruption
    - store event history necessary for lazy event scheduling.

If you want to implement 802.11e, you would use multiple low-level
MAC instances to talk to a single PHY. For example:

---------- MAC ---------
|          |> MAC-low1 | 
|          |> MAC-low2 | 
| MAC-high |> MAC-low3 | --> PHY <--> PHY
|          |> MAC-low4 | 
------------------------

Each of the MAC-lowX instance contains the packet queue associated to
their Access Category.
-------------------------------------------------------------------------

The Phy implements a relatively simplistic model for transmission 
interference. It is based on the assumption that the SNR of a received
packet is equal to the SNIR: SNR = S / (Nf + Ni) where S is the energy of
received signal, Nf is the noise floor of the receiver and Ni is the 
interference noise.

S is calculated by using a propagation model for the transmission medium
which calculates the attenuation based on the transmission power and the 
distance between the transmitter and receiver.

Nf depends on the receiving circuitry and the bandwidth of the received
signal. It is calculated with the following formula (at 60 degree 
farenheit):
Nf = (BOLTZMANN * 290.0 * bandwidth) * (circuitNoise / 10)^10
circuitNoise is a constant whose value depends on the receiver circuitry.
bandwidth is the half-bandwidth of the received signal.

Ni is the sum of the energy of all the other signals being received at
the instant where the SNR is calculated for a given signal.

It is possible to start receiving a signal (this does not mean that it
will really be successfully received) if:
- its energy is higher than the "receiving threshold" which we denote
  by the rxThreshold variable.
- no other signal whose energy is higher than rxThreshold is already
  being received.

-------------------------------------------------------------------------
The Phy layer has two state machines:
- the CCA state machine. The meaning of the CCA states depends on the
  CCA mode which is why it is decoupled from the internal state machine.
  - CCA_IDLE
  - CCA_BUSY
- its internal state machine
  - PHY_RX: if a signal is being received with an energy higher than
    rxThreshold.
  - PHY_TX
  - PHY_IDLE: if no signal is being transmitted or received with an 
    energy higher than rxThreshold.
  - PHY_SLEEP

The MAC layer has one state machine:
- MAC_IDLE
- MAC_SLEEP
- MAC_WAIT_CTS
- MAC_WAIT_ACK
- MAC_FRAGMENT_WAIT_ACK

-------------------------------------------------------------------------

When a packet is received at the phy layer, we:
- if state is PHY_RX or PHY_TX, we put this new packet in the history list.
- otherwise, if state is PHY_SLEEP, we just ignore the packet.
- otherwise, if state is PHY_IDLE, and if the energy of the new packet is 
  lower than the rxThreshold we put it in the history list.
- otherwise, if the state is PHY_IDLE and if its energy is higher
  than rxThreshold,
    - put it in the history list
    - schedule a rxCompleted event at the calculated end of reception 
      of this packet.
    - switch to PHY_RX state.

When a rxCompleted event occurs in the PHY layer, we:
- parse the history list to calculate the maximum total energy
  of all the signals received during the reception of this packet
  (i.e., the maximum Ni)
- use this maximum total energy to calculate a minimum SNIR over
  the reception of this packet.
- use the modulation/encoding scheme of this packet to calculate a drop
  criterion. 
- If the packet must be dropped, it is marked so. 
- We pass it to the MAC layer.
- switch to PHY_IDLE state.

When the MAC layer receives a packet from the PHY, we:
- update the NAV
- if the packet received is an ACK, we:
  - update the status of the previous transmission
  - notify the rate control algorithms
  - cancel the ACKTimeout event
- if the packet received is an ACK but not a fragment ACK, we:
  - start a backoff
- if the packet received is a RTS,
  - schedule a txCTS event for current+SIFS
- if the packet received is a CTS and if we are currently
  handling an RTS/CTS exchange,
  - schedule a txData event for current+SIFS
- if the packet received is a data (or fragment) packet,
  - schedule a txACK event for current+SIFS
  
When the MAC layer receives a txACK event, we:
- send the ACK packet to the PHY, regardless of the IDLE/BUSY status

When the MAC layer receives a txCTS event, we:
- if the state is IDLE (i.e., if the NAV indicates IDLE), 
  send the CTS packet to the PHY.
  
When the PHY receives a packet from the MAC,
- switch to PHY_TX state
- the packet is put in the history list.
- it is sent to the phy layers connected to this phy layer.

When the MAC layer needs to send a data packet to another MAC layer, we:
- parse the history list to calculate:
  - if the current CCA status is IDLE
  - if it is IDLE, how long it has been IDLE
  - if the last packet received was erronous or not.
- if the current CS is not IDLE, and if backoff is zero, we 
  restart a backoff.
- otherwise, if the current CS was not IDLE for longer than the 
  requested IFS (XIFS = EIFS if last packet received erronous, 
  DIFS otherwise), we schedule an event for current+XIFS.
- otherwise, if the backoff timer is zero, and if the packet
  requires RTS/CTS, we send a RTS to the phy layer and
  start a CTSTimeout event.
- otherwise, if the backoff time is zero and if the packet
  does not require an RTS/CTS, we send the packet to the phy layer
  and start an ACKTimeout event.
- otherwise, if the backoff timer is not zero, we schedule an event
  for the end of the backoff timer.
  
When the MAC layer receives a backoff timer event, we:
- parse the phy layer history list to calculate:
  - how long since the start of this backoff timer the
    CS (virtual+phy) was IDLE = CS_BUSY
  - how many times it switched from IDLE to BUSY.
- if the CS_BUSY is not zero, we restart a backoff timer
  to CS_BUSY.
- if the CS_BUSY is zero, the backoff has really expired
  so:
    - if the packet requires RTS/CTS, we send RTS and start a
      CTSTimeout.
    - if the packet does not require RTS/CTS, we send the
      data and start an ACKTimeout.
- we remove from the history list any event which has expired.

When the MAC layer receives an ACKTimeout event, we:
- start a backoff.
- notify the rate control algorithms

When the MAC layer receives a CTSTimeout event, we:
- start a backoff.
- notify the rate control algorithms

When the PHY layer receives a packet to tx, we:
- add an event in its phy event list
- send the packet to the other PHY connected to this PHY.

When the MAC layer receives a GC event, we:
- remove from the history list any event which has expired
  before current-(EIFS+255*aSlotTime).
- schedule another GC event sometime later.

-------------------------------------------------------------------------

Interesting remarks:
--------------------

1) a MAC (low-level) only needs to send a single data packet at
   a time, maybe with small fragments but only one packet/fragment
   is ever sent at a time.

2) the history list maintained by the PHY layer grows upon each event
   deemed necessary. Of course, there need to be a way to remove items
   form the list to make sure it does not grow infinitely.
   There are two events which can remove items from the list:
   - backoff timeout events should be used to remove any event whose
     end time is smaller than the current.
   - a special "garbage collection" event should be regularly scheduled
     to remove any event too old to be useful from the history list.
     This is necessary if the station does not tx any data (which means
     it would not trigger _any_ backoff timeout).

3) rxThreshold is understood to be the minimum signal energy required by 
   the receiver to be able to lock onto a receiving signal.

4) The Phy layer does not need to always update its internal state. It 
   merely need to record every event in its history list and recompute
   its state from the history list whenever needed. Specifically,
   this should avoid a txCompleted event in the PHY layer.

5) This scheme which moves the MAC queue into the MAC object is clearly
   against the ns2 philosophy and way of doing things but it is necessary
   to be able to correctly implement the specification (for example, see
   section 9.9.1.6 paragraph 6 of the 802.11e/D9 spec). This means that:
     - the ns2 input queue do the MAC object will have a size of zero.
     - there will be a need for some elaborate (read: evil) code in the 
       MAC object to obtain the packets and queue them in the MAC-low 
       objects.

6) OAR is available in 802.11e/D9: see section 9.9.1.4

7) To ensure that when the backoff timeout of two ACs (Access Categories)
   expire at the same time, the one with the highest UP (User Priority)
   wins (gains access to the medium), we need to get the MAC-low to ask
   their MAC-high which in turn asks every other MAC-low whether or not
   another backoff timeout is going to expire NOW and if their priority 
   is higher.

8) the wwise proposal for 802.11n does not really change the MAC in 
   fundamental ways. It merely adds frame aggregation which might be 
   a bit tricky to implement but should not require major reworks.

9) the tgnsync proposal for 802.11n changes the MAC in fundamental ways
   which will probably require a complete re-implementation of the 
   MAC-low. It might be possible to save part of the existing MAC-high
   but there is no way to know beforehand. Most notably:
   - pairwise spoofing requires elaborate duration calculations by
     the MAC.
   - LongNAV spoofing also requires elaborate duration calculations
     by the MAC.
   - rate control is fundamentaly different since it is possible to
     create something similar to RBAR.
   - packet agregation
   - ...

10) MCCA should be reasonably easy to implement within an existing 
    802.11e implementation. It looks furiously like the other 802.11n
    proposals though...



-------------------------------------------------------------------------

Open issues:

1) How do we evaluate the rxThreshold ? Should we set a simulation-wide
   constant ? Should this depend on the receiver circuitry ?

2) How do you deal with multi-protocol PHYs ? i.e., 802.11g. It is
   really really hard so I would suggest we support only 802.11a and 
   802.11b. Maybe we can. I don't know now.