Adaptive Rate Control based on Collision and Frame Aggregation Awareness by Dongjin Kim A dissertation submitted to the Graduate Faculty of Auburn University in partial ful llment of the requirements for the Degree of Doctor of Philosophy Auburn, Alabama August 2, 2014 Keywords: 802.11n, MIMO, Rate Adaptation, Rate Control, Channel Adaptation, Link Adaptation, Collision, Frame Aggregation, Copyright 2014 by Dongjin Kim Approved by Alvin Lim, Chair, Associate Professor of Computer Science and Software Engineering David Umphress, Associate Professor of Computer Science and Software Engineering Drew Hamilton, A liate Professor of Computer Science and Software Engineering Xiao Qin, Associate Professor of Computer Science and Software Engineering Abstract The innovative advances in mobile technologies have facilitated remarkable growth in the use of mobile devices such as smart phones, e-book readers, and tablet PCs. Since a signi cant amount of wireless tra c is generated from these devices, the shared channel medium may su er from serious mutual interference. In addition, various kinds of fading weaken the stability of channel quality. Though IEEE 802.11 standards specify an available set of transmission rates as one of the approaches to accommodate channel dynamics, they do not discuss in detail when and how to use them. Rate Adaptation (RA) algorithms try to solve this decision problem by determining the most appropriate data rate for the instantaneous wireless channel condition. The primary focus of Rate Adaptation studies for legacy standards such as IEEE 802.11 a/b/g has been on when to increase/decrease transmission rates or how to di erentiate be- tween collision-induced loss and channel disorder-induced error. However, with the advent of novel Multiple Input Multiple Output (MIMO), Channel Bonding, and Frame Aggrega- tion/Block Acknowledgement technologies, it has become possible to enable Gigabit con- nectivity in wireless communication. At the same time, these new technologies add a new dimension of problems with rate adaptation. Even though much research has attempted to address the non-monotonic relationship [1] between data rate and throughput via exploring MIMO technology or by identifying the usability of another channel space for bonding [2], little research has analyzed the impact of Frame Aggregation. This paper begins by surveying existing research on Rate Adaptation (RA) algorithms. A wide range of RAs are introduced and classi ed based on various design factors. Secondly, a new RA scheme called RACD (Rate Adaptation with Collision Di erentia- tion) is presented. RACD is capable of di erentiating the reasons for packet errors by using ii CTS-to-self control packets. After classifying the sources of errors, RACD responds accord- ingly with actions such as initiating RTS/CTS handshake or adjusting Contention Window size. Extensive simulation results con rm that RACD signi cantly improves performance, especially in simulated congestion scenarios. Finally, the new features introduced in the state of the art IEEE 802.11n standard are overviewed and discussed. Out of the three dominant innovations speci ed in the new amendment, the impact of one innovation, Frame Aggregation (FA), on RA algorithm design is examined from various perspectives with a case study. Based on the analysis and ndings from the case study, a novel AARA (Aggregation Aware Rate Adaptation) algorithm is proposed and evaluated with extensive experiments conducted in controlled and repeatable environments. The performance enhancement over representative existing RA algorithms is validated with throughput gains up to 473% in various experimental scenarios. Potential performance bene ts on RA design from Frame Aggregation awareness is discussed in detail. Although the experimental work and the proposed AARA algorithm provide insight into the signi cant in uence of FA on RA algorithm design, a number of critical issues remain which should be considered for further research. This dissertation concludes with a discussion of potential future work related to FA and RA for IEEE 802.11 Wireless Networks. iii Acknowledgments First of all, I would never have been able to nish my dissertation without the guidance of my advisor, Dr. Alvin Lim and I would like to express my deepest gratitude to him for his caring, patience, and providing me with an excellent atmosphere for doing research. I also thank my committee members, Dr. David Umphress, Dr. Drew Hamilton, Dr. Xiao Qin, and Dr. Shiwen Mao for their teaching, encouragement and consideration. I would like to give my best appreciation to my friends, Ted, Se-eung, Museung, Mike, Chris, Tom, Nesha. They have given me comfort and energy for me to go through lots of di culties. Many thanks to my lab mates, Qing, Brandon, Jian, Kanika, Seungbae, and Song. They have been always willing to help and give their best suggestions. I would have been lonely without them. I would also like to thank my parents and sister. They have never stopped supporting me and encouraging me with their best wishes. Finally, I would like to appreciate the help from my wife, Mia Kim and two children, Gaeun and Junhyeok Kim for their being there with me through the good and bad times. iv Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Rate Adaptation in 802.11 WLANs . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Key Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Terms and Abbreviation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 A Survey of Rate Adaptations in 802.11 WLANs . . . . . . . . . . . . . . . . . 5 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Classi cation of Rate Adaptation Algorithm . . . . . . . . . . . . . . . . . . 6 2.2.1 Rate Adaptation for Legacy Standards . . . . . . . . . . . . . . . . . 7 2.2.2 Rate Adaptation for the MIMO-enabled Standards . . . . . . . . . . 10 2.2.3 Rate Adaptation with Collision Di erentiation . . . . . . . . . . . . . 14 2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3 Problem Statement and Research Questions . . . . . . . . . . . . . . . . . . . . 17 3.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Research Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4 Rate Adaptation with Collision Di erentiation for IEEE 802.11 WLANs . . . . 19 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2.1 Distributed Coordination Function (DCF) . . . . . . . . . . . . . . . 21 4.2.2 CTS-to-self Protection Mechanism . . . . . . . . . . . . . . . . . . . 22 v 4.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.4 Algorithm Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.4.1 Rate Adaptation with Collision Di erentiation (RACD) . . . . . . . . 25 4.5 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.5.1 Simulation Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.5.2 Throughput Comparison with Di erent Schemes . . . . . . . . . . . . 30 4.5.3 Impact of Adjusting Contention Window . . . . . . . . . . . . . . . . 32 4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5 Aggregation Aware Rate Adaptation in IEEE 802.11n WLANs . . . . . . . . . . 35 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.2.1 Multiple Input Multiple Output (MIMO) . . . . . . . . . . . . . . . . 37 5.2.2 Channel Bonding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.2.3 Frame Aggregation and BlockACK . . . . . . . . . . . . . . . . . . . 38 5.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.3.1 MIMO-aware Rate Adaptations . . . . . . . . . . . . . . . . . . . . . 41 5.3.2 Research on Frame Aggregation . . . . . . . . . . . . . . . . . . . . . 43 5.4 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.5 Experiment Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.5.1 Experimental Platform . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.5.2 Experimental Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.5.3 Performance Metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.6 Case Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.6.1 Probing with A-MPDU . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.6.2 A-MPDU Retransmission . . . . . . . . . . . . . . . . . . . . . . . . 56 5.6.3 Multi-Rate Retry Scheme with Frame Aggregation . . . . . . . . . . 59 5.6.4 Impact of Congestion . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 vi 5.6.5 Multiplexing Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.7 Aggregation Aware Rate Adaptation (AARA) . . . . . . . . . . . . . . . . . 65 5.7.1 Best Transmission Rate Selection . . . . . . . . . . . . . . . . . . . . 65 5.7.2 Adaptive Probing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.7.3 Congestion Detection and Response . . . . . . . . . . . . . . . . . . . 71 5.8 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.8.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 5.8.2 Static Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 5.8.3 Mobile Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.8.4 In-range Collision Setting . . . . . . . . . . . . . . . . . . . . . . . . 78 5.8.5 Hidden Collision Setting . . . . . . . . . . . . . . . . . . . . . . . . . 80 5.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 6 Conclusion and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 vii List of Figures 4.1 Distributed Coordination Function in IEEE 802.11 Standards . . . . . . . . . . 21 4.2 CTS-to-self mechanism is newly introduced in 802.11 speci cation for secure communication. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.3 Flowchart of Proposed RACD Channel Status Di erentiation . . . . . . . . . . 26 4.4 Packet Size Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.5 In-range (left) and Hidden Collision Scenario (right) . . . . . . . . . . . . . . . 30 4.6 In-range Collision Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.7 Both In-range and Hidden Collision Scenario . . . . . . . . . . . . . . . . . . . 31 4.8 In-range collision Scenario Comparison . . . . . . . . . . . . . . . . . . . . . . . 33 4.9 Both In-range and Hidden Collision Scenario Comparison . . . . . . . . . . . . 34 5.1 Amortized Header Overhead according to Aggregated Number of Frames . . . . 39 5.2 Aggregated Frame Structure: A-MSDU (Left), A-MPDU (Right) . . . . . . . . 41 5.3 Experimental Floor Plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.4 Contention Scenario Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.5 Mobile Scenario Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 viii 5.6 Network Throughput with Varying Number of Frames in a Probing Packet . . . 56 5.7 A-MPDU Failure Probability over nFrames . . . . . . . . . . . . . . . . . . . . 58 5.8 A-MPDU Retransmission, Average nFrames, and Throughput over Di erent Con- gestion Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.9 Consecutive A-MPDU Retransmissions over Di erent Scenarios . . . . . . . . . 63 5.10 Throughput and FSR Comparison under Di erent MIMO modes . . . . . . . . 64 5.11 RSSI Di erences in Various Scenarios . . . . . . . . . . . . . . . . . . . . . . . . 65 5.12 State Transition Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.13 Cross mode Rate Probing Directions . . . . . . . . . . . . . . . . . . . . . . . . 70 5.14 Throughput in Static Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.15 Rate Evolution in Static Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.16 Performance in Static Setting (Location E) . . . . . . . . . . . . . . . . . . . . 77 5.17 Throughput and FER in Mobile Setting . . . . . . . . . . . . . . . . . . . . . . 78 5.18 Rate Evolution in Mobile Setting . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.19 Throughput in In-range Collision Setting . . . . . . . . . . . . . . . . . . . . . . 80 5.20 Rate Evolution in In-range Contention Setting . . . . . . . . . . . . . . . . . . 81 5.21 AFER w/ and w/o Retransmissions in In-range Contention Setting . . . . . . . 82 5.22 Throughput and Retransmission Ratio in Hidden Collision Setting . . . . . . . . 83 5.23 Throughput Comparison according to RTS/CTS Operation Duration . . . . . . 84 5.24 Rate Evolution in Hidden Contention Setting . . . . . . . . . . . . . . . . . . . 85 ix List of Tables 1.1 Terms and Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1 MCS Index Table Available in 2 Streams MIMO NIC . . . . . . . . . . . . . . . 13 4.1 Simulation Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5.1 Comparison between 802.11n and 802.11ac Standards . . . . . . . . . . . . . . . 37 5.2 Experimental Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.3 Variables used in Retransmission Cost and Goodput Calculation . . . . . . . . . 51 5.4 Maximum Possible nFrames and Maximum per A-MPDU Throughput (Thputmaxr ) 52 5.5 Probing Attempt Distribution and Success Ratio on Each Rate Option . . . . . 54 5.6 Rate Distribution, nFrames, Retransmission Ratio, FER . . . . . . . . . . . . . 59 5.7 Thoughtput Improvement of AARA over RAs in Comparison . . . . . . . . . . 74 x Chapter 1 Introduction 1.1 Rate Adaptation in 802.11 WLANs An extensive amount of research on wireless communications has been done both in the literature and industry. Such research has led to an explosive growth in the number of wireless devices used by people who are attracted by their inherent convenience and portability. Among di erent types of wireless networks, Wireless Local Area Network (WLAN), also called WiFi, has been in the limelight for short distance connections due to its convenience and relatively higher bandwidth availability. However, in addition to the inherent instability of the channel medium and signal distortion caused by movement of devices, the increasing volume of wireless tra c seriously degrades network performance. Hence, promptly and exibly adapting to unpredictable wireless link variations has become a primary challenge of wireless link performance. Rate Adaptation (RA) is one of the channel adapting methods which dynamically change data transmission rate according to the current wireless status. A series of WLAN standards developed by the IEEE 802.11 Working Group provide multiple data rates varied by di erent modulation types and coding rates. Furthermore, as technology advances, the number of available rate options is increasing. However, the IEEE Working Group did not specify an algorithm which selects the most appropriate rate to ongoing channel. The key problem is that the fastest rate does not always provide the best performance. Typically, a higher data rate can transmit more data in the same period of time than a lower option can due to denser signal modulation, but a lower rate can reach a longer distance 1 due to its robustness in transmission. Therefore, network e ciency is seriously a ected by adaptive data rate adjustment. 1.2 Key Contributions The goal of this dissertation is to design and propose e cient Rate Adaptation algo- rithms to optimize wireless link performance. To this end, Chapter 2 of this work surveys RA schemes which have been suggested to date. Important challenges involved in e cient design options are carefully reviewed. Then, two novel RA algorithms are proposed with intensive performance evaluation followed by in-depth research on how di erent aspects of RA design metrics a ect wireless network performance. The key contributions are as follows: First, a wide range of the existing RA algorithms are categorized and classi ed hier- archically. The survey not only deals with RA algorithms, but also includes design factors which are potentially related to wireless network problems connected to RA system design. Even though numerous RA algorithms have been proposed in the literature, little e ort has been made to organize and categorize those algorithms. Secondly, a new RA scheme called RACD (Rate Adaptation with Collision Di erenti- ation) is proposed in Chapter 4. RACD is capable of di erentiating the reasons for packet errors by means of using CTS-to-self control packets and minimizes the throughput degra- dation due to misinterpretation of collision-induced failure. After classifying the sources of error, RACD responds accordingly by actions such as initiating RTS/CTS handshake or adjusting Contention Window size. Extensive simulation results con rm that RACD signif- icantly improves performance especially in simulated congestion scenarios. Finally, Chapter 5 overviews and discusses the new features introduced in the state of the art IEEE 802.11n standard. Out of the three dominant innovations speci ed in the new amendment, the impact of one innovation, Frame Aggregation (FA) on RA algorithm design is closely investigated from various perspectives with a case study. Based on the analysis 2 and ndings from the case study, a novel AARA (Aggregation Aware Rate Adaptation) algorithm is proposed and evaluated via exhaustive experiments carried out in controlled and repeatable environments. Speci cally, in contrast to prior work, the test results exhibit per-AMPDU packet rate selection compared to the ideal transmission rate upon each channel condition. This chapter evaluates the performance enhancement over representative existing RA algorithms based on extensive experiments under various scenarios and discusses in detail the potential bene t on RA design from Frame Aggregation awareness. 1.3 Terms and Abbreviation Table 1.1 lists the most frequently used terms and abbreviations in this dissertation. Note that in order to avoid confusion, the term packet used in this paper indicates an completed data structure which can be transmitted without additional information such as protocol headers for each layer, check sequence, and padding bits; whereas the term frame means an individual MPDU or MSDU before being aggregated into either A-MPDU or A- MSDU packets as presented in Figure 5.2. Similarly, retry is used when an individual MPDU in an aggregated packet is failed and retried, whereas retransmission is used when an entire A-MPDU or A-MSDU packet is lost and retried. 3 Table 1.1: Terms and Abbreviations Terms Abbreviations Rate Adaptation (Link Adaptation) RA Modulation and Coding Scheme MCS Received Signal Strength Indicator RSSI Signal to Noise Ratio SNR Multi-Rate Retry MRR Multiple Input Multiple Output MIMO Spatial Diversity/Single Stream SD / SS Spatial Multiplexing/Multi Stream SM / MS Frame Aggregation FA Mac Protocol Data Unit MPDU Mac Service Data Unit MSDU Aggregated MPDU A-MPDU Aggregated MSDU A-MSDU Block Acknowledgement BlockACK Number of frames in an A-MPDU nFrames Number of bad frames in an A-MPDU nBad Packet Error Ratio for time window PER Frame Error Ratio in multiple A-MPDUs FER Frame Success Ratio in multiple A-MPDUs FSR A-MPDU Frame Error Ratio in a single A-MPDU AFER A-MPDU Frame Success Ratio in a single A-MPDU AFSR 4 Chapter 2 A Survey of Rate Adaptations in 802.11 WLANs 2.1 Introduction Rate Adaptation (also called Link Adaptation in the literature) is a set of processes to determine the most suitable transmission rate for the current channel condition out of available rate options speci ed in the standard. Determining the optimal transmission rate in timely fashion is a challenge for several reasons. First, it is essential to assess the ambient channel quality using various metrics typically available in the PHY and MAC layers. Channel estimation may be (but does not have to be) followed by di erentiating losses from various causes. Then, according to the channel estimation and loss di erentiation, the RA decides which rate option can maximize the current link capacity. The data rate can be increased or decreased step by step in a linear manner, or the RA can monitor statistics of each potential rate option and jump directly to the best one. Even though RA has been extensively studied in the last decade, little attempts has been made to survey the existing RA algorithms. S. Biaz and S. Wu [3] surveyed and compared di erent RA schemes, but their study includes only the initial RA algorithms proposed before 2008. This section extends their work to aggregate the most recent RA schemes, re-organizes them with distinct criteria, and gives a brief overview of each algorithm. 5 2.2 Classi cation of Rate Adaptation Algorithm A remarkable number of studies have been published on rate adaptations in the literature that provide high transmission throughput in wireless networks. These algorithms can be classi ed into di erent categories according to various criteria. One criterion for classifying RA algorithms is whether the decision-making station is the transmitter or the receiver. A transmitter-side decision rate adaptation scheme determines the best rate based only on the transmitter?s local information, whereas a receiver-side scheme determines the rate based on information exchanged between the transmitter and the receiver. The receiver-side decision is relatively more accurate compared to the transmitter- side decision but has the drawbacks of a longer delay and a more complicated decision. It also requires modi cation of the current IEEE 802.11 standard because it needs to wait for information about the channel sent from the transmitter. Secondly, a good number of RAs di erentiate collision-induced losses from channel de- grading losses, because decreasing data rate upon collision-induced losses not only degrades the network performance, but also further aggravates the channel congestion due to the longer transmission time of lower rate options. A variety of protocols studying collision avoidance mechanisms will be introduced in Section 2.2.3. On the other hand, RA schemes also can be classi ed into ones before and after the IEEE 802.11n standard. Since the new standard leads to a signi cant breakthrough in network bandwidth capacity, it introduces unique challenges which MIMO RAs must address for e ective adaptation. In this paper, the term Legacy RA refers to RA schemes that were used before the 802.11n standard, as opposed to MIMO RAs which targeted and exploited MIMO-enabled devices following the new amendment. In addition, RA protocols can also be classi ed by the ability to di erentiate collision-induced losses from channel-induced losses, regardless of which standard they are designed for. 6 2.2.1 Rate Adaptation for Legacy Standards In this section, RA protocols designed for the legacy standards 802.11a, b and g are introduced and categorized based on which protocol stack they access to infer channel con- dition. The parameters for channel interpretation can be obtained by either the PHY layer, the MAC layer, or both. Though the two types of RAs each have their own strengths and weaknesses, PHY metric-based RA is known to overestimate the channel status while MAC metric-based RA tends to underestimate the current state. Therefore, hybrid designs us- ing both PHY-layer and MAC-layer metrics have been introduced to take advantage of the strengths and constraints of each system. I. Haratcherev and K. Langendoen [4] selected the optimal transmission rate using MAC-layer frame error statistics and bounds available transmission rates according to the report from channel dynamic detector using RSSI varia- tion. Note that since the legacy standards do not have the aggregation mechanism speci ed in the protocol, each packet is transmitted with a single MPDU frame. MAC-layer Metric-based Rate Adaptation Algorithms While the PHY-layer metric based RAs gauge the link state using direct indications such as Received Signal Strength Indicator (RSSI) and Signal to Noise Ratio (SNR), MAC- layer metric based RAs (also called Loss-based RAs in the literature) indirectly estimate how e ciently the current or candidate rate option performs to infer the optimal transmission rate. Typically, the link quality is evaluated by checking packet loss information, which can be identi ed when the transceiver can neither decode nor receive the acknowledgement from the receiver. The packet loss pattern can be measured either by counting the number of consecutive successes (or losses) or by observing the Packet Error Ratio (PER) over a sliding time window. The initial stage RA algorithms such as ARF [5], AARF [6], AARF-CD [7], and RRAA [8] employ a consecutiveness counter to assess the link condition. For example, as the earliest RA scheme, Auto Rate Fallback (ARF) [5] simply increases the data rate by one step 7 after ten consecutive successful transmissions and decreases it upon two sequential packet losses. Using consecutiveness of packet losses as a decision guideline is intuitive and easy to implement; however, as I. Pefkianakis [9] demonstrated by well-organized experiments, this method has potential limitations due to unstable channel dynamics. Another RA proposal interprets link condition based on Packet Error Ratio (PER) between corrupted packets and total transmitted packets over a speci ed time frame. Sample Rate [10] collects statistics over a period of one to ten seconds and chooses the rate which exhibits the shortest expected transmission time in the last sample period. ONOE [11] also collects the packet transmission statistics, then adjusts credit counters whenever the statistic satis es certain conditions. If the credits reach a given threshold, the RA decides whether to use a higher or lower data rate for the next time frame. Atheros RA [12], Minstrel [13] and TERA [14] commonly measure network throughput re ecting the regulatory overhead speci ed in the standard and packet error rate for the sampling time window. Then the protocol switches directly to the best performing rate as opposed to making linear rate adjustments for consecutiveness based solutions. Context-Aware Rate Section (CARS) [15] takes advantage of context information in ad- dition to the MAC layer statistics, such as vehicle speed and distance between corresponding nodes, to achieve better performance in VANET. Also, RapidSample [16] adopts statistic- based SampleRate for static settings and employs the time di erence between the last failed attempts and current transmission to identify the best rate for mobile settings. The mobility can be detected by external sensors such as GPS and accelerometers. PHY-layer Metric-based Rate Adaptations As opposed to the MAC-layer metric-based RAs, a wide range of RA protocols have been proposed based upon diverse metrics from the PHY layer. The most popular and widely accepted parameters are Received Signal Strength Indicator (RSSI) and Signal-to- Noise Ratio (SNR). Receiver Based Auto Rate (RBAR) [17] is proposed as the rst and 8 most representative SNR-based, closed-loop rate adaptation algorithm; this method leverages RTS/CTS control packets to exchange SNR information between corresponding stations. A number of protocols, including Vehicular Ad-hoc Network (VANET), pay attention to mobile environments, which are di erent from typical o ce environments due to higher uctuation and channel asymmetry. K. Lee et al [18] paved the way for simulating VANET environment by collecting SNR traces from moving vehicles and feeding them into a sim- ulator to re ect the real channel condition. Instead of using simulations, J. Camp and E. Knightly [19] designed a custom cross-layer framework to implement the SNR-based RA protocol for VANET in their FPGA platform. In addition, P. Deshpande and S. Das [20] proposed the SNR-based RA scheme BRAVE, which predicts near future channel states based on short-term RSSI history. Recently, RFRA [20] applied a machine-learning heuris- tic algorithm to rate adaptation for vehicular networks to exploit statistical dependency between vehicle speed, SNR, and data rate. Since PHY-layer metric-based RAs are typically receiver-based (closed-loop) and the re- ceiver needs to feedback its surrounding channel state to a transceiver which is not standard- compliant, most PHY-layer protocols are either simulation-based or implemented in propri- etary test-beds. On the other hand, CHARM [21] designed and implemented a transmitter- based, open-loop RA algorithm based on RSSI measurements from receiver-side. It exploits channel reciprocity, which enables the transmitter to compute the path-loss based on the additional information provided by the receiver such as transmit power and antenna gain. RAM [22] also overcame the standard incompliance using receiver-side ACK rate variance to direct transmission rate adjustment. Accurate rate selections are made by more sophisticated symbol-level PHY-layer metrics to re ect the channel state in [23, 24, 25]. Softrate [23] computes interference-free bit error ratio based on SoftPHY hints, which are bit level con dence information, to estimate channel quality, while FARA [24] collects the SNR and BER values, respectively, of individual OFDM 9 data sub-bands to track the channel. On the other hand, AccuRate [25] observes symbol-level dispersion between the transmitted and received symbol pair on the constellation space. This type of RA schemes can be agile to adapt to fast-changing channel and adjust data rate; however, they have common issues which prevent vendors from implementation in practice: (1) They require cross-layer implementation and an explicit feedback mechanism for receiver-side channel measurements which are not standard-compliant. (2) Since these RAs need a-priori, pre-de ned mappings of the ambient channel conditions between a range of PHY metrics, PER, and rate options, an in-situ hardware-speci c calibration process is required to correctly re ect the surrounding channel. (3) As pointed out in [10], even though the SNR value is able to correctly interpret the current link condition, it has little predictive value for future transmissions because SNR is typically measured at the start of the packet reception and it cannot re ect variations even during the duration of transmission. 2.2.2 Rate Adaptation for the MIMO-enabled Standards The new 802.11n/ac standards shed light on a new era of up to Giga-bps network bandwidth for WLANs. The representative techniques to enable the performance surge are three-fold: (1) Multiple Input Multiple Output (MIMO) enables the involving stations to transmit more than two data streams simultaneously, (2) Channel Bonding allows the com- bination of adjacent channel bandwidths to boost performance, and (3) Frame Aggregation (FA) aggregates multiple data frames into a single packet to amortize protocol overheads. More details of these new characteristics are provided in Section 5.2. Since these advanced features introduce new levels of freedom to the decision-making process, RA algorithms for the new amendments require di erent approaches. This section presents various RA algo- rithms exploring the new properties. 10 Receiver-based Closed-loop Approaches In addition to the features for performance enhancement, the new standard also de nes the Channel Status Information (CSI). CSI, a MCS feedback mechanism, enables the receiver to feedback to the transceiver in response to incoming packets to overcome the limitation of the legacy standards. Thanks to this recti cation, the PHY-metric, receiver-based RAs can be implemented in a standard compliant way. E ective SNR [26] develops a packet delivery model based on information from the Net- work Interface Controller. The receiver averages the Bit Error Ratio (BER) of 56 OFDM subcarriers and calculates the e ective SNR over SNR of received signal and OFDM modu- lations, and then sends the CSI information back to the transceiver. G. Martorell et al [27] designed the Fast Link Adaptation scheme, which adjusts MCS to a pre-de ned target PER. The Exponential E ective SNR Mapping (EESM) and corre- sponding target BER is averaged over individual OFDM sub-carriers and translated to a representative Packet Error Ratio. ARAMIS [2] employs closed-loop approach as well. It takes advantage of SNR di er- ence between antennas along with the combined SNR to predict the channel quality. After measuring the SNR and SNR di erence, it identi es a corresponding Packet Reception Rate (PRR) from an a-priori mapping table, then feedbacks the highest available MCS rate which satis es the PRR threshold. Even though the CSI feedback mechanism is clearly de ned in the standard and paves the way for closed-loop, receiver-based RA algorithms, these algorithms are unpredictable because of the rapid channel variation during which the receiver detects the link and the transceiver obtains the feedback message. Moreover, since its cost ine ciency and imple- mentation complexity keep vendors from implementing real drivers, most of the proposed algorithms are just evaluated with simulations and not implemented in practice. 11 Transceiver-based Open-loop Approaches The general concept throughout legacy RAs is that Packet Error Ratio (PER) is pro- portional to MCS rate index where incremental rate growth can eventually reach the best option; however, this seemingly intuitive idea cannot be applied to MIMO RAs, because, given that the channel quality is not su cient to tolerate multiple streams, single-stream MCS rates outperform the double stream rates. For example, as indicated in Table 2.1, Single Stream (SS) MCS 5 and Double Stream (DS) MCS 11 both have 52 Mbps data rate when used with Long Guide Interval (LGI) without channel bonding (default 20GHz channel bandwidth). If the channel quality is stable enough to hold a double stream, DS MCS 11 is desirable due to the robustness of lower modulation (16QAM over 64QAM for MCS 5); however, if the channel cannot tolerate double streams, SS MCS 5 must be the better choice in spite of a more aggressive modulation type. This Non-monotonicity between PER and data rate has been the key challenge to open-loop RA designs, as opposed to the closed-loop approaches introduces in the previous section. MiRA [1] con rms the Non-monotonicity through extensive real world experiments. This study collected the per A-MPDU statistics and demonstrated that when both MIMO mode rates are used interchangeably, the A-MPDU Frame Error Ratio (AFER) does not grow monotonically as the bandwidth of the transmission rate increases. Yet the authors also validated monotonic relationship holds for the individual operation mode. Based on the result of a practical case study, the MiRA algorithm not only gathers statistics from the current MIMO mode (intra-mode), but also samples rate options of another MIMO mode (inter-mode) to avoid situations in which the RA gets stuck with the lower transmission rate rather than the potentially better rate option due to the Non-monotonicity. This algorithm also employs an adaptive probing scheme which prevents the protocol from frequent sampling for bad rates. WRA [28] follows MiRA?s motivation, but suggests a di erent solution. It operates separated, individual RA algorithms for each MIMO modes instead of zigzagging. These two schemes are well designed to overcome the Non-monotonicity, but aggressive 12 Table 2.1: MCS Index Table Available in 2 Streams MIMO NIC MCS Index # of Streams Modulation Type Coding Rate Data Rate (Mbps) 20GHz Channel 40GHz Channel LGI SGI LGI SGI 0 1 BPSK 1=2 6.50 7.20 13.50 15.00 1 1 QPSK 1=2 13.50 14.40 27.00 30.00 2 1 QPSK 3=4 19.50 21.70 40.50 45.00 3 1 16-QAM 1=2 26.00 28.90 54.00 60.00 4 1 16-QAM 3=4 39.00 43.30 81.00 90.00 5 1 64-QAM 2=3 52.00 57.80 108.00 120.00 6 1 64-QAM 3=4 58.50 65.00 121.50 135.00 7 1 64-QAM 5=6 65.00 72.20 135.50 150.00 8 2 BPSK 1=2 13.00 14.40 27.00 30.00 9 2 QPSK 1=2 26.00 28.90 54.00 60.00 10 2 QPSK 3=4 39.00 43.30 81.00 90.00 11 2 16-QAM 1=2 52.00 57.80 108.00 120.00 12 2 16-QAM 3=4 78.00 86.70 162.00 180.00 13 2 64-QAM 2=3 104.00 115.60 216.00 240.00 14 2 64-QAM 3=4 117.00 130.00 243.00 270.00 15 2 64-QAM 5=6 130.00 144.40 270.00 300.00 probing over di erent operation modes produces non-negligible overhead and limits further performance improvements. ARF-HT [29] divides the solution space into MIMO mode decisions and rate adjust- ments in each mode and adopts di erent MAC-layer metrics respectively. While a credit system based on RSSI di erence is used to select the MIMO operation modes, ARF-HT employs Expected Transmission Time (ETT) as SampleRate [10] for adjusting intra-mode rate selection. Similarly, RAMAS [30] divides available MAC-layer metrics used for rate selection into two independent groups: the modulation group and the enhancement group. The modulation group only takes account of modulation type and coding scheme; therefore, a monotonic relation between PER and data rate can be presumed among the rates for the same modulation group. On the other hand, the enhancement group deals only with the new improvement features in the 802.11n standard, such as the number of streams, guard 13 interval (GI), and channel width. Two independent groups employ separate credit-based protocols which are used to decide whether to move upward or downward. L3S[31] incorporates the Multi-Rate Retry (MRR) scheme, which is a set of tuples com- posed of data rate and retransmission limit. MRR enables RAs to attempt multiple trans- mission rates when packets are lost and retransmitted. L3S employs this MRR functionality to probe various candidate rate options to accommodate the current channel uctuation. In addition, the probing interval is adapted based on the consecutiveness of packet success and failure. S. Lakshmanan et al. [32] found that detrimental interference makes the MIMO process more susceptible to interference and developed a simple MAC-layer metric called Median Multiplexing Factor (MMF). MMF decides whether to use the MIMO mode rates under the current channel condition by throughput comparison between MCS rates which have the same modulation type and coding rate. 2.2.3 Rate Adaptation with Collision Di erentiation Wireless link degradation is mainly caused by: (1) signal fading, (2) In-range collision, (3) hidden collision, and (4) ambient interference. Signal fading is caused by either signal propagation loss by distance or Multi-path fading, which occur when multiple paths exist between a transceiver and receiver pair and the identical signals arrive at the receiver-side with a delay (called Delay Spread). On the other hand, In-range and hidden collisions involve additional stations besides the transmission pair. While In-range collision is attributed to simultaneous transmissions among stations within wireless range, hidden collision is caused by mutually unrecognized transmitters. Finally, interference is caused by random signals which the involved standard cannot decode. RA systems should respond only to fading-induced channel dynamics. If RAs switch rates over collision-induced packet failures, the switch worsens the link condition because the lower rate increases the channel occupancy and augments the chance of collision. Many 14 researchers have attempted to di erentiate the causes of channel deterioration and introduced various metrics for the distinction. The initial RAs [8, 33, 34, 35] employ RTS/CTS control packets to detect and respond to collision-induced packet failures. After a transceiver sends out an RTS packet after a frame loss, the packet determines the current condition by the success of CTS packet reception. DRANLD [36] used the received signal strength and Negative ACK packet (NACK) upon the RTS/CTS exchange to e ectively diagnose packet losses. Regardless of the distinction capability, RTS/CTS packets constitute a substantial over- head. Therefore, more sophisticated symbol level classi cation methods have been suggested. Z. Eu et al [36] correlates RSSI value with Link Quality Indicator (LQI) to classify packet transmission outcomes speci cally for Wireless Sensor Networks (WSNs). LQI value is an accumulation of magnitude di erence between ideal and actual signal level over individ- ual OFDM symbols. COLLIE [37] makes the distinction by collecting and analyzing the error-bit pattern upon reception of a corrupted packet. As pointed out earlier, symbol level implementation is complicated and cannot be made in a standard-compliant way. In order to overcome issues using symbol-level measurements in the PHY-layer, var- ious metrics available in the MAC-layer have been proposed to diagnose collision-induced packet losses. LDRA [38] uses beacon packets which are mandated in all of the 802.11 stan- dards for broadcasting necessary information for synchronization and power management. In addition, M. A. Y. Khan and D. Veitch [39] exploit a simple idea that if there is an ongoing protection protocol which reserves the channel proprietarily, such as fragmentation, RTS/CTS handshake, or Block reservation in 802.11e, the packet loss is caused by channel disorder. Similarly, REACT [40] de nes a green channel period which is a congestion-free interval, and considers any loss during the green channel period to be a collision-induced loss. On the other hand, time-domain metrics have been suggested in the literature to detect current congestion. WOOF [41] predicts the density of congestion by measuring channel 15 busy time with statistical mitigation for unpredictable uctuation. YARA [42] computes time di erence between transmission time and e ective transmission time. The E ective transmission time refers to the ideal transmission time where there is no contending station to attempt a channel access. In contrast to the previous work, M. Kim and C. Choi [44] explored Frame Aggregation (FA) and Block Acknowledgement (BlockACK) functionality presented in the IEEE 802.11n standard. In this functionality, a hidden node detection mechanism di erentiates losses from channel error, In-range collision, and hidden collision by mathematical analysis using MAC- layer parameters such as number of idle slots, missing BlockACK, and other transmissions, then reacts accordingly. 2.3 Summary In summary, all Rate Adaptation schemes should address two core challenges: (1) how to estimate the current channel condition, and (2) how to translate the estimate into the optimal transmission rate. In this chapter, a wide range of Rate Adaptation algorithms are brie y introduced and classi ed by various criteria which they use for channel estimation. 16 Chapter 3 Problem Statement and Research Questions 3.1 Problem Statement Wireless channels naturally su er from di erent types of interference than do wired chan- nels because the wireless signals radiated from the antenna take numerous di erent routes, collide with other signals, and experience attenuation while they are travelling through the channel medium. Moreover, a growing number of wireless devices make the channel more variant and unpredictable. Rate Adaptation is one of the approaches which attempt to en- hance di erent network performance metrics by improving agility in the presence of channel dynamics. In addition to adaptability, another important factor in designing RA algorithms is di erentiating the causes of packet losses, as packet failures resulting from collision should not a ect the decision of appropriate data rate. While these problems have been extensively researched, there are still many challenges to address to maximize the performance of wireless networks. This dissertation aims at exam- ining limitations of the current RA schemes and developing e ective rate control algorithms which enable responses to varying channel conditions. Despite of considerable e orts to classify the causes of packet failures in wireless com- munication, challenges still remain in di erentiating between In-range collision and hidden collision-induced packet failure. In addition, as the new IEEE 802.11n standard employs new techniques which are introduced in Section 5.2, most of the MIMO-enabled RAs proposed in the literature show limited improvement because they only focus on designing adaptive use of Spatial Multiplexing based on the MIMO feature and cannot fully pro t from the new enhancements. Speci cally, though Frame Aggregation aimed at amortizing the protocol overhead plays a key role in achieving intensive throughput gain, the need of active control 17 in the aggregation level has not been a major research focus. It is obvious that RAs should consider the impact of Frame Aggregation as a primary design criteria. 3.2 Research Questions The goal of this work is to design and implement e cient Rate Adaptation algorithms by addressing the following research questions. For static environments where the channel is relatively stable and an optimal xed rate exists, how does the proposed solution e ectively nd and switch to the best rate while maintaining adaptability to unpredictable short-term channel uctuation with minimal overhead? For mobile environments where the channel rapidly changes over time due to movement, how does the new algorithm e ectively adapt to the varying link conditions to obtain an instantaneous optimal rate? For congested environments where multiple stations compete for the channel occu- pancy, how does the RA scheme intelligently distinguish the potential reason for losses in order to employ adaptable responsive actions? { If the channel error is caused by In-range collision, what is the appropriate re- sponse for the solution to activate? { If the channel error is caused by hidden station collision, when and how long does the RA protocol initiate RTS/CTS handshake as the solution to the hidden station problem? In order to resolve these questions, this dissertation carries out extensive experiments and reveals several signi cant insights, then proposes two Rate Adaptation algorithms based on answers to the questions listed above. 18 Chapter 4 Rate Adaptation with Collision Di erentiation for IEEE 802.11 WLANs 4.1 Introduction Since the IEEE 802.11 Wireless Local Area Network (WLAN) has emerged as a domi- nant and promising technology for wireless access for mobile/portable devices, the increasing amount of wireless tra c leads to poor channel qualities. Channels deteriorate for four main reasons: (1) signal fading, (2) In-range collision, (3) hidden collision, and (4) ambient inter- ference. Signal fading is caused either by signal propagation loss by distance or Multi-path fad- ing, which occurs when multiple paths exist between a transceiver and receiver pair and identical signals arrive at the receiver-side with a delay (called Delay Spread). The im- pact of multi-path fading can be either constructive or destructive depending on how the two duplicated symbols combine. On the other hand, In-range and hidden collision involve additional stations besides the transmission pair. While In-range collision is attributed to simultaneous transmissions among stations within wireless range, hidden collision is caused by mutually unrecognized transceivers. Finally, interference is caused by random signals which the involving standard cannot decode. These causes cannot be eliminated due to the unstable nature of the wireless medium. Therefore, dynamic tra c control is necessary to make wireless communication more exible. Recent research in the IEEE 802.11 standard improved the PHY speci cation that enables the standard to provide multiple data rates. Thus, stations in WLAN can select appropriate transmission rates according to the current channel conditions to achieve higher throughput. Rate adaptation helps a transmitter choose the most appropriate transmission rate to maximize performance based on the current channel quality. The fundamental challenge 19 of rate adaptation algorithms is how to estimate, classify and respond to varying channel conditions. When a channel is estimated to be unstable, a rate adaptation algorithm classi es the cause of channel instability and then responds with pre-de ned reactive procedures. It is important for rate adaptation to properly diagnose the cause of channel degradation, because the appropriate action (e.g., increasing or decreasing transmission rate) di ers based on the cause of channel instability. Many recent studies di erentiate collisions from other causes using Request to-Send (RTS) probing [34, 35, 8] on the assumption that the chance of an RTS packet error is negligible due to its small size and robustness. Hence, an RTS packet transmission fails only when a collision occurs. In this case, rate adaptation algorithms do not decrease the transmission rate because decreasing the rate will actually increase collisions due to the longer transmission time at a lower data rate. On the other hand, when a data frame (that is transmitted after a successful RTS packet) fails, rate adaptation algorithms determine that the previous error was caused by signal fading or interference and reduce the transmission rate. Additionally, in the IEEE 802.11 standard, the Exponential Back-o Algorithm requires every station to wait a random back- o period before retransmitting or sensing a busy channel. This algorithm increases the Contention Window size exponentially when a packet collision occurs. The problem is that this algorithm cannot distinguish the cause of packet losses. Therefore, a transmission failure always doubles the Contention Window size. When packet failures are caused by collision from hidden stations and channel disorder, the CW size should not be increased because these causes of packet failure are not related to the ones that the Exponential Back-o Algorithm is designed to avoid and respond to. In-range collisions are de ned as a collision caused by stations within the same wireless transmission range. This type of collision occurs when more than two transmitters within a wireless range are assigned to the same back-o slot of the Contention Window. On the other hand, hidden collision is de ned as a collision caused by hidden stations that are 20 Figure 4.1: Distributed Coordination Function in IEEE 802.11 Standards out of a transmitter?s range but in the receiver?s range. These collisions happen when the out-of-range transmitters are unaware of the media usage and try to send data frames. In this paper, a novel rate adaptation algorithm Rate Adaptation with Collision Dif- ferentiated (RACD) is proposed. This algorithm distinguishes In-range collisions from hid- den collisions. Moreover, CTS-to-self packet is used to di erentiate hidden collisions from In-range collisions. Because a CTS-to-self packet is shorter than RTS/CTS packets, the decision can be made faster than with previous rate adaptation algorithms. Further, RACD combines rate adaptation with the Return to 0 on Channel Errors (R0CE) scheme presented in [43] to maximize throughput. The rest of this chapter is organized as follows. Related work is introduced in Section 4.3. Section 4.4 details our new algorithm and Section 4.5 presents the simulation results. Then the chapter is summarized in Section 4.6. 4.2 Background 4.2.1 Distributed Coordination Function (DCF) As opposed to a wired network which is able to detect packet collision, wireless networks cannot identify whether an error is caused by contention or channel disorder. In order to avoid collisions, the IEEE Working Group adopted Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) as a basic channel access protocol. However, CSMA/CA is not 21 su cient to address the problem e ectively because multiple transmission attempts can be started right after the carrier sensing. Therefore, Distributed Coordination Function (DCF) is proposed to combine the CSMA/CD with several time intervals such as DIFS, SIFS and Back-o slots. Figure 4.1 illustrates how DCF works in IEEE 802.11 WLANs. Upon a transmission request, a transceiver checks whether the channel is idle. If there is no ongoing transmission, it waits for DIFS, then senses the channel again. If the channel is still idle, the transceiver selects a random number within a range of Contention Window (CW) and defers access by the chosen time interval. In DCF, if a transmitter fails to transmit a packet and attempts retransmission, this failure is assumed to have occurred due to a collision and DCF doubles the Contention Window size up to prede ned maximum Contention Window size. Note that regardless of all the collision avoidance mechanisms listed above, collisions occur when multiple stations are assigned to the same random back-o number (In-range collision). In addition, the ongoing signal can be corrupted when another transmitter which is unaware of the current transmission attempts to send packets (hidden collision). 4.2.2 CTS-to-self Protection Mechanism CTS-to-self is a protection mechanism for secure communication and compatibility introduced in the interest of maximizing performance in IEEE 802.11 standard. Under the IEEE 802.11 speci cations, all stations compete with each other to gain access to wireless channels. Due to the half-duplex communication characteristic of wireless communication, a collision is not detectable but just avoidable. In order to avoid collisions, a station senses a channel before sending the rst packet. If the channel becomes busy, it waits for a Distributed Inter Frame Space (DIFS) with a random period of back-o time determined by an assigned number which ranges from zero to the size of contention window. As the number of stations grow, the probability of collisions increases. This increased probability is why the IEEE 802.11 standard doubles the size of the contention window up to a prede ned maximum 22 Figure 4.2: CTS-to-self mechanism is newly introduced in 802.11 speci cation for secure communication. window size to reduce the chance of collisions. However, it cannot reduce collisions coming from hidden stations because the Clear Channel Assessment (CCA) introduced earlier cannot detect the signal from hidden stations. The RTS/CTS mechanism addresses this problem by reserving the channel within the range of hidden stations at the expense of communication overhead. 4.3 Related Work Since Section 2 introduces and categorizes various RA algorithms, this section focuses on detailed explanation of research related to the RACD algorithm and simulative experiments presented in Section 4.5. Auto Rate Fallback (ARF) [5] is the rst Rate Adaptation algorithm and has been widely accepted for legacy WLANs because of its simplicity and ease of implementation. If there are two consecutive packet failures, which means that the transceiver does not successfully receive two ACK packets in a row, ARF automatically switches to a rate one step lower. It also switches to the next higher rate either after ten consecutive successes in transmission 23 or after a pre-de ned time interval. ARF is based on the general assumption that there is a monotonic relationship between rate bandwidth and Packet Error Rate (PER). Adaptive Auto Rate Fallback (AARF) [6] extended the idea of ARF to improve adapt- ability to time-varying channel conditions. Speci cally, AARF keeps changing the thresholds of consecutive success and failure at run-time. The thresholds increase using the Binary Ex- ponential Back-o algorithm, which multiplies the thresholds by two upon the failure of a rate change attempt. In addition, it adapts rate update time intervals when stable channels hardly uctuate. Collision-Aware Rate Adaptation (CARA) [34] is another extension of ARF, but it focuses on di erentiating collision-induced packet losses from fading-induced packet losses and handling fading-induced losses with RTS/CTS control packets. Based on the robust- ness of the short-length RTS/CTS packet using the lowest rate, CARA assumes that failed RTS/CTS handshake implies that the previous loss resulted from a collision. In other words, upon a packet loss, CARA initiates RTS/CTS handshake before retransmitting the missed packet. If the transmitter fails to receive data ACK after the handshake where the channel is exclusively reserved and stable enough for the lowest rate, the packet loss was due to an unsuitable data rate. It is then required to adjust the transmission rate. CARA also suggests a supplement detection mechanism using Clear Channel Assessment (CCA) measurements. Robust Rate Adaptation Algorithm (RRAA) [8] is a MAC-layer statistic-based RA scheme enhanced with collision di erentiation capability. RRAA is composed of three mod- ules: Loss estimation, Rate Change, and Adaptive RTS lter. The Loss estimation module counts the number of packet losses for a short time window and computes Packet Error Ratio for channel quality assessment. The Rate Change module decides whether to increase or de- crease data rate based on the PER estimation, determined by comparing the Max Tolerable Loss threshold (MTL) and the Opportunistic Rate Increase Threshold (ORI). Finally, the Adaptive RTS (A-RTS) lter selectively alternates the RTS/CTS option to mitigate collision- induced packet losses. Whenever a packet loss occurs even with RTS/CTS exchange, A-RTS 24 lter increments the size of the RTS window by one for the RRAA to suppress severe collision losses. As described in Section 4.2.1, Contention Window in DCF is used to mitigate the impact of In-range collisions. As the window size grows, the chance of collision-induced failure drops accordingly, at the expense of delay in channel access. As a result, dynamic Contention Window adjustment is required in addition to Rate Adaptation. M. Kim and C. Choi [44] initialized the Contention Window to the minimum available value whenever hidden collisions are identi ed based on their detection algorithm, while doubling the CW upon In- range collisions. P. Chaporkar et al. [43] builds and analyzes a mathematical model and shows that initiating the Back-o state to zero upon a packet loss improves the performance of Rate Adaptation algorithm. 4.4 Algorithm Design In this section, a novel rate adaptation algorithm called Rate Adaptation with Collision Di erentiation (RACD) is proposed; this algorithm chooses the most appropriate transmis- sion rate according to current channel quality to maximize the throughput of the IEEE 802.11-based wireless networks. In order to achieve this goal, our algorithm exploits CTS- to-self to distinguish In-range collisions from hidden collisions. Section 4.2.2 analyzes the e ect of CTS-to-self with a brief introduction to DCF. The detailed design of the RACD algorithm is presented in Section 4.4.1. 4.4.1 Rate Adaptation with Collision Di erentiation (RACD) CTS-to-self is a newly de ned mechanism to reduce this overhead. It lets a transmitter set the destination address of a packet to its own address so that other stations within range do not initiate their transmissions for a speci ed duration. Figure 4.2 shows the packet ex- change procedure in the CTS-to-self mechanism. Once the CTS-to-self packet from station A is overheard by other stations within range, stations B and C defer their transmissions 25 Figure 4.3: Flowchart of Proposed RACD Channel Status Di erentiation 26 Figure 4.4: Packet Size Comparison for the duration described in the CTS-to-self packet. The equation below compares the overhead of the two protection mechanisms and shows that the total transmission time of CTS-to-self mechanism is shorter than the RTS/CTS mechanism. According to the packet format de nition (IEEE 802.11) shown in Figure 4.4, the sizes of RTS, CTS, and CTS-to-self packets are 20 bits, 14 bits and 14 bits respectively. Given the basic transmission rate, 1 Mbps, the transmission time of RTS/CTS and CTS-to-self are 20 s and 14 s respectively. As the SIFS is de ned as 10 s in IEEE 802.11, it turns out that tRTS=CTS = 54 s and tCTS to self = 24 s. The CTS-to-self transmission time is reduced by 30 s, which is 55% of RTS/CTS probing time. tRTS=CTS = tRTS +tCTS + 2 SIFS (4.1) tCTS to self = tCTS +SIFS (4.2) On the other hand, the CTS-to-self mechanism can only avoid In-range collisions, not hidden collisions. Therefore, a RTS/CTS packet is used to avoid hidden collisions when CTS-to-self does not make a successful probe. 27 Table 4.1: Simulation Parameters Simulation Parameter Value Number of Stations 10 50 Min Contention Window Size 15 Max Contention Window Size 1023 Data Frame Size 2Kbytes Reference Loss 46.67dB As discussed earlier, channel quality can be impacted by signal fading, collisions, and interference. Collisions occur either because of In-range stations or hidden stations. In-range collisions take place when two packets depart from di erent In-range stations at nearly the same time, and the packets do not arrive at the destination. The hidden collision is driven by overlapped signals from out of the wireless range area. Though these collisions have di erent underlying reasons, they are treated as the same cause of channel degradation in the literature. It is assumed that when packets collide, the collision a ects more than two transmissions because there is a high probability that the colliding packet is longer than the entire transmitted packet and may also collide with subsequent CTS-to-self packets. The colliding packet is much shorter than the transmitted packet in only a small number of cases. In addition, this assumption is typically used in the RTS probing methods [34, 35] to distinguish a collision-based failure from channel-error failure. RACD exploits the bene t of the CTS-to-self function to di erentiate the types of collisions and adjusts the transmission rate and Contention Window size. As shown in Fig- ure 4.3, the RACD algorithm activates when a transmitter fails to get an acknowledgement, i.e., when a packet failure occurs. It divides the channel states into (1) In-range collision, (2) hidden collision, and (3) channel error in cooperation with CTS-to-self and RTS/CTS packets. First of all, RACD determines that the previous data loss was caused by an In-range collision when a data packet is transmitted successfully after reserving the channel with a CTS-to-self packet. Therefore, it increases the Contention Window size exponentially. 28 Second, if the data frame after CTS-to-self fails, the algorithm activates the RTS/CTS handshake. If the transmitted data after the RTS/CTS packets is not acknowledged, the algorithm regards the previous failure as being caused by a hidden collision. Though the hidden collision has no impact on the back-o counter, according to DCF, the Contention Window size is doubled after every packet loss. To address this issue, the RACD algorithm returns to the previous back-o stage by halving the size of Contention Window in the hidden collision state. Finally, if there is another data frame loss after a successful RTS/CTS exchange, the RACD scheme decides that the channel su ers from fading or interference and thus requires rate adjustment. This decision is based on the assumption that the RTS/CTS transmission has negligible chance to be interrupted by channel disorder due to its short length and robustness. As a result, the transmission rate is decreased by one unit during channel error state. In addition, as mentioned in Section 4.3, RACD utilizes the idea in [43] to maximize throughput. Our scheme initializes the back-o stage to 0 and sets the Contention Window size to the minimum. In this paper, the main focus is to nd how to adapt to the channel when the channel condition grows worse. Hence, when the channel condition becomes better, e.g., when the number of consecutive successful packets reach a certain threshold, the simple ARF approach is adopted to change the rate to the next higher rate. 4.5 Simulation Results 4.5.1 Simulation Setup The "NS-3"[45] simulator is used in our experiments to evaluate the e ciency of the algorithm which implements the CTS-to-self mechanism and modi es the inherent DCF function modules to support Contention Window adjustments. The PHY layer is set to WIFI PHY STANDARD holland, which is used in RBAR [17] and implemented in NS-3 [45] as one of the basic con gurations. In order to simulate multi-path fading e ects, a constant 29 Figure 4.5: In-range (left) and Hidden Collision Scenario (right) propagation delay model was used. The propagation loss was based on the Log distance model with a reference loss of 46.67 dB at a distance of 1m. Then all stations generated 2Kbyte data packets and sent the data packets to a single destination. Each simulation result was averaged over 20 repetitions of the experiment. Two di erent scenarios were simulated: (1) an In-range collision scenario without hid- den stations and (2) a hidden collision scenario. For the In-range collision scenario, a varying number of contending stations were randomly placed within a 50m-radius circle around the receiver. In the hidden collision scenario, varying number of hidden stations were randomly deployed out of the transmitter?s communication range but within the receiver?s communi- cation range. The simulation results were compared with ARF [5], AARF [6], CARA [34] and RRAA [8]. In order to evaluate the e ect of the Contention Window adjustment in the new algorithm, experiments with the Contention Window adjustment function turned o were conducted and compared with the original RACD. 4.5.2 Throughput Comparison with Di erent Schemes Figures 4.6 and 4.7 show the averaged throughput results from di erent rate adaptation algorithms. Throughput is de ned as the number of successfully received packets divided 30 10 15 20 25 300 1 2 3 4 5 6 7 8 9 10 Number of Contending Nodes Mean Throughput (Mbps) ARF AARF CARA RRAA RACD Figure 4.6: In-range Collision Scenario 10 15 20 25 300 1 2 3 4 5 6 Number of Contending Nodes Mean Throughput (Mbps) ARF AARF CARA RRAA RACD Figure 4.7: Both In-range and Hidden Collision Scenario 31 by the number of packets transmitted. To get more generalized results, the mean through- put presented in these experiments is an accumulated number of correctly received frames counted by each destination station divided by the number of stations. Typically, all ve algorithms showed a trend of throughput degradation as the number of contending stations increased. As shown in Figure4.6, RRAA performed the best out of these ve rate adaptation solutions. ARF, AARF and CARA deliver almost the same throughput. RRAA outperforms RACD by 11% and the other algorithms by an average of 128% due to the e ectiveness of its adaptive RTS lter. On the other hand, as shown in Figure4.7, when there were hidden stations typical in a wireless communication environment, our RACD scheme performed best. Although RRAA was e cient in the In-range collision scenario, its ine ciency in the hidden station scenario shows that the adaptive RTS lter does not e ectively deal with collisions caused by hidden stations. RACD gave a 67% throughput enhancement compared to RRAA and 22% compared to CARA, which exhibited the third best performance. This throughput improvement proves that our proposed RACD algorithm can e ectively respond to both In- range and hidden collisions because of the CTS-to-self probing mechanism?s e ectiveness in di erentiating two types of collisions. 4.5.3 Impact of Adjusting Contention Window In order to evaluate the impact of modifying the DCF function by adjusting the Con- tention Window size, the same simulations were performed with only CTS-to-self mechanism without modifying Contention Window adjustments. As can be seen in Figures 4.8 and 4.9, in both cases, the scheme with Contention Window adjustment represented better through- put. The original RACD outperformed RACD without DCF adjustment by 64% and 14% for the In-range and hidden collision scenario respectively. In addition, it is interesting to see that RACD without DCF adjustment performed better in the hidden station scenario than in the In-range scenario by an average of 12%. 32 10 15 20 25 30 35 40 45 500 1 2 3 4 5 6 7 8 Number of Contending Nodes Mean Throughput (Mbps) RACD RACD w/o DCF adjustment Figure 4.8: In-range collision Scenario Comparison This nding con rms that the new Contention Window control scheme signi cantly improves the performance of our algorithm when hidden stations cause collisions. 4.6 Summary This chapter proposed a novel Rate Adaptation with Collision Di erentiation (RACD) algorithm for the IEEE 802.11 WLANs which reduces the e ect of variability in wireless channels and improves data throughput. Our new scheme takes advantages of the newly standardized CTS-to-self mechanism and Contention Window adjustment in DCF. Simu- lation results show that RACD achieved a signi cant performance improvement in general communication environments compared to existing rate adapting schemes. The utility of CTS-to-self for discriminating In-range collisions from hidden collisions is shown through our experiments. 33 10 15 20 25 300 1 2 3 4 5 6 Number of Contending Nodes Mean Throughput (Mbps) RACD RACD w/o DCF adjustment Figure 4.9: Both In-range and Hidden Collision Scenario Comparison Future work should include implementing and testing our scheme in a real WLAN environment. In addition, further research work should attempt to test and analyze how this scheme a ects other metrics such as fairness and global network throughput. By utilizing the CTS-to-self packets for distinguishing In-range collisions from hidden collisions, various applications can be enhanced for di erent purposes in various IEEE 802.11 WLANs. 34 Chapter 5 Aggregation Aware Rate Adaptation in IEEE 802.11n WLANs 5.1 Introduction With the growing demand for high bandwidth data transmissions, the IEEE 802.11n standard paves a way for a new era of high bandwidth in wireless local area networks (WLANs). The foremost enhancement over the previous standards is achieved by Multiple- Input Multiple-Output (MIMO), Channel Bonding, and Frame Aggregation (FA) & Block Acknowledgement (BlockACK). By utilizing multiple antennas for transmitting data, MIMO technology can improve the transmission reliability by sending duplicated signals (Spatial Diversity), or can expand network bandwidth by simultaneously transmitting independent signals in parallel (Spatial Multiplexing). In addition to MIMO, the new standard also doubles the network performance by com- bining two adjacent channels so that the participating stations use a wider 40MHz chan- nel bandwidth instead of the basic 20MHz channel bandwidth. While the enhancement by MIMO and Channel bonding is achieved by increasing the resource utilization, Frame Aggregation (FA) & Block Acknowledgement (BlockACK) improves the performance by amortizing the network protocol overhead. Instead of sending a single frame per protocol overhead, the 802.11n stations can transmit multiple frames with a single protocol header. These enhancements improve network throughput up to 600 Mbps at the physical layer in a 40MHz channel with the maximum of four streams, and o er 32 available transmission rates to choose from. Since there is no pre-de ned speci cation in the standard illustrating how to select the data transmission rate, it is essential to have an Rate Adaptation (RA) process which selects the appropriate transmission rate to the current channel quality in order to exploit 35 the bene t of this novel technology. A number of studies have been carried out with the goal of accomplishing the maximum network performance in varying channel conditions. Most of the rate adaptation schemes in the previous 802.11 standards, such as 802.11a, b, and g, focus on adjusting the Modulation and Coding Scheme (MCS) according to the channel quality; in contrast, the 802.11n rate adaptation algorithm should not only be able to adjust MCS, but also be able to determine the number of streams, identify channel bonding availability, and decide on the level of aggregation. Moreover, IEEE WGn is developing a new IEEE 802.11ac standard that further expands the concept of wireless interface of 802.11n by increasing the number of available streams to eight and utilizing wider channel bonding of up to 160MHz. Therefore, the number of degrees of freedom on Rate Adaptation is drastically increased. The most distinctive problem in the new standard compared to the legacy RAs arises from the Frame Error Ratio (FER) non-monotonicity [1], which means that there is a non- monotonic relationship between the transmitting data rate and FER. In Single Input Single Output (SISO) systems, the FER is usually in proportion to the data rate, i.e., transmitting at a lower rate guarantees few packet failures. However, due to the added data streams, the MIMO-enabled stations exhibit non-monotonic behavior under certain scenarios. Most of the MIMO-aware RAs focus on resolving this non-monotonicity resulting from added space of freedom. In addition to MIMO and Channel Bonding, the FA & BlockACK scheme is one of the key enhancement factors in the 802.11n standard. Much research has analyzed the impact of FA to leverage its bene t; however, a little work has been done on inter-relationships between FA and RA. This chapter evaluates the impact of FA from a di erent perspective of RA schemes and suggests the need for frame aggregation level control for RA algorithms. Then using an e cient way of probing enabled by frame-level adjustment, a new Aggregation Aware Rate Adaptation algorithm is designed and evaluated to balance trade-o s between maintaining stability and agility to channel dynamics. 36 Table 5.1: Comparison between 802.11n and 802.11ac Standards Standard MIMO Channel Available Max Streams Bonding Modulation Throughput IEEE 802.11n 1-4 20-80 MHz BPSK-64QAM 600 Mbps IEEE 802.11ac 1-8 20-160 MHz BPSK-64QAM, 256QAM 1300 Mbps The remainder of this chapter is organized as follows. The background of the topic is introduced in Section 5.2 with related work reviewed in Section 5.3. Section 5.4 gives an overview of the following research work. Section 5.6 reports the ndings to provide rationales behind the AARA algorithm which is detailed in Section 5.7. Detailed experiment results are presented in Section 5.8. Section 5.9 summarizes the chapter. 5.2 Background Following intensive e orts to enhance wireless network performance, the IEEE Working Group released new amendments to the existing 802.11 standards. While the best legacy standard has potential optimal throughput up to only 54 Mbps, the new standards such as 802.11n and 802.11ac are designed to transmit a maximum of 600 Mbps and 1300 Mbps respectively. These novel enhancements come from three representative new techniques: Multiple Input Multiple Output (MIMO), Channel Bonding, and Frame Aggregation. Ex- cept one level higher order modulation, which is 256 QAM, most of the other improvements over 802.11n result from the multiplication of resources, as shown in Table 5.1. This section brie y describes these three key MAC-layer enhancements, focusing on Frame Aggregation, which is key to achieving better performance with the proposed algo- rithm. 5.2.1 Multiple Input Multiple Output (MIMO) MIMO technology is the key underlying model of IEEE 802.11n architecture and lays the foundation of higher network performance for standard-compliant stations. It leverages 37 multiple antennas for both transmitter and receiver and takes advantage of the multipath ef- fect which is inherently perceived as one of the interferences. MIMO operates in two di erent modes, Spatial Diversity (SD) based on single stream (SS), and Spatial Multiplexing (SM) using multiple streams (MS). Spatial Diversity is the technology that allows corresponding stations to transmit and receive duplicated information through multiple streams to improve reliability and sustainability over longer distances. The diversi ed identical signals encounter di erent spatial structures and experience varied fading, so the receiving station is able to compensate for the defects by comparing two decoded signals. On the other hand, Spatial Multiplexing makes use of multiple antennas to send indepen- dent, separately encoded signals for better network performance. The network throughput can be easily multiplied by the number of streams the related stations utilize. Even though the current 802.11n standard speci es a maximum of four streams, increasing the available number of streams can be one of the simplest and most convenient ways to enhance network utilization, so the next generation 802.11ac standard allows for maximum of eight streams. 5.2.2 Channel Bonding Similar to the way that increasing the number of possible streams improves spectral e ciency, Channel Bonding expands the channel bandwidth for wider utilization of the channel medium. While the legacy 802.11 standards operate only 20MHz channel bandwidth, the 802.11n standard extends the operable bandwidth to 40MHz. Therefore, it theoretically doubles the data transmission rate by utilizing one more adjacent channel band; however, for backward compatibility with legacy standards, it also operates with 20MHz. 5.2.3 Frame Aggregation and BlockACK Even with the assumption of in nite data rate increase, the maximum potential through- put is known to be bounded at 50 Mbps due to protocol overhead by the analysis estimated in [46]. The key concept behind Frame Aggregation (FA) is reducing the frequency of wasted 38 0 5 10 15 20 25 300 5 10 15 20 25 30 35 40 45 50 Number of Aggregated Frames in an A?MPDU (nFrames) Header Overhead Ratio(%) Figure 5.1: Amortized Header Overhead according to Aggregated Number of Frames time incurred by MAC and PHY headers. As a result, the FA scheme is essential to achieve the target maximum performance speci ed in the standard. In general, the MAC header is shorter than data frames; however, since the standard requires the headers to be transmitted at the one of the lowest rates to ensure transmission reliability, the overhead caused by protocol header is relatively large in legacy standards. In order to reduce this overhead, the new MAC layer of the 802.11n standard combines multiple frames to amortize the cost of non-data transmission overhead. As can be intuitively perceived, the amortized overhead signi cantly decreases with the growth in the number of sub-frames of an aggregated packet. Figure 5.1 reveals that irrespective of the non-trivial protocol overhead, as the level of aggregation increases when the data rate is 104 Mbps, the ratio of the packet header transmission time to actual data transmission time drops signi cantly from 48% to only 1.5%. 39 IEEE 802.11n speci es two di erent aggregation mechanisms as illustrated in Figure 5.2. First, Aggregated Mac Service Data Unit (A-MSDU) concatenates multiple MAC Data Ser- vice Units (MSDUs) for a single Mac Protocol Data Unit (MPDU). A sub-frame header and padding bytes are attached to each MSDU and a collection of sub-frames completes one A-MSDU, then a common MAC header Frame Check Sequence (FCS) is added to the end. Though A-MSDU maximizes the spatial e ciency even better than A-MPDU, due to the fact that each sub-frame does not have an individual FCS to check and correct possible errors, a single point bit failure within a sub-frame can corrupt the entire aggregated A-MSDU. This problem explains why A-MSDU is not robust enough for time varying, error-prone channels. On the other hand, as a dominant di erence from A-MSDU, a sub-frame in an Aggre- gated MAC Physical Data Unit (A-MPDU) has an individual MAC header and FCS, as depicted in Figure 5.2. Although A-MSDU exhibits higher analytic saturation throughput than A-MPDU structure, due to the vulnerability to channel dynamics, A-MPDU equipped with better protection is more appropriate in practice. In the Frame Aggregation scheme, the Block Acknowledgement (BlockACK) mechanism enables the aggregated MPDUs to be acknowledged by a single ACK packet instead of sending a separate ACK for each MPDU. Since the BlockACK contains a 64 bit long data structure where each bit represents the individual status of an MPDU, which is either success or failure, both A-MSDU and A-MPDU combines a maximum of only 64 sub-frames. 5.3 Related Work In addition to MIMO RAs introduced in Section 2, this section elaborates a few rep- resentative MIMO RAs used for evaluation of the newly proposed AARA algorithm and introduces research e orts on Frame Aggregation. 40 Figure 5.2: Aggregated Frame Structure: A-MSDU (Left), A-MPDU (Right) 5.3.1 MIMO-aware Rate Adaptations Thanks to the new features introduced in the IEEE 802.11n standard, MIMO-enabled Rate Adaptation algorithms have an array of choices in deciding the best option. RAMAS [30] divides these design choices into two categories, modulation group, and enhancement group, and each group employs an independent set of rules to determine the best option inside each group. The modulation group only takes modulation type and coding scheme into consideration so that a monotonic relationship between FER and MCS indices can be assumed. The modulation group keeps track of the number of success, failures and retried MPDU frames for 30 MPDU frame transmissions. It decreases the group index either when the number of retried frames is more than the number of successful transmissions or when the error rate is less than a pre-de ned credit value. Based on the guided parameters, it decreases the rate option within the same modulation group by one whenever there are six frame errors out of 30 transmitted frames. For rate escalation, it employs a credit-based routine. A credit is earned when the error ratio is less than 20%, and RAMAS increments the rate when the credit reaches 10. 41 The enhancement group is independent from the modulation group and only deals with the additional features for the new amendment, such as the number of streams, guard in- terval, and channel width. The enhancement group adjustment focuses on deciding whether the current link quality accommodates Spatial Multiplexing transmission based upon Frame Error Ratio (FER). The open-source Atheros 9K Rate Adaptation (Ath9K RA) [12] is built in the device- drivers for the popular Atheros network interface. It is a MAC-layer metric-based, throughput- based statistical RA algorithm. First, Ath9K RA picks up the valid rate set out of available MCS rates so that they are linearly sorted by available bandwidth. For example, it chooses only 10 data rates out of 16 candidates available in two-stream MIMO adapters without channel bonding. Ath9K RA sends out a probing packet periodically. Upon measuring the Frame Success Ratio (FSR) which is de ned as the ratio of the number of acknowledged MPDUs to the total number of transmitted MPDUs for a speci ed time interval, Ath9K RA computes throughput for the probing rate by multiplying the FSR and potential bandwidth of the rate. Note that FSR is maintained by the popular Exponential Weighted Moving Average (EWMA) routine to re ect partial performance history. The best performing rate which provides highest throughput is chosen from among the valid candidate rate set. This algorithm also utilizes Multi-Rate Retry (MRR) for adapting short-term extensive channel dynamic. The four available slots in MRR are lled with the next four sequentially lower rates. Minstrel HT [13] is the upgraded version taking the place of Minstrel for the IEEE 802.11n standard. Similar to Ath9K RA, it constructs MCS rate groups with varying num- bers of streams and channel width, probes the channel periodically, collects MAC-layer statistics, calculates throughput, and makes the appropriate rate decision. However, Min- strel HT utilizes the full rate set to take advantage of trade-o s between a Single Stream (SS) mode, higher modulation options and Double Stream (DS) mode lower modulation options. 42 In addition, it attempts to probe randomly chosen rates instead of sampling the next higher rate. The throughput for Minstrel HT is predicted precisely based on various proto- col overheads such as DIFS, transmission time according to the current rate and protocol headers. The noticeable di erence is the usage of MRR chain. It puts the best and second best throughput rates in the rst and second slots in the chain respectively, and for the third slot, uses the stable rate option which shows the highest successful rate in the SS mode. 5.3.2 Research on Frame Aggregation As discussed in Section 5.2, the Frame Aggregation (FA) scheme has recently been introduced in the IEEE 802.11n standard in an e ort to reduce the frequency of transmitting protocol overhead. Although there are many studies of FA in the literature, many of them [47, 48, 49] focus on exploring a complementary usage between the two aggregation schemes A- MPDU and A-MSDU. B. Ginzburg and A. Kesselman [49] formulated an analytic model to estimate the poten- tial achievement of each aggregation solution. Additionally, D. Skordoulis et al [47] proposed a hierarchical combination of A-MPDU and A-MSDU schemes for channel e ciency. A sim- ple adaptive scheduler proposed by Selvam T and Srikanth S [48] dynamically switches the type of aggregation scheme according to relevant channel metrics and adaptively determines the level of aggregation. Rather than adapting the level of aggregation, an adaptation algo- rithm was proposed in [50] to nd the optimal frame size in an A-MPDU packet for various channel environments. Whereas the above approaches focus on aggregation schemes alone, there have been few research attempts to exploit the bene ts of controlling Frame Aggregation over Rate Adaptation. Xin He et al. [51] presented an adaptation algorithm which jointly adjusts data rate and the size of individual frame size in an A-MPDU packet to achieve potential optimal throughput. M. Kim and C. Choi [52] suggested using a part of MPDU frames in 43 an aggregated packet for probing the link quality in Rate Adaptation and proposed a rate adjustment direction to overcome the non-monotonic problem of MIMO RA. In [44], FA is leveraged to di erentiate the basic causes of frame failures, which are In-range collision, hidden station collision, and channel disorder. This study examines and analyzes both cases for an entire A-MPDU failure and partial MPDU frame loss and designs and evaluates a Hidden node Detection (HD) algorithm by simulative study. MiRA [1] is the rst practically implemented rate adaptation providing insight into the promising relationship between RA and FA. This study found that higher aggregation level does not always guarantee better performance due to the responsiveness to dynamic channel variation, and it examined the e ects of frame loss on the number of aggregating frames in A-MPDU. 5.4 Overview In order to address the problems listed in Section 3.1 speci cally from the perspective of Frame Aggregation, a case study was carried out with well-known existing RAs (Minstrel HT and Ath9K RA). The goal is to provide rationales for the algorithm design provided in Section 5.6 by identifying which design factors a ect the performance of RA schemes and how those factors lead to performance variation. All experiments were conducted with Linux-based equipments over Atheros chipset. Some standard-compliant modi cations were made over the Compat-wireless driver to print out statistics in the 802.11n MIMO setting. Iperf [53] was used to collect data and all results were averaged over ten attempts, excluding the best and worst cases. First of all, the meaning of retransmission under Frame Aggregation scheme was re- examined and the probability of A-MPDU failure over di erent numbers of aggregated frames was analyzed and veri ed by experiment results. 44 The in uence of the Multi-Rate Retry (MRR) mechanism over the FA mechanism is investigated in Section 5.6.3. Although the inherent goal of MRR is to provide extra pro- tection for short-term channel dynamics, MRR inadvertently causes performance limitation when it is used with the Frame Aggregation scheme. In general, existing RAs estimate the current channel by attempting sample packets for probing. Two legacy probing mechanisms of the existing RAs are reviewed in Section 5.6.1. Problems with these probing schemes are identi ed and a possible solution is proposed based on the capability to control the level of aggregation. In Section 5.6.4, the impact of congestion over Frame Aggregation is described. Di er- ences in network throughput and retransmission ratio are illustrated for di erent congestion scenarios. Based on the observations from the case study, a new rate adaptation algorithm, called Aggregation Aware Rate Adaptation (AARA), is described in Section 5.7. This section ex- plains a detailed procedure of state transition for frame aggregation control and describes an adaptive probing scheme which can e ciently estimate the channel while avoiding the over- head. It then introduces a collision avoidance mechanism of AARA based on the discussion of A-MPDU retransmission. The performance results from extensive experiments show that the proposed AARA outperforms the existing RAs. The throughput gain varies from 7.8% to 473.2% in various experimental settings where the channel qualities are di erent. Performance is enhanced by analyzing the statistics collected, better utilizing of FA, and choosing better rates based on an e cient probing scheme. 5.5 Experiment Methodology This section introduces the experimental platform for the following case study and per- formance evaluation, including hardware and software setup, di erent experiment scenarios, and various performance metrics. 45 In this section, the experimental platform regarding hardware and software setup, dif- ferent experiment scenarios and various performance metrics are introduced in detail which are used for the following case study and performance evaluation. 5.5.1 Experimental Platform All experiments presented in the following sections were carried out with a Linux-based programmable platform equipped with Atheros 2.5/5 GHz MIMO-enabled chipset, which can support 16 MCS indices with a maximum of two streams. The transmission rate can reach up to 130 Mbps when used without channel bonding. For the access point, Hostapd [54] was installed in a MSI mini-computer [55] for the programmable platform operating in 802.11n with single stream (SS)/multiple streams (MS) modes being enabled. Among the two aggregation options, A-MPDU and A-MSDU, only A- MPDU scheme is supported with BlockACK functionality and Channel Bonding operation was not enabled in the tests. Three laptops were used in di erent scenarios as transmitters, and contending stations. Fedora 15 with Linux kernel 2.6.43 was built on each node and a stable version of the Compat- wireless device driver [56] was installed for wireless network communication. Iperf [53] was used to generate saturated back-to-back A-MPDU packet streams in order to estimate the maximum available network throughput. Each A-MPDU packet contained a number of 1500 byte frames based on the transmission rate. Four di erent RA algorithms were tested and compared in the following sections. The widely-used Minstrel High Throughput (Minstrel HT) and Atheros 9000 (Ath9K) RA are embedded and initially available in the Compat-wireless driver kit. In addition, due to its simplicity and clarity, the RAMAS was chosen as one of the state-of-the-art MIMO RAs published in recent years. The RAMAS algorithm was implemented and validated through a wide range of tests. Finally, the Aggregation-Aware Rate Adaptation (AARA) was also 46 Table 5.2: Experimental Parameters Parameter Value Operating System Fedora 15 Kernel Version Linux Kernel 2.6.43 WLAN Card Atheros AR9300 Device Driver Compat Wireless 3.6.8.1 Wireless PHY Standard IEEE 802.11n Channel Bandwidth 20 MHz Available MCS Indices 0 (6.5 Mbps) - 15 (130 Mbps) Frequency Bands 2.437GHz (Channel 6) / 5.2GHz (Channel 40) Access Point Module Hostapd 7.3 Packet Generator Iperf 2.0.5 implemented upon the driver kit and the performance was analyzed and compared with the other three RAs. The detailed parameters for experimental platform are listed in 5.2. 5.5.2 Experimental Scenario Due to the complication of variable wireless channel interference, it is a challenge to replay the same channel condition so that the performance of di erent RAs can be fairly compared. In order to clear out unexpected interference e ects and ensure a controlled environment setup, all the experiments were performed with 5GHz band around midnight on the weekend when no other signal was identi ed by a Wireshark [57] packet sni er equipped with the AirPcap [58] network card for enabling 802.11n packet capturing. In order to estimate the rate decision accuracy for diverse channel states, the experiments were conducted in di erent environments, each of which is characterized di erent channel conditions. First, a set of tests were carried out in the middle of plain terrain to emulate an environment with minimized multi-path fading e ect. Another set of experiments were performed in a campus building representing a typical o ce environment. The oor plan of the building is illustrated in the 5.3 and di erent locations of the client node are marked with letters A to F. In order to analyze the impact of contention, In-range nodes were placed within a range where they could sense each other?s signal. For a hidden station scenario, the hidden node 47 Figure 5.3: Experimental Floor Plan was placed not only behind a concrete wall but also on a di erent level where there were minimized re ecting objects for multipath e ect. Most of the signal was blocked except for occasional successes veri ed by the sni er. The contention scenario setup (In-range and hidden) is illustrated in Figure 5.4. Since di erent RAs cannot be executed simultaneously, it was important and challeng- ing to create a con guration where wireless equipment could experience the same channel dynamics especially in mobile environment. For fair comparison between RAs as possible, in the mobile scenario, a laptop was placed on top of a rolling chair and was moved toward the AP in increments of 25ft as shown in Figure 5.5. Finally, a set of experiments was conducted in the student center speci cally to examine the usage of MRR chain. In the student center, the link quality changed dramatically due to contention and moving people. 48 Figure 5.4: Contention Scenario Setup Figure 5.5: Mobile Scenario Setup 49 5.5.3 Performance Metric By enabling per-A-MPDU packet control functionality, most of the available MAC layer traces were collected and printed out to the Linux system log upon receiving BlockACK pack- ets. These layer traces included Received Signal Strength Indicator (RSSI), the di erence of RSSIs between multiple antennas, transmission rates, the number of hardware retransmis- sions including Multi-Rate Retry (MRR) chain information, BlockACK bitmaps, RTS/CTS control packet usage, and frame payload length. This information was then passed to a parsing program implemented to compute statistics such as Frame Success Ratio (FSR) and network throughput. The FSR is simply calculated as the following formula. FSR = (nSuccess 100)nFrames (5.1) nBad and nFrames imply the number of bad frames and the total number of frames in an A-MPDU packet respectively. Note that in contrast to previous work, the retransmission counts are not included in the formula. The detailed rationale behind this decision will be provided in Section 5.6.2. The network throughput is de ned as Throughput = (TnFrames TnBad) LdatT overhead +TMPDU (5.2) where TnFrames and TnBad represent the total number of frames and total number of failed frames during transmission time respectively. Toverhead is the sum of 802.11n protocol overhead which is represented as: Toverhead = DIFS +Tbf +Tphy +SIFS +Tlphy +TBlockACK (5.3) where detailed notations are described in 5.3. 50 Table 5.3: Variables used in Retransmission Cost and Goodput Calculation Variable Value DIFS 34:0 s SIFS 15:0 s Average Back-o Delay (Tbf) 63:0 s Mixed-mode PHY Preamble and Header Time (Tphy) 44:8 s Legacy-mode PHY Preamble and Header Time (Tlphy) 24:0 s BlockACK frame time (TBlockACK) 11:3 s A-MPDU MAC Header Length (Thdr) 34bytes In addition, TMPDU includes aggregated MPDU frame header and data transmission time as depicted in the following equations. TMPDU = TnFrames (Thdr +Tdat) (5.4) In contrast to the network throughput de ned above, the proposed algorithm uses a di erent metric, A-MPDU goodput, for performance measurement based on the computation model in order to simplify calculation and reduce computational overhead as follows: GA MPDU = Thputmaxr FSR (5.5) Thputmaxr represents the maximum per A-MPDU throughput associated with the data rate r, which can be pre-calculated with the assumption of no frame loss during A-MPDU packet transmission. FSR is Frame Success Ratio introduced in formula 5.1. Table 5.4 lists the maximum possible nFrames and Thputmaxr according to transmission rates available in this study. 5.6 Case Study As mentioned in the previous sections, FA and BlockACK are the key mechanisms in the 802.11n standard to enable high network throughput. However, since most of the current 51 Table 5.4: Maximum Possible nFrames and Maximum per A-MPDU Throughput (Thputmaxr ) MCS # of Modulation/ Data Rate Max Thputmaxr Index Streams Coding Rate (Mbps) nFrames (Mbps) 0 1 BPSK 1/2 6.5 1 5.8 1 1 QPSK 1/2 13 4 10.6 2 1 QPSK 3/4 19.5 6 17.7 3 1 16QAM 1/2 26 8 23.8 4 1 16QAM 3/4 39 12 35.4 5 1 64QAM 2/3 52 17 47.6 6 1 64QAM 3/4 58.5 18 54.2 7 1 64QAM 5/6 65 20 60.1 8 2 BPSK 1/2 13 4 10.6 9 2 QPSK 1/2 26 8 23.1 10 2 QPSK 3/4 39 12 35.4 11 2 16QAM 1/2 52 17 47.6 12 2 16QAM 3/4 78 25 71.1 13 2 64QAM 2/3 104 32 95.4 14 2 64QAM 3/4 117 32 108.1 15 2 64QAM 5/6 130 32 119.4 52 RA algorithm designs do not take FA into consideration, they cannot make fully use the potential bene ts of the new enhancement. In this section, a preliminary case study is performed to understand the impact of Frame Aggregation on rate adaptation using a few xed rates and Minstrel HT, which is one of the most representative and popular MIMO RA algorithms. Various RA algorithm design options such as A-MPDU retransmission, Multi-Rate Retry, contention avoidance, and channel probing were re-evaluated from the perspective of Frame Aggregation. The following questions are investigated in detail. What are the limitations of the current probing mechanism with single short packets to obtain more reliable statistics? How can the limitations be resolved with consideration of Frame Aggregation? How is the meaning of retransmission in an aggregated packet transmission di erent from a single packet transmission and how does it have to be handled? Based on the answer to the above question, how does RA use Multi-Rate Retry scheme for better adaptation? How can contention-induced packet losses be distinguished from fading-induced losses in the aggregation-enabled scheme? How can the RA detect the multiplexing structure which determines whether to use a low-modulation multiple stream rate or a high-modulation single stream rate? 5.6.1 Probing with A-MPDU Popular RA solutions examine whether other data rates (typically higher than the cur- rent option) are suitable for the existing channel performance. If the probing is successful or results in better performance, then the rate moves upward; otherwise, it is downgraded. In contrast to RA algorithms in the legacy standard, MIMO RAs can probe the channel using either (1) a single frame testing packet or (2) a normal A-MPDU packet. Minstrel HT 53 Table 5.5: Probing Attempt Distribution and Success Ratio on Each Rate Option Data Rate Total Success Failure FSR Rate Usage (Mbps) Count Count Count Distribution 6.5 3 3 100% 13 8 8 100% 19.5 4 4 100% 26 9 9 100% 39 6 6 100% 12.34% 52 7 7 100% 72.41% 58.5 3 3 100% 65 N/A N/A N/A N/A 78 19 15 4 78.95% 15.25% 104 25 14 11 56% 117 34 8 26 23.53% 130 34 0 34 0% Total 152 77 75 50.66% and Atheros RA send a 257 byte-long single short packet to determine whether the sample rate is suitable for the channel condition. The statistics are collected for a speci ed time interval, and then the best rate for the next transmission is chosen based on the estimated throughput. However, evaluating channel status from a single short packet is susceptible to overestimation due to the relatively high Frame Success Ratio (FSR) of the next higher option as pointed out in [9]. Table 5.5 shows the distribution of probing attempts and rate usage collected using Minstrel HT RA in the o ce setting. Given that the best performing rate is at least lower than 78 Mbps, as can be identi ed intuitively, sub-optimal rates such as 104 Mbps and 117 Mbps shows non-negligible success ratio in the experiment. Since the robustness of the shorter packet leads to a better success ratio, even inappropriate rate options may have more than a 50% chance of success, a limitation which can confuse the RA process. Furthermore, the single-frame packet probing has another defect around Frame Aggre- gation. When the aggregation module in the driver is triggered to send a probing packet, it 54 instantly stops and closes the current aggregation process and places a single probing packet into the transmission queue. This process further degrades the utilization of the Frame Aggregation and negatively impacts the performance. A few studies such as MiRA [1] and WRA [28] have tried sampling with the normal A-MPDU packet; however, the cost of full utilization of Frame Aggregation may give rise to severe loss when the sampling rate is un- suitable for the current channel. Consequently, the level of aggregation should not be too high or too low. To con rm the claim, another set of experiments was conducted in the o ce environment with no interference as veri ed by sni er. Instead of using a single short frame, multiple frames were aggregated into sampling packets. Figure 5.6 illustrates the network throughput (in Mbps) against the number of frames in a probing packet. Generally, the performance appeared to be in proportion to the number of frames in probing packets, but the throughput dropped when six frames were used for probing in this experiment. As other results show the same trend with little di erence of converging level, it can be concluded that the performance gain of multiple-frame probing increases to a certain level, then begins to converge and decreases. On the other hand, random probing in RA design also leads to performance degradation. As can be observed in Table 5.5, the data rate of 65 Mbps was not tried at all during the total of 152 probing attempts; consequently, the Minstrel HT RA does not use the 65 Mbps option, which may be the optimal on this setup. Similarly, the probing attempt of 58.5 Mbps was not su cient for RA to collect required statistics. Therefore, 72% of data transmissions were sent at 52 Mbps, which is seemingly more than two steps lower than the optimal rate. In summary, RAs that adjust rates using short-term statistical analysis and random probing cannot avoid misjudgment and su er from non-negligible performance degradation due to the distortion of the probing result. 55 Figure 5.6: Network Throughput with Varying Number of Frames in a Probing Packet Original 2 3 5 6 750 55 60 65 70 75 80 85 90 95 100 Number of Frames in a Probing Packet Throughput (Mbps) 5.6.2 A-MPDU Retransmission A-MPDU aggregates multiple numbers of MPDUs into a single packet, as overviewed in Section 5.2. The maximum number of MPDUs in each A-MPDU (called aggregation level or nFrames) is limited by speci ed total payload length (65,535 bytes) and by BlockACK, which can only acknowledge less than 64 MPDU frames based on the standard. The IEEE 802.11n standard additionally speci es the BlockACK sliding Window (BAW), which contains a range of sequence numbers to be transmitted in the TX queue. This window moves forward as the involved MPDU sequence numbers are acknowledged. If the rst MPDU in the BAW is lost and needs to be retransmitted, the aggregation level of the following A-MPDU is limited because the BAW is not able to move forward to hold another MPDU in the queue. The vendor implementation can further limit the aggregation level because the detailed aggregation logic is not speci ed in the standard. The Atheros network adapter used for this study is in compliance with regulatory 4ms transmission opportunity (TXOP) in 5 56 GHz band operation and the possible number of frames in an A-MPDU is further restricted according to the transmission rate involved. For example, the single-stream MCS 0, which sends data at 6.5 Mbps, cannot hold more than a single MPDU in an A-MPDU packet. On the other hand, the MIMO-enabled double stream MCS 15, which has 130 Mbps data rate, can aggregate 32 MPDUs due to the shorter transmission time of each MPDU, as listed in Table 5.4. A-MPDU retransmission occurs when all of the frames in an A-MPDU packet have been lost (called A-MPDU failure). This situation is di erent from an individual MPDU retry where some of the MPDU frames in an A-MPDU packet are not successfully decoded by the receiver upon reception of a BlockACK. In case of individual MPDU failures, a transceiver simply duplicates and inserts the lost MPDUs into the next available A-MPDU packet. On the other hand, A-MPDU failure takes place when either a transmitter fails to receive a BlockACK from the receiver within a speci ed time duration or when the received BlockACK indicates that all the frames have been lost. As can be easily perceived, A-MPDU failure has more impact on the network performance than individual MPDU retry. A-MPDU failure can be attributed to two representative reasons. First, all of the MPDU frames can be corrupted either by channel disorder or other interference. However, in contrast to the legacy standards without FA functionality where a single MPDU failure leads to a packet retransmission, a sudden channel dynamic which causes an MPDU frame error is rarely sustained for the entire A-MPDU transmission duration if the transmission rate is within a reasonable range. Second, A-MPDU failure can result from simple A-MPDU physical header corruption. Only short-term disruption can cause the A-MPDU failure. Because the standard mandates that the PHY header to be transmitted with the lowest rate available to ensure safe deliv- ery, the header is rarely corrupted by channel degradation except in some extreme cases. Furthermore, since the occupation of the header in an entire A-MPDU packet diminishes 57 0 5 10 15 20 25 300 10 20 30 40 50 60 70 80 90 100 nFrames Probability of A?MPDU failure (%) BER=10E?3 BER=13E?3 BER=16E?3 BER=19E?3 Figure 5.7: A-MPDU Failure Probability over nFrames signi cantly as the aggregation level grows as shown in Figure 5.1, there is less chance of A-MPDU failure by header loss due to channel disruption. The probability of A-MPDU failure according to Bit Error Rate (BER) regarding the channel dynamic can be expressed as PA MPDUfailure = nFramesY (1 (1 Pbit)L) (5.6) wherePbit is the BER andLis the total length of A-MPDU including various protocol headers in bits. With this formula, Figure 5.7 presents the in uence of nFrames on A-MPDU failure probability under di erent bit error rates. Noticeably, if the nFrames are greater than 20, the probability of A-MPDU failure caused by BER is lower than 30% even in erroneous channels. In other words, there is less chance of losing the entire A-MPDU packet, assuming FER of the current data transmission rate is within a normal range. Therefore, it can be assumed that an A-MPDU failure is mainly caused by header corruption. Table 5.6 presents 58 Table 5.6: Rate Distribution, nFrames, Retransmission Ratio, FER Data Rate nFrames RET Ratio (%) FER 117 Mbps 32 1:97% 0:06% 130 Mbps 32 2:71% 0:54% 130 Mbps 24 3:09% 0:71% the A-MPDU retransmission ratio and FER with varying transmission rate and nFrames set during the experiment where two stations were located in proximity, the sni er veri ed no contending station, and a stable channel was guaranteed by a plain terrain with no re ecting object around. As expected, the A-MPDU retransmission ratio scales with data rate, but is inversely proportional to nFrames. In summary, considering that the PHY protocol header is rarely corrupted by the chan- nel fading due the robustness of low rate for header transmission (usually 24 Mbps), it is reasonable to assume that A-MPDU failure is caused by other factors such as collisions and internal data queue over ow. Since these factors are not related to channel quality dete- rioration, the RA algorithm is required to tolerate such cases and keep the current data rate. 5.6.3 Multi-Rate Retry Scheme with Frame Aggregation Designing an RA algorithm gives rise to two interrelated design challenges. One is de- termining a data rate for the rst attempt, and the other is selecting the number of retrans- mission attempts when the rst attempted rate fails. Multi-Rate Retry (MRR) functionality is available in all the 802.11 PHY-compliant devices. Up to four di erent rates and retransmission counts can be chained in the MRR de- scriptor. The MRR chain is represented as (r0=c0), (r1=c1), (r2=c2), (r3=c3) where r0 r3 represent data rates, and c0 c3 represent packet retransmission counts corresponding with 59 each rate respectively. The sum of all counts (c0 + c1 + c2 + c3) de nes the retransmission limit after which the packet is discarded. The MRR mechanism improves responsiveness and reliability for transient short-term channel uctuation by re-sending the lost packets at lower transmission rates in order; how- ever, with FA, the MRR mechanism a ects the performance in a di erent way. Due to fairness in accessing wireless channel medium, the Atheros driver imposes a 4ms limit for maximum duration, which means that once a transmitting node obtains the channel access and gets a transmission opportunity, the slot is open for a maximum of 4ms. Hence, while the original maximum A-MPDU aggregation level is limited to 64 by the available informa- tion of BlockACK bitmap, it is further limited by the transmission rate chosen as shown in Table 5.4 to ensure an equivalent amount of air transmission time. This restriction can provide RA with a useful opportunity to control aggregation level in A-MPDU. The maximum nFrames of the lowest rate in the MRR chain imposes a limit on the current level of aggregation in the next A-MPDU, and therefore RA can easily control the aggregation level by simply putting the lower rate in the last available slot in the MRR chain. Even though MRR-based controlling has the shortcoming that it can be set for only the pre-de ned and restricted number of aggregation levels listed in Table 5.4, controlling the level of aggregation using MRR provides another level of protection against sudden channel deterioration. Since the probability of retransmission drops signi cantly in proportion to aggregation level, as discussed in Section 5.6.2, the depth of MRR chain, which means the number of A-MPDU retransmission counts of each rate, should be re-evaluated as well. From the experiments in the student center where the channel changed rapidly due to contention and moving people, the chance of using the second rate in the MRR chain ranged only from 0.2% to 5.9%, and only 0.8% of data was transmitted using the third rate. As a result, it is not necessary to have more than three rates speci ed in the chain. 60 5.6.4 Impact of Congestion In order to examine in detail the impact of collision on aggregated packet transmission, two sets of experiments were performed with In-range and hidden stations respectively as shown in Figure 5.4. Minstrel HT was used for Rate Adaptation algorithm and channel fading and multi-path e ects were minimized and veri ed with a sni er. Figure 5.8 illustrates throughput and A-MPDU retransmission ratio under an In-range contention scenario. The A-MPDU retransmission ratio is de ned as retransmission counts divided by total transmission counts. The contending In-range station used two xed rates, 65 Mbps and 130 Mbps. As the gure shows, the throughput dropped signi cantly when stations shared the channel medium. Notice that the performance was better when the contending station used the faster transmission rate (130 Mbps) than when it is used the slower rate (65 Mbps). This result occurred because the slower rate transmission occupies the channel longer; hence, the transceiver has fewer transmission opportunities. In contrast, it is interesting that the retransmission ratio was barely a ected by contending stations data rate but its frequency increased by 7.6 times due to collisions. It can be easily perceived that In-range collision occurs only when more than two transmitting stations are assigned to the same back-o slot, and the chance of being in the same slot is irrelevant to the transmission rate. The average aggregation level of three cases ranged from 22.6 to 23.5. Even though the results do not show a distinct di erence because of the insu cient level of contention, the claim still holds that more congestion leads to better utilization of aggregation due to the delay in channel access. With In-range stations, a collision occurs only when multiple stations are assigned to the same back-o slot, as explained in Section 4.2. Since involved stations start transmissions at the same time, there is a high probability that the header of the transmitting packet will be corrupted and trigger an entire A-MPDU retransmission. In other words, the In-range 61 Figure 5.8: A-MPDU Retransmission, Average nFrames, and Throughput over Di erent Congestion Scenarios A?MPDU RET Ratio (%) nFrames Throughtput (Mbps)0 10 20 30 40 50 60 70 80 90 100 No competitor 65Mbps competitor 130Mbps competitor collision may not cause a partial loss within the aggregated packet. This claim is proved by the fact that AFER of each A-MPDU transmission was negligible in the experiments. In contrast, hidden station collision can a ect both the header and body of an A-MPDU packet. Hence, it is di cult to di erentiate hidden collision traces from fading-induced error; however, due to the channel obliviousness of the hidden station, the erroneous status is sustained for a certain time interval and causes a burst of packet error. Figure 5.9 illustrates retransmission ratio over total number of A-MPDU transmissions, as the x axis indicates the number of consecutive A-MPDU retransmissions. As the gure shows, congestion triggers signi cant A-MPDU retransmissions, and the hidden station scenario leads to the highest number of retransmissions. In addition, the consecutiveness of A-MPDU retransmission can be an important noti er of the existence of hidden stations. 62 Figure 5.9: Consecutive A-MPDU Retransmissions over Di erent Scenarios 1 2 3 4 5 6?1 0 1 2 3 4 5 6 7 8 9 10 11 12 Number of Consecutive A?MPDU Retransmissions Distribution of Consecutive A?MPDU Retransmissions No contention In?range contention Hidden contention 5.6.5 Multiplexing Structure In contrast to Single Input Single Output (SISO) systems, the performance of the next higher bandwidth rate in a MIMO system does not always imply a higher network throughput because a MIMO system has multiple streams available which add another dimension to the decision plane. Making the best rate choice depends not only on modulation and coding scheme but also on the number of streams. Multiplexing structure is a channel condition metric upon which the link quality is su cient to allow the transceiver to transmit with multiple streams. With a multiplex- ing structure, the RA can prioritize a lower modulated multiple stream rate over a higher modulated single stream rate. Figure 5.10 depicts two sets of experiment results that show throughput performance and Frame Success Ratio (FSR) over di erent MIMO operation modes. While the Double Stream (DS) mode wins in the left, the Single Stream (SS) mode results in better performance even though the DS MCS 12 rate has a higher bandwidth and 63 Figure 5.10: Throughput and FSR Comparison under Di erent MIMO modes Throughput (Mbps) FSR (%)0 10 20 30 40 50 60 70 80 90 100 MCS 5 (52Mbps/SS/64QAM) MCS11 (52Mbps/DS/16QAM) Throughput (Mbps) FSR (%)0 10 20 30 40 50 60 70 80 90 100 MCS 7 (65Mbps/SS/64QAM) MCS12 (78Mbps/DS/16QAM) lower modulation scheme. Since the receiver of the second experiment was placed in a steel box and the received RSSI value was lower than a normal range, the channel did not allow DS transmission, that is, the multiplexing structure did not exist. Identifying whether the channel has the multiplexing structure is a non-trivial challenge. In spite of unpredictable uctuation, RSSI di erence between multiple antennas can be one of the potential metrics, as shown in ARF-HT [29]. In order to verify the quality of the metric, another experiment was performed under di erent scenarios. One of the two antenna was disabled on either side of the transmission pair. As shown in Figure 5.11, when the receiver?s antenna hurts the multiplexing structure, it does not su ciently clarify the situation; however, when the transceiver side?s antenna is disabled, the value of RSSI di erence clearly indicates the problem. Therefore, even though it is di cult to identify the receiver side?s problem, the RSSI di erence metric is a useful metric to detect a transceiver- side defect a ecting the multiplexing structure. 64 Figure 5.11: RSSI Di erences in Various Scenarios Normal Bad Transceiver Bad Receiver0 5 10 15 20 25 30 RSSI Difference 5.7 Aggregation Aware Rate Adaptation (AARA) In this section, a novel new rate adaptation algorithm called Aggregation Aware Rate Adaptation (AARA) is proposed based upon the observations and ndings from the case study. AARA is a standard-compliant open-loop RA scheme that involves only the trans- mitter for the best rate decision process. The design of AARA addresses the following issues: (1) How to estimate the channel and how to nd the best-performing transmission rate for the current channel, (2) How to keep the agility to the channel dynamic while maintaining stability in adaptation, (3) How to di erentiate and adapt to In-range and hid- den collision-induced interference. The following sub-sections provide detailed discussions of these questions. 5.7.1 Best Transmission Rate Selection AARA is a goodput-based statistical RA using probing for channel estimation. Upon reception of a BlockACK, the AARA begins to collect a speci ed number of A-MPDU packets and counts numbers of di erent variables listed in Algorithm 1. Based on the indications in BlockACK, Frame Success Ratio (FSR) is then calculated as discussed in Section 5.5.3. 65 Notice that the retransmission counts are not included in the FSR calculation, a unique di erence from previous research [1, 28]. This di erence is based on the assumption that channel deterioration not only causes A-MPDU retransmission, but also corrupts a part of an aggregated packet. Hence, if channel fading causes packet losses, it also a ects the FSR, which is computed without the retransmission counts. After obtaining FSR, AARA follows di erent procedures according to the current state. Figure 5.12 explains the transition condition between four di erent states. NORMAL: typical transmission status where a transceiver aggregates the maximum possible frames into an A-MPDU. PROBE: probe frame transmission status where a transceiver limits aggregation level for the probing packet. UP: rate increasing status where a transceiver increases data rate by one step and limits aggregation level for a speci ed interval upon successful probing. DOWN: prior phase before decreasing rate where a transceiver stays in the same rate, but limits aggregation level for a speci ed interval. Starting from NORMAL state, once the goodput of the last sampling window is greater than maximum potential goodput of the rate one step lower, AARA initiates channel probing, and then FSR of the probe packet is compared to an A-MPDU success threshold ( ) to determine whether the probing is successful. If the probing satis es the threshold, the current state is switched to UP state, otherwise, it turns back to NORMAL state. When the goodput of the last sampling window is less than maximum potential goodput of the rate one step lower in NORMAL state, the state changes to DOWN state before switching to a lower data rate. The A-MPDU success threshold ( ) is an important parameter to make the nal decision on rate increment in the PROBE status. In this dissertation, this value is set to 90% based upon the heuristics. 66 Figure 5.12: State Transition Diagram The rationale behind the state transition is that RA should be agile to short-term channel gain while maintaining stability to short-term channel disturbance. This balance is achieved by controlling frame aggregation level of A-MPDU packets before rate change. To this end, the Min nFrames is de ned as the minimum number of frames in an A-MPDU which can achieve the same throughput which a rate one step lower can accomplish with its Max nFrames listed in Table 5.4. Mid nFrames is de ned as the median value of the Max nFrames and Min nFrames. This value is used for transmission on UP and DOWN states, while Probe nFrames is used for PROBE state transmissions. This Probe nFrames is basically the same as Mid nFrames, but it has the maximal limit of ten frames. Using Multi-Rate Retry (MRR) chain [represented by (r0=c0)(r1=c1)(r2=c2)(r3=c3)] is another way for AARA to mitigate short-term uctuation of the link. When the current state is NORMAL, r0 is set to the best rate and r1 is set to the last data rate right before the current one. On the other hand, a probing rate is inserted into the rst slot (r0) for PROBE state, followed by the other two rates used in NORMAL state. Note that AARA 67 Algorithm 1 AARA Algorithm //Declaring variables //MRR includes (r0;c0)(r1;c1)(r2;c2)(r3;c3) nSuccess = number of true bits in BlockACK nFrames = total number of acknowledged bits in BlockACK = A-MPDU success threshold status = current status nextLowerRate = next lower bandwidth rate nextHigherRate = next higher bandwidth rate 1: FSR = (nSuccess 100)=nFrames 2: if status == PROBE then 3: if FSR> then 4: set rate (r0) 5: status = UP 6: else 7: status = NORMAL 8: end if 9: else if status == NORMAL then 10: goodput = max goodput (r0) FSR 11: if goodput < max goodput (nextLowerRate) then 12: status = DOWN 13: else if FSR> then 14: set probe (nextHigherRate) 15: status = PROBE 16: end if 17: else if status == UP or status == DOWN then 18: if FSR< then 19: set rate (nextLowerRate) 20: end if 21: status = NORMAL 22: end if does not utilize the fourth chain because the aggregation level can be unnecessarily limited as discussed in Section 5.6.3. The numbers of retransmission counts (c0 r3) are also key parameters that will be discussed in more detail in Section 5.7.3. The detailed pseudo code of state transition is presented in Algorithm 1. 68 5.7.2 Adaptive Probing Probing is a key mechanism to track the best performing rate in AARA. First, AARA uses a normal aggregated data packet instead of the single short packet used in Ath9K RA or Minstrel HT, but limits the aggregation level of a probing packet by Max nFrames value in order to obtain su cient statistics while still avoiding the risk of losing the entire aggregated packet. Secondly, AARA exponentially increments probing intervals to a certain limit when there are consecutive identical probing attempts, thus reducing unnecessary probing overhead under stable channel conditions. As introduced in Section 5.6.5, depending on the existence of multiplexing structure, the channel may have a non-monotonic relationship between rate increment and FSR. In other words, a higher rate option may counter-intuitively lead to less transmission failure than a lower rate option. Therefore, linear choice of candidate rates possibly causes the RA to be stuck in a sub-optimal rate. Based on in-depth reviews of the current MIMO RAs demonstrating non-monotonic be- haviors in MIMO system [1, 30], non-monotonic cases happen only when a high modulation SS rate is used even though a multiplexing structure exists. To avoid such cases, AARA not only tries to probe the next higher rate, but also attempts cross-mode rates. Figure 5.13 illustrates the cross mode probing directions for each MCS rate. The solid black line repre- sents the rst attempt. If the rst probing fails, the second candidate rate, represented by the dashed orange line, is attempted. The next higher rate within the same MIMO mode is chosen as the rst attempting direction, whereas the second direction selected is a higher bandwidth rate with lower modulation scheme among cross-mode rates. Notice that there is an exception on DS 52 Mbps where the cross-mode rate is tried ahead of the same mode higher rate. These probing candidates are set to the nextHigherRate used in Algorithm 1 by turns according to priority. 69 Figure 5.13: Cross mode Rate Probing Directions 70 5.7.3 Congestion Detection and Response As discussed earlier, there are two types of contention-induced losses. First, In-range collision is caused by limitation of DCF protocol where multiple stations are assigned to the same back-o slot. In this case, due to the timing proximity on transmissions, the headers of packets are corrupted causing A-MPDU retransmission. Since colliding with the same packet in the retransmission attempt is not likely, the number of consecutive retransmissions are limited. At this point, AARA identi es an In-range collision. In contrast, hidden station- induced collision may a ect a series of A-MPDUs in a row because hidden stations are oblivious of the ongoing transmissions. The number of retransmissions without partial frame loss is used for detecting congestion in AARA. Since most packet collisions corrupt not only data frames, but also the header of an A-MPDU, the collision destroys the entire A-MPDU rather than exploiting partial data frames, assuming that the working rate is within a reasonable range. Therefore, multiple retransmissions were made before the last successful attempt, and FSR of the last trial is over 90%, AARA judges that the current channel is su ering from congestion. Upon detecting In-range collisions, AARA ignores the incident; however, when AARA identi es a possible hidden station, it initiates the RTS/CTS handshake which is the only available solution for the hidden station problem. The current implementation sets the retransmission threshold to three for hidden station detection according to the heuristics given in Figure 5.9. 5.8 Performance Evaluation In this section, the performance of AARA is evaluated and compared with various MIMO RAs, Minstrel HT, Atheros RA and RAMAS [30], in diverse settings introduced in 5.5.2. Since performance degradation of MIMO-oblivious RAs with MIMO stations has been su ciently proven in the literature, only representative MIMO RAs were evaluated in this experiment. AARA was evaluated and compared by measuring the success or failure of 71 the chosen transmission rate as compared to the optimal rate for the current channel quality. Except for the contention scenario, the tra c was sent from the AP to clients. 5.8.1 Implementation The AARA algorithm was implemented using an open source Compat-wireless network driver. It provides Minstrel HT and Atheros RA, which are both statistic-based algorithm as embedded options. Even when the new rate is assigned to the driver, the change is not immediately applied to the next data transmission. Once the new rate is set, it becomes e ective after ve to seven A-MPDU packet transmissions. The delay is due to changing and obtaining values from shared memories between the transmission module and the RA module. Since the two built-in RA algorithms gather statistics at a speci ed interval (100ms), which is relatively longer than the delay in the rate update, the performance of these RAs is not adversely a ected. In comparison, AARA employs a faster statistics interval for adapting to the instantaneous channel variation. Consequently, a delay of this magnitude can cause serious distortion. Therefore, the RA module is directly embedded into the transmission module so that the updated rate is immediately applied to the next transmission. Along with AARA, RAMAS [30] was implemented to compare AARA performance with a representative MIMO RA. Since the algorithm is straightforward and relatively simple, it is not di cult to implement; however, obtaining similar performance in di erent experiment set-up from the original paper is challenging. In addition, the performance of RAMAS varies according to implementation parameters such as time window, credit threshold, and acceptable error rates. Even though the optimal parameters are di erent in the experiments, the original values were used as recommended in the paper. 5.8.2 Static Setting Experiments for static con guration were performed to evaluate whether di erent RAs e ciently identify the optimal transmission rate over the current link condition. Figure 5.14 72 Figure 5.14: Throughput in Static Setting A B C D E F 0 20 40 60 80 100 120 Experiment Location Throughput (Mbps) Minstrel HT Ath9K RA RAMAS AARA presents the UDP throughput measured at six di erent places inside a typical o ce building as shown in Figure 5.3. AARA consistently outperforms the other three algorithms by up to 14.3%, 64.2%, and 113.2% compared to Minstrel HT, Ath9K RA, and RAMAS respectively. Minstrel HT generally follows the AARA except for the location D. RAMAS shows good performance in proximal settings, but su ers in relatively far settings. Table 5.7 presents the percentage of performance gain of the new algorithm over existing RAs. Figure 5.15 presents a set of rate evolutions in the experiments of location E in order to investigate the factors of performance bene t in depth. As already pointed out, the purpose of RA in static settings is to locate the best rate as quickly as possible while minimizing overhead for channel estimation. The optimal rate, 117 Mbps, can be easily identi ed in Figure 5.15. All four RAs seemed to be successful in nding it, but except in the case of RAMAS, the di erence in throughput gain resulted from the probing overhead. Minstrel HT probes the candidate rates randomly. Even the lowest rate (6.5 Mbps) is occasionally attempted for link quality evaluation and these random attempts degrade performance. In contrast to Minstrel HT, Ath9K RA tries the next higher transmission rate than the current 73 Table 5.7: Thoughtput Improvement of AARA over RAs in Comparison Minstrel HT Ath9K RA RAMAS Static (A) 14.3% 19.6% 81.3% Static (B) 7.9% 64.1% 113.2% Static (C) 7.8% 22.8% 27.7% Static (D) 8.1% 0.2% 3.9% Static (E) 8.2% 12.6% 11.5% Static (F) 5.4% 19.1% 11.1% Mobile 27.0% 23.9% 48.8% In-range 50.6% 144.8% 473.2% Hidden 32.2% 149.5% 209.0% rate, but as discussed, a single short-length packet is used for probing, and the unexpectedly higher success ratio in transmitting at 130 Mbps rate option is attributed to this probing method. Even though the FER for 130 Mbps is around 36.9% in practice, all the probing attempts for the rate were successful. This overestimation requires the Ath9K RA to change the active rate to 130 Mbps causing serious frame losses. In RAMAS, the normal A-MPDU packet was exploited for the sampling. However, since it drops down transmission rate for every six losses out of 30 frames, RAMAS drastically decrements the rate choice when multiple A-MPDU packets cause high AFER in transmis- sion. For example, two consecutive A-MPDU can carry 64 MPDU frames total, 32 frames for each packet as indicated in Table 5.4, and assuming 50% of the frames are lost, 32 frames can be lost for only two A-MPDU transmissions. This loss can drop down the transmission rate by two steps at once and causes throughput reduction. As expected, AARA identi es the best rate as quickly as other RAs. Also, it e ciently probes the next higher rate with normal A-MPDU packets, but reduces probing overhead by limiting nFrames when probes fail. Moreover, the exponential probing interval increment works perfectly to further restrict the unnecessary probing attempts as can be found in the rate evolution gure. 74 Figure 5.15: Rate Evolution in Static Setting 26 39 52 65 78 104 117 130 Minstrel HT Data rate (Mbps) 26 39 52 65 78 104 117 130 Ath9K RA Data rate (Mbps) 26 39 52 65 78 104 117 130 RAMAS Data rate (Mbps) 26 39 52 65 78 104 117 130 AARA Data rate (Mbps) 75 Figure 5.16 shows varying performance statistics at the same location as the evolution graph. The rst graph exhibits average number of frames in a single A-MPDU over the transmissions. The reason that RAMAS shows the best aggregation level is that RAMAS does not utilize the MRR scheme which limits the aggregation level. While AARA uses three MRR chains on probing mode and two chains on the other modes, Ath9K RA utilizes all four chains, causing the aggregation density to stay in low levels. Although Minstrel HT sets only three chains, the third chain is required to be one stream rate. Hence, the aggregation level for Minstrel HT cannot exceed 20, which is the maximum nFrames for MCS 7, 65 Mbps rate option as shown in Table 5.4. The enhanced utilization of aggregation helps RAs to reduce the packet transmission attempts and the total number of transmitted packets is inversely proportional to nFrames, as shown in the middle graph. This reduced transmission also implies that there is less protocol overhead required per packet transmission and the channel can be less congested due to the reduced channel occupancy. The rightmost graph shows the frame error ratio out of all the transmitted MPDU frames. The Ath9K RA exhibits the worst FER due to the misjudgment of the short length probing of the 130 Mbps rate option, while the other RAs perform similarly. 5.8.3 Mobile Setting In order to observe responsiveness and adaptiveness to agile channel dynamics, four RAs were tested in a mobile environment. Figure 5.18 depicts throughput and FER of all four RAs tested in this setting. As can be noted, AARA performs better than Minstrel HT, Ath9K RA, and RAMAS by up to 51.9%, 53.2%, and 44.3% receptively. The performance enhancement is attributed to AARA?s agility to channel dynamics as explained by the rate evolution in Figure 5.18. AARA stays in a higher rate region when the node is static but moves quickly to lower options when the node starts to move. Minstrel HT su ers from the same drawback as in the static setting due to randomness in search, and Ath9K RA tends to stay in a higher rate region even when the station is moving 76 Figure 5.16: Performance in Static Setting (Location E) MIN ATH RAM AARA0 5 10 15 20 25 30 nFrames per A?MPDU MIN ATH RAM AARA0 5 10 15 Frame Error Ratio (%) MIN ATH RAM AARA0 200 400 600 800 1000 1200 1400 1600 1800 Total Transmitted Packets MIN ATH RAM AARA0 5000 10000 15000 20000 25000 30000 Total Successful Frames 77 Figure 5.17: Throughput and FER in Mobile Setting MIN ATH RAMAS AARA0 10 20 30 40 50 60 70 Throughput (Mbps) MIN ATH RAMAS AARA0 10 20 30 40 Frame Error Ratio (%) due to the overestimated probing results. Note that Ath9K RA does not use 65 Mbps for transmissions and this limitation a ects the performance as well. On the other hand, RAMAS exhibits a similar pattern according to movement, but the serious underestimation of the link quality drastically drops the rate to the lowest option and leads to signi cant performance degradation. FER is also illustrated in Figure 5.18 to show AARA?s low error rate compared to Minstrel HT and Ath9K RA. RAMAS exhibits the lowest FER among all the RAs tested because of inappropriately underestimating the channel and staying in the lower rate region. 5.8.4 In-range Collision Setting The purpose of this experiment was to test how RAs di erentiate and lter out In-range collision-induced packet losses from the channel estimation process. The performance gain of AARA for this experiments is the best out of four test-beds and reaches up to 50.6%, 144.8%, and 473.2% respectively over Minstrel HT, Ath9K RA, and RAMAS. As can be found in Figure 5.20, while other RAs stay in the lower rate region, AARA maintains the higher rate options during the experiment and produces the best performance. This improved performance results from the di erent channel estimation model. Minstrel 78 Figure 5.18: Rate Evolution in Mobile Setting 26 39 52 65 78 104 117 130 Minstrel HT Data rate (Mbps) 26 39 52 65 78 104 117 130 Ath9K RA Data rate (Mbps) 26 39 52 65 78 104 117 130 RAMAS Data rate (Mbps) 26 39 52 65 78 104 117 130 AARA Data rate (Mbps) 79 Figure 5.19: Throughput in In-range Collision Setting MIN ATH RAMAS AARA0 10 20 30 40 50 Throughput (Mbps) HT and Ath9K RA include the A-MPDU retransmission counts to compute the goodput of the currently transmitted A-MPDU packet so that the goodput takes account of lost frames upon A-MPDU failure. This approach seems intuitive and reasonable; however, because A-MPDU failure is caused by collisions, as discussed in Section 5.6.4, and the losses by collisions should be ltered out from channel estimation, considering retransmissions can mislead the RA?s decision. Figure 5.21 illustrates A-MPDU Frame Error Ratio with and without retransmission counts in the experiment. While the bars indicate the AFER with retransmission considered, the dots plot the AFER per-A-MPDU without retransmission counts. The majority of packets yield low AFER when retransmissions are excluded in computation. This nding con rms the assumption made in Section 5.6.4 that In-range collisions a ect the protocol header and cause A-MPDU failure rather than partial frame loss within each packet. 5.8.5 Hidden Collision Setting In the hidden collision setting, it is challenging to replicate the same environment so that each RA experiences the same link condition due to the capture e ect. When there are multiple signals transmitted, if one of them has enough signal power to be distinguished from 80 Figure 5.20: Rate Evolution in In-range Contention Setting 26 39 52 65 78 104 117 130 Minstrel HT Data rate (Mbps) 26 39 52 65 78 104 117 130 Ath9K RA Data rate (Mbps) 26 39 52 65 78 104 117 130 RAMAS Data rate (Mbps) 26 39 52 65 78 104 117 130 AARA Data rate (Mbps) 81 Figure 5.21: AFER w/ and w/o Retransmissions in In-range Contention Setting 0 10 20 30 40 50 60 70 80 90 100 Run time Error Rate (%) AFER w/ Retransmission AFER w/o Retransmission the another weaker signal, the physical layer capture e ect occurs and hidden collision e ect may diminish even with simultaneous transmissions. According to the rate evolutions pre- sented in Figure 5.24, the potential best rate seems to be 78 Mbps. Unlike other algorithms, AARA successfully stays around the possible optimal rate in spite of signi cant congestion by a hidden station. Similarly to other settings, AARA provides the best performance by up to 32.2%, 149.5%, and 209.0% over Minstrel HT, Ath9K RA, and RAMAS receptively. While the other algorithms perform poorly because they do not di erentiate the causes of collisions, AARA is proved to e ectively detect congestion caused by hidden stations and respond appropriately. Based upon the ndings in Section 5.6.4, AARA considers the current link state as hidden congestion when there are more than three consecutive A-MPDU failures and initiates the RTS/CTS handshake to prevent collision-induced packet losses. Minstrel HT also activates RTS/CTS handshake, but because it initializes the protection from the second rate (r1) in the MRR chain and no such case occurred during testing, Minstrel HT never activated the handshake during the experiments. The question is how long the handshake should be sustained to e ectively avoid the congestion. In Figure 5.23, the throughput performance is represented as the duration of RTS/CTS exchange grows by 100ms per unit. Since AARA performs best when the control 82 Figure 5.22: Throughput and Retransmission Ratio in Hidden Collision Setting MIN ATH RAM AARA0 10 20 30 Throughput (Mbps) MIN ATH RAM AARA0 10 20 30 40 50 Retransmission Ratio (%) mechanism is activated for 100ms, it has been set as the parameter for RTS/CTS activation duration. Thanks to the protection mechanism, retransmission ratio dropped by 42.5% and 35.5% compared to Minstrel HT and Ath9K RA respectively. On the other hand, RAMAS exhibited a slightly lower retransmission ratio than AARA because of the capture e ect. RAMAS transmitted most of the packets at the second lowest rates (13 Mbps) due to the serious losses from collisions. However, since the lower rates have the strongest signal, the receiver could intelligently lter out the weaker signal from the hidden station. 5.9 Summary In this chapter, based on extensive heuristic analysis of the impact of Frame Aggregation on Rate Adaptation algorithm, a novel rate adaptation scheme called AARA is designed and evaluated. AARA signi cantly improves network performance over existing RAAs by the following enhancements. First, it estimates the channel using a normal A-MPDU packet with reduced potential risk of excessive frame losses. Second, AARA alleviates drastic rate changing by adopting aggregation level control before and after the shift. Third, based on the case study, 83 Figure 5.23: Throughput Comparison according to RTS/CTS Operation Duration 100ms 300ms 500ms 700ms 900ms0 5 10 15 20 25 30 RTS/CTS Activation Duration Throughput (Mbps) AARA e ciently di erentiates the collision-induced frame losses based upon the implication of A-MPDU failure. The e cacy of the proposed algorithm was proved by extensive tests conducted in various environments. 84 Figure 5.24: Rate Evolution in Hidden Contention Setting 6 26 39 52 65 78 104 117 130 Minstrel HT Data rate (Mbps) 6 26 39 52 65 78 104 117 130 Ath9K RA Data rate (Mbps) 6 26 39 52 65 78 104 117 130 RAMAS Data rate (Mbps) 6 26 39 52 65 78 104 117 130 AARA Data rate (Mbps) 85 Chapter 6 Conclusion and Future Work 6.1 Conclusion The goals of this dissertation were to study various design factors required for e cient Rate Adaptation algorithm and to implement agile Rate Adaptation algorithms to optimize wireless link performance. In order to achieve this goal, a comprehensive survey of a wide range of RA schemes is carried out in Chapter 2. Along with categorizing and classifying popular existing RA algorithms, this chapter also summarized related work associated with potential factors of RA design. Chapter 3 describes design challenges and questions regarding RA. In summary, the proposed RAs should address the following questions: (1) For static environments, how does the proposed solution e ectively nd and switch to the best rate while remaining adaptable to unpredictable short-term channel uctuation with minimal overhead? (2) For mobile environments, how does the new algorithm e ective adapt to varying link conditions to obtain an instantaneous optimal rate? (3) For congested environments, how does the RA scheme intelligently distinguish the potential reason for the loss to employ adaptable responses? Two novel RA schemes are proposed to resolve these research challenges with exten- sive performance evaluation. In Chapter 4, Rate Adaptation with Collision Di erentiation (RACD) is proposed to address the question of collision di erentiation. RACD appears to be is the rst algorithm which attempts to di erentiate In-range collision from hidden collision by using CTS-to-self control packet. After classifying the error sources, RACD responds appropriately by actions such as initiating RTS/CTS handshake and adjusting Contention Window size. Extensive simulation results con rm that RACD signi cantly improves per- formance, especially in congestion scenarios. 86 Chapter 5 addresses the fact that typical RA algorithms do not consider Frame Aggre- gation in rate decisions even though FA is one of the dominant innovations speci ed in the new amendment. The impact of Frame Aggregation (FA) on RA algorithm design is closely investigated from various perspectives with a case study. Based on the analysis and nd- ings from the case study, a novel AARA (Aggregation Aware Rate Adaptation) algorithm is proposed and evaluated via exhaustive experiments carried out in controlled and repeatable environments. The experiment results verify that AARA nds the optimal rate with mini- mized probing overhead in the static setting, swiftly switches to short-term best rate in the mobile setting, and intelligently identi es the congestion-induced frame losses in the conges- tion setting. The improved performance mainly results from e ciently controlled probing packets, a bumping period during the rate transition, and a new contention-detection metric used for collision di erentiation. 6.2 Future Work Even though the proposed solutions address several challenging problems, drawbacks and limitations remain which are worthy of future research. First, the proposed RA assumes that the network tra c is saturated. In case of unsat- urated tra c scenario, mandating a maximal aggregation level may cause additional delay during which the transmission queue should be lled enough to complete an aggregated packet. This delay may lead to performance degradation due to the time constraints in real time application. In addition, the delay in transmission may a ect the TCP performance which mandates the speci ed arrival time. In addition to the problem caused by the trans- mission delay, Coherence time may a ect the e ciency of frame aggregation. Coherence time is de ned as the time-interval during which the channel stays su ciently constant for the receiver to be able to decode the transmitted signal with a certain data rate. If the co- herence time decreases, meaning that the channel condition changes faster over time (called Fast fading), holding the maximum possible aggregation level can lead to higher FER due 87 to the long transmission duration of A-MPDU packets. To address all the issues related to time domain, an interesting topic for future research would be adaptive aggregation level control which adaptively optimizes the level of aggregation according to both channel status and tra c pattern. Fairness in transmission can be another problem with RA design. Aggregation may impose serious imbalances between potential transceivers so that some of them could starve due to biased opportunity for channel access. As brie y mentioned in Section 5.6.5, some researchers have attempted to develop a metric to identify the multiplexing structure, but these e orts are either too complicated or are incompliant with the standard. Future research could develop a simple and useful metric which conforms to the standard and e ciently identi es the multiplexing structure. Besides the topics listed above, there are numerous issues regarding to channel adapta- tion because of the unpredictable nature of the wireless channel medium. 88 Bibliography [1] I. Pefkianakis, Y. Hu, S. H. Wong, H. Yang, and S. Lu, \Mimo rate adaptation in 802.11n wireless networks," in Proceedings of the Sixteenth Annual International Conference on Mobile Computing and Networking, ser. MobiCom ?10. New York, NY, USA: ACM, 2010, pp. 257{268. [Online]. Available: http://doi.acm.org/10.1145/1859995.1860025 [2] L. Deek, E. Garcia-Villegas, E. Belding, S.-J. Lee, and K. Almeroth, \Joint rate and channel width adaptation for 802.11 mimo wireless networks," in Sensor, Mesh and Ad Hoc Communications and Networks (SECON), 2013 10th Annual IEEE Communications Society Conference on, 2013, pp. 167{175. [3] S. Biaz and S. Wu, \Rate adaptation algorithms for ieee 802.11 networks: A survey and comparison," in Computers and Communications, 2008. ISCC 2008. IEEE Symposium on, July 2008, pp. 130{136. [4] I. Haratcherev, K. Langendoen, R. Lagendijk, and H. Sips, \Hybrid rate control for ieee 802.11," in Proceedings of the Second International Workshop on Mobility Management &Amp; Wireless Access Protocols, ser. MobiWac ?04. New York, NY, USA: ACM, 2004, pp. 10{18. [Online]. Available: http://doi.acm.org/10.1145/1023783.1023787 [5] A. Kamerman and L. Monteban, \Wavelan-ii: a high-performance wireless lan for the unlicensed band," Bell Labs Technical Journal, vol. 2, no. 3, pp. 118{133, 1997. [Online]. Available: http://dx.doi.org/10.1002/bltj.2069 [6] M. Lacage, M. H. Manshaei, and T. Turletti, \Ieee 802.11 rate adaptation: a practi- cal approach," in Proceedings of the 7th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, ser. MSWiM ?04. New York, NY, USA: ACM, 2004, pp. 126{134. [7] F. Maguolo, M. Lacage, and T. Turletti, \E cient collision detection for auto rate fallback algorithm," in Computers and Communications, 2008. ISCC 2008. IEEE Symposium on, July 2008, pp. 25{30. [8] S. H. Y. Wong, H. Yang, S. Lu, and V. Bharghavan, \Robust Rate Adaptation for 802.11 Wireless Networks," in Proceedings of the 12th annual international conference on Mobile computing and networking, ser. MobiCom ?06. ACM, 2006, pp. 146{157. [9] I. Pefkianakis, S. Wong, H. Yang, S.-B. Lee, and S. Lu, \Toward history-aware robust 802.11 rate adaptation," Mobile Computing, IEEE Transactions on, vol. 12, no. 3, pp. 502{515, March 2013. 89 [10] R. T. Morris, J. C. Bicket, and J. C. Bicket, \Bit-rate selection in wireless networks," Masters thesis, MIT, Tech. Rep., 2005. [11] \ONOE Rate Control," http://madwi .org. [12] \Atheros ra," http://wireless.kernel.org/en/users/Drivers/ath9k. [13] \Minstrel ra speci cation," http://linuxwireless.org/en/developers/Documentation/ mac80211/RateControl/minstrel. [14] D. Nguyen, J. Garcia-Luna-Aceves, and C. Westphal, \Throughput enabled rate adap- tation in wireless networks," in Computing, Networking and Communications (ICNC), 2013 International Conference on, Jan 2013, pp. 1173{1178. [15] P. Shankar, T. Nadeem, J. Rosca, and L. Iftode, \Cars: Context-aware rate selection for vehicular networks," in Network Protocols, 2008. ICNP 2008. IEEE International Conference on, Oct 2008, pp. 1{12. [16] L. Ravindranath, C. Newport, H. Balakrishnan, and S. Madden, \Improving wireless network performance using sensor hints," in Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, ser. NSDI?11. Berkeley, CA, USA: USENIX Association, 2011, pp. 21{21. [Online]. Available: http://dl.acm.org/citation.cfm?id=1972457.1972486 [17] G. Holland, N. Vaidya, and P. Bahl, \A Rate-adaptive MAC Protocol for Multi-Hop Wireless Networks," in Proceedings of the 7th annual international conference on Mobile computing and networking, ser. MobiCom ?01. ACM, 2001, pp. 236{251. [18] K. Lee, J. Navarro, T. Chong, U. Lee, and M. Gerla, \Trace-based evaluation of rate adaptation schemes in vehicular environments," in Vehicular Technology Conference (VTC 2010-Spring), 2010 IEEE 71st, May 2010, pp. 1{5. [19] J. Camp and E. Knightly, \Modulation rate adaptation in urban and vehicular environments: Cross-layer implementation and experimental evaluation," in Proceedings of the 14th ACM International Conference on Mobile Computing and Networking, ser. MobiCom ?08. New York, NY, USA: ACM, 2008, pp. 315{326. [Online]. Available: http://doi.acm.org/10.1145/1409944.1409981 [20] O. Punal, H. Zhang, and J. Gross, \Rfra: Random forests rate adaptation for vehicular networks," in World of Wireless, Mobile and Multimedia Networks (WoWMoM), 2013 IEEE 14th International Symposium and Workshops on a, June 2013, pp. 1{10. [21] G. Judd, X. Wang, and P. Steenkiste, \E cient channel-aware rate adaptation in dynamic environments," in Proceedings of the 6th International Conference on Mobile Systems, Applications, and Services, ser. MobiSys ?08. New York, NY, USA: ACM, 2008, pp. 118{131. [Online]. Available: http://doi.acm.org/10.1145/1378600.1378615 [22] X. Chen, P. Gangwal, and D. Qiao, \Ram: Rate adaptation in mobile environments," Mobile Computing, IEEE Transactions on, vol. 11, no. 3, pp. 464{477, March 2012. 90 [23] M. Vutukuru, H. Balakrishnan, and K. Jamieson, \Cross-layer wireless bit rate adaptation," in Proceedings of the ACM SIGCOMM 2009 Conference on Data Communication, ser. SIGCOMM ?09. New York, NY, USA: ACM, 2009, pp. 3{14. [Online]. Available: http://doi.acm.org/10.1145/1592568.1592571 [24] H. Rahul, F. Edalat, D. Katabi, and C. G. Sodini, \Frequency-aware rate adaptation and mac protocols," in Proceedings of the 15th Annual International Conference on Mobile Computing and Networking, ser. MobiCom ?09. New York, NY, USA: ACM, 2009, pp. 193{204. [Online]. Available: http://doi.acm.org/10.1145/1614320.1614342 [25] S. Sen, N. Santhapuri, R. R. Choudhury, and S. Nelakuditi, \Accurate: Constellation based rate estimation in wireless networks," in In USENIX NSDI, 2010. [26] D. Halperin, W. Hu, A. Sheth, and D. Wetherall, \Predictable 802.11 packet delivery from wireless channel measurements," SIGCOMM Comput. Commun. Rev., vol. 41, no. 4, pp. {, Aug. 2010. [Online]. Available: http://dl.acm.org/citation.cfm?id= 2043164.1851203 [27] G. Martorell, F. Riera-Palou, and G. Femenias, \Cross-layer fast link adaptation for mimo-ofdm based wlans," Wirel. Pers. Commun., vol. 56, no. 3, pp. 599{609, Feb. 2011. [Online]. Available: http://dx.doi.org/10.1007/s11277-010-9992-9 [28] I. Pefkianakis, Y. Hu, S.-B. Lee, C. Peng, S. Sakellaridi, and S. Lu, \Window-based rate adaptation in 802.11n wireless networks," Mobile Networks and Applications, vol. 18, no. 1, pp. 156{169, 2013. [Online]. Available: http://dx.doi.org/10.1007/ s11036-011-0347-x [29] Q. Xia, M. Hamdi, and K. Ben Letaief, \Open-loop link adaptation for next-generation ieee 802.11n wireless networks," Vehicular Technology, IEEE Transactions on, vol. 58, no. 7, pp. 3713{3725, 2009. [30] L. Deek, E. Garcia-Villegas, E. Belding, S.-J. Lee, and K. Almeroth, \Joint rate and channel width adaptation for 802.11 mimo wireless networks," in Sensor, Mesh and Ad Hoc Communications and Networks (SECON), 2013 10th Annual IEEE Communications Society Conference on, 2013, pp. 167{175. [31] A. Makhlouf and M. Hamdi, \Practical rate adaptation for very high throughput wlans," Wireless Communications, IEEE Transactions on, vol. 12, no. 2, pp. 908{916, 2013. [32] S. Lakshmanan, S. Sanadhya, and R. Sivakumar, \On link rate adaptation in 802.11n wlans," in INFOCOM, 2011 Proceedings IEEE, 2011, pp. 366{370. [33] Q. Pang, V. Leung, and S. Liew, \A rate adaptation algorithm for ieee 802.11 wlans based on mac-layer loss di erentiation," in Broadband Networks, 2005. BroadNets 2005. 2nd International Conference on, Oct 2005, pp. 659{667 Vol. 1. [34] J. Kim, S. Kim, S. Choi, and D. Qiao, \CARA: Collision-Aware Rate Adaptation for IEEE 802.11 WLANs," in INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, 2006, pp. 1{11. 91 [35] K. Zhang, A. Lim, S. Wu, and Q. Yang, \A High TCP Performance Rate Adaptation Algorithm for IEEE 802.11 Networks," International Journal of Computer Networks & Communications (IJCNC), vol. 2, no. 6, pp. 31{44, 2010. [36] A. Ngugi, Y. Chen, and Q. Li, \Rate adaptation with nak-aided loss di erentia- tion in 802.11 wireless networks," in Global Telecommunications Conference, 2009. GLOBECOM 2009. IEEE, Nov 2009, pp. 1{6. [37] S. Rayanchu, A. MISHRA, D. Agrawal, S. Saha, and S. Banerjee, \Diagnosing wireless packet losses in 802.11: Separating collision from weak signal," in INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, April 2008, pp. {. [38] S. Biaz and S. Wu, \Loss di erentiated rate adaptation in wireless networks," in Wireless Communications and Networking Conference, 2008. WCNC 2008. IEEE, March 2008, pp. 1639{1644. [39] M. Khan and D. Veitch, \Isolating physical per for smart rate selection in 802.11," in INFOCOM 2009, IEEE, April 2009, pp. 1080{1088. [40] H. Jung, T. T. Kwon, K. Cho, and Y. Choi, \React: Rate adaptation using coherence time in 802.11 fWLANsg," Computer Communications, vol. 34, no. 11, pp. 1316 { 1327, 2011. [Online]. Available: http://www.sciencedirect.com/science/article/pii/ S0140366411000594 [41] P. Acharya, A. Sharma, E. Belding, K. Almeroth, and K. Papagiannaki, \Rate adaptation in congested wireless networks through real-time measurements," Mobile Computing, IEEE Transactions on, vol. 9, no. 11, pp. 1535{1550, Nov 2010. [42] K. V. Cardoso and J. F. Rezende, \Increasing throughput in dense 802.11 networks by automatic rate adaptation improvement," Wirel. Netw., vol. 18, no. 1, pp. 95{112, Jan. 2012. [Online]. Available: http://dx.doi.org/10.1007/s11276-011-0389-9 [43] M. Kim and C.-H. Choi, \Hidden-node detection in ieee 802.11n wireless lans," Vehicular Technology, IEEE Transactions on, vol. 62, no. 6, pp. 2724{2734, 2013. [44] P. Chaporkar, A. Proutiere, and B. Radunoviac, \Rate Adaptation Games in Wireless LANs: Nash Equilibrium and Price of Anarchy," in INFOCOM, 2010 Proceedings IEEE, 2010, pp. 1{9. [45] \The Network Simulator-ns-3," http://www.nsnam.org. [46] T. Li, Q. Ni, D. Malone, D. Leith, Y. Xiao, and T. Turletti, \Aggregation with fragment retransmission for very high-speed wlans," Networking, IEEE/ACM Transactions on, vol. 17, no. 2, pp. 591{604, April 2009. [47] D. Skordoulis, Q. Ni, H.-H. Chen, A. Stephens, C. Liu, and A. Jamalipour, \Ieee 802.11n mac frame aggregation mechanisms for next-generation high-throughput wlans," Wireless Communications, IEEE, vol. 15, no. 1, pp. 40{47, 2008. 92 [48] T. Selvam and S. Srikanth, \A frame aggregation scheduler for ieee 802.11n," in Communications (NCC), 2010 National Conference on, 2010, pp. 1{5. [49] B. Ginzburg and A. Kesselman, \Performance analysis of a-mpdu and a-msdu aggrega- tion in ieee 802.11n," in Sarno Symposium, 2007 IEEE, 2007, pp. 1{5. [50] Y. Lin and V. Wong, \Wsn01-1: Frame aggregation and optimal frame size adaptation for ieee 802.11n wlans," in Global Telecommunications Conference, 2006. GLOBECOM ?06. IEEE, 2006, pp. 1{6. [51] X. He, F. Li, and J. Lin, \Link adaptation with combined optimal frame size and rate selection in error-prone 802.11n networks," in Wireless Communication Systems. 2008. ISWCS ?08. IEEE International Symposium on, Oct 2008, pp. 733{737. [52] M. Kim and C.-H. Choi, \Probing-based link adaptation for high data rate wireless lans," Wireless Communications, IEEE Transactions on, vol. 11, no. 7, pp. 2382{2390, 2012. [53] \Iperf," http://iperf.sourceforge.net/. [54] \Hostapd," http://wireless.kernel.org/en/users/Documentation/hostapd. [55] \Msi mini computer," http://us.msi.com/product/ipc/. [56] \Compat-wireless," https://www.kernel.org/pub/linux/kernel/projects/backports/ stable/. [57] \Wireshark packet sni er," http://www.wireshark.org. [58] \AirPcap Nx," http://www.airpcap.nl/airpcap-nx.htm. 93