当前位置: 首页 > >

Quality of Service schemes for IEEE 802.11

发布时间:

Quality of Service Schemes for IEEE 802.11
A Simulation Study
Anders Lindgren, Andreas Almquist, and Olov Schelén
Division of Computer Science and Communications Department of Computer Science and Electrical Engineering Lule? University of Technology, SE - 971 97 Lule?, Sweden {Anders.Lindgren, Andreas.Almquist, Olov.Schelen}@sm.luth.se

Abstract. This paper analyzes and compares four different mechanisms for providing QoS in IEEE 802.11 wireless LANs. We have evaluated the IEEE 802.11 mode for service differentiation (PCF), Distributed Fair Scheduling, Blackburst, and a scheme proposed by Deng et al. using the ns-2 simulator. The evaluation covers medium utilization, access delay, and the ability to support a large number of high priority mobile stations. Our simulations show that PCF performs badly, and that Blackburst has the best performance with regard to the above metrics. An advantage with the Deng scheme and Distributed Fair Scheduling is that they are less constrained, with regard to the characteristics of high priority traf?c, than Blackburst is.

1 Introduction
As usage and deployment of wireless Local Area Networks (WLANs) increases, it is reasonable to expect that the demands to be able to run real-time applications will be the same as on wired networks. Given the relatively low bandwidth in these networks, the introduction of Quality of Service is indispensable. The IEEE 802.11 standard [6] for WLANs is the most widely used WLAN standard today. It contains a mode for service differentiation, but that has been shown to perform badly and give poor link utilization [8]. We study and evaluate four schemes for providing QoS over IEEE 802.11 wireless LANs, the PCF mode of the IEEE 802.11 standard [6], Distributed Fair Scheduling [7], Blackburst [4], and a scheme proposed by Deng et al. [1]. 1.1 IEEE 802.11 IEEE 802.11 has two different access methods, the mandatory Distributed Coordinator Function (DCF) and the optional Point Coordinator Function (PCF). The latter aims at supporting real-time traf?c. Distributed Coordinator Function The Distributed Coordinator Function is the basic access mechanism of IEEE 802.11. It uses a Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) algorithm to mediate access to the shared medium [6].

Before sending a frame, the medium is sensed, and if it is idle for at least a DCF interframe space (DIFS), the frame is transmitted. Otherwise, a backoff time B (measured in time slots) is chosen randomly in the interval [0,CW ), where CW is the Contention Window. Whenever the medium has been idle for at least a DIFS, the backoff timer is decremented with one each time slot the medium remains idle. When the backoff timer reaches zero, the frame is transmitted. If a collision is detected (which is done by the use of a positive acknowledgment scheme), the contention window is doubled and a new backoff time is chosen. The backoff mechanism is also used after a successful transmission before sending the next frame. After a successful transmission, the contention window is reset to its start value, CWmin . Point Coordinator Function PCF is a centralized, polling-based access mechanism which requires the presence of a base station that acts as Point Coordinator (PC). If PCF is to be used, time is divided into superframes where each superframe consists of a contention period where DCF is used, and a contention-free period (CFP) where PCF is used. The CFP is started by a beacon frame sent by the base station, using the ordinary DCF access method. Therefore, the CFP may be shortened since the base station has to contend for the medium. During the CFP, the PC polls each station in its polling list (the high priority stations), when they are clear to access the medium. To ensure that no DCF stations are able to interrupt this mode of operation, the interframe space (IFS) between PCF data frames is shorter than the usual IFS (DIFS). This time is called a PCF interframe space (PIFS). To prevent starvation of stations that are not allowed to send during the CFP, there must always be room for at least one maximum length frame to be sent during the contention period. 1.2 DENG Deng and Chang proposes a method (which we call the DENG scheme) for service differentiation with minimal modi?cations of the IEEE 802.11 standard [1]. It uses two properties of IEEE 802.11 to provide differentiation: the interframe space (IFS) used between data frames, and the backoff mechanism. If two stations use different IFS, a station with shorter IFS will get higher priority than a station with a longer IFS. To further extend the number of available classes, different backoff algorithms are used depending on the priority class. Table 1 shows the four de?ned priority classes [1].
Table 1. DENG priority classes. Combining backoff algorithms and IFS gives priorities 0-3. ρ is a random variable in the interval (0, 1), and i means the ith backoff procedure for this frame. Priority IFS 0 1 2 3 Backoff algorithm
22+i 2

DIFS B = DIFS

B = ρ × 22
22+i 2

+ ρ × 22
2+i

2+i

PIFS B = PIFS

B = ρ × 22

+ ρ × 22
2+i

2+i

1.3

Distributed Fair Scheduling

In [7] an access scheme called Distributed Fair Scheduling (DFS) which utilizes the ideas behind fair1 queuing [2] in the wireless domain is presented. It uses the backoff mechanism of IEEE 802.11 to determine which station should send ?rst. Before transmitting a frame, the backoff process is always initiated. The backoff interval calculated is proportional to the size of the packet to send and inversely proportional to the weight of the ?ow. This causes stations with low weights to generate longer backoff intervals than those with high weights, thus getting lower priority. Fairness is achieved by including the packet size in the calculation of the backoff interval, causing ?ows with smaller packets to get to send more often. This gives ?ows with equal weights the same bandwidth regardless of the packet sizes used. If a collision occurs, a new backoff interval is calculated using the backoff algorithm of the IEEE 802.11 standard. 1.4 Blackburst

The main goal of Blackburst [4, 5] is to minimize the delay for real-time traf?c. Unlike the other schemes it imposes certain requirements on the high priority stations. Blackburst requires: 1) all high priority stations try to access the medium with equal, constant intervals, tsch ; and 2) the ability to jam the medium for a period of time. When a high priority station wants to send a frame, it senses the medium to see if it has been idle for a PIFS and then sends its frame. If the medium is busy, the station waits for the medium to be idle for a PIFS and then enters a black burst contention period. The station now sends a so called black burst to jam the channel. The length of the black burst is determined by the time the station has waited to access the medium, and is calculated as a number of black slots. After transmitting the black burst, the station listens to the medium for a short period of time (less than a black slot) to see if some other station is sending a longer black burst which would imply that the other station has waited longer and thus should access the medium ?rst. If the medium is idle, the station will send its frame, otherwise it will wait until the medium becomes idle again and enter another black burst contention period. By using slotted time, and imposing a minimum frame size on real time frames, it can be guaranteed that each black burst contention period will yield a unique winner [4]. After the successful transmission of a frame, the station schedules the next transmission attempt tsch seconds in the future. This has the nice effect that real-time ?ows will synchronize, and share the medium in a TDM fashion [4]. This means that unless some low priority traf?c comes and disturbs the order, very little blackbursting will have to be done once the stations have synchronized. Low priority stations use the ordinary CSMA/CA access method of IEEE 802.11.

2 Evaluation
2.1 Simulation setup To evaluate the above described methods described, we used the network simulator ns2 [3] which already has IEEE 802.11 DCF functionality. We extended the simulator with
1

Fair in the sense that each ?ow is allocated bandwidth proportional to some weight.

implementations of IEEE 802.11 PCF and the other schemes, and ran the simulation scenarios described below to measure three different metrics: throughput, access delay and maximum number of high priority stations. Scenarios Our simulation topology consisted of several wireless stations and one base station (connected to a wired node which serves as a sink for the ?ows from the wireless domain) in the wireless LAN. The traf?c in our simulations was generated by each station generating constant bit rate ?ows to the sink. We always used 230 byte frames (including IP and UDP headers), but varied the inter-frame interval between the simulations to vary the offered load, calculated as shown in (1). (1) cbitrate Each point in our plots is an average over ten simulation runs, and the error bars indicate the 95% con?dence interval. In the delay and throughput comparison simulations, we had 20 wireless stations and varied the fraction of high priority stations. When we investigated the maximum number of high priority stations we used a variable number of stations. Metrics The metrics we have used are throughput, access delay, and maximum number of high priority stations. To be able to see the differentiation and medium utilization of the schemes, we have looked at both the average throughput for the stations at each priority level, and the total throughput for all stations together. To compare the graphs from different levels of load, we plot a normalized throughput on the y axis which is calculated as the fraction of the offered data actually delivered to the destination. To determine to what extent the schemes were able to provide good service to high priority traf?c, we ran simulations where the stations sent 65.7 kbit/s streams. We ?xed the low priority traf?c load at certain levels, and gradually increased the number of high priority stations to see how many simultaneous high priority stations that could get good service. We used two de?nitions of good service. The ?rst considers throughput, and requires that 95% of the offered data is delivered, while the second requires access delay to be below 20 ms. Method speci?c details Table 2 shows the parameter values used in our simulations. For further explanation and description of the parameters, we refer to [1, 4, 6, 7].
Table 2. Parameter values used in our simulations
Parameter Value Parameter Value Parameter Value Parameter DIFS 50 ?s Time slot 20 ?s Deng high prio 3 DFS high weight PIFS 30 ?s cbitrate 2 Mbit/s Deng low prio 1 DFS low weight size pkt 230 bytes Deng DIFS 100 ?s DFS Scaling_Factor Superframe 110 TU 2 CWmin 31 Black slot 20 ?s Max CFP 108.85 TU
2

load =

pkt nstations · interval pkt

size

Value 0.075 0.025 0.02

1 TU = 1024 ?s

When using PCF, during a CFP the Point Coordinator (the base station) polls the stations in its polling list in a round robin fashion. If all stations have been polled once, the CFP will be ended prematurely. If there is not enough time to poll all stations the next station in the list will be polled ?rst in the next CFP. To enhance the performance of DFS when there is much low priority traf?c, we decided to use exponential mapping [7] of the backoff intervals. 2.2 Results

Our initial simulations compared the performance of the different schemes with regard to throughput. The simulations show that even at low loads, PCF gives low priority ?ows signi?cantly lower throughput than the other schemes do. The PCF high priority stations perform acceptable at this low load, but the performance for these starts to deteriorate when the amount of high priority traf?c increases. Fig. 1 shows how well the different schemes provides service differentiation with regard to throughput, and Fig. 2 shows the total throughput, which indicates how well the different schemes utilizes the medium. We have run simulations with several levels of load but because of space limitations we only present the most interesting graphs here.
Offered load 0.46 1 1 Offered load 0.657

Normalized throughput

0.6 PCF High PCF Low DENG High DENG Low DFS High DFS Low BB High BB Low 0 0.2 0.4 0.6 Fraction high priority nodes 0.8 1

Normalized throughput
?

0.8

0.8

0.6 PCF High PCF Low DENG High DENG Low DFS High DFS Low BB High BB Low 0 0.2 0.4 0.6 Fraction high priority nodes 0.8 1

Normalized throughput

0.6

Normalized throughput

0.4

0.2

0 0

PCF Total DENG Total DFS Total BB Total 0.2 0.4 0.6 Fraction high priority nodes 0.8 1

Fig. 2. Total throughput for the QoS schemes.

As we increased the load in our simulations (see Fig. 1, the right graph), none of the schemes were capable of delivering all data of the high priority stations when there are only high priority stations in the system. Blackburst gives the best performance both for high and low priority traf?c. This also implies that Blackburst has the best medium utilization, veri?ed in Fig. 2.

?

? ?

0.4

0.4

0.2

0.2

0

0

Fig. 1. Average throughput for a station at the given priority level.
Offered load 0.460 1 1 Offered load 0.657

0.8

0.8

0.6

0.4

0.2

0 0

PCF Total DENG Total DFS Total BB Total 0.2 0.4 0.6 Fraction high priority nodes 0.8 1

An interesting observation is that the throughput for low priority traf?c cases increases slightly for PCF and DENG when there is only one low priority station. Our hypothesis about this is that all high priority stations will send their frames in what appears to the low priority stations as a big “chunk” (not letting any low priority traf?c get in between their frames). After that, all high priority stations will start decrementing their backoff timers, not contending for the medium. During this time, low priority stations can access the medium. When there is only one low priority station, it will get to send, without contending with some other low priority station. A similar phenomenon occurs for Blackburst.
Offered load 0.541 0.2 PCF High PCF Low DENG High DENG Low DFS High DFS Low BB High BB Low 0.2 PCF High PCF Low DENG High DENG Low DFS High DFS Low BB High BB Low Offered load 0.657

0.15 Access delay (s)

0.15 Access delay (s) 0.4 0.6 Fraction high priority nodes 0.8 1
?

0.1

0.1

When investigating the second metric, access delay, we found that Blackburst and Deng performs well for high priority traf?c. Blackburst also gives low access delay to low priority traf?c as long as the load is relatively low, but it should be noted that when the network becomes heavily loaded Blackburst totally starves low priority traf?c. As shown in Fig. 3 one can see that the access delay increases as the fraction of high priority traf?c increases for all schemes.
Throughput bounded 20 20 Access delay bounded

Max #high prio stations

5 PCF DENG DFS BB 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 Offered low priority load 0.8 0.9 1

0

Fig. 4. Maximum number of high priority stations with good performance.

The investigation of the third metric, maximum number of high priority stations, indicates that Blackburst is the scheme capable of supporting the largest number of prioritized stations both with regard to throughput and access delay. As Fig. 4 shows, both Blackburst and DENG are able to give the high priority stations good service, regardless of the amount of low priority traf?c. The reason why DFS doesn’t perform that well is due to the fact that DFS tries to distribute the bandwidth fairly among the stations according to their weights instead of trying to give perfect service to high

?

10

Max #high prio stations

?

?

0.05

0.05

0 0 0.2

0 0 0.2 0.4 0.6 Fraction high priority nodes 0.8 1

Fig. 3. Average access delay for a station at each priority level.

15

15

10

5 PCF DENG DFS BB 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 Offered low priority load 0.8 0.9 1

0

priority traf?c. For PCF this is both because it has poor medium utilization, and because there must always be room for a low priority frame during the contention period. In a real life scenario, it is not likely that all traf?c is CBR and therefore we also ran simulations with burstier traf?c3 which did not affect the high priority traf?c in any signi?cant way. Thus we feel that the results presented here would be valid even with other characteristics of low priority traf?c.

3 Conclusions
From our simulations we can conclude that the PCF mode of the IEEE 802.11 standard performs poorly in the metrics studied compared to the other schemes evaluated. Blackburst gives the best performance to high priority traf?c both with regard to throughput and access delay. A drawback with Blackburst is the requirements it imposes on the high priority traf?c. If these can not be met, DENG might be a suitable alternative since it can serve quite many high priority stations, while giving them very low access delay. An major advantage of DFS is that it will try to achieve fairness, and will not starve low priority traf?c, which in many cases is a desirable property of a scheme. Further, our simulations show that Blackburst is the scheme among those studied here that gives the best medium utilization, which is important, given the scarcity of bandwidth in wireless networks. Finally, we conclude with the observation that there might not be one scheme that is the best to choose in all situations, but the choice of QoS scheme should instead depend on the expectations of the traf?c, and other circumstances. Before deciding on what QoS scheme to use in a network, an analysis of what the network should be used for, and what kind of services that is needed should be done.

References
1. D-J. Deng and R-S. Chang. A priority scheme for IEEE 802.11 DCF access method. IEICE Transactions on Communications, E82-B(1), January 1999. 2. S. J. Golestani. A self-clocked fair queueing scheme for broadband applications. In Proceedings of IEEE INFOCOM, 1994. 3. S. McCanne and S. Floyd. ns network simulator version 2.1b6, August 2000. 4. J. L. Sobrinho and A. S. Krishnakumar. Real-time traf?c over the IEEE 802.11 medium access control layer. Bell Labs Technical Journal, pages 172–187, Autumn 1996. 5. J. L. Sobrinho and A. S. Krishnakumar. Quality-of-Service in ad hoc carrier sense multiple access networks. IEEE Journal on Selected Areas in Communications, 17(8):1353–1368, August 1999. 6. The Institute of Electrical and Electronics Engineers, Inc. IEEE Std 802.11 - Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) speci?cations, 1999 edition. 7. N. H. Vaidya, P. Bahl, and S. Gupta. Distributed fair scheduling in a wireless LAN. In Sixth Annual International Conference on Mobile Computing and Networking, Boston, August 2000. 8. M. A. Visser and M. El Zarki. Voice and data transmission over an 802.11 wireless network. In Proceedings of PIMRC’95, Toronto, Canada, pages 648–652, September 1995.
3

ON-OFF sources with ON and OFF periods from a Pareto distribution




友情链接: