Optimization of template-driven scheduling mechanisms: Regularity measures and computational techniques

Template-driven scheduling mechanisms provide a simple and robust scheme for sharing a resource among several traffic classes. The performance of such scheduling mechanisms critically relies on the regularity properties of the template. An important application, which motivated our study, arises in the context of weighted round-robin cell scheduling algorithms used for (de)multiplexing the various traffic streams in high-speed switches. In that setting, regularity of the template significantly reduces cell delay and delay variation (jitter), and equally important, the burstiness of the outgoing stream. We propose a measure for quantifying the regularity in terms of the spacing of the slots assigned to the various classes. The proposed criterion is consistent with common regularity notions, while the structural form allows for the computation of an optimal template using a quadratic assignment formulation. We also establish the asymptotic optimality of simple and fast heuristic algorithms in a scenario with a large number of traffic classes. Numerical experiments demonstrate that the heuristic procedures yield excellent results, even if the regime of asymptotic optimality does not strictly apply.