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

Abstract

Many real-tim e applications need a delay guarantee from th e network. For this scheduling algorithms are useful. Therefore, given a scheduling algorithm and a characterization of arriving traffic, it is im p o rtan t to evolve a m ethod of obtaining the end-to-end delay guarantee. Real-tim e applications are a very large class needing different traffic m odels for their analysis. Therefore, analyzing scheduling policies w ithout any assum ption on an arrival process is highly desirable. The subject m atter of this thesis is to evolve a unified framework to obtain network delay guarantees without any assum ptions on scheduling policies and arrival processes. The only restrictions we impose are; • Scheduling policies are dynam ic; policies assign priorities to packets (and not to flows) as and when they arrive. We have shown th a t this priority indicator can be thought of as a “finish tim e” , which is the tim e a t which a packet is expected to finish its service. • The sources are packet sources w ith the m axim um packet length bounded for any flow. We obtained the necessary and sufficient condition fo r source schedulability, a condition for ensuring th a t all packets leave never after their respective finish times. W ith this, we redefined delay guarantees in term s of finish tim es and th en obtained the necessary and sufficient condition fo r guaranteeing delay at a multiplexer. Since we have not assum ed any scheduling policy or any specific arrival process, the adm ission control condition obtained is very general. Therefore, we have devised a general framework th at gives guidelines for effectively using the Delay G uarantee theorem to o btain the guaranteeable network delays for a given scheduling policy and an arrival process. We have analyzed some well known scheduling policies like V irtual Clock, E arliest Deadline F irst and Packetby- packet Generalized Processor Sharing for the leaky bucket constrained sources and sources constrained by M inimum Interarrival Time. T his analysis shows th a t th e bounds obtained are tight and they m atch w ith those reported in literature. Having obtained the guaranteeable regions of the scheduling policies, we addressed the question of finding delay optim al scheduling policies in a given set of scheduling policies for a given source vector, if such policies exist. We have devised tests for obtaining such a policy. Using these tests we have shown the absolute delay optim ality of the Preem ptive Earliest Deadline F irst policy. Also, we extended the delay o p tim ality of the Non Preem ptive Earliest Deadline F irst policy to a larger class of sources. E arlier it was shown only for Leaky Bucket C onstrained Sources. In the network, the departure process of an upstream node is the arrival process at a downstream node. For sim plifying the analysis we replaced the departure process by the finish tim e process. We found th a t this replacem ent does not always lead to guaranteeable delay, even when schedulability is guaranteed a t each node. We have obtained a class of scheduling policies for which such a replacem ent indeed leads to a valid endto- end guaranteeable delay. Using this class we have devised a general m ethod to obtain guaranteeable end-to-end delays in th e internetw orking environm ent w ith general arrival process. Using these results, we have developed a work-conserving architecture to support per-flow guarantees w ith scalable core.