Effort-limited Fair (ELF) Scheduling for Wireless Networks

Abstract— 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 fair-ness for wireless links, effort-limited fairness (ELF), which extends WFQ via dynamic weight adjustments. ELF guarantees that all flows experiencing a