Optimality of periodwise static priority policies in real-time communications

Abstract — We consider the problem of real-time communica-tion 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 periodwise static priority policy can satisfy any set of requirements that the more general class of history dependent policies can? We answer this by showing that the set of feasible timely-throughput vectors is a polymatroid. We do so by establishing a submodularity property of the complement of the unavoidable idle time function. This shows that a periodwise static priority policy, where the priority order is revised at the beginning of each period, but never in the middle of a period, can attain any feasible timely-throughput vector. We next go on to investigate a more general problem where the packet arrivals and channel conditions can vary over periods, and establish the existence of an optimal periodwise static priority policy