Scheduling for Weighted Flow and Completion Times in Reconfigurable Networks
Scheduling for Weighted Flow and Completion Times in Reconfigurable Networks
复制标题
DOI：
10.1109/infocom41043.2020.9155537
复制
发表时间：
2020-01
期刊：
影响因子：
--
通讯作者：
M. Dinitz;Benjamin Moseley
中科院分区：
文献类型：
--
作者：
M. Dinitz;Benjamin Moseley
新的光纤技术提供了动态重新配置网络拓扑的能力，而不是一劳永逸地设置它们。这在光广域网(光广域网)和数据中心中都是如此，尽管这两种设置之间存在许多差异。由于这些新技术，对利用这些新技术的算法的实践和理论研究都出现了激增。特别是，Jia et al.[Infocom‘17]为最大完工时间和完工时间总和目标设计了动态可重构拓扑的在线调度算法。在这篇文章中，我们在相同的环境下工作，但研究一个在在线环境下更有意义的目标：流动时间的总和。作业的流动时间是它在系统中花费的总时间，如果它被延迟释放，它可能会比它的完成时间短得多。我们给出了具有速度增强的在线设置的竞争性算法，并给出了一个下界，证明了速度增强实际上是必要的。作为我们技术的一个副作用，我们还改进和推广了Jia等人的结果。对于任意大小和释放时间，给出了一个O(1)竞争算法，并且允许完成时间(或流时间)的加权和，即使当节点具有不同度界时也是如此。
New optical technologies offer the ability to recon-figure network topologies dynamically, rather than setting them once and for all. This is true in both optical wide area networks (optical WANs) and in datacenters, despite the many differences between these two settings. Because of these new technologies, there has been a surge of both practical and theoretical research on algorithms to take advantage of them. In particular, Jia et al. [INFOCOM '17] designed online scheduling algorithms for dynamically reconfigurable topologies for both the makespan and sum of completion times objectives. In this paper, we work in the same setting but study an objective that is more meaningful in an online setting: the sum of flow times. The flow time of a job is the total amount of time that it spends in the system, which may be considerably smaller than its completion time if it is released late. We provide competitive algorithms for the online setting with speed augmentation, and also give a lower bound proving that speed augmentation is in fact necessary. As a side effect of our techniques, we also improve and generalize the results of Jia et al. on completion times by giving an O(1)-competitive algorithm for arbitrary sizes and release times even when nodes have different degree bounds, and moreover allow for the weighted sum of completion times (or flow times).