Most balancing algorithms for optimal packet scheduling in multi-server wireless systems

We present an algorithm to implement “most balancing” packet scheduling policies in a discrete-time multi-server system of parallel queues with independent random queue-server connectivity. The MB policies are characterized by minimizing the total difference in queue lengths at every time slot. The proposed algorithm produces the server allocation strategy that achieves the minimum “imbalance index” at every time slot. This algorithm has a reduced computational complexity compared to a full-search through the set of all feasible policies. We also provide a low-complexity approximate implementation algorithm that performs close to the exact algorithm. Simulation results confirm our claims.