Instability of the Proportional Fair Scheduling Algorithm for HDR

In this letter, we study the Proportional Fair scheduler that has been proposed for scheduling in the high data rate (HDR) wireless data system. We consider a single basestation transmitting to a set of mobile users. In each time slot, the scheduler has to decide on a mobile to which it will transmit data. The decision is based on information that the basestation receives about the time-varying channels between itself and the mobiles. We focus on deciding whether or not Proportional Fair is stable in a situation with finite queues and a data arrival process. That is, we wish to decide if Proportional Fair keeps all queues bounded whenever this is feasible. There are, in fact, multiple versions of Proportional Fair, depending on how it treats small queues. In this letter, we consider six different versions and show that all are unstable for one simple example.