Linear complexity algorithms for maximum throughput in radio networks and input queued switches

A resource allocation model that has within its scope a number of computer and communication network architectures was introduced by Tassiulas and Ephremides (1992) and scheduling methods that achieve maximum throughput were proposed. Those methods require the solution of a complex optimization problem at each packet transmission time and as a result they are not amenable to direct implementations. We propose a class of maximum throughput scheduling policies for the model introduced by Tassiulas and Ephremides that have linear complexity and can lead to practical implementations. They rely on a randomized, iterative algorithm for the solution of the optimization problem arising in the scheduling, in combination with an incremental updating rule. The proposed policy is of maximum throughput under some fairly general conditions on the randomized algorithm.