We analyze a switch with cross-bar constraints. Beginning with an initial loading and no further arrivals, we provide necessary conditions for a scheduling policy to minimize the workload at all times. We show that these conditions are sufficient for a switch of size N x 3 or smaller. We then consider a weaker notion of optimality: cumulative average workload optimality. Using a counter example for a 7 x 7 switch, we show that it is not possible to approximate the cumulative average workload within (1+4/475) of the optimal at all times. We conjecture that the workload under the MVM policy is within twice of the optimal at all times.
No takes yet. Share an insight, caveat, or question.
Gupta et al. (2009) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: