Research Abstracts - 2006

Path Diversity Techniques for Efficient Packet Delivery in Wireless LANs

Allen Miu & Hari Balakrishnan

Introduction

An important requirement in the design of indoor wireless local area networks (WLAN) is loss resilience. However, wireless communication channels have notoriously time-varying characteristics, where the quality of received signals changes dramatically even over time durations lasting just milliseconds. The complex behavior of wireless signal propagation, particularly indoors and in presence of mobility, leads to bursty frame corruptions at the link-layer that can last over tens of milliseconds. The detrimental link-layer effects are manifested in the higher layers as packet losses and higher and more variable packet latencies that can severely impact the performance of many WLAN applications such as bulk file transfer, telephony, video streaming and other wireless applications. Figure 1 shows a sample constant rate User Datagram Protocol (UDP) data trace that reflects the magnitude and frequency of losses and delay that can occur in a 802.11b network.

Figure 1: A 15-minute trace of packet transmissions from two access points. Burst loss count is defined as an event where 2 or more packets are lost consecutively in the transmission. (Click image for full resolution figure.)

Traditional approaches to increase loss resilience in WLANs are retransmission and rate adaptation. Retransmission works well when the period of channel degradation is short. But when the channel quality deteriorates for a long period, retransmission becomes ineffective and wasteful. Rate adaptation, on the other hand, can work well even when the wireless channel experiences severe deterioration. However, efficient rate adaptation is difficult to achieve because channel conditions vary quickly and are often unpredictable. Furthermore, both strategies can significantly increase the delay of packet delivery, which could drastically impact the perceived quality of many interactive and delay sensitive applications.

Approach

Typically, a WLAN is a system composed of many access points (AP) that relay packets for a WLAN client. In today's WLAN (e.g., 802.11), each AP operates independently and each WLAN client can communicate with only one AP. When the channel quality of the transmission path deteriorates, the transmitter must either repeat retransmissions until the channel quality improves or reduce the transmission rate to compensate for the poor channel. The net result is increased transmission delay or a loss due to exhausting the retransmission limit or queue overflow.

In practice, APs with overlapping coverage can provide alternate transmission paths for the same client. The observations illustrated in the next section suggest that 1) successful wireless transmissions depends on the physical path traversed by the transmitted signal and 2) the channel quality of different transmission paths varies independently. When both conditions hold, there is a good chance that transmissions will succeed through at least one of the available transmission paths. Based on these observations, we propose to design a new WLAN system, called Multi-radio Diversity (MRD), which---in contrast to today's WLANs---coordinates packet transmissions and receptions via multiple radios in reducing frame error rates in the wireless network. MRD exploits the path diversity that is inherent in the physical infrastructure by integrating two path diversity data transmission techniques, fine-grained path selection and spatial packet combining, to reduce path-dependent packet losses and delays in the wireless network.

Design of MRD

Figure 2 shows MRD's system architecture. Each AP offers a different physical transmission path with uncorrelated loss characteristics, and the most reliable communication path between the AP infrastructure a client may change rapidly over time. Our research will explore two path diversity techniques that can be implemented within the MRD architecture using existing WLAN standards such as 802.11 and its variants (11a, 11b, 11g, etc.). The first technique is called fine-grained AP selection. In this technique, the Diversity Monitor (DM) obtains the current channel conditions at each AP and feeds them to the Diversity Controller (DC), which selects the best communication path for downlink transmissions. The DC can switch paths on a frame-by-frame basis, which allows the system to adapt to varying channel conditions quickly and effectively.

Figure 2: MRD's system architecture. (Click image for full resolution figure.)

The main challenge of fine-grained AP selection is designing an efficient and effective algorithm for choosing the appropriate AP for data transmission. In theory, a path-selection algorithm should select the best path for each data frame transmission to reduce loss and delay. To do so, a system must acquire accurate knowledge of the wireless channel condition of each available path within a few milliseconds, which is difficult to implement in practice.

Our hypothesis is that selecting the best path for every data frame is unnecessary to achieve good results. We observe that frame losses usually occur in bursts, especially when the receiver is mobile, and different transmission paths often exhibit weakly correlated channel conditions. Therefore, we develop a path selection heuristic that monitors only the current transmission path. When the current transmission path has fallen into a bad state, the system can avoid burst losses in the original path by diverting the subsequent transmissions to an alternate path.

We develop a second path diversity technique called spatial packet combining. In this technique, we configure multiple APs to listen on the same radio frequency, allowing multiple APs to receive a copy of the client's uplink transmission. The Diversity Controller gathers all received copies of the same transmission and forwards the data on to the rest of the network if any one packet copy is received correctly.

In many cases, corrupted data frames contain a large number of correct data bits, which may be salvaged for error recovery. Thus, when none of the APs receive a correct copy of the transmitted data frame, the Diversity Controller can save the corrupted data frames and perform error recovery by combining the data bits from different corrupted copies of the same transmitted frame. Table 1 illustrates how the packet combining algorithm works.

Because different APs receive a copy of the transmitted data frame simultaneously, the Diversity Controller can often recover a packet immediately without requiring a retransmission from the client. When needed, the Diversity Controller can also perform combining with retransmitted data frames to increase its effectiveness of recovering corrupt packets.

However, the main challenge behind spatial packet diversity is the complexity of the algorithm. The packet combining algorithm locates bit differences between the received copies of the same packet and flips the unmatched bits until the payload passes the data checksum. The combinatorial search in this algorithm has a computational complexity that grows exponentially with respect to the number of corrupt bits in a data frame.

We exploit the observation that bit errors in a frame often occur in bursts. Thus, instead of operating at the bit level, we bound the computational complexity by subdividing a packet into fixed-size blocks and combining packets in the block level.

Experimental Results

We design and implemented MRD as a fully functional WLAN infrastructure optimized for 802.11 WLANs. We deployed a small scale indoor testbed to evaluate the performance of fine-grained path selection and spatial packet combining. Our experimental results show that fine-grained path selection can reduce frame loss rates for mobile clients by as much as 26% compared to a fixed-path scheme that uses the best available transmitter. Receive diversity and frame combining provided throughput gains of up to 3x over conventional 802.11 communication schemes. For a detailed description of MRD's design and analysis of our experimental results, please consult the references below.

References:

[1] Allen Miu, Hari Balakrishnan, Can Emre Koksal. Improving Loss Resilience with Multi-Radio Diversity in Wireless Networks. In Proc. of 11th ACM MobiCom, Cologne, Germany, August, 2005. (1 of 3 Best Paper Candidate)

[2] Allen Miu, Godfrey Tan, Hari Balakrishnan, John Apostolopoulos. Divert: Fine-grained Path Selection for Wireless LANs. In Proc. of 2nd ACM MobiSys, pp. 203--216, Boston, MA, June 2004.

[3] Allen Miu, John Apostolopoulos, Wai-tian Tan, Mitchell Trott. Low-Latency Wireless Video Over 802.11 Networks Using Path Diversity. In Proc. of IEEE ICME, vol. 2, pp. 441--444, Baltimore, MD, July 2003.