On Optimal Scheduling Algorithms for Small Generalized Switches

摘要

It has been conjectured that MWS-$alpha $ scheduling policies with $alpha $ going to zero are heavy-traffic optimal for scheduling in a generalized switch when the objective is to minimize the number of backlogged packets in the system. We examine this conjecture by first deriving optimal or heavy-traffic optimal policies for small switches and then comparing them to MWS- $alpha $ policies by simulation. Our conclusion is that the conjecture is not true in general, i.e., there are simple topologies for which there exist policies that outperform MWS-$alpha $ in heavy traffic.