Dynamic scheduling with reconfiguration delays
Dynamic scheduling with reconfiguration delays
复制标题
具有重新配置延迟的动态调度
作者：
G. Çelik;S. Borst;P. Whiting;E. Modiano
我们考虑在网络中的干扰约束和重新配置的延迟，这可能会发生时，一个服务计划被丢弃，并通过一个不同的服务计划调度。重新配置延迟发生在各种通信设置中，例如卫星、光学或延迟容忍网络。在没有重新配置延迟的情况下，众所周知，著名的最大权重调度算法保证吞吐量最优，而不需要任何知识的到达率。然而，正如我们将要展示的，在非零重新配置延迟的情况下，最大权重算法可能无法实现吞吐量最优。出于后一个问题，我们提出了一类自适应调度算法，坚持与当前的时间表，直到达到一定的停止标准，切换到下一个时间表之前。虽然早先提出的基于可变帧的最大权重（VFMW）的政策属于这一类，我们还提出了基于切换曲线（SCB）的政策，更适应突发的到来。我们开发了新的李雅普诺夫漂移技术，证明了这类算法在一定条件下，通过动态适应的持续时间的交换间隔，实现吞吐量最优。数值结果表明，这些算法显着优于普通的最大权重算法，SCB策略产生更好的延迟性能比VFMW策略。
We consider scheduling in networks with interference constraints and reconfiguration delays, which may be incurred when one service schedule is dropped and a distinct service schedule is adopted. Reconfiguration delays occur in a variety of communication settings, such as satellite, optical, or delay-tolerant networks. In the absence of reconfiguration delays it is well known that the celebrated Max-Weight scheduling algorithm guarantees throughput optimality without requiring any knowledge of arrival rates. As we will show, however, the Max-Weight algorithm may fail to achieve throughput optimality in case of nonzero reconfiguration delays. Motivated by the latter issue, we propose a class of adaptive scheduling algorithms which persist with the current schedule until a certain stopping criterion is reached, before switching to the next schedule. While earlier proposed Variable Frame-Based Max-Weight (VFMW) policies belong to this class, we also present Switching-Curve-Based (SCB) policies that are more adaptive to bursts in arrivals. We develop novel Lyapunov drift techniques to prove that this class of algorithms under certain conditions achieves throughput optimality by dynamically adapting the durations of the interswitching intervals. Numerical results demonstrate that these algorithms significantly outperform the ordinary Max-Weight algorithm, and that SCB policies yield a better delay performance than VFMW policies.