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

S.C. Borst, K.G. Ramakrishnan

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)19-33
Number of pages15
JournalJournal of Scheduling
Issue number1
Publication statusPublished - 1999


Dive into the research topics of 'Optimization of template-driven scheduling mechanisms: regularity measures and computational techniques'. Together they form a unique fingerprint.

Cite this