Stability of size-based scheduling disciplines in resource-sharing networks

I.M. Verloop, S.C. Borst, R. Núñez Queija

Research output: Contribution to journalArticleAcademicpeer-review

22 Citations (Scopus)

Abstract

Size-based scheduling strategies such as Shortest Remaining Processing Time first (SRPT) and Least Attained Service first (LAS) provide popular mechanisms for improving the overall delay performance by favoring smaller service requests over larger ones. The performance gains from these disciplines have been thoroughly investigated for single-server systems, and have also been experimentally demonstrated in web servers for example. In the present paper we explore the fundamental stability properties of size-based scheduling strategies in multi-resource systems, such as bandwidth-sharing networks, where users require service from several shared resources simultaneously. In particular, we establish the exact stability conditions for the SRPT and LAS disciplines in various limiting regimes. The results indicate that size-based scheduling strategies may fail to use the available resources efficiently, and in fact cause instability effects, even at arbitrarily low traffic loads, and will therefore not yield optimal delay performance. The qualitative findings confirm the tendency for users with long routes and large service requirements to experience severe performance degradation.
Original languageEnglish
Pages (from-to)247-262
JournalPerformance Evaluation
Volume62
Issue number1-4
DOIs
Publication statusPublished - 2005

Fingerprint

Dive into the research topics of 'Stability of size-based scheduling disciplines in resource-sharing networks'. Together they form a unique fingerprint.

Cite this