高优先级随机协同流调度性能界限

Performance bounds for priority-based stochastic coflow scheduling

摘要 Abstract

我们考虑了非clairvoyant设置下的协同流调度问题,假设流大小在线根据给定的概率分布实现。目标是在期望下最小化协同流的加权平均完成时间。我们首先为该问题获得适用于所有非预测性基于顺序的速率分配策略的不等式,并定义此类调度策略性能空间的多面体松弛。利用这种松弛来分析一种简单优先级策略的性能,其中优先级顺序由Sincronia根据预期流大小而非未知实际值计算得出。我们针对任意流大小概率分布(具有有限的一阶和二阶矩)建立了该优先级策略相对于最优优先级策略的近似比界。对于某些特定分布,获得了更紧的上界。广泛的数值结果表明,所提出策略的性能远优于该界。

We consider the coflow scheduling problem in the non-clairvoyant setting, assuming that flow sizes are realized on-line according to given probability distributions. The goal is to minimize the weighted average completion time of coflows in expectation. We first obtain inequalities for this problem that are valid for all non-anticipative order-based rate-allocation policies and define a polyhedral relaxation of the performance space of such scheduling policies. This relaxation is used to analyze the performance of a simple priority policy in which the priority order is computed by Sincronia from expected flow sizes instead of their unknown actual values. We establish a bound on the approximation ratio of this priority policy with respect to the optimal priority policy for arbitrary probability distributions of flow sizes (with finite first and second moments). Tighter upper bounds are obtained for some specific distributions. Extensive numerical results suggest that performance of the proposed policy is much better than the upper bound.

高优先级随机协同流调度性能界限 - arXiv