Effort-limited Fair (ELF) Scheduling for Wireless Networks

While packet scheduling for wired links is a maturing area, scheduling of wireless links is less mature. A fundamental difference between wired and wireless links is that wireless media can exhibit substantial rates of link errors, resulting in significant and unpredictable loss of link capacity. This capacity loss results in a special challenge for wireless schedulers. For example, a weighted fair queue (WFQ) scheduler assumes an error free link and specifies how flows should share the link capacity. However, this specification is not sufficient to determine the correct outcome when link capacity is sharply reduced, because flows that have been allocated the same weights may differ greatly in their ability to tolerate throughput loss. In this paper, we first describe the wireless scheduling challenge in terms of an effort-outcome disconnection. Next we propose a novel notion of fairness for wireless links, effort-limited fairness (ELF), which extends WFQ via dynamic weight adjustments. ELF guarantees that all flows experiencing an error rate below a per flow threshold receive their expected service, defined as a specified rate for reserved flows or a specified share of best-effort capacity for best effort flows. After motivating and defining ELF, we present a practical approximation algorithm, which we evaluate through both trace-driven simulation and measurement of a prototype wireless radio network based on the WaveLAN physical layer