Two-aggregator network topology optimization with splitting

We consider the problem of data aggregation using two aggregators. We assume that the source racks can split the data they need to send to the aggregators across multiple paths. We show that obtaining a topology that minimizes aggregation time is NP-hard for k = 2, 3,4, where k the degree of ToR (top-of-rack) switches. We also show that an optimal topology can be computed in polynomial time for k = 5 and 6 and conjecture this to be the case when k > 6 as well. Experimental results show that, when k = 6, our topology optimization algorithm reduces the aggregation time by as much as 83.3% and reduces total network traffic by as much as 99.5% relative to the torus heuristic, proposed by [1].