02-02-2010, 03:31 PM
[attachment=1680]
Performance Analysis of CSMA/CA protocol in IEEE 802.11 Networks using Backoff mechanism
Abstract: The distributed coordination function (DCF) in the IEEE 802.11 standard for wireless LAN is based on the Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) like medium access control protocol. This collision avoidance is implemented by means of backoff procedure which uses a rotating window mechanism. This paper presents a simulation analysis of the slot selection probabilities and the backoff mechanism. The obtained simulations allow us to determine the effective throughput versus offered load for different values of the contention window parameter and the number of the contending stations. The choice of CWmin and CWmax parameters were analyzed.
Submitted by
Amith M.N, M.Tech (DCN),
Department of Electronics and Communications,
University B D T College of Engineering, Davanagere, Karnataka, India.
1. Introduction
With the spread of high performance portable computers, data terminals, and devices such as personal digital assistants, Wireless LANs (WLANs) have become an emerging technology for today™s computer and communication industries. They will pay their part in the network architecture as a provider for easy and unconstrained access to the wired infrastructure “ an extension of the wired network with a wireless last link to attach the large number of mobile data communication terminals. WLANs are also increasingly being used in the hospitals and university environments in which users are high mobile and may only require moderate bandwidths. WLANs have also been used in environments where cable installation is expensive or impractical. Two organizations have been involved in standardizing the physical layer and the medium access control for WLANs, namely IEEE 802.11 wireless LAN and ETSI HIPERLAN. In this paper we are considering only the IEEE 802.11 MAC (Medium Access Control) layer.
The backoff mechanism has intensively been studied in the literature since the beginning of 70â„¢s. The idea of using the backoff mechanism in the MAC layer of the IEEE 802.11 standard has brought a new interest in such a mechanism. The proper selection of backoff parameters is an essential issue for the network performance. For example, the problem of unequal slot selection probabilities was considered in [3]. Two modified backoff schemes, namely weighted selection probabilities and load adaptive selection were proposed with an increase in the throughput performance and the decrease in the average access delay.
2. IEEE 802.11 MAC
The IEEE 802.1 1 standard covers the MAC (Medium Access Control) sub-layer and the physical layer of the OS1 (Open System Interconnection) reference model. In this paper, we only focus on the MAC part. IEEE 802.1l standard supports two services: Distributed Coordination Function(DCF) and Point Coordination Function (PCF). The IEEE 802.11 MAC architecture [3] can be briefly described as in figure 1.
Figure 1 IEEE 802.11 MAC architecture
Distributed Coordination Function (DCF), is particularly made for asynchronous data traffic, where all users with data to transmit have an equally fair chance of accessing the network. The Point Coordination function (PCF) is a second MAC service. The PCF is based on Polling that is controlled by an access point (AP). The PCF is primarily designed for the transmission of delay-sensitive traffic. In this paper we consider the DCF MAC scheme with Carrier Sense Medium Access with Collision Avoidance (CSMA/CA) protocol as the medium access protocol.
3. Basic Access Method: DCF
The Basic access method in the 802.11 standard is Distributed Coordination Function (DCF) which is essentially Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). In CSMA, a node with a packet to transmit first senses the medium to detect any on going transmission. If the medium is busy (i.e some other node is transmitting), the node differs its transmission to later time. If the medium is sensed to be free for duration greater than the DCF interframe space (DIFS) interval, the packet is transmitted immediately. The sending station will recognize a successful transmission by means of an acknowledgement (ACK) packet from the receiving station. The receiving station, on successful reception of packet delivers an ACK packet to source station after short inter frame space interval (SIFS). All stations except the source station in the BSS use the duration field of the data packet to adjust their Network Allocation Vector (NAV), which indicates the amount of the time that must elapse until the end of the current transmission, for deferring access to the medium. CSMA is very effective when the medium is lightly loaded since the protocol allows nodes to transmit with minimum delay. Due to finite propagation delay along the transmission medium, there is a probability of two or more nodes simultaneously sensing the medium as being free and transmitting at the same time, thereby causing a collision. Clearly, when the network is heavily loaded, such collisions will occur often [3], [4].
The CSMA protocol incorporates a Collision Avoidance (CA) scheme that introduces a random interframe space which we call as backoff between successive packet transmissions. Collision avoidance part is performed to reduce the high probability of collision immediately after a successful packet transmission. If the medium is detected to be busy, the node must first delay until the end of the DIFS interval and further wait for a random number of time slots i.e the backoff interval, before attempting transmission. The backoff mechanism is explained in detail in the later sections.
In wireless scenario, it cannot be guaranteed that all station will be able to listen to each other. Thus some station will be hidden to other simply because they are out of the range of this station. Carrier sensing is difficult due to the hidden terminal scenario where collisions can not be securely detected at the sending stations. The DCF protocol is enhanced further by provision of a virtual CS indication called Net Allocation Vector (NAV) which is based on duration information transferred in special RTS/CTS frames before the data exchange [5]. It allows stations to avoid transmission in time intervals in which the medium is surely busy.
4. Exponential backoff mechanism
IEEE 802.11 backoff mechanism follows rotating window mechanism for the backoff procedure as follows: whenever a station gets ready with a packet for transmission and senses the medium busy it has to choose a random number between (0,CW) (CW: Contention Window) and wait for this number of slots before accessing the medium. Contention window is the range of slots within which a station selects random slots during backoff process. For every station, for a new packet, the value of contention window will be equal to minimum value: CWmin, and it will increase exponentially as it experiences collision until a maximum value: CWmax, and sets back CWmin on every successful transmission [2].
At each backoff time slot, carrier sensing is performed to determine if there is any activity on the medium. The station that selected the short random time will gain access for transmission, the others freeze their backoff timers until the winning stationâ„¢s transmission is finished and wait for the remaining time in the following cycle. In this case, when the medium becomes idle again for a period greater then the DIFS, the backoff procedure continues decrementing from the time slot which was previously disrupted. Hence a packet that was delayed while performing the backoff procedure has a high probability of being transmitted earlier than a newly arrived packet. The process is repeated until the backoff interval reaches zero and once it reaches zero the packet is transmitted immediately. That way station that has been waiting for long to gain access is more likely to win this competition than another that just entered it. The probability of gaining access to medium increases with the time waited. If two or more stations complete there backoff procedure at the same time, or else if the stations select the same slot then collision will occur.
When retransmission is necessary, the backoff interval increases exponentially up to a certain threshold. Conversely, the backoff interval reduces to minimum value when packets are transmitted successfully. Now, each station will have to increase its CW exponentially (until the maximum CWmax) and then select again a new random slot between 0 and CW. For every retransmission attempt, the backoff time grows as a function of 2i where i is the number of collision encountered. And whenever there is a successful transmission for a station its contention window is brought back to minimum CW value-CWmin. The effect of this procedure is that when multiple stations are deferring and go into random backoff, then the station selecting the smallest backoff time slot will win the contention [2]. The situation is best presented in the figure 2.
Figure 2. Backoff Mechanism
We shall now discuss about the slot selection probabilities of the backoff mechanism. Considering the initial state it appears that each slot is selected with the same probability. In the next cycle all stations that competed for access reduce the backoff times. The new value is reduced by the time that elapsed until the wining station started its transmission. Within this reduced contention window all slots are selected with the same probability by the remaining stations. So, if a new station enters the competition or stations that collided in the previous cycle return back into it, they will choose slots within the whole range of contention window with the same probability [3]. Assuming a situation in a wireless LAN under high load, i.e. there are always stations left in the competition as well as there are always stations entering the competition, and in an equilibrium state, we see that slots positioned early in the contention window have a much higher probability to be chosen.
Figure 3. Slot selection probability in equilibrium state.
The result is a decreasing staircase function for the slot selection probability as shown in Figure 3.
5. Simulation Results
In order to reduce the complexity of the wireless LAN scenario, some assumptions are made in the simulation of wireless LAN model. They are as follows:
¢ All network nodes are assumed to be in Radio contact with each other. Hence the simulation will not consider the hidden node problem.
¢ The channel is assumed to be ideal with no transmission errors.
¢ The propagation delay between the transmissions is neglected,
¢ It is assumed that a transmitted MAC protocol data unit (MPDU) will immediately be received by the destination station without being buffered.
¢ All stations are assumed to be symmetric users.
¢ Packets are assumed to be of fixed length.
In the simulation the wireless LAN was first simulated with Distributed Coordination Function access scheme using the CSMA/CA protocol. The gathered simulation results allow us to determine the slot selection probabilities in the equilibrium state and the throughput analysis versus offered load for different CW parameters. The next group of simulation results presents the realized throughput versus the number of stations for different values of the CW parameters. The last group of simulations allows us to determine the optimal value of CWmin in dependence of the number of contending stations.
The result plot in figure 4 presents slot selection probability at the equilibrium state obtained for 25 stations with CWmin = 32 and CWmax = 256. The newly entering stations select the slots under 0 and CWmin and the collided stations will have their window size exponentially increasing until it reach the CWmax.
Figure 4 Slot selection probability at the equilibrium state obtained for 25 stations.
By the analysis of this result we can infer that as the system reaches equilibrium state the higher numbered slots are selected with lower probability and the low numbered slots are selected with higher probability leading to increase in the number of collisions.
The analysis of the different backoff parameters with respect to the window size is presented in the figures 5, 6 and 7.
¢ The realized throughput for different number of stations versus offered load for four different values of CWmin and CWmax.
¢ The realized throughput versus the number of stations for different values of CWmin and CWmax
¢ The realized throughput versus CWmin with CWmax = 8* CWmin for 25, 100 stations
Figure 5. Throughput versus load for 25 stations
Figure 6. Throughput versus load for 100 stations
Figure 7. Throughput versus number of stations
The results obtained for 25 contending stations are presented in figure 5. Almost best results are obtained for the CWmin =128 with CWmax = 1024 and CWmin = 512 with CWmax = 4096. A small decrease in the throughput is found for CWmin = 32 and CWmax = 256. The performance of the system is heavily degraded for CWmin = 8 and CWmax = 64 with a steep decrease in the throughput under heavily loaded conditions. As the window size decreases and the number of participating stations increases the number of collisions increases and the performance of the system degrades under high load conditions. The results obtained for the 100 participating stations are shown in the figure 6 with best results obtained for CWmin = 512 and CWmax = 4096. A very small degradation in performance brings the choice of CWmin = 128 and CWmax = 1024 parameters. In all other parameters we obtain degradation in the performance.
Before concluding it is better we consider the dependency between the number of stations and the throughput for different values of CWmin and CWmax. The obtained result is as shown in figure 7. By these plots we can infer that it is better to select less value of CWmin for less number of stations and must select large number of CWmin parameters for large number of participating stations.
6. Conclusions.
The numerical results reported in this paper clearly show that the CSMA/CA basic protocol suffers of several performance drawbacks. DCF is the fundamental access method with CSMA/CA protocol used to support the asynchronous data transmission. To avoid the collisions the random backoff mechanism is employed. The slot selection probability obtained is the decreasing exponential in nature from which we can conclude that due to this characteristic of slot selection the number of collisions increases.
The analysis of the backoff parameters led to some important conclusions presented below:
¢ Using too small values of CWmin at large number of stations bring large collisions and degrades the network performance.
¢ Using too large CWmin at small number of stations degrades the performance due to wastage of bandwidth.
Hence the choice of the CWmin is dependent on the number of participating stations.
My work is still continuing for the final summary of all the carried simulations. i.e The dependencies between throughput, CWmin size and number of stations are to be presented.
7. References
[1] Bharghavan V., Demers A., Shenker S., Zhang L., MACAW: A Media Access Protocol for Wireless LANâ„¢s, ACM Sigcomm 1994.
[2] Marek Natkaniec and Andrzej R. Pach, An Analysis of the Backoff Mechanism used in IEEE 802.11 Networks, IEEE: 2000.
[3] Woesner H., Weinmiller J., Wolisz A., Modified Backoff Algorithms for DFWMAC DCF, IEEE 802.11 Working Group paper: JULY 1995
[4] G.bianchi, L. Fratta, Performance evaluation and enhancement of the CSMA/CA MAC protocol for 802.11 Wireless LANs, IEEE 1996
[5] Woesner H., Weinmiller J., Wolisz A., Analysing the RTS/CTS mechanism in the DFWMAC media access protocol for Wireless LANs.
Performance Analysis of CSMA/CA protocol in IEEE 802.11 Networks using Backoff mechanism
Abstract: The distributed coordination function (DCF) in the IEEE 802.11 standard for wireless LAN is based on the Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) like medium access control protocol. This collision avoidance is implemented by means of backoff procedure which uses a rotating window mechanism. This paper presents a simulation analysis of the slot selection probabilities and the backoff mechanism. The obtained simulations allow us to determine the effective throughput versus offered load for different values of the contention window parameter and the number of the contending stations. The choice of CWmin and CWmax parameters were analyzed.
Submitted by
Amith M.N, M.Tech (DCN),
Department of Electronics and Communications,
University B D T College of Engineering, Davanagere, Karnataka, India.
1. Introduction
With the spread of high performance portable computers, data terminals, and devices such as personal digital assistants, Wireless LANs (WLANs) have become an emerging technology for today™s computer and communication industries. They will pay their part in the network architecture as a provider for easy and unconstrained access to the wired infrastructure “ an extension of the wired network with a wireless last link to attach the large number of mobile data communication terminals. WLANs are also increasingly being used in the hospitals and university environments in which users are high mobile and may only require moderate bandwidths. WLANs have also been used in environments where cable installation is expensive or impractical. Two organizations have been involved in standardizing the physical layer and the medium access control for WLANs, namely IEEE 802.11 wireless LAN and ETSI HIPERLAN. In this paper we are considering only the IEEE 802.11 MAC (Medium Access Control) layer.
The backoff mechanism has intensively been studied in the literature since the beginning of 70â„¢s. The idea of using the backoff mechanism in the MAC layer of the IEEE 802.11 standard has brought a new interest in such a mechanism. The proper selection of backoff parameters is an essential issue for the network performance. For example, the problem of unequal slot selection probabilities was considered in [3]. Two modified backoff schemes, namely weighted selection probabilities and load adaptive selection were proposed with an increase in the throughput performance and the decrease in the average access delay.
2. IEEE 802.11 MAC
The IEEE 802.1 1 standard covers the MAC (Medium Access Control) sub-layer and the physical layer of the OS1 (Open System Interconnection) reference model. In this paper, we only focus on the MAC part. IEEE 802.1l standard supports two services: Distributed Coordination Function(DCF) and Point Coordination Function (PCF). The IEEE 802.11 MAC architecture [3] can be briefly described as in figure 1.
Figure 1 IEEE 802.11 MAC architecture
Distributed Coordination Function (DCF), is particularly made for asynchronous data traffic, where all users with data to transmit have an equally fair chance of accessing the network. The Point Coordination function (PCF) is a second MAC service. The PCF is based on Polling that is controlled by an access point (AP). The PCF is primarily designed for the transmission of delay-sensitive traffic. In this paper we consider the DCF MAC scheme with Carrier Sense Medium Access with Collision Avoidance (CSMA/CA) protocol as the medium access protocol.
3. Basic Access Method: DCF
The Basic access method in the 802.11 standard is Distributed Coordination Function (DCF) which is essentially Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). In CSMA, a node with a packet to transmit first senses the medium to detect any on going transmission. If the medium is busy (i.e some other node is transmitting), the node differs its transmission to later time. If the medium is sensed to be free for duration greater than the DCF interframe space (DIFS) interval, the packet is transmitted immediately. The sending station will recognize a successful transmission by means of an acknowledgement (ACK) packet from the receiving station. The receiving station, on successful reception of packet delivers an ACK packet to source station after short inter frame space interval (SIFS). All stations except the source station in the BSS use the duration field of the data packet to adjust their Network Allocation Vector (NAV), which indicates the amount of the time that must elapse until the end of the current transmission, for deferring access to the medium. CSMA is very effective when the medium is lightly loaded since the protocol allows nodes to transmit with minimum delay. Due to finite propagation delay along the transmission medium, there is a probability of two or more nodes simultaneously sensing the medium as being free and transmitting at the same time, thereby causing a collision. Clearly, when the network is heavily loaded, such collisions will occur often [3], [4].
The CSMA protocol incorporates a Collision Avoidance (CA) scheme that introduces a random interframe space which we call as backoff between successive packet transmissions. Collision avoidance part is performed to reduce the high probability of collision immediately after a successful packet transmission. If the medium is detected to be busy, the node must first delay until the end of the DIFS interval and further wait for a random number of time slots i.e the backoff interval, before attempting transmission. The backoff mechanism is explained in detail in the later sections.
In wireless scenario, it cannot be guaranteed that all station will be able to listen to each other. Thus some station will be hidden to other simply because they are out of the range of this station. Carrier sensing is difficult due to the hidden terminal scenario where collisions can not be securely detected at the sending stations. The DCF protocol is enhanced further by provision of a virtual CS indication called Net Allocation Vector (NAV) which is based on duration information transferred in special RTS/CTS frames before the data exchange [5]. It allows stations to avoid transmission in time intervals in which the medium is surely busy.
4. Exponential backoff mechanism
IEEE 802.11 backoff mechanism follows rotating window mechanism for the backoff procedure as follows: whenever a station gets ready with a packet for transmission and senses the medium busy it has to choose a random number between (0,CW) (CW: Contention Window) and wait for this number of slots before accessing the medium. Contention window is the range of slots within which a station selects random slots during backoff process. For every station, for a new packet, the value of contention window will be equal to minimum value: CWmin, and it will increase exponentially as it experiences collision until a maximum value: CWmax, and sets back CWmin on every successful transmission [2].
At each backoff time slot, carrier sensing is performed to determine if there is any activity on the medium. The station that selected the short random time will gain access for transmission, the others freeze their backoff timers until the winning stationâ„¢s transmission is finished and wait for the remaining time in the following cycle. In this case, when the medium becomes idle again for a period greater then the DIFS, the backoff procedure continues decrementing from the time slot which was previously disrupted. Hence a packet that was delayed while performing the backoff procedure has a high probability of being transmitted earlier than a newly arrived packet. The process is repeated until the backoff interval reaches zero and once it reaches zero the packet is transmitted immediately. That way station that has been waiting for long to gain access is more likely to win this competition than another that just entered it. The probability of gaining access to medium increases with the time waited. If two or more stations complete there backoff procedure at the same time, or else if the stations select the same slot then collision will occur.
When retransmission is necessary, the backoff interval increases exponentially up to a certain threshold. Conversely, the backoff interval reduces to minimum value when packets are transmitted successfully. Now, each station will have to increase its CW exponentially (until the maximum CWmax) and then select again a new random slot between 0 and CW. For every retransmission attempt, the backoff time grows as a function of 2i where i is the number of collision encountered. And whenever there is a successful transmission for a station its contention window is brought back to minimum CW value-CWmin. The effect of this procedure is that when multiple stations are deferring and go into random backoff, then the station selecting the smallest backoff time slot will win the contention [2]. The situation is best presented in the figure 2.
Figure 2. Backoff Mechanism
We shall now discuss about the slot selection probabilities of the backoff mechanism. Considering the initial state it appears that each slot is selected with the same probability. In the next cycle all stations that competed for access reduce the backoff times. The new value is reduced by the time that elapsed until the wining station started its transmission. Within this reduced contention window all slots are selected with the same probability by the remaining stations. So, if a new station enters the competition or stations that collided in the previous cycle return back into it, they will choose slots within the whole range of contention window with the same probability [3]. Assuming a situation in a wireless LAN under high load, i.e. there are always stations left in the competition as well as there are always stations entering the competition, and in an equilibrium state, we see that slots positioned early in the contention window have a much higher probability to be chosen.
Figure 3. Slot selection probability in equilibrium state.
The result is a decreasing staircase function for the slot selection probability as shown in Figure 3.
5. Simulation Results
In order to reduce the complexity of the wireless LAN scenario, some assumptions are made in the simulation of wireless LAN model. They are as follows:
¢ All network nodes are assumed to be in Radio contact with each other. Hence the simulation will not consider the hidden node problem.
¢ The channel is assumed to be ideal with no transmission errors.
¢ The propagation delay between the transmissions is neglected,
¢ It is assumed that a transmitted MAC protocol data unit (MPDU) will immediately be received by the destination station without being buffered.
¢ All stations are assumed to be symmetric users.
¢ Packets are assumed to be of fixed length.
In the simulation the wireless LAN was first simulated with Distributed Coordination Function access scheme using the CSMA/CA protocol. The gathered simulation results allow us to determine the slot selection probabilities in the equilibrium state and the throughput analysis versus offered load for different CW parameters. The next group of simulation results presents the realized throughput versus the number of stations for different values of the CW parameters. The last group of simulations allows us to determine the optimal value of CWmin in dependence of the number of contending stations.
The result plot in figure 4 presents slot selection probability at the equilibrium state obtained for 25 stations with CWmin = 32 and CWmax = 256. The newly entering stations select the slots under 0 and CWmin and the collided stations will have their window size exponentially increasing until it reach the CWmax.
Figure 4 Slot selection probability at the equilibrium state obtained for 25 stations.
By the analysis of this result we can infer that as the system reaches equilibrium state the higher numbered slots are selected with lower probability and the low numbered slots are selected with higher probability leading to increase in the number of collisions.
The analysis of the different backoff parameters with respect to the window size is presented in the figures 5, 6 and 7.
¢ The realized throughput for different number of stations versus offered load for four different values of CWmin and CWmax.
¢ The realized throughput versus the number of stations for different values of CWmin and CWmax
¢ The realized throughput versus CWmin with CWmax = 8* CWmin for 25, 100 stations
Figure 5. Throughput versus load for 25 stations
Figure 6. Throughput versus load for 100 stations
Figure 7. Throughput versus number of stations
The results obtained for 25 contending stations are presented in figure 5. Almost best results are obtained for the CWmin =128 with CWmax = 1024 and CWmin = 512 with CWmax = 4096. A small decrease in the throughput is found for CWmin = 32 and CWmax = 256. The performance of the system is heavily degraded for CWmin = 8 and CWmax = 64 with a steep decrease in the throughput under heavily loaded conditions. As the window size decreases and the number of participating stations increases the number of collisions increases and the performance of the system degrades under high load conditions. The results obtained for the 100 participating stations are shown in the figure 6 with best results obtained for CWmin = 512 and CWmax = 4096. A very small degradation in performance brings the choice of CWmin = 128 and CWmax = 1024 parameters. In all other parameters we obtain degradation in the performance.
Before concluding it is better we consider the dependency between the number of stations and the throughput for different values of CWmin and CWmax. The obtained result is as shown in figure 7. By these plots we can infer that it is better to select less value of CWmin for less number of stations and must select large number of CWmin parameters for large number of participating stations.
6. Conclusions.
The numerical results reported in this paper clearly show that the CSMA/CA basic protocol suffers of several performance drawbacks. DCF is the fundamental access method with CSMA/CA protocol used to support the asynchronous data transmission. To avoid the collisions the random backoff mechanism is employed. The slot selection probability obtained is the decreasing exponential in nature from which we can conclude that due to this characteristic of slot selection the number of collisions increases.
The analysis of the backoff parameters led to some important conclusions presented below:
¢ Using too small values of CWmin at large number of stations bring large collisions and degrades the network performance.
¢ Using too large CWmin at small number of stations degrades the performance due to wastage of bandwidth.
Hence the choice of the CWmin is dependent on the number of participating stations.
My work is still continuing for the final summary of all the carried simulations. i.e The dependencies between throughput, CWmin size and number of stations are to be presented.
7. References
[1] Bharghavan V., Demers A., Shenker S., Zhang L., MACAW: A Media Access Protocol for Wireless LANâ„¢s, ACM Sigcomm 1994.
[2] Marek Natkaniec and Andrzej R. Pach, An Analysis of the Backoff Mechanism used in IEEE 802.11 Networks, IEEE: 2000.
[3] Woesner H., Weinmiller J., Wolisz A., Modified Backoff Algorithms for DFWMAC DCF, IEEE 802.11 Working Group paper: JULY 1995
[4] G.bianchi, L. Fratta, Performance evaluation and enhancement of the CSMA/CA MAC protocol for 802.11 Wireless LANs, IEEE 1996
[5] Woesner H., Weinmiller J., Wolisz A., Analysing the RTS/CTS mechanism in the DFWMAC media access protocol for Wireless LANs.