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

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.