Optimal Scheduling Policies in Small Generalized Switches

The authors consider small generalized switches with less than or equal to four links, and study scheduling policies designed to minimize the total number of packets in the system. By focusing on very small switches, they are able to derive optimal or heavy-traffic optimal policies whose performance can then be compared to previously conjectured optimal policies. In particular, it has been conjectured that the max-weight policy with weight q?¿ is optimal in heavy-traffic when ?¿ ?¨ 0. The results show that this conjecture is not true.