Is it enough to drain the heaviest bottlenecks?

This paper takes a philosophically new approach to throughput-optimal scheduling queueing systems with interference. All existing popular approaches (e.g. max-weight, greedy, ¿pick-and-compare¿ etc.) focus on the weights of individual queues. We take an alternative approach, by focusing instead on the aggregate queues of bottlenecks. A bottleneck is a set of mutually-interfering queues; a schedule drains a bottleneck if it removes a packet from any one of its queues. We consider (the standard) switch scheduling problem, where the bottlenecks are the nodes. We establish the following phase-transition (1) ensuring only that the very heaviest nodes are drained is not enough for throughput optimality, but (2) ensuring scheduling for all nodes with weight within (1-¿) of the heaviest is enough for throughput optimality, for any ¿ > 0. The proof uses a new Lyapunov function: the weight of the critical bottleneck. Our alternate node-focused view also enables the development of new algorithms for scheduling. We show (a) how any policy can be made throughput-optimal by doing a small number of extra operations, (b) a new algorithm - maximum vertex-weighted matching (MVM) - has (empirical) delay performance better than the current state of the art, and lower complexity than max-(edge)weighted matching, and (c) a class o f throughput-optimal policies that trade off between complexity and delay.