Abstract:
We present results on the stability of MaxWeight and Proportional Fairness, both of which are policies that are readily employed in the analysis of communications systems. MaxWeight is a greedy policy that does not depend on knowledge of arrival rates and is straightforward to implement. We prove that MaxWeight itself is not in general maximally stable in networks where jobs move between queues. We prove MaxWeight is maximally stable in a more restrictive setting, and that a weighted version of MaxWeight, where the weighting depends on the traffic intensity, is always stable. We introduce a scheduling policy for FIFO networks, the Proportional Scheduler, which is based on the proportional fairness criterion. We show that the Proportional Scheduler has a maximal stability region and does not require explicit knowledge of traffic arrival rates. The Proportional Scheduler has the advantage that information about the network's route structure is not required for scheduling, which substantially improves the policy's performance for large networks.

Based on joint work with Maury Bramson and Bernardo D’Auria.

Go to recording (lecture starts at 4:00)
Go to slides