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)

    Abstract

    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
    Volume2
    Issue number1
    DOIs
    Publication statusPublished - 1999

    Fingerprint

    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