Revision of a Non-Preemptive EDF Packet Scheduling Algorithm

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 24, 2009
Accession Number
ADA538864

Entities

People

  • Dai Bui

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • California
  • Communication Channels
  • Computer Science
  • Education
  • Electrical Engineering
  • Engineering
  • Equations
  • Hard Copy
  • Intervals
  • Military Research
  • Networks
  • Packet Switching
  • Saturation
  • Scheduling (Production)
  • Switching

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Parallel and Distributed Computing.