PAQ: A Starvation-Resistant Alternative to Proportional Fair

Proportional Fair (PF) is a frequently used channel- aware scheduling algorithm in 3G wireless networks. However, recent work by us and others has shown that, in practice, PF suffers from significant robustness issues that can unnecessarily starve "well-behaved" users. In this paper, we analyze these issues with the goal of developing an alternative scheduling algorithm more robust than PF. We start by identifying two scenarios in which PF can cause starvation. We analyze both scenarios and develop mechanisms that prevent such starvation. Then, we combine these mechanisms to propose our Parallel Adaptive Quantile-based (PAQ) scheduling algorithm. We use simulation experiments with synthetic and measurement-based traces of wireless channel conditions to show that PAQ is not only robust but also achieves comparable or better throughput and fairness than PF.