• Twitter
  • Facebook
  • Google+
  • LinkedIn

Throughput Optimization and Delay Sensitive Scheduling in Next Generation WiFi

Name: Muhammad Inamullah

Department: CSE

Program: Ph D. (6th year)

Name of supervisor: Prof. Bhaskaran Raman

Importance or applications of the research

Wireless LAN (WLAN or, more popularly, WiFi) is the de facto technology nowadays for wireless internet access in places ranging from homes to large industrial complexes. In spite of its success in consumer internet access, we still cannot use WiFi in such time-critical applications as industrial control and for remote control of vehicles and drones that need time bound packet delivery, because we cannot guarantee such deadlines due to contention based channel access. By ‘contention-based’ we mean all stations (STAs) connected to an access point (AP), and the AP itself, have equal right to grab the channel (that is, the air, in which they send their packet like a broadcast signal) and send their packet. All the STAs who want to send a packet compete to capture the channel, and only the winning STA can send its packet at a time. Though all STAs follow the same defined protocol for channel access, there is some chance that packet could not reach the receiver because, for example, there was a collision as two STAs sensed the channel idle and started transmitting their packets at exactly the same instant and both the packets were lost, or because a transmitter or receiver moved and the signal was lost. That is why we say that the WiFi employs a best effort service, and packet delays cannot be guaranteed.

Novelty

Recently, the IEEE 802.11ax amendment has included OFDMA (which is short for orthogonal frequency division multiple access), which brings in one important change especially for uplink (UL) traffic: now the channel access is changed from being contention-based all the time to a mechanism that puts AP in charge of deciding each STA's access to the channel. 

To provide for OFDMA-based access the AP assigns one resource unit (RU) – a group of OFDM subcarriers – per STA and the STAs transmit in their RUs parallely. This is called scheduled UL OFDMA. The other is UORA (UL OFDMA random access), where a group of STAs is assigned an RU and the STAs of the group contend for that particular sub-band. We discuss the first type.

When AP schedules UL RUs, it optimizes some metric, which is generally either the overall throughput or the upload time. But with time sensitive networking, the better quantity to be optimized is the number of packets dropped due to deadline, and the problem becomes how to assign RUs to STAs such that such packet drops are minimized. We minimize such packet-drops by giving the first chance to transmit to a STA whose  head-of-line (HOL) packet (i.e, a packet positioned in the front of the queue) has the earliest deadline. To schedule, the AP needs to know the deadlines of HOL packets. But even with the knowledge of delay tolerance of traffic classes, the AP cannot be sure of the deadline of an HOL packet because it does not know how much time the packet has spent in its queue.

Thus the novelty of our work lies in enabling the AP estimate the deadlines with the mere knowledge of the queue size that each associated STA reports to the AP. 

Methodologies adopted

We employ Little’s theorem to reach an expression for  deadlines of HOL packets waiting at STAs, and schedule the up link transmissions as per the remaining time to deadlines using UL OFDMA.

A couple of most significant results

Results show a five to six times reduction in packet drops when the AP schedules RUs to minimize the number of packets that miss the deadlines while estimating the deadlines with our algorithm, compared to the conventional approach of scheduling based on minimum total upload time. In fact, even simply using the delay tolerance plus the current time as deadline, without considering the packet delays in queues, reduces packet drops by up to 3 times.

We validated the results with random as well as real IoT traffics, with the same delay tolerance for all traffic flows versus different values of delay tolerance, with changing BSR and rescheduling period, and with changing the channel conditions. Our approach works well in all these varying conditions, and in the worst case remains better than the conventional approach of scheduling to minimize upload time. We show in Figure 1 the results with our scheduling, where the packet drops due to deadlines are much less for two variants of our algorithms (SCHD-NR and SCHD-DE) as compared to the existing approach of minimizing the upload time (MINUL). ACTUAL in the figure shows the ‘would-be’ packet drops in the hypothetical case of AP knowing exact deadline of every HOL packet.

More about this work can be read in our  paper titled “Will My Packet Reach On Time? Deadline-Based Uplink OFDMA Scheduling in 802.11ax WLANs” in the ACM Digital Library (available after the MSWiM 2020 Conference of 16  Nov 2020)

Conclusions

The important insights we gained about OFDMA and time sensitive traffic are that smaller the delay tolerance, smaller should be the OFDMA rescheduling (and BSR reporting) period, and that if the packet delay in queues is known to the AP, the deadlines can be honored in a better way. The best option would be that the standard is amended to include a mechanism of reporting the time the HOL packet was enqueued, in which case, as we have shown in our implementation, the number of packets that miss their deadlines will be even lower than that obtained with our estimated deadlines.

A problem that may arise out of our scheduling algorithm is that always assigning the RUs to the earlier-deadline STAs first can cause starvation of STAs with best effort traffic. This can be solved if we allocate some  random access RUs (through uplink OFDMA random access or UORA) for best effort traffic, and allow such STAs to contend for channel within these RUs.

Figure: Fraction of bytes dropped out of total arrived at STA queues, totaled across the 14 nodes that send delay-bound traffic