论文标题
安排开关上的流动以优化响应时间
Scheduling Flows on a Switch to Optimize Response Times
论文作者
论文摘要
我们研究开关上流的调度，目的是优化与流量响应时间有关的指标。该问题的输入是开关上的流程请求序列，该序列由在每个顶点（或端口）上具有容量的两分图表示，而流程请求是带有相关需求的边缘。在每一轮中，可以安排一个边集的子集，但要受到以下限制，即任何顶点的预定边缘的总需求最多是顶点的能力。以前的工作基本上解决了基于{\ em完成时间}的指标的复杂性。但是，平均或最大{\ em响应时间}的目标更具挑战性。 我们提出了在开关上进行流程调度的近似算法，以优化基于响应时间的指标。对于平均响应时间度量，其NP硬度直接从过去的工作中遵循，我们提出了一个离线$ O（1 + O（\ log（n）/c）单位流的$近似算法，假设开关的端口容量可以增加$ 1 + c $，则可以增加开关的端口容量。对于最大响应时间度量，我们首先确定在没有增强能力的情况下，达到超过4/3的近似因素是NP-HARD。然后，我们提出了一个离线算法，该算法可以实现{\ em最佳最大响应时间}，假设每个端口的容量最多增加了$ 2 d_ {max} -1 $，其中$ d_ {max {max} $是任何流量的最大需求。这两种算法均基于线性编程松弛。我们还使用竞争性分析的角度研究了在线版流程计划的在线版本，并提出了初步结果以及评估快速在线启发式方法的实验。
We study the scheduling of flows on a switch with the goal of optimizing metrics related to the response time of the flows. The input to the problem is a sequence of flow requests on a switch, where the switch is represented by a bipartite graph with a capacity on each vertex (or port), and a flow request is an edge with associated demand. In each round, a subset of edges can be scheduled subject to the constraint that the total demand of the scheduled edges incident on any vertex is at most the capacity of the vertex. Previous work has essentially settled the complexity of metrics based on {\em completion time}. The objective of average or maximum {\em response time}, however, is much more challenging. We present approximation algorithms for flow scheduling over a switch to optimize response time based metrics. For the average response time metric, whose NP-hardness follows directly from past work, we present an offline $O(1 + O(\log(n))/c)$ approximation algorithm for unit flows, assuming that the port capacities of the switch can be increased by a factor of $1 + c$, for any given positive integer $c$. For the maximum response time metric, we first establish that it is NP-hard to achieve an approximation factor of better than 4/3 without augmenting capacity. We then present an offline algorithm that achieves {\em optimal maximum response time}, assuming the capacity of each port is increased by at most $2 d_{max} - 1$, where $d_{max}$ is the maximum demand of any flow. Both algorithms are based on linear programming relaxations. We also study the online version of flow scheduling using the lens of competitive analysis, and present preliminary results along with experiments that evaluate the performance of fast online heuristics.
