From Switch Scheduling to Datacenter Scheduling: Matching-Coordinated Greed is Good
From Switch Scheduling to Datacenter Scheduling: Matching-Coordinated Greed is Good
复制标题
DOI：
10.1145/3519270.3538443
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Rachit Agarwal;S. Rajakrishnan;David B. Shmoys
中科院分区：
文献类型：
--
作者：
Rachit Agarwal;S. Rajakrishnan;David B. Shmoys
基于交换(互连)结构的分组调度是分布式计算中一个被广泛研究的问题，已知的基于接近最佳的分布式二部匹配的协议。我们对数据中心网络中的分布式流调度进行了理论研究。基于现代数据中心网络使用类似于交换结构的CLOS拓扑结构，我们引入了一种新的k-稀疏流匹配(k=k-SFM)问题，它是经典匹配问题的一种变体，该问题捕获了数据中心网络中流调度施加的唯一约束。在k=k-SFM问题中，我们被赋予一个加权图和一个整数k。目标是在以下三个约束下为每条边分配一个分数流量值：(1)对于每条边，分配的流量值不大于其输入权重；(2)对于每个顶点，分配给与顶点关联的边的流量值之和至多是该顶点的容量；(3)对于每个顶点，至多k条关联边被分配一个非零的流量值。目标是计算具有最大总分数权重的可行解。
Packet scheduling over a switch (interconnect) fabric is a wellstudied problem in distributed computing, with known near-optimal distributed bipartite matching based protocols. We initiate a theoretical study of distributed flow scheduling in datacenter networks. Building upon the observation that modern datacenter networks use Clos-like topologies similar to switch fabrics, we introduce a new k-sparse flow-matching (k=k-SFM) problem, a variant of the classical matching problem that captures the unique constraints imposed by flow scheduling in datacenter networks. In the k=k-SFM problem, we are given a weighted graph and an integer k. The goal is to assign a fractional flow value to each edge under the following three constraints: (1) for each edge, the assigned flow value is no greater than its input weight; (2) for each vertex, the sum of flow values assigned to edges incident to the vertex is at most the capacity of the vertex; and (3) for each vertex, at most k incident edges are assigned a non-zero flow value. The goal is to compute a feasible solution with the largest total fractional weight.