To implement the new restricted access window (RAW) medium access control mechanism in IEEE 802.11ah, stations (STAs) must be assigned to RAW slots based on their association IDs (AIDs). In this paper, we first identify the fixed subgroup problem with the current round-robin slot assignment. To address it, a novel AID shuffle mechanism is proposed for each STA to distributedly find a different and distinct temporary AID in each RAW. Each STA then reuses the round-robin slot assignment with its temporary AID. As a result, the set of STAs assigned to each subgroup/slot are randomized, yet with the same subgroup size. Simulation results show that the transmission fairness problem with the original round-robin assignment is solved and the system throughput is also improved.

Traffic generated by sensors can be classified into three types, periodic, on-demand, and alarm-triggered. In an IEEE 802.11ah WLAN, AP needs to support up to 8,000 sensors. To alleviate the channel contention, two new mechanisms, target wake time (TWT) and restricted access window (RAW), are introduced to facilitate channel reservation. While TWT is tailor-made for periodic traffic, a RAW-based paging scheme is designed in this paper for contention-free scheduling of on-demand traffic. Notably, alarm events (e.g., fire) are unpredictable and yet alarm reporting is time-critical. It is thus inefficient to handle alarm-triggered traffic by a channel reservation scheme. To this end, we propose to enhance the contention-based DCF by using a standard-compliant timer mechanism called limited local extension (LLE). With LLE, when a sensor with a pending alarm-report detects an alarm-report sent by another sensor, it extends its own backoff timer by a random duration. The random duration is chosen such that the total amount of extension is bounded by the current contention window size. Based on an existing alarm event propagation model, simulation results show that LLE can greatly shorten the alarm-reporting time.

A fat-tree network is scalable, but the probability of network faults also increases with the fat-tree size. Faulttolerant routing in fat tree is thus particularly important. Instead of relying on a time-consuming centralized recovery process, a fast local rerouting algorithm is highly desirable. A deflection based fast local rerouting algorithm, which we call it Local Rerouting by Deflection (LRD), was recently proposed to handle the network fault locally and dynamically. However, in LRD, all rerouted packets need to follow an elongated recovery path, which incurs extra propagation delay and additional network congestion. Aiming at addressing the inefficiency of LRD, a new local rerouting algorithm, called Local Rerouting by Backtracking (LRB), is proposed in this paper. With LRB, the faultdetecting switch immediately reroutes the affected packets back to where they came from until a V-turn switch is found. A V-turn switch is a switch from where an alternate minimal path to the destination is found. We show that LRB can minimize packet loss, incur no penalty in path length (except the small amount of backtracked in-flight packets), and treat backtracked packets as implicit fault notification. To ensure efficient implementation of our LRB algorithm, a simple self-routing (instead of table lookup) mechanism is devised to simplify the switch operation. As compared with LRD, we show by simulations that our LRB can minimize the TCP performance degradation caused by network faults.

A probabilistic quorum system (PQS) allows distributed services to be replicated on only a subset (quorum) of servers. The replicas can be kept consistent with high levels of assurance as long as any two quorums intersect with very high probability. PQS thus provides a means to trade off levels of consistency against the scalability and efficiency of a quorum system. When quorums are constructed by choosing members of the subset uniformly at random, the non-intersection probability can be easily computed. On a distributed system with n servers, uniform sampling is often conducted using random walk of length O(log n). To collect multiple uniform samples naively would require as many random walks. A number of works have relied on analytical results based on the Chernoff bound to reduce the number of random walks needed to collect multiple samples. Controlled flooding is another efficient method to collect multiple samples. In this paper we evaluate both methods analytically and found that quorums formed using either method cannot satisfy the non-intersection probability bound associated with quorum formed by uniform sampling. Our contributions are: (1) to show that overlay topology can be constructed to cache multiple random walks, (2) to show that repeated use of this cache to obtain multiple uniform samples leads to degradation of sample uniformity over time, and (3) to propose and evaluate graph re-wiring as a simple method to keep the cache fresh, to take advantage of overhead reduction of random walk caching while alleviating the degradation in sample uniformity.

To allow mobile devices to conserve energy, IEEE 802.11 standard specifies a power save mode (PSM). A station in PSM, i.e. a PSM-STA, will wake up at a predefined listen interval (LI) to receive frames buffered at the access point (AP) while it is sleeping. When a PSM-STA wakes up to receive a beacon and finds that there are no buffered frames, the PSM-STA experiences an unnecessary wakeup. In case of an unnecessary wakeup, the associated mode transition energy (i.e. from doze to awake and from awake back to doze) is wasted. According to the IEEE 802.11 standard, each STA chooses its own LI at the time of association, and the value chosen remains unchanged throughout its association duration. If LI=1, a STA wakes up at every beacon interval (BI). As a result, the data frame delay is minimized but the chance of unnecessary wakeup can be high. On the other hand, if a larger LI is used, the chance of unnecessary wakeup is reduced but the delay performance will suffer. Aiming at minimizing unnecessary wakeup without sacrificing delay performance, a dynamic listen interval (DLI) scheme is proposed in this paper. In essence, a STA increases its LI by one for every unnecessary wakeup experienced, and reset its LI to one when a necessary wakeup occurs. While more sophisticated schemes can be designed, we prefer this simple scheme for its compatibility with the existing standard. Simulation results show that when traffic is bursty, total energy consumption can be reduced without noticeable degradation in delay performance.

In an 802.11 WLAN, it can be observed that the shared wireless channel has a rush hour right after the periodic beacon frames. This is because mobile stations in power save mode (i.e. PSM-STAs) will wake up to retrieve data frames arrived at the access point (AP) while they are sleeping. PSM-STAs will stay awake until all buffered frames are retrieved. Notably, if the channel is congested, having all PSM-STAs staying awake will not improve the system delay performance but consume more power. Aiming at saving battery power while not affecting delay-throughput performance, a novel delayed wakeup (DW) scheme is proposed in this paper. Specifically, we divide a beacon interval (BI) into n sub-BIs. Then based on the amount of backlogged traffic, AP identifies and instructs “excess” stations to sleep immediately and wake up at a non-congested sub-BI later on. “Instructions” are judiciously encoded inside the modified traffic indication map (TIM) in the beacon frame. We show that our modifications are fully transparent to legacy stations. Last but not least, a seamless association procedure is designed to allow coexistence of legacy and DW-capable stations.