Achieving end-to-end delay bounds by EDF scheduling without traffic shaping

Authors:
  • KZK. Zhu
    K. Zhu
  • YZY. Zhuang
    Y. Zhuang
  • YVY. Viniotis
    Y. Viniotis
Publisher website
Google Scholar
Abstract
Earliest Deadline First scheduling with per-node traffic shap- ing (RC-EDF) has the largest schedulable region among all practical poli- cies known today and has been considered a good solution for providing end-to-end packet delay bounds. In order to harness the traffic bursti- ness inside a network to satisfy the schedulability condition of EDF, per- node traffic shaping has been believed to be necessary. However, shaping introduces artificial packet delays. In this paper, we show that by dead- line assignments at each node that are strict time-shifting of the source packet arrival times, the functionality of shaping can be implicitly real- ized; the resulting schedulable region of the new scheduling policy is as large as that of RC-EDF. We name the new policy as deadline-curve based EDF (DC-EDF). Not only working in a natural work-conserving way, when the global schedulability condition fails DC-EDF will also work in a "best- effort" way to allow packets excessively delayed at previous nodes to catch up and meet the end-to-end delay bounds. Therefore, DC-EDF is likely to provide "tight" statistical delay bounds. We also prove that a known EDF policy without traffic shaping also has a schedulable region as large as that of RC-EDF.

This publication has 15 references indexed in Scilit: