On optimal scheduling for time-constrained services in multi-channel data dissemination systems

摘要

We study the problem of disseminating data of time-constrained services through multiple broadcast channels. By time-constrained services, we mean those services whose data must reach clients before a certain constrained time. Otherwise, the data would become useless or substantially less valuable to the clients. We first explore the difficulties of solving the problem and derive the theoretical minimum number of channels required for the task. Then, we propose a transformation-based data allocation (TDA) algorithm that guarantees to fulfill the task (i.e., all requested data reach the clients within the constrained time) by using the minimum number of channels. Finally, we analyze the computation complexity and prove the validity and optimality of the TDA algorithm.