Beyond processor sharing
While the (Egalitarian) Processor-Sharing (PS) discipline offers crucial insights in the performance of fair resource allocation mechanisms, it is inherently limited in analyzing and designing differentiated scheduling algorithms such as Weighted Fair Queueing and Weighted Round-Robin. The Discriminatory Processor-Sharing (DPS) and Generalized Processor-Sharing (GPS) disciplines have emerged as natural generalizations for modeling the performance of such service differentiation mechanisms. A further extension of the ordinary PS policy is the Multilevel Processor-Sharing (MLPS) discipline, which has captured a pivotal role in the analysis, design and implementation of size-based scheduling strategies. We review various key results for DPS, GPS and MLPS models, highlighting to what extent these disciplines inherit desirable properties from ordinary PS or are capable of delivering service differentiation. Keywords: Discriminatory Processor Sharing; Generalized Processor Sharing; Multilevel Processor Sharing; asymptotic analysis; insensitivity; queue length; size-based scheduling; slowdown; service differentiation; sojourn time; delay minimization; workload.
|Discriminatory Processor Sharing, Generalized Processor Sharing, Multilevel Processor Sharing, asymptotic analysis, insensitivity, queue length, size-based scheduling, slowdown, service differentiation, sojourn time, delay minimization, workload"|
|Performance evaluation; queueing; scheduling (msc 68M20), Queueing theory (msc 60K25), Communication networks (msc 90B18)|
|Logistics (theme 3), Energy (theme 4)|
|CWI. Probability, Networks and Algorithms [PNA]|
Aalto, S, Ayesta, U, Borst, S.C, Misra, V, & Núñez Queija, R. (2007). Beyond processor sharing. CWI. Probability, Networks and Algorithms [PNA]. CWI.