| Hard real-time scheduling algorithms have their roots in the processor scheduling problem where a number of real-time tasks are coordinated to share the processor without missing any of their periodic deadlines. With the increase of continuous media applications, these techniques are now being considered to schedule the transmission of data streams across shared networks. From a theoretical standpoint, this is not surprising since the processor scheduling and the network scheduling problems are isomorphisms of each other. In both cases, there is a shared resource (the processor vs. the network), there are concurrent tasks competing for the resource (the real time processes of the processor vs. the real-time communication channels of the network), and there are deadlines associated with the completion of intermediate components (i.e. job completion times vs. packet delivery times).; This dissertation is based on exploring the application of hard real-time scheduling algorithms to the network scheduling problem. We first show that the Distance Constrained Scheduling (DCS) algorithm can schedule a greater percentage of real-time task sets than Rate Monotonic Scheduling (RMS) algorithm even though DCS and RMS have the same worst case schedulability performance. We then develop a deterministic data-link later real-time protocol in order to compare their operational performance. We establish that DCS outperforms RMS in terms of the qualities of the produced schedules as well. Specifically, we show through simulations that DCS has better latency and jitter characteristics when scheduling traffic that we would associate with surveillance types of networks. The difference is especially significant when we incorporate system level variances in packet sizes, periodicity, and host synchronization during the formation of new schedules. The proposed data-link layer protocol also addresses many of the issues that need to be considered if real-time operation is to be achieved on non-real-time components. |
