Revision of a Non-Preemptive EDF Packet Scheduling Algorithm
Dai Bui
EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2009-50
April 24, 2009
http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-50.pdf
One issue with today's Internet is that it only supports best-effort service; hence Internet users often experience unpredicted delay. Deployment of new real-time, highly reliable applications that require fixed delay bound on packets, such as remote surgery, become very difficult. Communication environment that can assert a strict delay bound will help estimate the worst-case execution time of distributed real-time applications. This paper revises a flaw in estimation of delay bound and an incorrect proof for of a non-preemptive Earliest Deadline First (EDF) packet scheduling algorithm used in packet scheduling for implementing real-time communication services in packet-switching network described in [1,2,3], which is one of few seminal works on guaranteed service in packet-switching network. We discuss the found flaw then correct the error and provide a substitute proof for this new correction.
BibTeX citation:
@techreport{Bui:EECS-2009-50,
Author = {Bui, Dai},
Title = {Revision of a Non-Preemptive EDF Packet Scheduling Algorithm},
Institution = {EECS Department, University of California, Berkeley},
Year = {2009},
Month = {Apr},
URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-50.html},
Number = {UCB/EECS-2009-50},
Abstract = {One issue with today's Internet is that it only supports best-effort service; hence Internet users often experience unpredicted delay. Deployment of new real-time, highly reliable applications that require fixed delay bound on packets, such as remote surgery, become very difficult. Communication environment that can assert a strict delay bound will help estimate the worst-case execution time of distributed real-time applications.
This paper revises a flaw in estimation of delay bound and an incorrect proof for of a non-preemptive Earliest Deadline First (EDF) packet scheduling algorithm used in packet scheduling for implementing real-time communication services in packet-switching network described in [1,2,3], which is one of few seminal works on guaranteed service in packet-switching network. We discuss the found flaw then correct the error and provide a substitute proof for this new correction.}
}
EndNote citation:
%0 Report %A Bui, Dai %T Revision of a Non-Preemptive EDF Packet Scheduling Algorithm %I EECS Department, University of California, Berkeley %D 2009 %8 April 24 %@ UCB/EECS-2009-50 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-50.html %F Bui:EECS-2009-50