Optimal scheduling for jobs with progressive deadlines
- 1 April 2015
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2015 IEEE Conference on Computer Communications (INFOCOM)
- p. 1113-1121
- https://doi.org/10.1109/infocom.2015.7218485
Abstract
This paper considers the problem of server-side scheduling for jobs composed of multiple pieces with consecutive (progressive) deadlines. One example is server-side scheduling for video service, where clients request flows of content from a server with limited capacity, and any content not delivered by its deadline is lost. We consider the simultaneous goals of 1) minimizing overall loss, and 2) differentiating loss fractions across classes of flows in proportion to relative weights. State-of-the-art policies, like Discriminatory Processor Sharing and Weighted Fair Queueing, use a fixed static proportional allocation of service rate and fail to achieve both goals. The well-known Earliest Deadline First policy minimizes overall loss, but fails to provide proportional loss across flows, because it treats packets as independent jobs. This paper introduces the Earliest Progressive Deadline First (EPDF) class of policies. We prove that all policies in this broad class minimize overall loss. Furthermore, we demonstrate that many EPDF policies accurately differentiate loss fractions in proportion to class weights, satisfying the second goal.Keywords
This publication has 14 references indexed in Scilit:
- On queues with impatience: stability, and the optimality of Earliest Deadline FirstQueueing Systems, 2013
- Heavy traffic analysis for EDF queues with renegingThe Annals of Applied Probability, 2011
- Introduction to Packet Scheduling Algorithms for Communication NetworksPublished by IntechOpen ,2010
- A Method for Performance Analysis of Earliest-Deadline-First Scheduling PolicyThe Journal of Supercomputing, 2006
- Real-time queueing theoryPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A new scheduling mechanism to provide relative differentiation for real-time IP trafficPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Service disciplines for guaranteed performance service in packet-switching networksProceedings of the IEEE, 1995
- A generalized processor sharing approach to flow control in integrated services networks: the multiple node caseIEEE/ACM Transactions on Networking, 1994
- A formal proof of the Deadline Driven schedulerLecture Notes in Computer Science, 1994
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973