Deadline-based scheduling in support of real-time data delivery
The use of deadline-based scheduling in support of real-time delivery of application data units (ADUs) in a packet-switched network is investigated. Of interest is priority scheduling where a packet with a smaller ratio of T/H (time until delivery deadline over number of hops remaining) is given a higher priority. We refer to this scheduling algorithm as the T/H algorithm. T/H has time complexity of O(logN) for a backlog of N packets and was shown to achieve good performance in terms of the percentage of ADUs that are delivered on-time. We develop a new and efficient algorithm, called T/H?p, that has O(1) time complexity. The performance difference of T/H, T/H?p and FCFS are evaluated by simulation. Implementations of T/H and T/H?p in high-speed routers are also discussed. We show through simulation that T/H?p is superior to FCFS but not as good as T/H. In view of the constant time complexity, T/H?p is a good candidate for high-speed routers when both performance and implementation cost are taken into consideration.
deadline-based scheduling real-time data delivery packet-switched networks performance evaluation