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 distr...
详细信息
ISBN:
(纸本)9781450392624
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-SFM) problem, a variant of the classical matching problem that captures the unique constraints imposed by flow scheduling in datacenter networks. In the 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. We design centralized and distributedalgorithms for the k-SFM problem on bipartite graphs. For the centralized setting, we present a greedy 1/2-approximation algorithm. For the distributed setting, we present three algorithms under the CONGEST model: a randomized 1/4-approximation algorithm that runs in O(k log n) rounds, a randomized Omega(1)-approximation algorithm that runs in O(log k log n) rounds, and a deterministic 1/(4 + epsilon)-approximation algorithm that runs in O(k log(2) n log(1/epsilon)) rounds. The key idea in all of our algorithms is that existing approaches for computing maximum-weight matching can be used as a "coordination" mechanism, alongside local and greedy decisions on updating residual weights, to design near-optimal algorithms for the k-SFM problem.
暂无评论