Realizing airtime allocations in multi-hop Wi-Fi networks: A stability and convergence study with testbed evaluation

Abstract

REACT is a distributed resource allocation protocol used to negotiate a max–min allocation of airtime for multi-hop ad hoc wireless networks. Two approaches are proposed for a node to realize its REACT allocation in a contention-based MAC protocol. This is achieved by tuning its contention window to a value that corresponds to its allocation. Only a change in the allocation, due to a change in local traffic requirements or local network views, results in re-tuning. The approaches for tuning are implemented in commercial Wi-Fi devices and their stability and convergence are studied experimentally in the w-iLab.t wireless network testbed. These properties are also studied analytically to support the experimental results. In addition, REACT is extended to support airtime reservations for multi-hop flows. With a reservation in place, multi-hop TCP flows exhibit improved performance metrics when running over REACT than when running over 802.11 DCF in the w-iLab.t testbed.

Introduction

Most wireless networks, such as cellular networks, rely on fixed network infrastructure. Instead, ad hoc wireless networks emerge spontaneously, formed by nodes communicating directly or through multi-hop paths. Though Wi-Fi and cellular coverage are nearly ubiquitous, there remain situations where network infrastructure is not present, not useable, or perhaps even maliciously inoperative.

For example, after disasters such as the wild fires in California and the Boston marathon bombing, cellular networks have been overwhelmed and have even failed [2], [3]. In the 2016 Gambian presidential election both the Internet and cellular networks were blocked [4]. Hong Kong street protesters faced a similar problem in 2014 and turned to the FireChat application program [5], [6]. This app uses the capabilities already present in the IEEE 802.11b standard [7], i.e., Wi-Fi, to allow users to communicate in an ad hoc manner. While 802.11 based ad hoc networks still face many challenges for their widespread use, variants of 802.11 are likely to continue to coexist with future cellular (5G) networks [8], [9], [10].

A specific challenge of Wi-Fi networks is that their performance is known to degrade dramatically when node density is high, and when flows are sustained over multiple hops. These conditions arise when multiple networks coexist [11], [12] and when large access infrastructure is deployed [13], [14]. The degradation results from the starvation and unfairness associated with carrier sense multiple access (CSMA) based protocols, of which Wi-Fi is one. This is attributed to a mismatch of local views that nodes have of the wireless medium, and to high levels of contention when the network is congested [15].

To mitigate such problems, several approaches have been proposed. These include adopting rate limiters on nodes [16], [17], [18], using multi-hop reservations [19], [20], using different access priorities for data and control traffic [21], [22], and exploiting admission control [23], [24]; see also Serrano et al. [25]. Instead, we control the airtime of each node differently.

Airtime measures the channel time in which a link is sensed busy due to frame transmissions. Airtime measurements are position-dependent, because channel attenuation differs for each transmitter–receiver pair. While airtime has been applied in routing in mesh networks [16], [26], and in admission control [27], we use a measurement-driven approach to control the airtime allocated to each node by the REACT distributed resource allocation protocol [28]. We use REACT to negotiate airtime allocations among nodes on the basis of their traffic requirements and their local network views.

The idea is to tune the contention window (CW) dynamically at each node to achieve its allocation. There has been much work on contention window tuning. Among the first may be MACAW [29], which replaced binary exponential backoff with a multiplicative increase and linear decrease (MILD) of the contention window size to improve fairness. Other work tunes the contention window to achieve a theoretical throughput limit [30]. Adaptive schemes continue to be proposed for ad hoc networks [31], [32], [33] and their variants, including vehicular ad hoc networks (VANETs) [34], [35], [36], wireless sensor networks (WSNs) [37], [38], and others.

Our objective in this paper is different: Our aim is to tune the contention window at each node to realize a specific airtime allocation. We develop two mechanisms for this purpose, one based on renewal theory (RENEW) and another using a control theoretic approach (SALT). Each is compatible with the 802.11 standard and has been implemented on legacy devices. Extensive experimentation in the w-iLab.t wireless network testbed [39] shows that each approach is able to tune the contention window to align allocations to those negotiated by REACT.

However the stability and convergence properties of these two tuning approaches differ from each other. RENEW converges more quickly to an airtime allocation, while SALT yields more stable and accurate allocations. A study of these properties analytically supports these observations from the experimental results, and suggests how RENEW and SALT could be combined to obtain the benefits of each.

We also extend REACT to reserve an allocation along the end-to-end path of a multi-hop flow. This requires that neighbours of the nodes along the forwarding path take the reservation into account as part of their own negotiations for airtime. We consider TCP multi-hop flows in experimentation on w-iLab.t which are known present many challenges. In addition to the unreliable wireless transmission at each hop, contention from hidden and exposed nodes constrain the TCP throughput achievable over a multi-hop path [40]. Gupta et al. [41] have conducted experimentation with TCP over 802.11 in a physical wireless network. However, their emphasis is on how TCP throughput is affected by routing, user mobility, and the network diameter rather than on the impact of the MAC protocol. While no performance advantages for TCP were found in their results [41], we have achieved slightly higher TCP throughput in running the flow with REACT over our contention window tuning, than over 802.11.

In summary, this paper makes three contributions:

• Two measurement-based approaches, RENEW and SALT, for a node to tune its contention window dynamically to realize a specific airtime allocation are proposed, implemented on legacy Wi-Fi cards, and evaluated in the w.i-Lab.t network testbed.

• The stability and convergence of RENEW and SALT are studied analytically and found to support the observations from the experimental results.

• An extension of the REACT protocol to reserve an allocation along the end-to-end path of a multi-hop flow is provided, and evaluated in w-iLab.t on multi-hop TCP flows.

The rest of this paper is organized as follows. In Section 2, we overview the REACT protocol used for negotiating channel airtime. Section 3 presents two contention window tuning algorithms, RENEW and SALT, for realizing an airtime allocation. In Section 4 we compare the two algorithms, present their implementation in legacy commercial Wi-Fi cards, and evaluate how well each achieves an allocation. Section 5 studies the stability and convergence properties of the tuning algorithms, supporting the experimental results in Section 3. It also suggests how the two approaches may be combined, using RENEW to tune SALT. Section 6 provides an algorithm to reserve airtime for a multi-hop flow in the REACT framework and evaluates the algorithm for multi-hop TCP flows. Finally, we summarize and propose future work in Section 7.