Borrowed Channel Relaying: A Novel Method to Improve Infrastructure Network Throughput

Current 802.11 wireless networks are typically infrastructure-based, where an Access Point (AP) and its clients form a Basic Service Set (BSS). Virtually all traffic within these networks is between the AP and its clients. To leverage the fundamental tradeoff between channel quality and transmission speed, 802.11 devices are designed with the ability to operate at different data rates. This capability, known as rate diversity, allows an 802.11 device to use more efficient modulation schemes during better channel conditions. Unfortunately, in practical networks, rate diversity was observed to cause a detrimental effect, called the "performance anomaly" [1]. This anomaly refers to the fact that when one client throttles back its data rate, the throughput of all clients serviced by the same Access Point (AP) suffers substantially: the fast clients see their throughput decreased to a rate comparable to that of the slow client. This is illustrated in Figure 1, which shows the throughput of a fast 802.11b client versus the total number of clients in the system, for two cases: one with one slow client (1 Mbps), and one where all clients are fast (11 Mbps). Regardless of how many clients are in the system (the value on the x-axis), just one client becoming slow moves the performance of all other clients from the top line to the bottom line. The reason is that a slow link transmitting at 1 Mb/s captures the channel eleven times longer than a link using 11 Mb/s.

To alleviate this performance anomaly, relaying was proposed as an effective mechanism [2, 3]. This principle is illustrated in Figure 2 for the case of downlink traffic, that is, from the AP to a client. Instead of using a slow link between the AP and client, the use of a relay (i.e., another client acting as a forwarder node) can improve the overall throughput. The idea is that two fast transmissions (AP to relay and relay to client) can occupy less time than a single slow transmission, therefore freeing channel access time for other transmissions. Although significant benefits are attainable in principle, relaying hinges solely on the availability of relay nodes with good channels. To evaluate relaying in a more realistic setting, we performed actual field experiments using our own 802.11b platform, called CalRadio [4]. Unfortunately, our versus-range experiments indicated that the benefits of relaying are minimal except for very specific scenarios where relay nodes are placed optimally as we will show in Section 5.3.

However, we have also discovered that relaying can be much more effective if cleverly combined with channel borrowing between access points. The idea is that if one Basic Service Set (BSS), a group of nodes consisting of an AP and its clients, is lightly loaded, the channel assigned to it could be used by a neighboring BSS to significantly improve the performance of relaying. This will alleviate the transmission bottleneck around the access point, which was found to be the main obstacle to throughput enhancement. In this paper, we will introduce this novel concept of relaying with channel borrowing, propose a practical protocol solution, and demonstrate its ability to achieve significant overall throughput performance enhancement.

Before getting to the details of our relaying with channel borrowing, we will take a small step back to list some of the different concepts related to relaying and rate diversity that have been proposed to enhance throughput in 802.11-type networks. One of the first ideas was to leverage multihopping for spatial reuse. In a wireless network, using multiple short hops can increase the number of simultaneous transmissions if combined with power control (note that this work assumed that all nodes have a fixed data rate, so it does not exploit rate diversity) [5]. However, it was also observed that if most traffic goes to and from an access point, spatial reuse alone does not lead to an increase in network throughput [5]. The reason is that the access point remains the bottleneck, and each path is basically contending for the same resources, much the same way direct transmissions would. The first main point to realize is that infrastructure networks thus behave fundamentally differently than mesh networks: the access point is the true bottleneck and spatial reuse by itself does not alleviate this problem!

It was realized that another motivation for using multihop routes is to overcome bad channel conditions [6]. This could be thought of as a generalization of range-extension. Since in a typical wireless local area network (WLAN) scenario, devices support multiple data rates; the best rate can be chosen on each link. With such use of rate diversity, a succession of multiple fast hops can free up time on the channel compared to one slow hop. In a scenario where traffic flows to and from an access point, this approach can alleviate the observed bottleneck there, which is the throughput limiting factor in these types of networks. Specific protocols, called rDCF (relay distributed coordination function) and rPCF (relay point coordination function), have been proposed to take advantage of this situation [2, 3]. They are modifications of the 802.11 standard to include such relaying in combination with rate diversity, and basically explore the use of a single relay in a 2-hop path as was illustrated in Figure 2. However, we have found through experimental testing that while these protocols can increase network throughput in carefully constructed scenarios, the amount of throughput gain realized in a network with random node placement is low. The reason is that the probability of having two fast hops to replace a much slower one is small, given the specific dependence of rate versus distance for typical 802.11 devices. We will further illustrate this in Section 4.

Figure 3 illustrates the operation of these protocols, as well as their benefits and drawbacks. Figure 3(a) shows the scenario where the AP sends directly to the client; the link is assumed slow and communication therefore takes up a significant amount of channel time. Note that during this transmission, the relay node experiences a busy channel and would be unable to receive or send data to any other node. In Figure 3(b), we depict the principle of rDCF. By using the relay as an intermediate hop, the slow communication is replaced by two faster ones, thereby giving other nodes more time to access the channel. In practice however, the possible gains are small, as it is not very likely that two transmissions will take much less time than a single slow one. On the flip side, this figure also shows the key element we will exploit in our scheme. During the second communication, the AP sits idle, as it would interfere with the relay-client communication. However, it is also not doing anything useful. As the AP is really the bottleneck in these networks, having the AP sit idle has a direct negative impact on the overall throughput. Therefore, conceptually, we must devise a mechanism to allow the access point to remain busy most of the time by servicing another client during the second packet transmission in Figure 3(b). This is possible by changing the relay-client transmission such that it does not interfere with the AP, by using a separate channel.

The main problem with the relaying setup in rDCF and rPCF is that of the two hops in the path (AP-relay and relay-client ), only one of them can be active at the same time. As such, the combination of both hops, in terms of time-on-the-channel, has to outperform the direct link ( ). For example, in Figure 2, if both and are slow, relaying will not be beneficial, even if link from the AP is fast. Since the access point is the actual bottleneck, ideally one would hope to be able to exploit the fast link r₁ from the AP. Basically, due to its bottleneck status, any throughput gain for the AP translates into similar benefits to the network. The problem with rDCF and rPCF is that the second hop forces the AP to sit idle, thereby wasting valuable resources. In this paper, we solve this problem by leveraging yet another degree of freedom in 802.11 networks: the channel assignment. Current 802.11 infrastructure networks are frequency planned with static partitioning of spectrum. The total of spectrum available to the network as a whole is split up in channels. For example, there are 3 nonoverlapping channels for 802.11b in the United States. Other variants of 802.11, such as 802.11a in the 5 GHz band, have 12 nonoverlapping channels, which is even more beneficial for our protocol as we will see in this paper. Each BSS is typically assigned just one channel, so a heavily used AP can have its single channel nearly maxed out while a nonoverlapping channel assigned to a neighbor BSS sits idle. By allowing a single BSS to use more than one channel, more than one transmission can occur simultaneously, therefore improving throughput. This is the basis of the novel approach we propose in this paper: relaying and rate diversity combined with borrowing channels between BSS'. Each node (AP, relay or client) still only uses one channel at a time. However, the AP-relay links and relay-client links operate on different channels through careful coordination. In certain common scenarios, such as an AP in a busy hotel conference room next to lightly used APs in hallways and guest rooms, our protocol is likely to work well because the probability that additional channels will be available at any given time is high. In [7], some of our colleagues monitored the load on 4 APs providing service to attendees of an ACM conference at UC San Diego. They found that most of the long sessions (devices associated with an AP for greater than 10 minutes) have very low average data rates, which they conclude to be machines of users who associate with an AP and then remain idle as they pay attention to the conference sessions. They also found that load distribution at the APs was very bursty and uneven and was governed mostly by individual users and workloads rather than the number of users associated at any given time. We would like to point out that putting two transceivers on the AP, although also directly attacking the bottleneck in these systems, is not an option. The reason is that self jamming will occur if one transceiver is transmitting while the other is receiving [8]. Though they would use different channels, they operate in the same band, very close in frequency. The transmitter can easily be 50 dB or more above the received signal and even the best filters cannot handle this type of interference almost directly adjacent to the received channel. This is in contrast to systems that are designed to transmit and receive at the same time, like cellular base stations. Unlike 802.11, these systems have the benefit of operating in paired spectrum, where transmit and receive frequencies are separated by a guard band relatively large compared to the channel size to prevent self jamming. Our usage of relay nodes essentially provides the means to do more than one simultaneous transmission without special hardware, within the existing frequency band structure, while avoiding self jamming.

Besides 802.11 networks, the idea of using relays to improve throughput has also been proposed for cellular networks. Most 2G cellular networks are frequency planned systems just like 802.11, with a static set of channels allocated to each cell. If one cell is heavily loaded while neighbor cells have light traffic, spectrum is not being used efficiently. Methods by which one cell can borrow unused spectrum from neighboring cells have been developed [9, 10]. Later works have looked at the use of relays to improve throughput in 3G networks, which are all based on CDMA. The general idea is to use relays to forward packets to clients with poor channel quality [6]. Mobile devices with more than one interface can be used as relay stations and the relayed data can be sent between the mobile devices and the relay stations as either an in-band (licensed) transmission or an out-of-band (unlicensed) transmission. Cooperative diversity techniques, which can take advantage of the same types of diversity that MIMO uses but do not require more than one antenna on each node, can be used. In [11], the authors argue that using more than two hops results in only marginal throughput improvement but greatly increases the complexity of the routing algorithms, and found no reason to investigate algorithms with 3 or more hops in detail. They also found that two of the relay protocols can approximately double the throughput of 3G networks. It should be noted that [6, 11] rely on having more than one wireless interface per node, while our work assumes only one interface per node.

In 802.11, each node has an equal opportunity to gain access to the channel in any interframe space between packets, which translates to equal throughput if the packet size used by all nodes is fixed and each transmits as fast as possible. Some protocols, however, such as the Opportunistic Auto Rate (OAR) [12], attempt to redefine fairness as each node receiving a throughput proportional to the data rate, which roughly translates to an equal amount of time on (rather than opportunity to access) the channel. However, the AP remains a system bottleneck and all the time it spends transmitting to or receiving from nodes with a slow connection is still spent sending relatively few bits per unit time.

Work has also been published about the capacity of wireless networks using multiple channels [13‐15]. People have created MAC layers for 802.11 networks that use more than one channel [16]. In their simulations, traffic patterns did not necessarily reflect those of typical infrastructure networks with most of the traffic originating or terminating at a single node, and rate diversity was not considered. Mobile Ad Hoc Network (MANET) systems with multiple channels have been explored [17]. Another idea proposed is allowing traffic to pass through neighboring APs by having nodes explicitly switch channels since many nodes are in the transmission range of more than one AP [18]. This protocol was extended by allowing clients to relay and switch between various BSSes [19]. Rate diversity was not considered in either. The work in [20] takes rate diversity into account and uses a network of mesh routers to connect end users to gateways. Time is divided into superframes and each mesh node has a designated receive channel in each receive timeslot, with the remaining slots reserved for transmission. The receive pattern of each node is known to its neighbors, and a node wishing to relay a packet through a mesh node needs to transmit on the designated channel in a receive timeslot for the destination node. To help avoid conflicts, part of each superframe is reserved for downlink traffic and part for uplink traffic. Although this protocol outperformed the single channel network by up to 100%, it relies on the assumption that traffic loads across the network are steady over time. This is not the case in real networks, where bursty traffic might generate flows that are not optimal for the superframes, and the system would operate inefficiently until it could have time to adapt to the new traffic flows. Also, this protocol relies a reservation MAC, unlike our protocol which relies on the far more prevalent random backoff MAC and is therefore more suited for typical wireless networks and traffic patterns. We should emphasize that the major difference between our work and other multichannel MAC protocols is that while they focus on mesh networks with randomly generated one-to-one traffic, we focus on WiFi infrastructure networks with very different traffic patterns and a distinct bottleneck at the access point.

Other protocols require each device to have two transceivers [21]. This is the case in the vast majority of multichannel protocols. In [22], nodes are equipped with as many radios as necessary to make optimal use of the channels. The authors found that in general, nodes closer to the gateways need more radios (as they will be relaying more packets than nodes at the fringes of the networks). Besides the problem that this protocol requires special hardware, it is simply not practical to expect the nodes with the greatest number of radios to be located near the gateways in networks with mobile nodes.

Finally in [23], nodes can be equipped with as many radios as needed to optimize use of the available channels (at which point the number of simultaneous transmissions is limited by interference). Although throughput can be improved by as much as 4 to 7 times that of a single channel network, this required each node to be equipped with an average of 4 radios!

While using multiple radio interfaces works in theory, in practice the antenna location, channels used, and filters must be carefully controlled to avoid self jamming, and it is not practical because it both adds to the cost of the hardware and is not compatible with preexisting infrastructure.

Our method improves upon the rDCF and rPCF [2, 3] protocols by reducing the amount of time the AP's channel is occupied during the relay process. Since the AP is the bottleneck, the worst thing we can do is force it to sit idle, which is precisely what happens in rDCF and rPCF when packets are being relayed, because each BSS in rDCF and rPCF is allowed to use only one channel. Unlike many other multichannel MAC protocols, we assume that each node has only one transceiver, which makes our protocol possible to implement on existing hardware and does not increase the cost of the equipment required to use it.

802.11 networks are frequency planned systems, which result in inefficiencies from static partitioning of spectrum. Existing work had addressed how to improve throughput using multiple channels and relaying with rate diversity, but we realized that these protocols may not work well if there is random node placement. Also, many existing protocols designed for multichannel MACs assume that each node can have more than one transceiver, making them incompatible with existing hardware. Building on an idea from cellular networks, we introduced a new protocol that leverages channel borrowing and relaying in combination with rate diversity to further improve throughput without custom hardware.

We used our customizable 802.11b research platform, CalRadio, to obtain data on the data rate versus distance tradeoffs in 802.11b, and used these results as inputs to our simulations. We simulated our protocol in both Matlab and NS-2. In NS-2, we saw average gains of 20–30% for random placement, and 60% for ideal placement. We believe we can do even better. Our protocol is not limited to the 802.11 family, but will work with any protocol that provides a tradeoff between signal strength and data rate. The new 802.11n protocol, for example, provides even greater rate diversity with varying signal strength, so the potential gains are even greater. Unfortunately, while our protocol cannot be used with channel bonding in the 2.4 GHz band because there is not enough spectrum to borrow even one extra 40 MHz channel pair, it is an excellent candidate to use with 802.11n in the 5 GHz band, which provides 12 nonoverlapping channels instead of just 3. Another possible improvement comes from the fact that 802.11 transceivers are generally not designed to change channels frequently because in normal operation, switching channels is an infrequent event. If this time can be cut down significantly by designing the hardware to have the ability to rapidly change channels, even more throughput gains can be made. Our transceiver in CalRadio, for example, takes 200 microseconds to tune between channels [24], and since it contains a typical 802.11 physical layer implementation, we used this channel switching overhead time as an input to our simulations. If we used radios designed to switch channels much faster, our protocol would yield even larger throughput gains. Such a task is possible, as some ultra wideband (UWB) radios can switch channels in a few nanoseconds [25].