Approach to the Analysis of Scheduling Policies for Guaranteeing Delay with Arbitrary Arrivals

Abstract

Many real-time applications require delay guarantees from the network. To achieve this, scheduling algorithms play a crucial role. Therefore, given a scheduling algorithm and a characterization of arriving traffic, it is important to develop a method for obtaining end-to-end delay guarantees. Real-time applications form a large and diverse class, necessitating different traffic models for analysis. Hence, analyzing scheduling policies without any assumptions on the arrival process is highly desirable. This thesis presents a unified framework to obtain network delay guarantees without assumptions on scheduling policies or arrival processes. The only restrictions imposed are:

Scheduling policies are dynamic: Policies assign priorities to packets (not flows) as they arrive. This priority indicator can be interpreted as a “finish time”, which is the time at which a packet is expected to complete its service. Sources are packet-based, with a bounded maximum packet length for any flow.

Key Contributions

Source Schedulability Condition A necessary and sufficient condition is derived to ensure that all packets depart no later than their respective finish times.

Delay Guarantees via Finish Times Delay guarantees are redefined in terms of finish times, leading to a general condition for guaranteeing delay at a multiplexer.

General Admission Control Since no assumptions are made about scheduling policies or arrival processes, the admission control condition is very general. This forms the basis of a framework that guides the use of the Delay Guarantee Theorem to obtain guaranteeable network delays for any given scheduling policy and arrival process.

Analysis of Known Scheduling Policies The framework is applied to well-known policies such as:

Virtual Clock Earliest Deadline First (EDF) Packet-by-Packet Generalized Processor Sharing (PGPS) These are analyzed for traffic models like Leaky Bucket constrained sources and Minimum Interarrival Time constrained sources, showing that the bounds obtained are tight and match those reported in literature.

Delay Optimality Tests The thesis addresses the problem of identifying delay-optimal scheduling policies from a given set for a specific source vector. Tests are devised to find such policies, demonstrating:

Absolute delay optimality of Preemptive EDF Extended delay optimality of Non-Preemptive EDF to a broader class of sources (beyond just Leaky Bucket constrained sources)

End-to-End Delay Guarantees in Networks In networks, the departure process of an upstream node becomes the arrival process at a downstream node. To simplify analysis, the departure process is replaced by the finish time process. However, this replacement does not always guarantee delay, even if schedulability is ensured at each node. A class of scheduling policies is identified for which this replacement does lead to valid end-to-end delay guarantees. Using this class, a general method is developed to obtain guaranteeable end-to-end delays in internetworking environments with general arrival processes.

Scalable Architecture for Per-Flow Guarantees Based on the above results, a work-conserving architecture is proposed to support per-flow guarantees with a scalable core.