Analysis of a Window-Constrained Scheduler for Real-Time and Best-Effort Packet Streams

Abstract

This paper describes how Dynamic Window-Constrained Scheduling (DWCS) can guarantee real-time service to packets from multiple streams with different performance objectives. We show that: (1) DWCS can guarantee that no more than x packets miss their deadlines for every y consecutive packets requiring service, (2) using DWCS, the delay of service to real-time packet streams is bounded even when the scheduler is overloaded, (3) DWCS can ensure the delay bound of any given stream is independent of other streams, and (4) a fast response time for best-effort packet streams, in the presence of real-time packet streams, is possible. As long as the minimum aggregate bandwidth requirement of all real-time packet streams does not exceed the available bandwidth, DWCS can guarantee that each such stream does not miss more than x deadlines for every y requests. Furthermore, if a feasible schedule exists, each stream is guaranteed a minimum fraction of available bandwidth over a finite window of time. Consequently, DWCS can provide bounded delay of service to each real-time stream in a manner which is independent of other streams, while also meeting per-stream, explicit delay and loss constraints.