Maximizing the Throughput of Edge-Based In-Network Aggregation With Routing Optimization

As is known, in-network aggregation (INA) is a promising solution to alleviate the communication bottlenecks faced by emerging distributed applications like data-parallel distributed machine learning (DML). Recent studies have shown that INA-aware routing optimization is the key to making efficient use of deployed aggregators for acceleration. In this paper, we consider a specific INA scenario, where aggregators are deployed at the edge of the data center network (DCN), like the Smart-NIC of servers and the programmable top-ofrack (ToR) switches. We find that existing INA-aware routing schemes like ATP and GRID are far from optimal for such a scenario, since they do not take the characteristics of edgebased INA into consideration. To address the problem, we propose EINA, a model-based routing optimization scheme for edge-based INA. In the core, EINA establishes a Mixed-Integer Quadratically Constrained Programming (MIQCP) mathematical model to precisely encode the requirements, constraints, and objective of edge-based INA. Then, EINA transforms the model into an Integer Quadratically Constrained Programming (IQCP) for solving acceleration. Based on the results of the model, EINA generates near-optimal (if not optimal) routing schemes to maximize the total aggregation throughput, using deployed edge aggregators. Performance studies indicate that EINA is able to achieve aggregation throughput up to about $3.02 \times$ and $3.45 \times$ of those of existing schemes, ATP and GRID, respectively, especially for the case where edge aggregators have limited network bandwidth.