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

S.C. Borst, K.G. Ramakrishnan

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    2 Citaten (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.
    Originele taal-2Engels
    Pagina's (van-tot)19-33
    Aantal pagina's15
    TijdschriftJournal of Scheduling
    Nummer van het tijdschrift1
    StatusGepubliceerd - 1999


    Duik in de onderzoeksthema's van 'Optimization of template-driven scheduling mechanisms: regularity measures and computational techniques'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit