Optimality of Periodwise Static Priority Policies in Real-Time Communications
The authors consider the problem of real-time communication with delay constraints. In earlier work it has been shown that a certain weighted-debt policy is feasibility-optimal in the sense that if any scheduling policy can satisfy the throughput-with-deadline requirements of all the clients, then the weighted-debt policy can do so. This raises the interesting question: Why is it that a period-wise static priority policy can satisfy any set of requirements that the more general class of history dependent policies can? They answer this by showing that the set of feasible timely-throughput vectors is a polymatroid. They do so by establishing a sub-modularity property of the complement of the unavoidable idle time function.