Distributed Coordination Function (DCF)
802.11 Distributed Coordination Function is a protocol which uses carrier sensing along with a four way handshake to maximize the throughput while preventing packet collisions.
A packet collision is defined as any case where a node is receiving more than one packet at a time, resulting in neither packet being correctly received.
Essentially, 802.11 is a carrier sensing multiple access with collision avoidance (CSMA/CA) medium access control(MAC) protocol using a direct sequence spread spectrum(DSSS) physical interface.
802.11 DCF Algorithm
The basic functionality of 802.11 is as follows. Assume that a node has data that it needs to transmit. First it will wait a random backoff time. This is a random number of time slots which is within a contention window. If at any time the node senses that another node is using the channel, it will pause its timer until the other node has finished transmitting. When the backoff timer has expired, it will sense the channel to determine if there is another node transmitting. If the channel is clear, it will then wait for a short time and sense the channel again. If the channel is still free, it will transmit a request to send (RTS) to the destination. The destination will response with a clear to send (CTS) if it is available to receive data.
802.11 Distributed Coordination Function (DCF) maximizes throughput while preventing packet collisions. When the source receives the CTS, it will transmit its data. Along with both the RTS and CTS, a network allocation vection (NAV) is transmitted. After correct reception of the data, the destination will transmit an acknowledgment (ACK) back to the sender. At this point, if the sender has more data to transmit, it will again begin its backoff and repeat the process. This process is demonstrated in above figure.
802.11 Carrier Sensing
In 802.11, carrier sensing is the primary method used to avoid collision. Carrier sensing is accomplished by simply measure the amount of energy received on the channel. If that energy is above a threshold, the sensing node determines that another node is currently transmitting and that it must remain silent.
Along with carrier sensing, interframe spacing is primarily to ensure that the channel is truly free. When a node is sensing the channel, it must be free for the length of the DCF interframe spacing (DIFS) period. The short interframe spacing (SIFS) is used as the wait time between the RTS, CTS, DATA and ACK frames. Since the SIFS is always shorter than DIFS, this ensure that another node does NOT incorrectly determine that the channel is idle during the handshake and that priority is given to the transmission in progress.
** Now let us see how a station transmits packets, what is the work flow? **
If a node wants to send a packet:
- Sense the channel whether it is idle. If yes, It wait a DIFS
- Then wait a random backoff time
- If the channel is still free, send the packet
- Continue to wait SIFS, after receive the ACK, release the channel.
** What happens if another node wants to send a packet? **
For example, when Mira also wants to send a packet to Arnold:
- It senses the channel is busy, so it waits until the transmission is finished
- When the channel is idle, it waits a DIFS,
- If it is still idle after DIFS, waits a random backoff time within contention window
- If it is still idle, send the packet
** What happens when collsion occurs? **
- Both Sue and Mira are preparing to send packets to Arnold, they wait a DIFS and a random backoff time.
- Unfortunately, they send packets at the same time because of different start time of DIFS and backoff time. Collsion occurs, but they don't know and they still wait a SIFS. Only Arnold senses the collision, so it doesn't response with ACK.
- When SIFS times out, both Sue and Mira don't receive the ACK, so they wait a random backoff time and retransit again. This time Mira's backoff time is shorter and get the higher priority to send the packet.
802.11 Network Allocation Vector
As an alternative to carrier sensing, the network allocation vector (NAV) is used to inform other nodes how long the current node will need the channel. Any nodes overhearing the NAV knows that they have no need to sensing the channel for the time indicated. Since idle sensing of the channel is the biggest use of the energy in the network, the NAV reduces the amount of idle sensing required at any nodes which can overhear it, thus saving energy at all nodes in the network.
To provide fairness, each node which is transmitting first performs a random countdown, where the length of the countdown is within the length of the contention window. During the countdown, if the node senses that another node is transmitting, it will pause its countdown and continue at that same number after the other transmission is finished. When countdown reaches 0, the node will sense the channel and if the channel is free, transmit the RTS.
The range of values which can be chosen for the random backoff time is referred to as the contention window. The size of the window is very important and can change based on network conditions. If the window is too small, there is an increased chance that two nodes attempt to transmit at the same time. If the window is too large, the nodes may be idle for a long time before transmitting. The window size can increase by a factor of 2 if a transmission fails.
Summary
There are 2 types of carrier sensing as described above: the physical carrier sensing and virtual carrier sensing functions. If either carrier sensing function indicates that the medium is busy, the MAC reports this to higher layers.
Finally, hidden and exposed nodes are a major problem with any carrier sensing based on MAC.
** Hidden note problem **
Station A can communicate with Station B. Station can also communicate with Station B. However, Station A and Station C can't sense each other on the network, because they are out of range of each other. So Station A and Station C may send packets simultaneously to the Station B, then collsion occurs.
** Exposed node problem **
The exposed node problem occurs when a node is prevented from sending packets to other nodes because of a neighboring transmitter. If a transmission between S1 and R1 is taking place, node S2 is prevented from transmitting to R2 as it conculudes after carrier sense that it will interfere with the transmission by its neighbor S1. Howerver node R2 could still receive the transmission of S2 without interference because it is out of range of S1
802.11 CTS/RTS mechanism helps to solve these problems. More details refer to <<How NAV works>>
NOTE: exposed node problem is more difficult, CTS/RTS only solve this problem only if the nodes are synchronized and packet size and data rate are the same for both transmitting nodes. When a node S2 hears an RTS from a neighboring node S1, but no the corresponding CTS, that node can deduce that it is an exposed node and is permitted to transmit to other neighboring node R2.
